Структура данных для хранения объектов, идентифицированных уникальными 8-значными шестнадцатеричными числами для быстрой вставки и поиска

Question

У меня есть набор объектов с уникальными 8-значными шестнадцатеричными идентификаторами, например ex [fd4786ac], которые мне нужно сконструировать и быстро найти. Удаление не является приоритетом. Эти шестнадцатеричные значения в настоящее время хранятся в виде строк.

Рассматривается три (или несколько вариаций), список пропусков и некоторая вариация хеш-таблицы. Использование списка пропусков по дереву AVL было бы предпочтительнее, так как вполне вероятно, что эти строки будут последовательными, но не гарантированными, и перебалансировка дерева будет часто. Как бы то ни было, я открыт для других структур данных, если они лучше соответствуют моим потребностям.

Answer 1

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

Если вы хотите написать свою собственную только для этого варианта использования, то:

• Вместо того, чтобы все время хешировать ключи или хранить хеш-значения, используйте биективную хеш-функцию и используйте хеши вместо ключей.
• Поскольку ваши ключи очень маленькие, вывероятно, следует использовать открытую адресацию - это сэкономит место и будет немного быстрее.Википедия предоставит вам множество вариантов для изучения схем.В настоящее время мне нравится хэширование Робин Гуда: https://www.sebastiansylvan.com/post/robin-hood-hashing-should-be-your-default-hash-table-implementation/

Answer 2

Ваши 8-значные шестнадцатеричные идентификаторы представляют 4-байтовое (32-битное) целое число, так что вы можете использовать его в качестве индекса для (довольно большого) массива с 2 ^ 32 записями.Если массив содержит указатели, это будет стоить 64 ГБ.

Скорее всего, слишком много, чтобы держать его в оперативной памяти.

Так что, если количество элементов на порядки ниже 2 ^ 32, используйте Hash-Map или отсортированный ist (доступ O (logn)).