Хеш-таблица - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:42:06Z

rollbackEdits.php mass rollback

185.244.195.157 в 03:33, 1 сентября 2022

2022-09-01T03:33:52Z

Kirlf: /* Хеширование в современных языках программирования */

2021-09-24T09:28:47Z

‎Хеширование в современных языках программирования

Kirlf: /* Хеширование в современных языках программирования */ Python examples

2021-09-24T09:26:07Z

‎Хеширование в современных языках программирования: Python examples

Dmozze: Правка орфографии

2019-09-05T19:56:18Z

Правка орфографии

176.59.15.166: Отмена правки 64065, сделанной 93.85.153.53 (обсуждение)

2018-03-10T11:29:50Z

Отмена правки 64065, сделанной 93.85.153.53 (обсуждение)

93.85.153.53: Полностью удалено содержимое страницы

2018-03-09T19:27:39Z

Полностью удалено содержимое страницы

Paul1298 в 13:54, 21 июня 2017

2017-06-21T13:54:03Z

217.66.156.115: /* Источники информации */

2015-06-05T20:06:11Z

‎Источники информации

217.66.156.115: /* Источники информации */

2015-06-05T20:04:28Z

‎Источники информации

@@ Строка 1: / Строка 1: @@
 {{Определение
-|definition='''Хеш-табли́ца''' (англ. ''hash-table'') {{---}} структура данных, реализующая интерфейс ассоциативного массива. В отличие от [[Дерево_поиска,_наивная_реализация|деревьев поиска]], реализующих тот же интерфейс, обеспечивают меньшее время отклика в среднем. Представляет собой эффективную структуру данных для реализации словарей, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.
+|definition='''Хеш-табли́ца''' (англ. ''hash-table'') {{---}} структура данных, реализующая интерфейс ассоциативного массива. В отличие от [[Дерево_поиска,_наивная_реализация|деревьев поиска]], реализующих тот же интерфейс, обеспечивают меньшее время отклика в среднем. Представляет собой эффективную структуру данных для реализации словарей, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.
 }}
@@ Строка 42: / Строка 21: @@
 }}
-Способ разрешения коллизий — важная составляющая любой хеш-таблицы.
+Способ разрешения коллизий — важная составляющая любой хеш-таблицы.
 Полностью избежать коллизий для произвольных данных невозможно в принципе, и хорошая хеш-функция в состоянии только минимизировать их количество. Но, в некоторых специальных случаях их удаётся избежать. Если все ключи элементов известны заранее, либо меняются очень редко, то можно подобрать хеш-функцию, с помощью которой, все ключи будут распределены по хеш-таблице без коллизий. Это хеш-таблицы с ''прямой адресацией''; в них все операции, такие как: поиск, вставка и удаление работают за <tex>O(1)</tex>.

@@ Строка 1: / Строка 1: @@
 {{Определение
-|definition='''Хеш-табли́ца''' (англ. ''hash-table'') {{---}} структура данных, реализующая интерфейс ассоциативного массива. В отличие от [[Дерево_поиска,_наивная_реализация|деревьев поиска]], реализующих тот же интерфейс, обеспечивают меньшее время отклика в среднем. Представляет собой эффективную структуру данных для реализации словарей, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.
+|definition='''Хеш-табли́ца''' (англ. ''hash-table'') {{---}} структура данных, реализующая интерфейс ассоциативного массива. В отличие от [[Дерево_поиска,_наивная_реализация|деревьев поиска]], реализующих тот же интерфейс, обеспечивают меньшее время отклика в среднем. Представляет собой эффективную структуру данных для реализации словарей, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.
 }}
@@ Строка 21: / Строка 42: @@
 }}
-Способ разрешения коллизий — важная составляющая любой хеш-таблицы.
+Способ разрешения коллизий — важная составляющая любой хеш-таблицы.
 Полностью избежать коллизий для произвольных данных невозможно в принципе, и хорошая хеш-функция в состоянии только минимизировать их количество. Но, в некоторых специальных случаях их удаётся избежать. Если все ключи элементов известны заранее, либо меняются очень редко, то можно подобрать хеш-функцию, с помощью которой, все ключи будут распределены по хеш-таблице без коллизий. Это хеш-таблицы с ''прямой адресацией''; в них все операции, такие как: поиск, вставка и удаление работают за <tex>O(1)</tex>.

@@ Строка 62: / Строка 62: @@
 *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/releasing/3.6/file/tip/Objects/setobject.c ] </ref> {{---}} реализация интерфейса множества с использованием хеш-таблицы.
+**set <ref>[https://hg.python.org/releasing/3.6/file/tip/Objects/setobject.c setobject.c {{---}} https://hg.python.org ] </ref> {{---}} реализация интерфейса множества с использованием хеш-таблицы.
 == Примечания ==

@@ Строка 60: / Строка 60: @@
 **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>  {{---}} реализация интерфейса множества с использованием хеш-таблицы.
 == Примечания ==

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

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

	+	=== Введение ===
	+	Существует два основных вида хеш-таблиц: [[Разрешение_коллизий#Разрешение коллизий с помощью цепочек\|''с цепочками'']] и [[Разрешение_коллизий#Линейное разрешение коллизий\|''открытой адресацией'']]. Хеш-таблица содержит некоторый массив <tex>H</tex>, элементы которого есть пары (хеш-таблица с открытой адресацией) или списки пар (хеш-таблица с цепочками).
	+
	+	Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа. Хеш-код <tex>i = h(key)</tex> играет роль индекса в массиве <tex>H</tex>, а зная индекс, мы можем выполнить требующуюся операцию (добавление, удаление или поиск).
	+
	+	Количество коллизий зависит от хеш-функции; чем лучше используемая хеш-функция, тем меньше вероятность их возникновения.
	+	{{Лемма
	+	\|statement=Вероятность коллизий при вставке в хеш-таблицу превышает 50%
	+	\|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> > \dfrac{1}{2}</tex>
	+	}}
	+
	+	Способ разрешения коллизий — важная составляющая любой хеш-таблицы.
	+
	+	Полностью избежать коллизий для произвольных данных невозможно в принципе, и хорошая хеш-функция в состоянии только минимизировать их количество. Но, в некоторых специальных случаях их удаётся избежать. Если все ключи элементов известны заранее, либо меняются очень редко, то можно подобрать хеш-функцию, с помощью которой, все ключи будут распределены по хеш-таблице без коллизий. Это хеш-таблицы с ''прямой адресацией''; в них все операции, такие как: поиск, вставка и удаление работают за <tex>O(1)</tex>.
	+
	+	Если мы поделим число хранимых элементов на размер массива <tex>H</tex> (число возможных значений хеш-функции), то узнаем коэффициент заполнения хеш-таблицы (англ. ''load factor''). От этого параметра зависит среднее время выполнения операций.
	+
	+	=== Хеширование ===
	+	'''Хеширование''' (англ. ''hashing'') {{---}} класс методов поиска, идея которого состоит в вычислении хеш-кода, однозначно определяемого элементом с помощью хеш-функции, и использовании его, как основы для поиска (индексирование в памяти по хеш-коду выполняется за <tex>O(1)</tex>). В общем случае, однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем вариантов исходных данных, поэтому существуют элементы, имеющие одинаковые хеш-коды — так называемые коллизии, но если два элемента имеют разный хеш-код, то они гарантированно
	+	различаются. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций. Для того чтобы коллизии не замедляли работу с таблицой существуют [[Разрешение коллизий\|методы для борьбы с ними]].
	+
	+	{{Определение
	+	\|id=def1
	+	\|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>.
	+	При этом не гарантируется, что время выполнения отдельной операции мало́, так как при достижении некоторого значения коэффициента заполнения необходимо [[Перехеширование. Амортизационный анализ\|перехешировать]] таблицу: увеличить размер массива <tex>H</tex> и заново добавить в новую хеш-таблицу все пары.
	+
	+	===Хеширование в современных языках программирования===
	+
	+	Почти во всех современных языках присутствуют классы, реализующие хеширование. Рассмотрим некоторые из них.
	+	*Java
	+	**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. Позволяет просматривать значения в том порядке, в котором они были добавлены.
	+	*C++
	+	**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> {{---}} реализация интерфейса множества с использованием хеш-таблицы.
	+
	+	== Примечания ==
	+	<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/Хеш-таблица Википедия {{---}} Хеш-таблица]
	+
	+	[[Категория:Дискретная математика и алгоритмы]]
	+	[[Категория:Хеширование]]
	+	[[Категория:Структуры данных]]

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

−	~~=== Введение ===~~
−	Существует два основных вида хеш-таблиц: [[Разрешение_коллизий#Разрешение коллизий с помощью цепочек\|''с цепочками'']] и [[Разрешение_коллизий#Линейное разрешение коллизий\|''открытой адресацией'']]. Хеш-таблица содержит некоторый массив <tex>H</tex>, элементы которого есть пары (хеш-таблица с открытой адресацией) или списки пар (хеш-таблица с цепочками).
−
−	Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа. Хеш-код <tex>i = h(key)</tex> играет роль индекса в массиве <tex>H</tex>, а зная индекс, мы можем выполнить требующуюся операцию (добавление, удаление или поиск).
−
−	Количество коллизий зависит от хеш-функции; чем лучше используемая хеш-функция, тем меньше вероятность их возникновения.
−	~~{{Лемма~~
−	~~\|statement=Вероятность коллизий при вставке в хеш-таблицу превышает 50%~~
−	~~\|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> > \dfrac{1}{2}</tex>~~
−	}}
−
−	~~Способ разрешения коллизий — важная составляющая любой хеш-таблицы.~~
−
−	Полностью избежать коллизий для произвольных данных невозможно в принципе, и хорошая хеш-функция в состоянии только минимизировать их количество. Но, в некоторых специальных случаях их удаётся избежать. Если все ключи элементов известны заранее, либо меняются очень редко, то можно подобрать хеш-функцию, с помощью которой, все ключи будут распределены по хеш-таблице без коллизий. Это хеш-таблицы с ''прямой адресацией''; в них все операции, такие как: поиск, вставка и удаление работают за <tex>O(1)</tex>.
−
−	Если мы поделим число хранимых элементов на размер массива <tex>H</tex> (число возможных значений хеш-функции), то узнаем коэффициент заполнения хеш-таблицы (англ. ''load factor''). От этого параметра зависит среднее время выполнения операций.
−
−	~~=== Хеширование ===~~
−	'''Хеширование''' (англ. ''hashing'') {{---}} класс методов поиска, идея которого состоит в вычислении хеш-кода, однозначно определяемого элементом с помощью хеш-функции, и использовании его, как основы для поиска (индексирование в памяти по хеш-коду выполняется за <tex>O(1)</tex>). В общем случае, однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем вариантов исходных данных, поэтому существуют элементы, имеющие одинаковые хеш-коды — так называемые коллизии, но если два элемента имеют разный хеш-код, то они гарантированно
−	различаются. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций. Для того чтобы коллизии не замедляли работу с таблицой существуют [[Разрешение коллизий\|методы для борьбы с ними]].
−
−	~~{{Определение~~
−	~~\|id=def1~~
−	\|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>.
−	При этом не гарантируется, что время выполнения отдельной операции мало́, так как при достижении некоторого значения коэффициента заполнения необходимо [[Перехеширование. Амортизационный анализ\|перехешировать]] таблицу: увеличить размер массива <tex>H</tex> и заново добавить в новую хеш-таблицу все пары.
−
−	~~===Хеширование в современных языках программирования===~~
−
−	~~Почти во всех современных языках присутствуют классы, реализующие хеширование. Рассмотрим некоторые из них.~~
−	*Java
−	**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. Позволяет просматривать значения в том порядке, в котором они были добавлены.
−	*C++
−	**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> {{---}} реализация интерфейса множества с использованием хеш-таблицы.
−
−	~~== Примечания ==~~
−	~~<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/Хеш-таблица Википедия {{---}} Хеш-таблица]
−
−	~~[[Категория:Дискретная математика и алгоритмы]]~~
−	~~[[Категория:Хеширование]]~~
−	~~[[Категория:Структуры данных]]~~

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

	=== Введение ===		=== Введение ===

@@ Строка 65: / Строка 65: @@
 * Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» {{---}} «Вильямс», 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 Википедия] {{---}} [http://ru.wikipedia.org/wiki/Хеш-таблица Хеш-таблица]
+* [http://ru.wikipedia.org/wiki/Хеш-таблица Википедия {{---}} Хеш-таблица]
 [[Категория:Дискретная математика и алгоритмы]]
 [[Категория:Хеширование]]
 [[Категория:Структуры данных]]