Page 120 - Bkhargava_-_Grokaem_algoritmy

Быстродействие 119

Одну минуту! Вся хеш-таблица полностью пуста, кроме одной ячейки.
И эта ячейка содержит огромный связанный список! Каждый элемент этой
хеш-таблицы хранится в связанном списке. Ситуация ничуть не лучше той,
когда все данные сразу хранятся в связанном списке. Работа с данными

замедляется.
Из этого примера следуют два важных урока:

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

о если связанные списки становятся слишком длинными, работа с хеш-
таблицей сильно замедляется. Но они не станут слишком длинными при
использовании хорошей хеш-функции!

Хеш-функции играют важную роль. Хорошая хеш-функция создает мини­
мальное число коллизий. Как же выбрать хорошую хеш-функцию? Об этом
в следующем разделе!

Быстродействие

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

СРЕ..П.НИК '1..Y.ll.lllИK
СЛУЧАК СЛУЧАК
1
поиск Ot1) Q(n)

ЬСП6К~ 0(1) Q(n)

У.П.АЛЕ- 0(1> Q(n)
НИЕ
БЫСТРО.ll.Е.КСТ& И Е.
)Шll-ПБЛМЦ

В среднем хеш-таблицы выполняют любые операции за время 0(1). Время
О( 1) называется постоянным. Ранее примеры постоянного времени вам еще

www.trk.kg