Открытое и закрытое хеширование - История изменений

Nechaev: Перенаправление на Хеш-таблица#Разрешение коллизий с помощью цепочек

2012-06-12T10:21:51Z

Перенаправление на Хеш-таблица#Разрешение коллизий с помощью цепочек

Nechaev: Перенаправление на Хеширование#Открытое хеширование

2012-04-30T11:31:12Z

Перенаправление на Хеширование#Открытое хеширование

194.85.161.2: Перенаправление на Хеширование

2012-04-30T11:25:56Z

Перенаправление на Хеширование

Baev.dm: /* Закрытое хеширование */

2011-05-18T02:45:06Z

‎Закрытое хеширование

Baev.dm: /* Открытое хеширование */

2011-05-18T02:18:32Z

‎Открытое хеширование

Baev.dm: /* Открытое хеширование */

2011-05-18T02:11:10Z

‎Открытое хеширование

Baev.dm: /* Закрытое хеширование */

2011-05-17T18:01:25Z

‎Закрытое хеширование

Baev.dm: /* Закрытое хеширование */

2011-05-17T18:01:03Z

‎Закрытое хеширование

Baev.dm: /* Закрытое хеширование */

2011-05-17T18:00:10Z

‎Закрытое хеширование

Baev.dm: /* Открытое хеширование */

2011-05-17T17:53:57Z

‎Открытое хеширование

← Предыдущая		Версия 10:21, 12 июня 2012
Строка 1:		Строка 1:
−	#перенаправление [[~~Хеширование~~#~~Открытое хеширование~~]]	+	#перенаправление [[Хеш-таблица#Разрешение коллизий с помощью цепочек]]

← Предыдущая		Версия 11:31, 30 апреля 2012
Строка 1:		Строка 1:
−	#перенаправление [[Хеширование]]	+	#перенаправление [[Хеширование#Открытое хеширование]]

← Предыдущая		Версия 11:25, 30 апреля 2012
Строка 1:		Строка 1:
−	~~Есть разные методы борьбы с коллизиями. Рассмотрим два из них.~~	+	#перенаправление [[Хеширование]]
−	~~==Открытое хеширование==~~
−	Открытое хеширование (или по-другому: метод цепочек) — простейший метод борьбы с коллизиями. При использовании этого метода мы объединяем все элементы, хешированные в одну и ту же ячейку, в связный список. Ячейка <tex>j</tex> содержит указатель на заголовок списка всех элементов, хэш-значение ключа которых равно <tex>j</tex>; если таких элементов нет, ячейка содержит значение <tex>nil</tex>. Элементы вставляются в заголовок списка. Время, необходимое для вставки в наихудшем случае равно <tex>O(1)</tex>, учитывая то, что мы предполагаем отсутствие вставляемого элемента в таблице. Время поиска зависит от длины списка, и в худшем случае равно <tex>O(n)</tex>. Эта ситуация, когда все элементы хешируются в единственную ячейку. Если функция распределяем <tex>n</tex> ключей по <tex>m</tex> ячейкам таблицы равномерно, то в каждом списке будет содержаться порядка <tex>n/m</tex> ключей. Это число называется коэффициентом заполнения хеш-таблицы. Математический анализ хеширования с цепочками показывает, что в среднем случае все операции в такой хеш-таблице в среднем выполняются за время <tex>O(1)</tex>. (Анализ открытого хеширования см. Т.Корман, второе издание, стр. 288)
−	[[~~Файл:Hash_open_new.png\|900px\|thumb\|center\|Открытое хеширование~~]]
−
−	~~==Закрытое хеширование==~~
−	В случае метода открытой адресации (или по-другому: метод закрытого хеширования) все элементы хранятся непосредственно в хеш-таблице, без использования связных списков. В отличии от хеширования с цепочками, при использовании метода открытой адресации может возникнуть ситуация, когда хеш-таблица окажется полностью заполненной, так что будет невозможно добавлять в неё новые элементы. Так что при возникновении такой ситуации решением может быть динамическое увеличение размера хеш-таблицы, с одновременной её перестройкой.
−	Для разрешения же коллизий применяются несколько подходов. Самый простой из них – это метод линейного исследования. В этом случае при возникновении коллизии следующие за текущей ячейки проверяются одна за другой, пока не найдётся пустая ячейка, куда и помещается наш элемент. Так, при достижении последнего индекса таблицы, мы перескакиваем в начало, рассматривая её как «цикличный» массив.
−	~~[[Файл:Hash_close.png\|550px\|thumb\|center\|Закрытое хеширование с использованием метода линейного исследования]]~~
−	Одной из сложных вопросов реализации хеширования с открытой адресацией – это операция удаления элемента. Дело в том, что если мы просто удалим некий элемент их хеш-таблицы, то сделаем невозможным поиск ключа, в процессе вставки которого текущая ячейка оказалась заполненной. Так, мы можем помечать очищенные ячейки какой-то меткой, чтобы впоследствии это учитывать. (Анализ закрытого хеширования см. Т.Корман, второе издание, стр. 305)
−
−	~~==См. также==~~
−	* [[Различные алгоритмы хеширования]]
−	* [[Поиск свободного места при закрытом хешировании]]
−
−	~~==Литература==~~
−	* ''Т. Кормен, Ч. Лейзерсон, Р. Ривест'': Алгоритмы: построение и анализ, 2-е изд

@@ Строка 7: / Строка 7: @@
 В случае метода открытой адресации (или по-другому: метод закрытого хеширования) все элементы хранятся непосредственно в хеш-таблице, без использования связных списков. В отличии от хеширования с цепочками, при использовании метода открытой адресации может возникнуть ситуация, когда хеш-таблица окажется полностью заполненной, так что будет невозможно добавлять в неё новые элементы. Так что при возникновении такой ситуации решением может быть динамическое увеличение размера хеш-таблицы, с одновременной её перестройкой.
 Для разрешения же коллизий применяются несколько подходов. Самый простой из них – это метод линейного исследования. В этом случае при возникновении коллизии следующие за текущей ячейки проверяются одна за другой, пока не найдётся пустая ячейка, куда и помещается наш элемент. Так, при достижении последнего индекса таблицы, мы перескакиваем в начало, рассматривая её как «цикличный» массив.
-[[Файл:Hash_close_new.JPG|500px|thumb|center|Закрытое хеширование с использованием метода линейного исследования]]
+[[Файл:Hash_close.png|550px|thumb|center|Закрытое хеширование с использованием метода линейного исследования]]
 Одной из сложных вопросов реализации хеширования с открытой адресацией – это операция удаления элемента. Дело в том, что если мы просто удалим некий элемент их хеш-таблицы, то сделаем невозможным поиск ключа, в процессе вставки которого текущая ячейка оказалась заполненной. Так, мы можем помечать очищенные ячейки какой-то меткой, чтобы впоследствии это учитывать. (Анализ закрытого хеширования см. Т.Корман, второе издание, стр. 305)

@@ Строка 2: / Строка 2: @@
 ==Открытое хеширование==
 Открытое хеширование (или по-другому: метод цепочек) — простейший метод борьбы с коллизиями. При использовании этого метода мы объединяем все элементы, хешированные в одну и ту же ячейку, в связный список. Ячейка <tex>j</tex> содержит указатель на заголовок списка всех элементов, хэш-значение ключа которых равно <tex>j</tex>; если таких элементов нет, ячейка содержит значение <tex>nil</tex>. Элементы вставляются в заголовок списка. Время, необходимое для вставки в наихудшем случае равно <tex>O(1)</tex>, учитывая то, что мы предполагаем отсутствие вставляемого элемента в таблице. Время поиска зависит от длины списка, и в худшем случае равно <tex>O(n)</tex>. Эта ситуация, когда все элементы хешируются в единственную ячейку. Если функция распределяем <tex>n</tex> ключей по <tex>m</tex> ячейкам таблицы равномерно, то в каждом списке будет содержаться порядка <tex>n/m</tex> ключей. Это число называется коэффициентом заполнения хеш-таблицы. Математический анализ хеширования с цепочками показывает, что в среднем случае все операции в такой хеш-таблице в среднем выполняются за время <tex>O(1)</tex>. (Анализ открытого хеширования см. Т.Корман, второе издание, стр. 288)
-[[Файл:Hash_open_new.png|800px|thumb|center|Открытое хеширование]]
+[[Файл:Hash_open_new.png|900px|thumb|center|Открытое хеширование]]
 ==Закрытое хеширование==