• если связанные списки становятся слишком длинными, работа с хеш-таблицей сильно замедляется. Но они не станут слишком длинными при использовании хорошей хеш-функции!
Хеш-функции играют важную роль. Хорошая хеш-функция создает минимальное число коллизий. Как же выбрать хорошую хеш-функцию? Об этом в следующем разделе!
Быстродействие
Глава началась с примера магазинчика. Вы хотели построить механизм, который мгновенно выдает цены на продукты. Что ж, хеш-таблицы работают очень быстро.
В среднем хеш-таблицы выполняют любые операции за время O(1). Время O(1) называется постоянным. Ранее примеры постоянного времени вам еще не встречались. Оно не означает, что операции выполняются мгновенно; просто время остается постоянным независимо от размера хеш-таблицы. Например, вы знаете, что простой поиск выполняется за линейное время.
Бинарный поиск работает быстрее — за логарифмическое время:
Поиск данных в хеш-таблице выполняется за постоянное время.
Видите горизонтальную линию? Она означает, что при любом размере хеш-таблицы — 1 элемент или 1 миллиард элементов — выборка данных займет одинаковое время. На самом деле вы уже сталкивались с постоянным временем: получение элемента из массива выполняется за постоянное время. От размера массива оно не зависит. В среднем случае хеш-таблицы работают действительно быстро.
В худшем случае все операции с хеш-таблицей выполняются за время O(n) (линейное время), а это очень медленно. Сравним хеш-таблицы с массивами и списками.
Взгляните на средний случай для хеш-таблиц. При поиске хеш-таблицы не уступают в скорости массивам (получение значения по индексу). А при вставке и удалении они так же быстры, как и связанные списки. Получается, что они взяли лучшее от обеих структур! Но в худшем случае хеш-таблицы медленно выполняют все эти операции, поэтому очень важно избегать худшего случая быстродействия при работе с хеш-таблицами. А для этого следует избегать коллизий. Для предотвращения коллизий необходимы:
• низкий коэффициент заполнения;
• хорошая хеш-функция.
примечание
Материал следующего раздела не является обязательным. Речь пойдет о том, как реализовать хеш-таблицу, но вам никогда не придется делать это самостоятельно. Какой бы язык программирования вы ни выбрали, в нем найдется готовая реализация хеш-таблиц. Вы можете воспользоваться встроенной реализацией хеш-таблицы, не сомневаясь в том, что она имеет хорошую эффективность. А в следующем разделе мы заглянем во внутреннее устройство хеш-таблиц.
Коэффициент заполнения
Коэффициент заполнения хеш-таблицы вычисляется по простой формуле.
Хеш-таблицы используют массив для хранения данных, поэтому для вычисления коэффициента заполнения можно подсчитать количество заполненных элементов в массиве. Например, в следующей хеш-таблице коэффициент заполнения равен 2/5, или 0,4.
Скажите, каков коэффициент заполнения этой таблицы?
Если вы ответили «1/3» — все правильно. По коэффициенту заполнения можно оценить количество пустых ячеек в хеш-таблице.
Предположим, в хеш-таблице нужно сохранить цены 100 товаров и хеш-таблица состоит из 100 элементов. В лучшем случае каждому товару будет выделен отдельный элемент.
Коэффициент заполнения этой хеш-таблицы равен 1. А если хеш-таблица состоит всего из 50 элементов? Тогда ее коэффициент заполнения будет равен 2. Выделить под каждый товар отдельный элемент ни при каких условиях не удастся, потому что элементов попросту не хватит! Коэффициент заполнения больше 1 означает, что количество товаров превышает количество элементов в массиве.
С ростом коэффициента заполнения в хеш-таблицу приходится добавлять новые элементы, то есть изменять ее размер. Представим, что эта хеш-таблица приближается к заполнению.
Хеш-таблицу необходимо расширить. Расширение начинается с создания нового массива большего размера. Обычно в таком случае создается массив вдвое большего размера.
Теперь все эти элементы необходимо заново вставить в новую хеш-таблицу функцией hash: