Изменения
Нет описания правки
На поиск элемента в хеш-таблице в худшем случае, может потребоваться столько же времени, как и в списке, а именно <tex>\Theta(n)</tex>, но на практике хеширование более эффективно. При некоторых разумных допущениях математическое ожидание времени поиска элемента в хеш-таблице составляет <tex>O(1)</tex>. А все операции (поиск, вставка и удаление элементов) в среднем выполняются за время <tex>O(1)</tex>.
При этом не гарантируется, что время выполнения отдельной операции мало́, так как при достижении некоторого значения коэффициента заполнения необходимо [[Перехеширование. Амортизационный анализ|перехешировать]] таблицу: увеличить размер массива <tex>H</tex> и заново добавить в новую хеш-таблицу все пары.
{{Лемма
|statement=Вероятность коллизий при вставке в хеш-таблицу превышает 50%
|proof=
Пусть хеш-таблица имеет размер <tex>len</tex> и в нее добавляют <tex>n</tex> элементов. Рассмотрим <tex>{p}'(n)</tex> - вероятность того, что не возникнет ни одной коллизии. Добавим два любых элемента в нашу хеш-таблицу. Вероятность того, что они не попадут в одну и ту же ячейку таблицы равна <tex>1 - \frac{1}{len}</tex>. Возьмем еще один элемент. Тогда вероятность того, что третий элемент не попадет в одну из уже занятых ячеек равна <tex>1 - \frac{2}{len}</tex>. Рассуждая аналогичным образом, получим формулу:
<tex>{p}'(n) = \left( 1 - \frac{1}{len}\right )\cdot \left( 1 - \frac{2}{len}\right )\dots\left( 1 - \frac{n - 1}{len}\right ) = \frac{len \cdot \left(len - 1 \right )\dots\left (len - n + 1 \right )}{len^{n}} = \frac{len!}{len^{n} \cdot \left (len - n \right)!}</tex>
Тогда <tex>{p}(n)</tex> - вероятность возникновения коллизии равна:
<tex>p(n) = 1 - {p}'(n)</tex>,
что в общем случае <tex> > \frac{1}{2}</tex>
}}
===Хеширование в современных языках программирования===
