Создание «разреженного» поискового массива, минимизирующего объем памяти

Question

скажем, я хочу создать массив для поиска для анализа сетевых протоколов (например, ethertype). Так как такой идентификатор имеет длину 2 байта, я бы получил массив из 2 ^ 16 ячеек, если бы использовал прямую индексацию: это реальная трата, потому что весьма вероятно, что массив редок - то есть много пробелов в массив.

Чтобы максимально сократить использование памяти, я бы использовал идеальный генератор хеш-функций, такой как CMPH , чтобы я мог отобразить свои "n" идентификаторы в массив n-размера без каких-либо коллизий. Недостатком этого подхода является то, что мне приходится полагаться на внешнюю «экзотерическую» библиотеку.

Мне интересно, есть ли - в моем случае - более разумные способы поиска с постоянным временем при одновременном использовании памяти; имейте в виду, что меня интересует индексирование 16-битных беззнаковых чисел , а размер набора довольно ограничен.

Спасибо

Answer 1

Поскольку вы точно знаете, что имеете дело с 16-битными значениями, любой алгоритм поиска будет алгоритмом постоянного времени, поскольку существует только O (1) различных возможных значений.Следовательно, алгоритмы, которые на поверхности могут быть медленнее (например, линейный поиск, который запускается в O (n) для n элементов), на самом деле могут быть полезны здесь.гарантируя быстрый поиск, я бы посоветовал изучить хеширование кукушки , которое гарантирует время поиска O (1) в худшем случае и ожидает вставку в O (1) времени (хотя вы должны быть немного сообразительны с вашимхэш-функции).Это действительно легко генерировать хеш-функции для 16-битных значений;если вы вычислите два 16-битных умножителя и умножите старшие и младшие биты 16-битного значения на эти значения, а затем сложите их вместе, я считаю, что вы получите хорошую хеш-функцию для любого простого числа.В качестве альтернативы, если вам не обязательно иметь O (1) поиск и вы согласны с хорошим ожидаемым временем поиска, вы можете также использовать стандартную хеш-таблицу с открытой адресацией, такую ​​как хеш-таблица с линейным зондированием или таблица хэширования двойного хеширования .Использование меньшего массива с такой схемой хеширования может быть чрезвычайно быстрым и должно быть очень простым для реализации.

Для совершенно другого подхода, если вы храните разреженные данные и хотите быстрое время поиска, опция, котораяможет хорошо работать для вас, это использовать простое сбалансированное двоичное дерево поиска.Например, структура данных treap проста в реализации и дает ожидаемый O (log n) поиск значений.Поскольку вы имеете дело с 16-битными значениями, здесь log n составляет около 16 (я думаю, что основание логарифма на самом деле немного отличается), поэтому поиск должен быть довольно быстрым.Это вносит немного накладных расходов на элемент, но если у вас есть только несколько элементов, это должно быть просто реализовать.Для еще меньших накладных расходов вы можете рассмотреть деревьев splay , для которых требуется только два указателя на элемент.

Надеюсь, это поможет!