Page 265 - Bkhargava_-_Grokaem_algoritmy

264 Глава 11. Что дальше?

.... \ ь~ ,(}:)V"\
~с.,~
o..A\t..io

Появляется новый объект, и вы хотите узнать, содержится ли он в суще­
ствующем наборе. Эта задача быстро решается при помощи хеша. На­
пример, представьте, что Google создает большой хеш, ключами которого
являются все обработанные страницы.

Как узнать, обрабатывался ли сайт adit.io? Нужно заглянуть в хеш.

У adit.io имеется свой ключ в хеше, а значит, адрес уже обрабатывался.
Среднее время обращения к элементам в хеш-таблице составляет 0(1). Та­
ким образом, вы узнали о том, что страница adit.io уже проиндексирована
за постоянное время. Неплохо!

www.trk.kg