Вопросы Теги

Лучший выбор для в структуре данных памяти для фильтра IP-адресов в Java

У меня есть файл в формате CIDR вроде этого 192.168.1.0/24 , и он конвертируется в эту структуру из двух столбцов 

3232236030 3232235777

Конвертация IP-адреса каждой строки происходит с помощью этого кода: 

String subnet = "192.168.1.0/24";
SubnetUtils utils = new SubnetUtils(subnet);

Inet4Address a = (Inet4Address) InetAddress.getByName(utils.getInfo().getHighAddress());
long high = bytesToLong(a.getAddress());
Inet4Address b = (Inet4Address) InetAddress.getByName(utils.getInfo().getLowAddress());
long low = bytesToLong(b.getAddress());

private static long bytesToLong(byte[] address) {
   long ipnum = 0;
   for (int i = 0; i < 4; ++i) {
       long y = address[i];
       if (y < 0) {
           y += 256;
       }
       ipnum += y << ((3 - i) * 8);
   }
   return ipnum;
}

Учтите, что существует более 5 миллионов записей (низкий высокий: 3232236030 3232235777) .
Также будут пересечения, поэтому IP-адрес может происходить из нескольких диапазонов. Только первое более чем нормально.
Данные доступны только для чтения.
Как быстрее всего найти диапазон, к которому принадлежит ipToBefiltered ? Структура будет полностью в памяти, поэтому поиск в базе данных не выполняется.

ОБНОВЛЕНИЕ:

Я нашел этот проект Peerblock (у него более миллиона загрузок, поэтому я думаю, что у него должны быть быстрые алгоритмы): http: // code.google.com/p/peerblock/source/browse/trunk/src/pbfilter/filter_wfp.c

Кто-нибудь знает, какой метод используется в проекте для создания списка диапазонов и чем для их поиска?

7
задан Mat B. 30 November 2011 в 00:35
поделиться