История изменений
Исправление iVS, (текущая версия) :
Видимо, мы по-разному понимаем задачу. Я вижу ее так, что маски не нужны (я не знаю почему, постановка задачи на совести ТС):
список IP адресов (без зон и масок, скорее всего только адреса)
В этом случае достаточно хэш-таблицы. В теории, два доступа к памяти будут достаточны; на практике, достигается использованием Cuckoo Hashing.
У radix tree тоже доступ O(1) и отличное сжатие
В худшем случае понадобится 32 обращения для IPv4, тоже O(1), но какая разница по сравнению с двумя! Если интересует сжатие, то есть perfect hashing, как я отмечал (проблемы, правда, с обновлением — придется создавать структуру заново), это ни разу не хуже radix tree. А если не оптимизировать указатели в radix tree, то с учетом них, perfect hashing может быть лучше. ЕМНИП, в perfect hashing поиск требует 5 доступов.
Резюмируя, решения на основе деревьев, включая radix tree, решают более общую задачу, нежели хэш-таблицы, поэтому всегда менее эффективны в смысле баланса скорости поиска и занимаемой памяти.
Исходная версия iVS, :
Видимо, мы по-разному понимаем задачу. Я вижу ее так, что маски не нужны (я не знаю почему, постановка задачи на совести ТС):
список IP адресов (без зон и масок, скорее всего только адреса)
В этом случае достаточно хэш-таблицы. В теории, два доступа к памяти будут достаточны; на практике, достигается использованием Cuckoo Hashing.
У radix tree тоже доступ O(1) и отличное сжатие
В худшем случае понадобится 32 обращения для IPv4, тоже O(1), но какая разница по сравнению с двумя! Если интересует сжатие, то есть perfect hashing, как я отмечал (проблемы, правда, с обновлением — придется создавать структуру заново), это ни разу не хуже radix tree. А если не оптимизировать указатели в radix tree, то с учетом них, perfect hashing может быть лучше. ЕМНИП, в perfect hashing поиск требует 5 доступов.
Резюмируя, решения на основе деревьев, включая radix tree, решают более общую задачу, нежели хэш-таблицы, поэтому всегда менее эффективны.