Грокаем а Иллюстрированное пособие для программистов и любопытствующих

СРЕДНИК ХУДШИЙ СЛУЧАЙ СЛУЧАЙ

поиск	0(1)	0<П)
ЬСТАбКА	Оо>	о>
УДАЛЕ­ НИЕ	СК»	О)

БЫСТР0ДЕЙСТ5ИЕ
ХЕШ-ТАБЛИЦ





В среднем хеш-таблицы выполняют любые операции за время 0(1). Время 0(1) называется постоянным. Ранее примеры постоянного времени вам еще
н
ОСЮ
ЛИНЕЙНОЕ ВРЕМЯ (ПРОСТОЙ ПОИСК)

е встречались. Оно не означает, что операции выполняются мгновенно; просто время остается постоянным независимо от размера хеш-таблицы. Например, вы знаете, что простой поиск выполняется за линейное время.
Б
Q(Lo
ЛОГАРИФМИЧЕСКОЕ ВРЕМЯ (БИНАРНЫЙ ПОИСК)

инарный поиск работает быстрее — за логарифмическое время:
Поиск данных в хеш-таблице выполняется за постоянное время.
О СО
ПОСТОЯННОЕ ВРЕМЯ
(ХЕШ-ТАБЛИЦЫ)
Видите горизонтальную линию? Она означает, что при любом размере хеш-таблицы — 1 элемент или 1 миллиард элементов — выборка данных займет одинаковое время. На самом деле вы уже сталкивались с постоян­ным временем: получение элемента из массива выполняется за постоянное
время. От размера массива оно не зависит. В среднем случае хеш-таблицы работают действительно быстро.
В худшем случае все операции с хеш-таблицей выполняются за время 0(п) (линейное время), а это очень медленно. Сравним хеш-таблицы с массива­ми и списками.

поиск	Of-^1)	Ск»>	Oci)	о>
ЪСТАВКА	OU)	<5 о	0о>	ОСЮ
УДАЛЕ­ НИЕ	Осо	О")	Ск>р	Осо

ХЕШ- ХЕШ-


ТАБЛИЦЫ ТАБЛИЦЫ СВЯ-
(СРЕД.НИЙ (ХУДШИЙ MAC- ЗАННЫЕ СЛУЧАЙ) СЛУЧАЙ) СИВЫ СПИСКИ

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

• 
  низкий коэффициент заполнения;
  
• 
  х
  — — ~ — — ~ — — —
  ! ПРИМЕЧАНИЕ I
  ¹ Материал следующего раздела не является обязательным. Речь пойдет о том, [
  ! как реализовать хеш-таблицу, но вам никогда не придется делать это само- i
  ^! стоятельно. Какой бы язык программирования вы ни выбрали, в нем найдет- ¹
  I ся готовая реализация хеш-таблиц. Вы можете воспользоваться встроенной ,
  ¹ реализацией хеш-таблицы, не сомневаясь в том, что она имеет хорошую эф- ¹
  ! фективность. А в следующем разделе мы заглянем во внутреннее устройство ,
  i хеш-таблиц. ¹
  
  орошая хеш-функция.
  

Коэффициент заполнения
К
КОЛИЧЕСТВО ЭЛЕМЕНТОВ
В ХЕШ-ТАБЛИЦЕ


ОБЩЕЕ КОЛИЧЕСТВО
ЭЛЕМЕНТОВ

оэффициент заполнения хеш-таблицы вычисляет­ся по простой формуле.
Х
ЗАНЯТЫЕ ЭЛЕМЕНТЫ
4 V
КОЭФФИЦИЕНТ ЗАПОЛНЕНИЯ - У₅

еш-таблицы используют массив для хранения данных, поэтому для вы­числения коэффициента заполнения можно подсчитать количество за­полненных элементов в массиве. Например, в следующей хеш-таблице коэффициент заполнения равен ²/₅, или 0,4.
С
1Ф

кажите, каков коэффициент заполнения этой таблицы?
КОЭФФИЦИЕНТ
ЗАПОЛНЕНИЯ
Если вы ответили «*/₃» — все правильно. По коэффициенту заполнения можно оценить количество пустых ячеек в хеш-таблице.
Предположим, в хеш-таблице нужно сохранить цены 100 товаров и хеш- таблица состоит из 100 элементов. В лучшем случае каждому товару будет выделен отдельный элемент.
Ц
ЦЕНА ж МОЛОКА ^


1А


и *м. д....

ЕНА АПЕЛЬ­СИНОВ
Коэффициент заполнения этой хеш-таблицы равен 1. А если хеш-таблица состоит всего из 50 элементов? Тогда ее коэффициент заполнения будет равен 2. Выделить под каждый товар отдельный элемент ни при каких условиях не удастся, потому что элементов попросту не хватит! Коэффи­циент заполнения больше 1 означает, что количество товаров превышает количество элементов в массиве.
С ростом коэффициента заполнения в хеш-таблицу приходится добавлять новые элементы, то есть изменять ее размер. Представим, что эта хеш- таблица приближается к заполнению.
[4ТзТГ
КОЭФФИЦИЕНТ
ЗАПОЛНЕНИЯ - V,
Х
еш-таблицу необходимо расширить. Расширение начинается с создания нового массива большего размера. Обычно в таком случае создается массив вдвое большего размера.
Т
4


3

еперь все эти элементы необходимо заново вставить в новую хеш-таблицу функцией hash: