Самый быстрый поиск по списку элементов с большим ключом

Рейтинг: 1Ответов: 1Опубликовано: 11.03.2011

Здравствуйте!

Помогите, пожалуйста, решить следующую задачу: имеется массив элементов (от 1000 до 100000), у каждого элемента есть уникальный ключ (32 байта), необходимо максимально быстро найти среди них элемент с заданным ключом (если он, конечно, есть). Все данные хранятся в памяти. Какие существуют оптимальные алгоритмы/технологии поиска при таких условиях (деревья, хэштаблицы, БД, что-то еще)? Значение уникального ключа может быть произвольное (от 0x0000...0000 до 0хffff...ffff).

алгоритм поиск
Источник: Stack Overflow на русском

Ответы

▲ 3

Мне кажется, хэш-таблица с разрешением коллизий цепочками, т.е. все элементы с одинаковым хэш кодом попадают в один список. Размер таблицы не менее 1.5 от максимального. Ну и, конечно, надо тщательно поработать функцию хэширования для снижения числа коллизий для вероятного распределения ключей. Ну, без представления о природе данных, максимально быстро не получится.