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