Page 122 - Bkhargava_-_Grokaem_algoritmy

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

время. От размера массива оно не зависит. В среднем случае хеш-таблицы
работают действительно быстро.

В худшем случае все операции с хеш-таблицей выполняются за время О(п)
(линейное время), а это очень медленно. Сравним хеш-таблицы с массива­

ми и списками .

"1.Elll- "1.Elll-
ТAliЛMЦЬI ТАliЛМЦЬI C.llJl-
(C.PE.a.HMP. ()(УJШМР. МАС.- JAHHЬIE
С.ЛУЧАR) С.ЛУЧАR) C.MllЬI С.ПМСКМ
nомск (}(1) 0(.1\> 0С1) Q<")

ЬСП6КА
0(1) O<.n> 0Cn) (Х1)

Y.Il.AЛE.-
0(1) O(n) Q(.") ()<1)
НМЕ.

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

Q низкий коэффициент заполнения;
Q хорошая хеш-функция.

ПРИМЕЧАНИЕ

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

www.trk.kg