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

Patarakin: /* Разрешение коллизий */

2022-12-09T13:13:34Z

Разрешение коллизий

← Предыдущая версия		Версия от 16:13, 9 декабря 2022
Строка 51:		Строка 51:


	Ниже представлен код ([[С]]), демонстрирующий двойное хеширование:		Ниже представлен код ([[C]]), демонстрирующий двойное хеширование:

	<syntaxhighlight lang="c" line>		<syntaxhighlight lang="c" line>

Patarakin в 13:11, 9 декабря 2022

2022-12-09T13:11:54Z

← Предыдущая версия		Версия от 16:11, 9 декабря 2022
Строка 51:		Строка 51:


	Ниже представлен код, демонстрирующий двойное хеширование:		Ниже представлен код ([[С]]), демонстрирующий двойное хеширование:

	<syntaxhighlight lang="c" line>		<syntaxhighlight lang="c" line>

Patarakin в 07:52, 19 октября 2022

2022-10-19T07:52:41Z

← Предыдущая версия		Версия от 10:52, 19 октября 2022
Строка 53:		Строка 53:
	Ниже представлен код, демонстрирующий двойное хеширование:		Ниже представлен код, демонстрирующий двойное хеширование:

	<~~source~~ lang="c">		<syntaxhighlight lang="c" line>
	// DICT_CELL_COUNT должно быть простым числом!		// DICT_CELL_COUNT должно быть простым числом!
	#define DICT_CELL_COUNT 30011		#define DICT_CELL_COUNT 30011
Строка 116:		Строка 116:
	return uWordArSize++; // NB: инкремент!		return uWordArSize++; // NB: инкремент!
	} // unsigned int GetOrAddWordIdx( const char* const pcszWord )		} // unsigned int GetOrAddWordIdx( const char* const pcszWord )
	</~~source~~>		‎</syntaxhighlight>

	== См. также ==		== См. также ==

Patarakin в 07:49, 19 октября 2022

2022-10-19T07:49:33Z

← Предыдущая версия		Версия от 10:49, 19 октября 2022
Строка 1:		Строка 1:
	~~{{Структура_данных~~
	~~\|name=Hash table~~
	~~\|type=ассоциативный массив~~
	~~\|invented_year=1953~~
	~~\|space_avg=O(n)~~
	~~\|space_worst=O(n)~~
	~~\|search_avg=O(1)~~
	~~\|search_worst=O(n)~~
	~~\|insert_avg=O(1)~~
	~~\|insert_worst=O(n)~~
	~~\|delete_avg=O(1)~~
	~~\|delete_worst=O(n)~~
	}}

	'''Хеш-табли́ца''' — это [[структура данных]], реализующая интерфейс [[ассоциативный массив\|ассоциативного массива]], а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.		'''Хеш-табли́ца''' — это [[структура данных]], реализующая интерфейс [[ассоциативный массив\|ассоциативного массива]], а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.

Строка 21:		Строка 7:
	который хранится в соответствующей ячейке массива <math>H[i]</math>.		который хранится в соответствующей ячейке массива <math>H[i]</math>.

	Ситуация, когда для различных ключей получается одно и то же хеш-значение, называется [[Коллизия хеш-функции\|коллизией]]. Такие события не так уж и редки — например, при вставке в хеш-таблицу размером 365 ячеек всего лишь 23 элементов вероятность коллизии уже превысит 50% (если каждый элемент может равновероятно попасть в любую ячейку) ~~— см. [[парадокс дней рождения]]~~. Поэтому механизм разрешения коллизий — важная составляющая любой хеш-таблицы.		Ситуация, когда для различных ключей получается одно и то же хеш-значение, называется [[Коллизия хеш-функции\|коллизией]]. Такие события не так уж и редки — например, при вставке в хеш-таблицу размером 365 ячеек всего лишь 23 элементов вероятность коллизии уже превысит 50% (если каждый элемент может равновероятно попасть в любую ячейку). Поэтому механизм разрешения коллизий — важная составляющая любой хеш-таблицы.

	В некоторых специальных случаях удаётся избежать коллизий вообще. Например, если все ключи элементов известны заранее (или очень редко меняются), то для них можно найти некоторую [[Хеширование#Идеальное хеширование\|совершенную хеш-функцию]], которая распределит их по ячейкам хеш-таблицы без коллизий. Хеш-таблицы, использующие подобные хеш-функции, не нуждаются в механизме разрешения коллизий, и называются хеш-таблицами с ''прямой адресацией''.		В некоторых специальных случаях удаётся избежать коллизий вообще. Например, если все ключи элементов известны заранее (или очень редко меняются), то для них можно найти некоторую [[Хеширование#Идеальное хеширование\|совершенную хеш-функцию]], которая распределит их по ячейкам хеш-таблицы без коллизий. Хеш-таблицы, использующие подобные хеш-функции, не нуждаются в механизме разрешения коллизий, и называются хеш-таблицами с ''прямой адресацией''.
Строка 39:		Строка 25:

	=== Метод цепочек ===		=== Метод цепочек ===
	~~[[Файл:Hash table 5 0 1 1 1 1 1 LL.svg\|thumb\|380px\|right\|Разрешение коллизий при помощи цепочек.]]~~
	Каждая ячейка массива ''H'' является указателем на [[связный список]] (цепочку) пар ключ-значение, соответствующих одному и тому же хеш-значению ключа. Коллизии просто приводят к тому, что появляются цепочки длиной более одного элемента.		Каждая ячейка массива ''H'' является указателем на [[связный список]] (цепочку) пар ключ-значение, соответствующих одному и тому же хеш-значению ключа. Коллизии просто приводят к тому, что появляются цепочки длиной более одного элемента.

Строка 47:		Строка 32:

	=== Открытая адресация ===		=== Открытая адресация ===
	[[Файл:Hash table 5 0 1 1 1 1 0 SP.svg\|thumb\|380px\|right\|Пример хеш-таблицы с открытой адресацией и линейным пробированием, получающейся при вставке элементов в левой колонке сверху вниз.]]
	В массиве ''H'' хранятся сами пары ключ-значение. Алгоритм вставки элемента проверяет ячейки массива ''H'' в некотором порядке до тех пор, пока не будет найдена первая свободная ячейка, в которую и будет записан новый элемент. Этот порядок вычисляется на лету, что позволяет сэкономить на памяти для указателей, требующихся в хеш-таблицах с цепочками.		В массиве ''H'' хранятся сами пары ключ-значение. Алгоритм вставки элемента проверяет ячейки массива ''H'' в некотором порядке до тех пор, пока не будет найдена первая свободная ячейка, в которую и будет записан новый элемент. Этот порядок вычисляется на лету, что позволяет сэкономить на памяти для указателей, требующихся в хеш-таблицах с цепочками.

Строка 65:		Строка 50:
	* [[Двойное хеширование]]: интервал между ячейками фиксирован, как при линейном пробировании, но, в отличие от него, размер интервала вычисляется второй, вспомогательной хеш-функцией, а значит, может быть различным для разных ключей. Значения этой хеш-функции должны быть ненулевыми и взаимно-простыми с размером хеш-таблицы, что проще всего достичь, взяв [[простое число]] в качестве размера, и потребовав, чтобы вспомогательная хеш-функция принимала значения от 1 до ''N'' — 1.		* [[Двойное хеширование]]: интервал между ячейками фиксирован, как при линейном пробировании, но, в отличие от него, размер интервала вычисляется второй, вспомогательной хеш-функцией, а значит, может быть различным для разных ключей. Значения этой хеш-функции должны быть ненулевыми и взаимно-простыми с размером хеш-таблицы, что проще всего достичь, взяв [[простое число]] в качестве размера, и потребовав, чтобы вспомогательная хеш-функция принимала значения от 1 до ''N'' — 1.

	<!-- TODO: достоинства и недостатки приведенных схем — у линейного пробирования есть эффект скучивания, а двойное хеширование плохо сочетается с хеш-памятью -->
	~~<!-- TODO: анализ сложность операции поиска в хеш-таблице с открытой адресацией -->~~

	Ниже представлен код, демонстрирующий двойное хеширование:		Ниже представлен код, демонстрирующий двойное хеширование:
	~~{{Скрытый~~
	~~\|Рамка = 1px dashed #2f6fab~~
	~~\|Заголовок = Реализация на C~~
	~~\|Содержание =~~
	<source lang="c">		<source lang="c">
	// DICT_CELL_COUNT должно быть простым числом!		// DICT_CELL_COUNT должно быть простым числом!
Строка 136:		Строка 116:
	return uWordArSize++; // NB: инкремент!		return uWordArSize++; // NB: инкремент!
	} // unsigned int GetOrAddWordIdx( const char* const pcszWord )		} // unsigned int GetOrAddWordIdx( const char* const pcszWord )
	</source>}}		</source>

	== См. также ==		== См. также ==
Строка 142:		Строка 122:
	* [[Фильтр Блума]]		* [[Фильтр Блума]]

	~~== Литература ==~~
	* {{Книга:CLRS\|2005\|часть='''Глава 11. Хеш-таблицы.'''}}

	~~{{Структуры данных}}~~

	~~[[Категория:Хеширование]]~~
	[[Категория:Структуры данных]]		[[Категория:Структуры данных]]
	~~[[Категория:Статьи с примерами кода Си]]~~

Patarakin: 1 версия импортирована

2022-10-19T07:30:50Z

1 версия импортирована

← Предыдущая версия	Версия от 10:30, 19 октября 2022
(нет различий)

185.97.201.72: /* Открытая адресация */

2021-02-07T09:54:27Z

Открытая адресация

Новая страница

{{Структура_данных
|name=Hash table
|type=ассоциативный массив
|invented_year=1953
|space_avg=O(n)
|space_worst=O(n)
|search_avg=O(1)
|search_worst=O(n)
|insert_avg=O(1)
|insert_worst=O(n)
|delete_avg=O(1)
|delete_worst=O(n)
}}

'''Хеш-табли́ца''' — это [[структура данных]], реализующая интерфейс [[ассоциативный массив|ассоциативного массива]], а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.

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

Выполнение операции в хеш-таблице начинается с вычисления [[Хеш-функция|хеш-функции]] от ключа. Получающееся хеш-значение <math>i = \mbox{hash}(key)</math> играет роль индекса в массиве <math>H</math>. Затем выполняемая операция (добавление, удаление или поиск) перенаправляется объекту,
который хранится в соответствующей ячейке массива <math>H[i]</math>.

Ситуация, когда для различных ключей получается одно и то же хеш-значение, называется [[Коллизия хеш-функции|коллизией]]. Такие события не так уж и редки — например, при вставке в хеш-таблицу размером 365 ячеек всего лишь 23 элементов вероятность коллизии уже превысит 50% (если каждый элемент может равновероятно попасть в любую ячейку) — см. [[парадокс дней рождения]]. Поэтому механизм разрешения коллизий — важная составляющая любой хеш-таблицы.

В некоторых специальных случаях удаётся избежать коллизий вообще. Например, если все ключи элементов известны заранее (или очень редко меняются), то для них можно найти некоторую [[Хеширование#Идеальное хеширование|совершенную хеш-функцию]], которая распределит их по ячейкам хеш-таблицы без коллизий. Хеш-таблицы, использующие подобные хеш-функции, не нуждаются в механизме разрешения коллизий, и называются хеш-таблицами с ''прямой адресацией''.

Число хранимых элементов, делённое на размер массива <math>H</math> (число возможных значений хеш-функции), называется '''коэффициентом заполнения хеш-таблицы''' (load factor) и является важным параметром, от которого зависит среднее время выполнения операций.

== Свойства хеш-таблицы ==

Важное свойство хеш-таблиц состоит в том, что, при некоторых разумных допущениях, все три операции (поиск, вставка, удаление элементов) в среднем выполняются за время <math>O(1)</math>.
Но при этом не гарантируется, что время выполнения отдельной операции мало́.
Это связано с тем, что при достижении некоторого значения коэффициента заполнения
необходимо осуществлять перестройку индекса хеш-таблицы: увеличить значение размера массива <math>H</math> и заново добавить в пустую хеш-таблицу все пары.

== Разрешение коллизий ==

Существует несколько способов разрешения [[Коллизия хеш-функции|коллизий]].

=== Метод цепочек ===
[[Файл:Hash table 5 0 1 1 1 1 1 LL.svg|thumb|380px|right|Разрешение коллизий при помощи цепочек.]]
Каждая ячейка массива ''H'' является указателем на [[связный список]] (цепочку) пар ключ-значение, соответствующих одному и тому же хеш-значению ключа. Коллизии просто приводят к тому, что появляются цепочки длиной более одного элемента.

Операции поиска или удаления элемента требуют просмотра всех элементов соответствующей ему цепочки, чтобы найти в ней элемент с заданным ключом. Для добавления элемента нужно добавить элемент в конец или начало соответствующего списка и в случае, если коэффициент заполнения станет слишком велик, увеличить размер массива ''H'' и перестроить таблицу.

При предположении, что каждый элемент может попасть в любую позицию таблицы ''H'' с равной вероятностью и независимо от того, куда попал любой другой элемент, среднее [[Сложность алгоритма|время работы]] операции поиска элемента составляет [[О-нотация|Θ]](1 + ''α''), где ''α'' — коэффициент заполнения таблицы.

=== Открытая адресация ===
[[Файл:Hash table 5 0 1 1 1 1 0 SP.svg|thumb|380px|right|Пример хеш-таблицы с открытой адресацией и линейным пробированием, получающейся при вставке элементов в левой колонке сверху вниз.]]
В массиве ''H'' хранятся сами пары ключ-значение. Алгоритм вставки элемента проверяет ячейки массива ''H'' в некотором порядке до тех пор, пока не будет найдена первая свободная ячейка, в которую и будет записан новый элемент. Этот порядок вычисляется на лету, что позволяет сэкономить на памяти для указателей, требующихся в хеш-таблицах с цепочками.

Последовательность, в которой просматриваются ячейки хеш-таблицы, называется '''последовательностью проб'''. В общем случае, она зависит только от ключа элемента, то есть это последовательность ''h''0(''x''), ''h''1(''x''), …, ''h''''n'' — 1(''x''), где ''x'' — ключ элемента, а ''h''''i''(''x'') — произвольные функции, сопоставляющие каждому ключу ячейку в хеш-таблице. Первый элемент в последовательности, как правило, равен значению некоторой хеш-функции от ключа, а остальные считаются от него одним из приведённых ниже способов. Для успешной работы алгоритмов поиска последовательность проб должна быть такой, чтобы все ячейки хеш-таблицы оказались просмотренными ровно по одному разу.

Алгоритм поиска просматривает ячейки хеш-таблицы в том же самом порядке, что и при вставке, до тех пор, пока не найдется либо элемент с искомым ключом, либо свободная ячейка (что означает отсутствие элемента в хеш-таблице).

Удаление элементов в такой схеме несколько затруднено. Обычно поступают так: заводят булевый флаг для каждой ячейки, помечающий, удален элемент в ней или нет. Тогда удаление элемента состоит в установке этого флага для соответствующей ячейки хеш-таблицы, но при этом необходимо модифицировать процедуру поиска существующего элемента так, чтобы она считала удалённые ячейки занятыми, а процедуру добавления — чтобы она их считала свободными и сбрасывала значение флага при добавлении.

'''Последовательности проб'''

Ниже приведены некоторые распространенные типы последовательностей проб. Сразу оговорим, что нумерация элементов последовательности проб и ячеек хеш-таблицы ведётся от нуля, а ''N'' — размер хеш-таблицы (и, как замечено выше, также и длина последовательности проб).

* [[Линейное_зондирование|Линейное пробирование]]: ячейки хеш-таблицы последовательно просматриваются с некоторым фиксированным интервалом ''k'' между ячейками (обычно ''k'' = 1), то есть ''i''-й элемент последовательности проб — это ячейка с номером (hash(''x'') + ''ik'') mod ''N''. Для того, чтобы все ячейки оказались просмотренными по одному разу, необходимо, чтобы ''k'' было [[Взаимная простота|взаимно-простым]] с размером хеш-таблицы.
* [[Квадратичное пробирование]]: интервал между ячейками с каждым шагом увеличивается на константу. Если размер хеш-таблицы равен степени двойки (''N'' = 2''p''), то одним из примеров последовательности, при которой каждый элемент будет просмотрен по одному разу, является:
*: hash(''x'') mod ''N'', (hash(''x'') + (1+1*1)/2) mod ''N'', (hash(''x'') + (2+2*2)/2) mod ''N'', (hash(''x'') + (3+3*3)/2) mod ''N'', … - [[треугольные числа]].
* [[Двойное хеширование]]: интервал между ячейками фиксирован, как при линейном пробировании, но, в отличие от него, размер интервала вычисляется второй, вспомогательной хеш-функцией, а значит, может быть различным для разных ключей. Значения этой хеш-функции должны быть ненулевыми и взаимно-простыми с размером хеш-таблицы, что проще всего достичь, взяв [[простое число]] в качестве размера, и потребовав, чтобы вспомогательная хеш-функция принимала значения от 1 до ''N'' — 1.




Ниже представлен код, демонстрирующий двойное хеширование:
{{Скрытый
|Рамка = 1px dashed #2f6fab
|Заголовок = Реализация на C
|Содержание =
<source lang="c">
// DICT_CELL_COUNT должно быть простым числом!
#define DICT_CELL_COUNT 30011

char* szWordAr[ DICT_CELL_COUNT ];
unsigned int uWordArSize = 0;

#define WORD_IDX_BAD (( unsigned int )-1)

unsigned int uWordIdxByHashAr[ DICT_CELL_COUNT ]; // необходимо инициализировать элементы значением WORD_IDX_BAD

#define STRIDE_1 17
#define STRIDE_2 13

// Функция GetOrAddWordIdx( .. ) возвращает индекс слова pcszWord в массиве szWordAr.
// При этом происходит добавление слова pcszWord в словарь szWordAr, если его там нет.

unsigned int GetOrAddWordIdx( const char* const pcszWord )
{
unsigned int uHash1 = 0, uHash2 = 0;

const unsigned char* cbtWordCharCur = ( const unsigned char* )pcszWord;

// Вычислим два хеша слова pcszWord:
// uHash1 лежит в диапазоне [ 0 .. DICT_CELL_COUNT - 1 ]
// uHash2 лежит в диапазоне [ 1 .. DICT_CELL_COUNT - 1 ]

do
{
uHash1 *= STRIDE_1; uHash1 += ( STRIDE_2 * *cbtWordCharCur );
uHash2 *= STRIDE_2; uHash2 += ( STRIDE_1 * *cbtWordCharCur );
}
while( *( cbtWordCharCur++ ) ); // NB: инкремент!

// #1: cbtWordCharCur указывает на символ за посл. '\0' в pcszWord,
// будет использовано в #2

uHash1 %= DICT_CELL_COUNT;
uHash2 %= ( DICT_CELL_COUNT - 1 ); ++uHash2;

while( uWordIdxByHashAr[ uHash1 ] != WORD_IDX_BAD )
{
if ( !strcmp( pcszWord, szWordAr[ uWordIdxByHashAr[ uHash1 ] ] ) )
return uWordIdxByHashAr[ uHash1 ];

uHash1 += uHash2; uHash1 %= DICT_CELL_COUNT;
}

strcpy(
szWordAr[
uWordIdxByHashAr[ uHash1 ] = // NB: присвоение!
uWordArSize
] = // NB: присвоение!
( char* )malloc(
// длина pcszWord плюс 1:
( const char* )cbtWordCharCur - // #2: используем значение cbtWordCharCur из #1
pcszWord
),
pcszWord
);

return uWordArSize++; // NB: инкремент!
} // unsigned int GetOrAddWordIdx( const char* const pcszWord )
</source>}}

== См. также ==
* [[Ассоциативный массив]]
* [[Фильтр Блума]]

== Литература ==
* {{Книга:CLRS|2005|часть='''Глава 11. Хеш-таблицы.'''}}

{{Структуры данных}}

[[Категория:Хеширование]]
[[Категория:Структуры данных]]
[[Категория:Статьи с примерами кода Си]]