|
|
| (не показана 21 промежуточная версия 2 участников) |
| Строка 1: |
Строка 1: |
| − | <tex>q</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>H</tex>, элементы которого есть пары (хеш-таблица с открытой адресацией) или списки пар (хеш-таблица с цепочками).
| |
| − | | |
| − | Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа. Получающееся хеш-значение <tex>i = hash(key)</tex> играет роль индекса в массиве <tex>H</tex>. Затем выполняемая операция (добавление, удаление или поиск) перенаправляется объекту, который хранится в соответствующей ячейке массива <tex>H[i]</tex>.
| |
| − | | |
| − | Ситуация, когда для различных ключей получается одно и то же хеш-значение, называется коллизией. Такие события не так уж и редки — например, при вставке в хеш-таблицу размером 365 ячеек всего лишь 23-х элементов вероятность коллизии уже превысит 50 % (если каждый элемент может равновероятно попасть в любую ячейку). Поэтому механизм разрешения коллизий — важная составляющая любой хеш-таблицы.
| |
| − | | |
| − | В некоторых специальных случаях удаётся избежать коллизий вообще. Например, если все ключи элементов известны заранее (или очень редко меняются), то для них можно найти некоторую совершенную хеш-функцию, которая распределит их по ячейкам хеш-таблицы без коллизий. Хеш-таблицы, использующие подобные хеш-функции, не нуждаются в механизме разрешения коллизий, и называются хеш-таблицами с ''прямой адресацией''.
| |
| − | | |
| − | Число хранимых элементов, делённое на размер массива <tex>H</tex> (число возможных значений хеш-функции), называется коэффициентом заполнения хеш-таблицы (load factor) и является важным параметром, от которого зависит среднее время выполнения операций.
| |
| − | | |
| − | == Свойства хеш-таблицы ==
| |
| − | | |
| − | Важное свойство хеш-таблиц состоит в том, что, при некоторых разумных допущениях, все три операции (поиск, вставка, удаление элементов) в среднем выполняются за время <tex>O(1)</tex>.
| |
| − | Но при этом не гарантируется, что время выполнения отдельной операции мало́.
| |
| − | Это связано с тем, что при достижении некоторого значения коэффициента заполнения
| |
| − | необходимо осуществлять перестройку индекса хеш-таблицы: увеличить значение размера массива <tex>H</tex> и заново добавить в пустую хеш-таблицу все пары.
| |
| − | | |
| − | == Разрешение коллизий ==
| |
| − | | |
| − | === Открытое хеширование ===
| |
| − | [[Файл:open_hash.png|thumb|380px|right|Разрешение коллизий при помощи цепочек.]]
| |
| − | Каждая ячейка массива <tex>H</tex> является указателем на связный список(цепочку) пар ключ-значение, соответствующих одному и тому же хеш-значению ключа. Коллизии просто приводят к тому, что появляются списки длиной более одного элемента.
| |
| − | | |
| − | Операции поиска или удаления элемента требуют просмотра всех элементов соответствующему ему списка, чтобы найти в нем элемент с заданным ключом. Для добавления элемента нужно добавить элемент в конец или начало соответствующего списка, и, в случае, если коэффициент заполнения станет слишком велик, увеличить размер массива <tex>H</tex> и перестроить таблицу.
| |
| − | | |
| − | === Закрытое хеширование ===
| |
| − | [[Файл:close_hash.png|thumb|380px|right|Пример хеш-таблицы с открытой адресацией и линейным пробированием.]]
| |
| − | В массиве <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> — произвольные функции, сопоставляющие каждому ключу ячейку в хеш-таблице. Первый элемент в последовательности, как правило, равен значению некоторой хеш-функции от ключа, а остальные считаются от него каким-нибудь способом. Для успешной работы алгоритмов поиска последовательность проб должна быть такой, чтобы все ячейки хеш-таблицы оказались просмотренными ровно по одному разу.
| |
| − | | |
| − | Алгоритм поиска просматривает ячейки хеш-таблицы в том же самом порядке, что и при вставке, до тех пор, пока не найдется либо элемент с искомым ключом, либо свободная ячейка (что означает отсутствие элемента в хеш-таблице).
| |
| − | | |
| − | Удаление элементов в такой схеме несколько затруднено. Обычно поступают так: заводят булевый флаг для каждой ячейки, помечающий, удален ли элемент в ней или нет. Тогда удаление элемента состоит в установке этого флага для соответствующей ячейки хеш-таблицы, но при этом необходимо модифицировать процедуру поиска существующего элемента так, чтобы она считала удалённые ячейки занятыми, а процедуру добавления — чтобы она их считала свободными и сбрасывала значение флага при добавлении.
| |
| − | | |
| − | === Источники ===
| |
| − | * Дональд Кнут "Искусство программирования" Хеширование
| |
| − | * [http://ru.wikipedia.org/wiki/Хеширование Хеширование]
| |
| − | * [http://ru.wikipedia.org/wiki/Хеш-таблица Хеш-таблица]
| |
| − | | |
| − | [[Категория:Дискретная математика и алгоритмы]]
| |
