Page 125 - Bkhargava_-_Grokaem_algoritmy

124 Глава 5. Хеш-таблицы

изменяйте размер хеш-таблицы, когда коэффициент заполнения превышает
0,7. Но ведь на изменение размеров уходит много времени, скажете вы,
и будете абсолютно правы! Да, изменение размеров требует значитель­
ных затрат ресурсов, поэтому оно не должно происходить слишком часто.
В среднем хеш-таблицы работают за время 0(1) даже с изменением раз­
меров.

Хорошая хеш-функция

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

Плохая хеш-функция создает скопления и порождает множество коллизий.

Какую хеш-функцию считать хорошей? К счастью, вам об этом никогда не
придется беспокоиться - пусть об этом беспокоятся пожилые бородатые
умники, сидящие в полутемных комнатах. Если вам интересна эта тема,
поищите информацию об алгоритме SHA (короткое описание приведено
в последней главе). Вы можете использовать этот алгоритм в своей хеш­
функции.

www.trk.kg