сопоставление диапазона ipaddress с кодами стран (хэш-карты структуры данных или деревья?) - PullRequest
3 голосов
/ 09 августа 2009

пытается решить головоломку, которую я нашел здесь: http://zcasper.blogspot.com/2005/10/google-phone-interview.html

цель состоит в том, чтобы повторно представить диапазон IP-адресов в справочной таблице кодов стран в памяти и использовать эту структуру данных для обработки zilloin-строк ipaddress для идентификации кода страны.

, так что я начал со стрельбы из бедра, подумав об использовании HashTable отлично работает хеш-таблица; если у нас есть код страны для поиска диапазона, так как у нас меньше названий стран, которые сопоставляются с диапазонами IP-адресов?

но не уверен; Как мне перейти с IPaddress для кода страны. Какие-нибудь мысли? или я могу использовать древовидную структуру данных?

Ответы [ 4 ]

1 голос
/ 09 августа 2009

Входной файл предоставляет диапазон IP-адресов (не сопоставление 1: 1), поэтому вам нужна какая-то упорядоченная структура карты.

// Assuming IPv4, and the inputs are valid (start before end) 
// and no overlapping ranges. 
public class CountyCodeToIPMap {
    private final TreeMap<Long, CountryCodeEntry> ipMap = 
            new TreeMap<Long, CountryCodeEntry>();

    public void addIpRange(long startIp, long endIp, String countryCode) {
        ipMap.put(startIp, new CountryCodeEntry(endIp, countryCode);
    }

    public String getCountryCode(long ip) {
        Map.Entry<Long, CountryCodeEntry> entry = ipMap.floorEntry(ip);
        if (entry != null && ip <= entry.getValue().endIpAddress) {
            return entry.getValue().countryCode;
        } else {
            return null;
        }
    }
}

public class CountryCodeEntry {
    public final long endIpAddress;
    public final String countryCode;
    public CountryCodeEntry (long endIpAddress, String countryCode) {
        this.endIpAddress = endIpAdddress;
        this.countryCode = countryCode;
    }
}
0 голосов
/ 09 августа 2009

В связи с тем, как работает интернет-маршрутизация, ваш алгоритм должен обрабатывать сопоставление длинных префиксов, и вы хотите хранить CIDR-блоков вместо адресов.

Я разработал алгоритм, чтобы справиться с этим, но не могу опубликовать его здесь. Самая близкая вещь в Open Source - это код обработки таблицы маршрутизации в Linux.

Вы также можете проверить алгоритмы Патрисии Три или Radix Tree . Они могут быть использованы для решения этой проблемы.

0 голосов
/ 09 августа 2009

это если вы рассматриваете решение sql:

Если вы можете добавить некоторые ограничения к вашему набору данных, вы можете использовать очень простой SQL. где вы можете даже использовать простые индексы. - это тот случай, когда вы используете GeoCityLite набор данных

если ваши ip-блоки не перекрываются, вы можете просто вставить их в базу данных как беззнаковые 32-битные числа в таблице «блоков» и запросить их так же, как в hibernate:

     (GeoipBlocks) getSession()
            .createQuery("select  gb" +
                    " from GeoipBlocks gb" +
                    " where gb.startIpNum <= :ipnumeric " +
                    " order by gb.startIpNum desc").
                    setMaxResults(1)
            .setParameter("ipnumeric", ipInLongValue)
            .uniqueResult()

я записал его в синтаксисе hql, потому что не все базы данных используют одинаковый синтаксис для offset + limit

, который выдает запрос на лучшее соответствие, предполагая, что все блоки не перекрываются. - вам даже не нужен конечный IP для этого, это автоматически определяется преемником.

избегайте запрашивать его таким образом!:

    select * from blocks where ipstart <= ip and ipend >= ip 

моя база данных не смогла полностью использовать их индексы и провела много сканирования таблиц.

0 голосов
/ 09 августа 2009

у вас нет шансов сохранить все IP-адреса. то, что вы можете сделать, это сохранить начало и конец интервалов, где находятся диапазоны IP-адресов.

существует специализированная структура данных, называемая Interval Tree , которая позволяет запрашивать это.

...