Изменения
→Введение
Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа. Хеш-код <tex>i = h(key)</tex> играет роль индекса в массиве <tex>H</tex>, а зная индекс, мы можем выполнить требующуюся операцию (добавление, удаление или поиск).
Количество коллизий зависит от хеш-функции; чем лучше используемая хеш-функция, тем меньше вероятность их возникновения. При вставке в хеш-таблицу вероятность коллизии в общем случае превышает <tex>50%</tex><ref>
<tex>p(n) = 1 - 1 \cdot \left(1-\frac{1}{len}\right) \cdot \left(1-\frac{2}{len}\right) \cdots \left(1-\frac{n-1}{len}\right) = { len \cdot len-1 \cdots (len-n+1) \over len^n } </tex> <tex> = { len! \over len^n \cdot (len-n)!},</tex><br>
где <tex>n</tex> {{---}} количество элементов в хеш-таблице, а <tex>len</tex> {{---}} её размер.</ref> (при равномерном распределении значений хеш-функции)<ref>[http://ru.wikipedia.org/wiki/Парадокс_дней_рождения Парадокс дней рождения {{---}} Википедия]</ref>. Способ разрешения коллизий — важная составляющая любой хеш-таблицы.
