На этом шаге рассмотрим быстродействие хеш-функции.
Мы начали рассматривать хеш-таблицы с примера магазинчика. Вы хотели построить механизм, который мгновенно выдает цены на продукты. Что ж, хеш-таблицы работают очень быстро.
В среднем хеш-таблицы выполняют любые операции за время O(1). Время О(1) называется постоянным. Ранее примеры постоянного времени вам еще не встречались. Оно не означает, что операции выполняются мгновенно; просто время остается постоянным независимо от размера хеш-таблицы. Например, вы знаете, что простой поиск выполняется за линейное время. Бинарный поиск работает быстрее - за логарифмическое время. Поиск данных в хеш-таблице выполняется за постоянное время.
Горизонтальная линия означает, что при любом размере хеш-таблицы - 1 элемент или 1 миллиард элементов - выборка данных займет одинаковое время. На самом деле вы уже сталкивались с постоянным временем: получение элемента из массива выполняется за постоянное время. От размера массива оно не зависит. В среднем случае хеш-таблицы работают действительно быстро. В худшем случае все операции с хеш-таблицей выполняются за время О(n) (линейное время), а это очень медленно. Сравним хеш-таблицы с массивами и списками.
Взгляните на средний случай для хеш-таблиц. При поиске хеш-таблицы не уступают в скорости массивам (получение значения по индексу). А при вставке и удалении они так же быстры, как и связанные списки. Получается, что они взяли лучшее от обеих структур! Но в худшем случае хеш-таблицы медленно выполняют все эти операции, поэтому очень важно избегать худшего случая быстродействия при работе с хеш-таблицами. А для этого следует избегать коллизий. Для предотвращения коллизий необходимы:
- низкий коэффициент заполнения;
- хорошая хеш-функция.
На следующем шаге рассмотрим понятие коэффициента заполнения хеш-таблицы.
