2
правки
Изменения
м
→Хеширование в современных языках программирования
{{Определение|definition='''Хеш-табли́ца''' (англ. ''hash-table'') {{---}} структура данных, реализующая интерфейс ассоциативного массива. В отличие от [[Дерево_поиска,_наивная_реализация|деревьев поиска]], реализующих тот же интерфейс, обеспечивают меньшее время отклика в среднем. Представляет собой эффективную структуру данных для реализации словарей, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.}}
=== Введение ===
|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>
}}
=== Хеширование ===
'''Хеширование''' (англ. ''hashing'') {{---}} класс методов поиска, идея которого состоит в вычислении хеш-кода, однозначно определяемого элементом с помощью хеш-функции, и использовании его, как основы для поиска (индексирование в памяти по хеш-коду выполняется за <tex>O(1)</tex>). В общем случае, однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем вариантов исходных данных, поэтому существуют элементы, имеющие одинаковые хеш-коды — так называемые коллизии, но если два элемента имеют разный хеш-код, то они гарантированно
различаются. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций. Для того чтобы коллизии не замедляли работу с таблицой таблицей существуют [[Разрешение коллизий|методы для борьбы с ними]].
{{Определение
**unordered_map <ref>[http://www.cplusplus.com/reference/unordered_map/unordered_map/ unordered_map {{---}} cplusplus.com]</ref> {{---}} реализация интерфейса ассоциативного массива с использованием хеш-таблицы,
**unordered_set <ref>[http://www.cplusplus.com/reference/unordered_map/unordered_set/ unordered_set {{---}} cplusplus.com]</ref> {{---}} реализация интерфейса множества с использованием хеш-таблицы.
*Python (CPython)
**dict <ref>[https://github.com/python/cpython/blob/main/Objects/dictobject.c#L1 dictobject.c {{---}} https://github.com/python/cpython]</ref> {{---}} реализация интерфейса ассоциативного массива с использованием хеш-таблицы,
**set <ref>[https://hg.python.org/releasing/3.6/file/tip/Objects/setobject.c setobject.c {{---}} https://hg.python.org ] </ref> {{---}} реализация интерфейса множества с использованием хеш-таблицы.
== Примечания ==
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» {{---}} «Вильямс», 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/Хеш-таблица Хеш-таблица Википедия {{---}} ВикипедияХеш-таблица]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Хеширование]]
[[Категория:Структуры данных]]
