Изменения
→Источники информации
|proof=
Пусть хеш-таблица имеет размер <tex>len</tex> и в нее добавляют <tex>n</tex> элементов. Рассмотрим <tex>{p}'(n)</tex> - — вероятность того, что не возникнет ни одной коллизии. Добавим два любых элемента в нашу хеш-таблицу. Вероятность того, что они не попадут в одну и ту же ячейку таблицы равна <tex>1 - \dfrac{1}{len}</tex>. Возьмем еще один элемент. Тогда вероятность того, что третий элемент не попадет в одну из уже занятых ячеек равна <tex>1 - \dfrac{2}{len}</tex>. Рассуждая аналогичным образом, получим формулу:
<tex>{p}'(n) = \left( 1 - \dfrac{1}{len}\right )\cdot \left( 1 - \dfrac{2}{len}\right )\dots\left( 1 - \dfrac{n - 1}{len}\right ) = \dfrac{len \cdot \left(len - 1 \right )\dots\left (len - n + 1 \right )}{len^{n}} = \dfrac{len!}{len^{n} \cdot \left (len - n \right)!}</tex>
Тогда <tex>{p}(n)</tex> - — вероятность возникновения коллизии равна:
<tex>p(n) = 1 - {p}'(n)</tex>,
что в общем случае <tex> > \fracdfrac{1}{2}</tex>
}}
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» {{---}} «Вильямс», 2011 г. {{---}} 1296 стр. {{---}} ISBN 978-5-8459-0857-5, 5-8459-0857-4, 0-07-013151-1
* Дональд Кнут. «Искусство программирования, том 3. Сортировка и поиск» {{---}} «Вильямс», 2007 г. {{---}} 824 стр. {{---}} ISBN 0-201-89685-0
* Википедия {{---}} [http://ru.wikipedia.org/wiki/Хеш-таблица Википедия {{---}} Хеш-таблица]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Хеширование]]
[[Категория:Структуры данных]]
