<?xml version="1.0"?>
<feed xmlns="http://www.w3.org/2005/Atom" xml:lang="ru">
	<id>http://digida.mgpu.ru/api.php?action=feedcontributions&amp;feedformat=atom&amp;user=185.97.201.72</id>
	<title>Поле цифровой дидактики - Вклад [ru]</title>
	<link rel="self" type="application/atom+xml" href="http://digida.mgpu.ru/api.php?action=feedcontributions&amp;feedformat=atom&amp;user=185.97.201.72"/>
	<link rel="alternate" type="text/html" href="http://digida.mgpu.ru/index.php?title=%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%92%D0%BA%D0%BB%D0%B0%D0%B4/185.97.201.72"/>
	<updated>2026-11-16T04:55:22Z</updated>
	<subtitle>Вклад</subtitle>
	<generator>MediaWiki 1.46.0</generator>
	<entry>
		<id>http://digida.mgpu.ru/index.php?title=%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0&amp;diff=4536</id>
		<title>Хеш-таблица</title>
		<link rel="alternate" type="text/html" href="http://digida.mgpu.ru/index.php?title=%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0&amp;diff=4536"/>
		<updated>2021-02-07T09:54:27Z</updated>

		<summary type="html">&lt;p&gt;185.97.201.72: /* Открытая адресация */&lt;/p&gt;
&lt;hr /&gt;
&lt;div&gt;{{Структура_данных&lt;br /&gt;
|name=Hash table&lt;br /&gt;
|type=ассоциативный массив&lt;br /&gt;
|invented_year=1953&lt;br /&gt;
|space_avg=O(n)&lt;br /&gt;
|space_worst=O(n)&lt;br /&gt;
|search_avg=O(1)&lt;br /&gt;
|search_worst=O(n)&lt;br /&gt;
|insert_avg=O(1)&lt;br /&gt;
|insert_worst=O(n)&lt;br /&gt;
|delete_avg=O(1)&lt;br /&gt;
|delete_worst=O(n)&lt;br /&gt;
}}&lt;br /&gt;
&lt;br /&gt;
&#039;&#039;&#039;Хеш-табли́ца&#039;&#039;&#039; — это [[структура данных]], реализующая интерфейс [[ассоциативный массив|ассоциативного массива]], а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.&lt;br /&gt;
&lt;br /&gt;
== Введение ==&lt;br /&gt;
Существуют два основных варианта хеш-таблиц: с цепочками и открытой адресацией. Хеш-таблица содержит некоторый [[массив (программирование)|массив]] &amp;lt;math&amp;gt;H&amp;lt;/math&amp;gt;, элементы которого есть пары (хеш-таблица с открытой адресацией) или списки пар (хеш-таблица с цепочками).&lt;br /&gt;
&lt;br /&gt;
Выполнение операции в хеш-таблице начинается с вычисления [[Хеш-функция|хеш-функции]] от ключа. Получающееся хеш-значение &amp;lt;math&amp;gt;i = \mbox{hash}(key)&amp;lt;/math&amp;gt; играет роль индекса в массиве &amp;lt;math&amp;gt;H&amp;lt;/math&amp;gt;. Затем выполняемая операция (добавление, удаление или поиск) перенаправляется объекту,&lt;br /&gt;
который хранится в соответствующей ячейке массива &amp;lt;math&amp;gt;H[i]&amp;lt;/math&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
Ситуация, когда для различных ключей получается одно и то же хеш-значение, называется [[Коллизия хеш-функции|коллизией]]. Такие события не так уж и редки — например, при вставке в хеш-таблицу размером 365 ячеек всего лишь 23 элементов вероятность коллизии уже превысит 50% (если каждый элемент может равновероятно попасть в любую ячейку) — см. [[парадокс дней рождения]]. Поэтому механизм разрешения коллизий — важная составляющая любой хеш-таблицы.&lt;br /&gt;
&lt;br /&gt;
В некоторых специальных случаях удаётся избежать коллизий вообще. Например, если все ключи элементов известны заранее (или очень редко меняются), то для них можно найти некоторую [[Хеширование#Идеальное хеширование|совершенную хеш-функцию]], которая распределит их по ячейкам хеш-таблицы без коллизий. Хеш-таблицы, использующие подобные хеш-функции, не нуждаются в механизме разрешения коллизий, и называются хеш-таблицами с &#039;&#039;прямой адресацией&#039;&#039;.&lt;br /&gt;
&lt;br /&gt;
Число хранимых элементов, делённое на размер массива &amp;lt;math&amp;gt;H&amp;lt;/math&amp;gt; (число возможных значений хеш-функции), называется &#039;&#039;&#039;коэффициентом заполнения хеш-таблицы&#039;&#039;&#039; (load factor) и является важным параметром, от которого зависит среднее время выполнения операций.&lt;br /&gt;
&lt;br /&gt;
== Свойства хеш-таблицы ==&lt;br /&gt;
&lt;br /&gt;
Важное свойство хеш-таблиц состоит в том, что, при некоторых разумных допущениях, все три операции (поиск, вставка, удаление элементов) в среднем выполняются за время &amp;lt;math&amp;gt;O(1)&amp;lt;/math&amp;gt;.&lt;br /&gt;
Но при этом не гарантируется, что время выполнения отдельной операции мало́.&lt;br /&gt;
Это связано с тем, что при достижении некоторого значения коэффициента заполнения&lt;br /&gt;
необходимо осуществлять перестройку индекса хеш-таблицы: увеличить значение размера массива &amp;lt;math&amp;gt;H&amp;lt;/math&amp;gt; и заново добавить в пустую хеш-таблицу все пары.&lt;br /&gt;
&lt;br /&gt;
== Разрешение коллизий ==&lt;br /&gt;
&lt;br /&gt;
Существует несколько способов разрешения [[Коллизия хеш-функции|коллизий]].&lt;br /&gt;
&lt;br /&gt;
=== Метод цепочек ===&lt;br /&gt;
[[Файл:Hash table 5 0 1 1 1 1 1 LL.svg|thumb|380px|right|Разрешение коллизий при помощи цепочек.]]&lt;br /&gt;
Каждая ячейка массива &#039;&#039;H&#039;&#039; является указателем на [[связный список]] (цепочку) пар ключ-значение, соответствующих одному и тому же хеш-значению ключа. Коллизии просто приводят к тому, что появляются цепочки длиной более одного элемента.&lt;br /&gt;
&lt;br /&gt;
Операции поиска или удаления элемента требуют просмотра всех элементов соответствующей ему цепочки, чтобы найти в ней элемент с заданным ключом. Для добавления элемента нужно добавить элемент в конец или начало соответствующего списка и в случае, если коэффициент заполнения станет слишком велик, увеличить размер массива &#039;&#039;H&#039;&#039; и перестроить таблицу.&lt;br /&gt;
&lt;br /&gt;
При предположении, что каждый элемент может попасть в любую позицию таблицы &#039;&#039;H&#039;&#039; с равной вероятностью и независимо от того, куда попал любой другой элемент, среднее [[Сложность алгоритма|время работы]] операции поиска элемента составляет [[О-нотация|Θ]](1 + &#039;&#039;α&#039;&#039;), где &#039;&#039;α&#039;&#039; — коэффициент заполнения таблицы.&lt;br /&gt;
&lt;br /&gt;
=== Открытая адресация ===&lt;br /&gt;
[[Файл:Hash table 5 0 1 1 1 1 0 SP.svg|thumb|380px|right|Пример хеш-таблицы с открытой адресацией и линейным пробированием, получающейся при вставке элементов в левой колонке сверху вниз.]]&lt;br /&gt;
В массиве &#039;&#039;H&#039;&#039; хранятся сами пары ключ-значение. Алгоритм вставки элемента проверяет ячейки массива &#039;&#039;H&#039;&#039; в некотором порядке до тех пор, пока не будет найдена первая свободная ячейка, в которую и будет записан новый элемент. Этот порядок вычисляется на лету, что позволяет сэкономить на памяти для указателей, требующихся в хеш-таблицах с цепочками.&lt;br /&gt;
&lt;br /&gt;
Последовательность, в которой просматриваются ячейки хеш-таблицы, называется &#039;&#039;&#039;последовательностью проб&#039;&#039;&#039;. В общем случае, она зависит только от ключа элемента, то есть это последовательность &#039;&#039;h&#039;&#039;&amp;lt;sub&amp;gt;0&amp;lt;/sub&amp;gt;(&#039;&#039;x&#039;&#039;), &#039;&#039;h&#039;&#039;&amp;lt;sub&amp;gt;1&amp;lt;/sub&amp;gt;(&#039;&#039;x&#039;&#039;), …, &#039;&#039;h&#039;&#039;&amp;lt;sub&amp;gt;&#039;&#039;n&#039;&#039; — 1&amp;lt;/sub&amp;gt;(&#039;&#039;x&#039;&#039;), где &#039;&#039;x&#039;&#039; — ключ элемента, а &#039;&#039;h&#039;&#039;&amp;lt;sub&amp;gt;&#039;&#039;i&#039;&#039;&amp;lt;/sub&amp;gt;(&#039;&#039;x&#039;&#039;) — произвольные функции, сопоставляющие каждому ключу ячейку в хеш-таблице. Первый элемент в последовательности, как правило, равен значению некоторой хеш-функции от ключа, а остальные считаются от него одним из приведённых ниже способов. Для успешной работы алгоритмов поиска последовательность проб должна быть такой, чтобы все ячейки хеш-таблицы оказались просмотренными ровно по одному разу.&lt;br /&gt;
&lt;br /&gt;
Алгоритм поиска просматривает ячейки хеш-таблицы в том же самом порядке, что и при вставке, до тех пор, пока не найдется либо элемент с искомым ключом, либо свободная ячейка (что означает отсутствие элемента в хеш-таблице).&lt;br /&gt;
&lt;br /&gt;
Удаление элементов в такой схеме несколько затруднено. Обычно поступают так: заводят булевый флаг для каждой ячейки, помечающий, удален элемент в ней или нет. Тогда удаление элемента состоит в установке этого флага для соответствующей ячейки хеш-таблицы, но при этом необходимо модифицировать процедуру поиска существующего элемента так, чтобы она считала удалённые ячейки занятыми, а процедуру добавления — чтобы она их считала свободными и сбрасывала значение флага при добавлении.&lt;br /&gt;
&lt;br /&gt;
&#039;&#039;&#039;Последовательности проб&#039;&#039;&#039;&lt;br /&gt;
&lt;br /&gt;
Ниже приведены некоторые распространенные типы последовательностей проб. Сразу оговорим, что нумерация элементов последовательности проб и ячеек хеш-таблицы ведётся от нуля, а &#039;&#039;N&#039;&#039; — размер хеш-таблицы (и, как замечено выше, также и длина последовательности проб).&lt;br /&gt;
&lt;br /&gt;
* [[Линейное_зондирование|Линейное пробирование]]: ячейки хеш-таблицы последовательно просматриваются с некоторым фиксированным интервалом &#039;&#039;k&#039;&#039; между ячейками (обычно &#039;&#039;k&#039;&#039; = 1), то есть &#039;&#039;i&#039;&#039;-й элемент последовательности проб — это ячейка с номером (hash(&#039;&#039;x&#039;&#039;)&amp;amp;nbsp;+&amp;amp;nbsp;&#039;&#039;ik&#039;&#039;)&amp;amp;nbsp;mod&amp;amp;nbsp;&#039;&#039;N&#039;&#039;. Для того, чтобы все ячейки оказались просмотренными по одному разу, необходимо, чтобы &#039;&#039;k&#039;&#039; было [[Взаимная простота|взаимно-простым]] с размером хеш-таблицы.&lt;br /&gt;
* [[Квадратичное пробирование]]: интервал между ячейками с каждым шагом увеличивается на константу. Если размер хеш-таблицы равен степени двойки (&#039;&#039;N&#039;&#039; = 2&amp;lt;sup&amp;gt;&#039;&#039;p&#039;&#039;&amp;lt;/sup&amp;gt;), то одним из примеров последовательности, при которой каждый элемент будет просмотрен по одному разу, является:&lt;br /&gt;
*: hash(&#039;&#039;x&#039;&#039;) mod &#039;&#039;N&#039;&#039;, (hash(&#039;&#039;x&#039;&#039;) + (1+1*1)/2) mod &#039;&#039;N&#039;&#039;, (hash(&#039;&#039;x&#039;&#039;) + (2+2*2)/2) mod &#039;&#039;N&#039;&#039;, (hash(&#039;&#039;x&#039;&#039;) + (3+3*3)/2) mod &#039;&#039;N&#039;&#039;, … - [[треугольные числа]].&lt;br /&gt;
* [[Двойное хеширование]]: интервал между ячейками фиксирован, как при линейном пробировании, но, в отличие от него, размер интервала вычисляется второй, вспомогательной хеш-функцией, а значит, может быть различным для разных ключей. Значения этой хеш-функции должны быть ненулевыми и взаимно-простыми с размером хеш-таблицы, что проще всего достичь, взяв [[простое число]] в качестве размера, и потребовав, чтобы вспомогательная хеш-функция принимала значения от 1 до &#039;&#039;N&#039;&#039; — 1.&lt;br /&gt;
&lt;br /&gt;
&amp;lt;!-- TODO: достоинства и недостатки приведенных схем — у линейного пробирования есть эффект скучивания, а двойное хеширование плохо сочетается с хеш-памятью --&amp;gt;&lt;br /&gt;
&amp;lt;!-- TODO: анализ сложность операции поиска в хеш-таблице с открытой адресацией --&amp;gt;&lt;br /&gt;
&lt;br /&gt;
Ниже представлен код, демонстрирующий двойное хеширование:&lt;br /&gt;
{{Скрытый&lt;br /&gt;
|Рамка = 1px dashed #2f6fab&lt;br /&gt;
|Заголовок = Реализация на C&lt;br /&gt;
|Содержание =&lt;br /&gt;
&amp;lt;source lang=&amp;quot;c&amp;quot;&amp;gt;&lt;br /&gt;
// DICT_CELL_COUNT должно быть простым числом!&lt;br /&gt;
#define DICT_CELL_COUNT 30011&lt;br /&gt;
&lt;br /&gt;
char* szWordAr[ DICT_CELL_COUNT ];&lt;br /&gt;
unsigned int uWordArSize = 0;&lt;br /&gt;
&lt;br /&gt;
#define WORD_IDX_BAD (( unsigned int )-1)&lt;br /&gt;
&lt;br /&gt;
unsigned int uWordIdxByHashAr[ DICT_CELL_COUNT ]; // необходимо инициализировать элементы значением WORD_IDX_BAD&lt;br /&gt;
&lt;br /&gt;
#define STRIDE_1 17&lt;br /&gt;
#define STRIDE_2 13&lt;br /&gt;
&lt;br /&gt;
// Функция GetOrAddWordIdx( .. ) возвращает индекс слова pcszWord в массиве szWordAr.&lt;br /&gt;
// При этом происходит добавление слова pcszWord в словарь szWordAr, если его там нет.&lt;br /&gt;
&lt;br /&gt;
unsigned int GetOrAddWordIdx( const char* const pcszWord )&lt;br /&gt;
  {&lt;br /&gt;
    unsigned int uHash1 = 0, uHash2 = 0;&lt;br /&gt;
&lt;br /&gt;
    const unsigned char* cbtWordCharCur = ( const unsigned char* )pcszWord;&lt;br /&gt;
&lt;br /&gt;
    // Вычислим два хеша слова pcszWord:&lt;br /&gt;
    // uHash1 лежит в диапазоне [ 0 .. DICT_CELL_COUNT - 1 ]&lt;br /&gt;
    // uHash2 лежит в диапазоне [ 1 .. DICT_CELL_COUNT - 1 ]&lt;br /&gt;
&lt;br /&gt;
    do&lt;br /&gt;
      {&lt;br /&gt;
        uHash1 *= STRIDE_1; uHash1 += ( STRIDE_2 * *cbtWordCharCur );&lt;br /&gt;
        uHash2 *= STRIDE_2; uHash2 += ( STRIDE_1 * *cbtWordCharCur );&lt;br /&gt;
      }&lt;br /&gt;
    while( *( cbtWordCharCur++ ) ); // NB: инкремент!&lt;br /&gt;
&lt;br /&gt;
    // #1: cbtWordCharCur указывает на символ за посл. &#039;\0&#039; в pcszWord,&lt;br /&gt;
    // будет использовано в #2&lt;br /&gt;
&lt;br /&gt;
    uHash1 %= DICT_CELL_COUNT;&lt;br /&gt;
    uHash2 %= ( DICT_CELL_COUNT - 1 ); ++uHash2;&lt;br /&gt;
&lt;br /&gt;
    while( uWordIdxByHashAr[ uHash1 ] != WORD_IDX_BAD  )&lt;br /&gt;
      {&lt;br /&gt;
        if ( !strcmp( pcszWord, szWordAr[ uWordIdxByHashAr[ uHash1 ] ] ) )&lt;br /&gt;
          return uWordIdxByHashAr[ uHash1 ];&lt;br /&gt;
&lt;br /&gt;
        uHash1 += uHash2; uHash1 %= DICT_CELL_COUNT;&lt;br /&gt;
      }&lt;br /&gt;
&lt;br /&gt;
    strcpy(&lt;br /&gt;
      szWordAr[&lt;br /&gt;
        uWordIdxByHashAr[ uHash1 ] = // NB: присвоение!&lt;br /&gt;
          uWordArSize&lt;br /&gt;
      ] = // NB: присвоение!&lt;br /&gt;
        ( char* )malloc(&lt;br /&gt;
          // длина pcszWord плюс 1:&lt;br /&gt;
          ( const char* )cbtWordCharCur - // #2: используем значение cbtWordCharCur из #1&lt;br /&gt;
            pcszWord&lt;br /&gt;
        ),&lt;br /&gt;
      pcszWord&lt;br /&gt;
    );&lt;br /&gt;
&lt;br /&gt;
    return uWordArSize++; // NB: инкремент!&lt;br /&gt;
  } // unsigned int GetOrAddWordIdx( const char* const pcszWord )&lt;br /&gt;
&amp;lt;/source&amp;gt;}}&lt;br /&gt;
&lt;br /&gt;
== См. также ==&lt;br /&gt;
* [[Ассоциативный массив]]&lt;br /&gt;
* [[Фильтр Блума]]&lt;br /&gt;
&lt;br /&gt;
== Литература ==&lt;br /&gt;
* {{Книга:CLRS|2005|часть=&#039;&#039;&#039;Глава 11. Хеш-таблицы.&#039;&#039;&#039;}}&lt;br /&gt;
&lt;br /&gt;
{{Структуры данных}}&lt;br /&gt;
&lt;br /&gt;
[[Категория:Хеширование]]&lt;br /&gt;
[[Категория:Структуры данных]]&lt;br /&gt;
[[Категория:Статьи с примерами кода Си]]&lt;/div&gt;</summary>
		<author><name>185.97.201.72</name></author>
	</entry>
</feed>