277
правок
Изменения
→Линейное разрешение коллизий
'''Сортировка подсчётомХеш-табли́ца''' {{---}} алгоритм сортировкиструктура данных, реализующая интерфейс ассоциативного массива. Представляет собой эффективную структуру данных для реализации словарей, в котором предполагаетсяа именно, что все сортируемые элементы {{---}} целые числаона позволяет хранить пары (ключ, принадлежащие интервалу от <tex>0</tex> до <tex>k</tex>значение) и выполнять три операции: операцию добавления новой пары, где <tex>k</tex> {{---}} некоторая целая константаоперацию поиска и операцию удаления пары по ключу.
== Основная идея = Введение ===Основная идея сортировки подсчетом заключается в том, чтобы для каждого элемента Существует два основных вида хеш-таблиц: ''с цепочками'' и ''открытой адресацией''. Хеш-таблица содержит некоторый массив <tex>xH</tex> определить количество элементов, которые меньше <tex>x</tex>. С помощью этого, мы можем поместить элемент туда, где он должен находиться в отсортированном массиве. Например, если элементы которого есть <tex>42</tex> элемента, которые меньше <tex>x</tex>, то после сортировки он будет занимать <tex>43</tex>пары (хеш-таблица с открытой адресацией) или списки пар (хеш-ю позицию. Если допускается, что несколько элементов могут иметь одинаковое значение, то алгоритм придётся модифицировать, потому что мы не можем разместить все такие элементы в одной позициитаблица с цепочками).
== Анализ = Хеширование ===В первом алгоритме первые два цикла работают за <tex>\Theta(k)</tex> и <tex>\Theta(n)</tex>, соответственно; двойной цикл за <tex>\Theta(n + k)</tex>. Во втором алгоритме циклы занимают <tex>\Theta(k)</tex>, <tex>\Theta(n)</tex>, <tex>\Theta(k)</tex> и <tex>\Theta(n)</tex>, соответственно. Итого оба алгоритма имеют линейную временную трудоёмкость <tex>\Theta(n + k)</tex>. Используемая память в первом алгоритме равна <tex>\Theta(k)</tex>, а во втором <tex>\Theta(n + k)</tex>.
'''Хеширование''' {{---}} класс методов поиска, идея которого состоит в вычислении хеш-кода, однозначно определяемого элементом с помощью хеш-функции, и использовании его, как основы для поиска (индексирование в памяти по хеш-коду выполняется за <tex>O(1)</tex>). В общем случае, однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем вариантов исходных данных, поэтому существуют элементы, имеющие одинаковые хеш-коды — так называемые коллизии, но если два элемента имеют разный хеш-код, то они гарантированно различаются. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций.{{Определение|id=def1|definition=<tex>U </tex> {{---}} множество объектов (универсум).<br> <tex>h : U \rightarrow S = \mathcal {f} 0 ... m - 1 \mathcal {g}</tex> {{---}} называется хеш-функцией, где множество <tex>S</tex> хранит ключи из множества <tex>U</tex>.<br> Если <tex>x \in U</tex> значит <tex>h(x) \in S</tex> <br> '''Коллизия:''' <tex>\exists x \neq y : h(x) = h(y)</tex>}}==== Виды хеширования ====* По способу хранения:** Статическое {{---}} фиксированное количество элементов. Один раз заполняем хеш-таблицу и осуществляем только проверку на наличие в ней нужных элементов.** Динамическое {{---}} добавляем, удаляем и смотрим на наличие нужных элементов.* По виду хеш-функции:** Детерминированная хеш-функция.** Случайная хеш-функция. === Свойства хеш-таблицы === На поиск элемента в хеш-таблице в худшем случае, может потребоваться столько же времени, как и в списке, а именно <tex>\Theta(n)</tex>, но на практике сортировка подсчетом применяетсяхеширование более эффективно. При некоторых разумных допущениях математическое ожидание времени поиска элемента в хеш-таблице составляет <tex>O(1)</tex>. А все операции (поиск, когда вставка и удаление элементов) в среднем выполняются за время <tex>O(1)</tex>.При этом не гарантируется, что время выполнения отдельной операции мало́, так как при достижении некоторого значения коэффициента заполнения необходимо [[Перехеширование. Амортизационный анализ|перехешировать]] таблицу: увеличить размер массива <tex>H</tex>k и заново добавить в новую хеш-таблицу все пары. == Разрешение коллизий == = == Разрешение коллизий с помощью цепочек ===[[Файл:open_hash.png|thumb|380px|right|Разрешение коллизий при помощи цепочек.]]Каждая ячейка <tex>i</tex> массива <tex>H</tex> содержит указатель на начало списка всех элементов, хеш-код которых равен <tex>i</tex>, либо указывает на их отсутствие. Коллизии приводят к тому, что появляются списки размером больше одного элемента. Время, необходимое для вставки в наихудшем случае равно <tex>O(n1)</tex>. Это операция выполняет быстро, так как считается, что вставляемый элемент отсутствует в таблице, но если потребуется, то перед вставкой мы можем выполнить поиск этого элемента. Время работы поиска в наихудшем случае пропорционально длине списка, а если все <tex>n</tex> ключей захешировались в этом случае одну и ту же ячейку (создав список длиной <tex>n</tex>) время работы алгоритма поиска будет равно <tex>\Theta(n)</tex> плюс время вычисления хеш-функции, что ничуть не лучше, чем использование связного списка для хранения всех <tex>n</tex> элементов. Удаления элемента может быть выполнено за <tex>O(1)</tex>, как и вставка, при использовании двухсвязного списка. === Линейное разрешение коллизий ===[[Файл:close_hash.png|thumb|380px|right|Пример хеш-таблицы с открытой адресацией и линейным пробированием.]]Все элементы хранятся непосредственно в хеш-таблице, без использования связных списков. В отличии от хеширования с цепочками, при использовании этого метода может возникнуть ситуация, когда хеш-таблица окажется полностью заполненной, следовательно будет невозможно добавлять в неё новые элементы. Так что при возникновении такой ситуации решением может быть динамическое увеличение размера хеш-таблицы, с одновременной её перестройкой. Рассмотрим один из таких методов.<ref>Другой метод борьбы с коллизиями {{---}} [[Двойное хеширование | двойное хеширование]]</ref> В массиве <tex>H</tex> хранятся сами пары ключ-значение. Алгоритм вставки элемента проверяет ячейки массива <tex>H</tex> в заданном порядке до тех пор, пока не будет найдена первая свободная ячейка, в неё и будет записан новый элемент. Это позволяет сэкономить память на хранение указателей. Последовательность, в которой просматриваются ячейки хеш-таблицы, называется последовательностью проб. В общем случае, она зависит только от ключа элемента, то есть это последовательность <tex>h_0(x)</tex>, <tex>h_1(x)</tex>, ...,<tex>h_n</tex><tex>_-</tex><tex>_1</tex><tex>(x)</tex>, где <tex>x</tex> — ключ элемента, а <tex>h_i(x)</tex> — произвольные функции, сопоставляющие каждому ключу ячейку в хеш-таблице. Первый элемент в последовательности, как правило, равен значению некоторой хеш-функции от ключа, а остальные считаются от него каким-нибудь способом. Для успешной работы алгоритмов поиска последовательность проб должна быть такой, чтобы все ячейки хеш-таблицы оказались просмотренными ровно по одному разу.<ref>[[Поиск свободного места при закрытом хешировании | Поиск свободного места при закрытом хешировании]]</ref> == Примечания ==<references/>
== Источники ==
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» {{---}} «Вильямс», 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/Сортировка_подсчётом Сортировка подсчетом Хеш-таблица Хеш-таблица {{---}} Википедия]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:СортировкаХеширование]]
