Лучшие устройства хеш таблиц

[krlz]

В последнее время я собеседовал достаточно много народу в наш новый проект. Один из моих вопросов это устройство хеш таблицы, и за время этих собеседований я узнал много нового. Поэтому, по просьбе коллег я решил составить этот топ самых лучших неправильных хеш таблиц

Comments

[alf_kadett]

"Beware of the man who works hard to learn something, learns it, and finds himself no wiser than before. He is full of murderous resentment of people who are ignorant without having come by their ignorance the hard way."

[krlz]

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

[coolbaskin]

Как раз сейчас изучаем интересный баг с хэш-таблицами. Похоже, что определённый набор данных вызывает множество коллизий в таблице в каком-то небольшом диапазоне значений хэш-функции, что вызывает увеличение диапазона и remapping... который не помогает, потому что хэш-функция всё равно продолжает класть их в один bucket, что вызывает новый resize-remap.

[denspb]

А попробуйте полученый hash дополнительно просаливать, причём новую случайную соль выбирайте при каждом rehash'е.

[krlz]

Я думаю все кандидаты думали что они знают что такое хеш таблица :-)