Изменения

{{Определение |definition='''Хеш-табли́ца''' (англ. ''hash-table'') {{---}} структура данных, реализующая интерфейс ассоциативного массива. В отличие от [[Дерево_поиска,_наивная_реализация|деревьев поиска]], реализующих тот же интерфейс, обеспечивают меньшее время отклика в среднем. Представляет собой эффективную структуру данных для реализации словарей, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.

Существует два основных вида хеш-таблиц: [[Разрешение_коллизий#Разрешение коллизий с помощью цепочек|''с цепочками'' ]] и [[Разрешение_коллизий#Линейное разрешение коллизий|''открытой адресацией'']]. Хеш-таблица содержит некоторый массив <tex>H</tex>, элементы которого есть пары (хеш-таблица с открытой адресацией) или списки пар (хеш-таблица с цепочками).

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

{{Определение |definition='''Хеширование''' (англ. ''hashing'') {{---}} класс методов поиска, идея которого состоит в вычислении хеш-кода, однозначно определяемого элементом с помощью хеш-функции, и использовании его, как основы для поиска (индексирование в памяти по хеш-коду выполняется за <tex>O(1)</tex>). В общем случае, однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем вариантов исходных данных, поэтому существуют элементы, имеющие одинаковые хеш-коды — так называемые коллизии, но если два элемента имеют разный хеш-код, то они гарантированно различаются. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций. Для того чтобы коллизии не замедляли работу с таблицой таблицей существуют [[Разрешение коллизий|методы для борьбы с ними]].}}

|definition=<tex>U </tex> {{---}} множество объектов (универсум).<br> <tex>h : U \rightarrow S = \mathcal {f} 0 \dots m - 1 \mathcal {g}</tex> {{---}} называется хеш-функцией, где множество <tex>S</tex> хранит ключи из множества <tex>U</tex>.<br> Если <tex>x \in U</tex> значит <tex>h(x) \in S</tex> <br> '''Коллизия:''' (англ. ''collision''): <tex>\exists x \neq y : h(x) = h(y)</tex>

** Статическое {{---}} фиксированное количество элементов. Один раз заполняем хеш-таблицу и осуществляем только проверку на наличие в ней нужных элементов., ** Динамическое {{---}} добавляем, удаляем и смотрим на наличие нужных элементов.

** Детерминированная хеш-функция., ** Случайная хеш-функция.

На поиск элемента в хеш-таблице в худшем случае, может потребоваться столько же времени, как и в списке, а именно <tex>\Theta(n)</tex>, но на практике хеширование более эффективно. При некоторых разумных допущениях [[Математическое_ожидание_случайной_величины|математическое ожидание ]] времени поиска элемента в хеш-таблице составляет <tex>O(1)</tex>. А все операции (поиск, вставка и удаление элементов) в среднем выполняются за время <tex>O(1)</tex>.

**HashMap <ref>[http://docs.oracle.com/javase/7/docs/api/java/util/HashMap.html HashMap {{---}} Java Platform SE 7]</ref> {{---}} реализация интерфейса ассоциативного массива с использованием хеш-таблицы,**HashSet <ref>[http://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html HashSet {{---}} Java Platform SE 7]</ref> {{---}} реализация интерфейса множества с использованием хеш-таблицы,**LinkedHashMap <ref>[http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html LinkedHashMap {{---}} Java Platform SE 7]</ref> {{---}} потомок класса HashMap. Позволяет просматривать значения в том порядке, в котором они были добавлены.

**hash_map unordered_map <ref>[http://www.cplusplus.com/reference/unordered_map/unordered_map/ unordered_map {{---}} cplusplus.com]</ref> {{---}} реализация интерфейса ассоциативного массива с использованием хеш-таблицы,**hash_set 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> {{---}} реализация интерфейса множества с использованием хеш-таблицы.

* [http://ru.wikipedia.org/wiki/Хеш-таблица Хеш-таблица Википедия {{---}} ВикипедияХеш-таблица]