Хеш-таблица

Hash table
Тип	ассоциативный массив
Изобретено в	1953 году
Временная сложность в О-символике
	В среднем	В худшем случае
Расход памяти	O(n)	O(n)
Поиск	O(1)	O(n)
Вставка	O(1)	O(n)
Удаление	O(1)	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> и заново добавить в пустую хеш-таблицу все пары.

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

Существует несколько способов разрешения коллизий.

Метод цепочек

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

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

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

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

В массиве H хранятся сами пары ключ-значение. Алгоритм вставки элемента проверяет ячейки массива H в некотором порядке до тех пор, пока не будет найдена первая свободная ячейка, в которую и будет записан новый элемент. Этот порядок вычисляется на лету, что позволяет сэкономить на памяти для указателей, требующихся в хеш-таблицах с цепочками.

Последовательность, в которой просматриваются ячейки хеш-таблицы, называется последовательностью проб. В общем случае, она зависит только от ключа элемента, то есть это последовательность h₀(x), h₁(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) mod N, (hash(x) + 3) mod N, (hash(x) + 6) mod N, …

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

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

Реализация на 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 )

См. также

• Ассоциативный массив
• Фильтр Блума

Литература

• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 11. Хеш-таблицы. // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.

Отрывок, характеризующий Хеш-таблица

– Берись, – шепнул Герасим дворнику.
Макара Алексеича схватили за руки и потащили к двери.
Сени наполнились безобразными звуками возни и пьяными хрипящими звуками запыхавшегося голоса.
Вдруг новый, пронзительный женский крик раздался от крыльца, и кухарка вбежала в сени.
– Они! Батюшки родимые!.. Ей богу, они. Четверо, конные!.. – кричала она.
Герасим и дворник выпустили из рук Макар Алексеича, и в затихшем коридоре ясно послышался стук нескольких рук во входную дверь.


Пьер, решивший сам с собою, что ему до исполнения своего намерения не надо было открывать ни своего звания, ни знания французского языка, стоял в полураскрытых дверях коридора, намереваясь тотчас же скрыться, как скоро войдут французы. Но французы вошли, и Пьер все не отходил от двери: непреодолимое любопытство удерживало его.
Их было двое. Один – офицер, высокий, бравый и красивый мужчина, другой – очевидно, солдат или денщик, приземистый, худой загорелый человек с ввалившимися щеками и тупым выражением лица. Офицер, опираясь на палку и прихрамывая, шел впереди. Сделав несколько шагов, офицер, как бы решив сам с собою, что квартира эта хороша, остановился, обернулся назад к стоявшим в дверях солдатам и громким начальническим голосом крикнул им, чтобы они вводили лошадей. Окончив это дело, офицер молодецким жестом, высоко подняв локоть руки, расправил усы и дотронулся рукой до шляпы.
– Bonjour la compagnie! [Почтение всей компании!] – весело проговорил он, улыбаясь и оглядываясь вокруг себя. Никто ничего не отвечал.
– Vous etes le bourgeois? [Вы хозяин?] – обратился офицер к Герасиму.
Герасим испуганно вопросительно смотрел на офицера.
– Quartire, quartire, logement, – сказал офицер, сверху вниз, с снисходительной и добродушной улыбкой глядя на маленького человека. – Les Francais sont de bons enfants. Que diable! Voyons! Ne nous fachons pas, mon vieux, [Квартир, квартир… Французы добрые ребята. Черт возьми, не будем ссориться, дедушка.] – прибавил он, трепля по плечу испуганного и молчаливого Герасима.
– A ca! Dites donc, on ne parle donc pas francais dans cette boutique? [Что ж, неужели и тут никто не говорит по французски?] – прибавил он, оглядываясь кругом и встречаясь глазами с Пьером. Пьер отстранился от двери.
Офицер опять обратился к Герасиму. Он требовал, чтобы Герасим показал ему комнаты в доме.
– Барин нету – не понимай… моя ваш… – говорил Герасим, стараясь делать свои слова понятнее тем, что он их говорил навыворот.
Французский офицер, улыбаясь, развел руками перед носом Герасима, давая чувствовать, что и он не понимает его, и, прихрамывая, пошел к двери, у которой стоял Пьер. Пьер хотел отойти, чтобы скрыться от него, но в это самое время он увидал из отворившейся двери кухни высунувшегося Макара Алексеича с пистолетом в руках. С хитростью безумного Макар Алексеич оглядел француза и, приподняв пистолет, прицелился.
– На абордаж!!! – закричал пьяный, нажимая спуск пистолета. Французский офицер обернулся на крик, и в то же мгновенье Пьер бросился на пьяного. В то время как Пьер схватил и приподнял пистолет, Макар Алексеич попал, наконец, пальцем на спуск, и раздался оглушивший и обдавший всех пороховым дымом выстрел. Француз побледнел и бросился назад к двери.
Забывший свое намерение не открывать своего знания французского языка, Пьер, вырвав пистолет и бросив его, подбежал к офицеру и по французски заговорил с ним.
– Vous n'etes pas blesse? [Вы не ранены?] – сказал он.
– Je crois que non, – отвечал офицер, ощупывая себя, – mais je l'ai manque belle cette fois ci, – прибавил он, указывая на отбившуюся штукатурку в стене. – Quel est cet homme? [Кажется, нет… но на этот раз близко было. Кто этот человек?] – строго взглянув на Пьера, сказал офицер.
– Ah, je suis vraiment au desespoir de ce qui vient d'arriver, [Ах, я, право, в отчаянии от того, что случилось,] – быстро говорил Пьер, совершенно забыв свою роль. – C'est un fou, un malheureux qui ne savait pas ce qu'il faisait. [Это несчастный сумасшедший, который не знал, что делал.]
Офицер подошел к Макару Алексеичу и схватил его за ворот.
Макар Алексеич, распустив губы, как бы засыпая, качался, прислонившись к стене.
– Brigand, tu me la payeras, – сказал француз, отнимая руку.
– Nous autres nous sommes clements apres la victoire: mais nous ne pardonnons pas aux traitres, [Разбойник, ты мне поплатишься за это. Наш брат милосерд после победы, но мы не прощаем изменникам,] – прибавил он с мрачной торжественностью в лице и с красивым энергическим жестом.
Пьер продолжал по французски уговаривать офицера не взыскивать с этого пьяного, безумного человека. Француз молча слушал, не изменяя мрачного вида, и вдруг с улыбкой обратился к Пьеру. Он несколько секунд молча посмотрел на него. Красивое лицо его приняло трагически нежное выражение, и он протянул руку.
– Vous m'avez sauve la vie! Vous etes Francais, [Вы спасли мне жизнь. Вы француз,] – сказал он. Для француза вывод этот был несомненен. Совершить великое дело мог только француз, а спасение жизни его, m r Ramball'я capitaine du 13 me leger [мосье Рамбаля, капитана 13 го легкого полка] – было, без сомнения, самым великим делом.
Но как ни несомненен был этот вывод и основанное на нем убеждение офицера, Пьер счел нужным разочаровать его.
– Je suis Russe, [Я русский,] – быстро сказал Пьер.
– Ти ти ти, a d'autres, [рассказывайте это другим,] – сказал француз, махая пальцем себе перед носом и улыбаясь. – Tout a l'heure vous allez me conter tout ca, – сказал он. – Charme de rencontrer un compatriote. Eh bien! qu'allons nous faire de cet homme? [Сейчас вы мне все это расскажете. Очень приятно встретить соотечественника. Ну! что же нам делать с этим человеком?] – прибавил он, обращаясь к Пьеру, уже как к своему брату. Ежели бы даже Пьер не был француз, получив раз это высшее в свете наименование, не мог же он отречься от него, говорило выражение лица и тон французского офицера. На последний вопрос Пьер еще раз объяснил, кто был Макар Алексеич, объяснил, что пред самым их приходом этот пьяный, безумный человек утащил заряженный пистолет, который не успели отнять у него, и просил оставить его поступок без наказания.
Француз выставил грудь и сделал царский жест рукой.
– Vous m'avez sauve la vie. Vous etes Francais. Vous me demandez sa grace? Je vous l'accorde. Qu'on emmene cet homme, [Вы спасли мне жизнь. Вы француз. Вы хотите, чтоб я простил его? Я прощаю его. Увести этого человека,] – быстро и энергично проговорил французский офицер, взяв под руку произведенного им за спасение его жизни во французы Пьера, и пошел с ним в дом.
Солдаты, бывшие на дворе, услыхав выстрел, вошли в сени, спрашивая, что случилось, и изъявляя готовность наказать виновных; но офицер строго остановил их.
– On vous demandera quand on aura besoin de vous, [Когда будет нужно, вас позовут,] – сказал он. Солдаты вышли. Денщик, успевший между тем побывать в кухне, подошел к офицеру.
– Capitaine, ils ont de la soupe et du gigot de mouton dans la cuisine, – сказал он. – Faut il vous l'apporter? [Капитан у них в кухне есть суп и жареная баранина. Прикажете принести?]
– Oui, et le vin, [Да, и вино,] – сказал капитан.


Французский офицер вместе с Пьером вошли в дом. Пьер счел своим долгом опять уверить капитана, что он был не француз, и хотел уйти, но французский офицер и слышать не хотел об этом. Он был до такой степени учтив, любезен, добродушен и истинно благодарен за спасение своей жизни, что Пьер не имел духа отказать ему и присел вместе с ним в зале, в первой комнате, в которую они вошли. На утверждение Пьера, что он не француз, капитан, очевидно не понимая, как можно было отказываться от такого лестного звания, пожал плечами и сказал, что ежели он непременно хочет слыть за русского, то пускай это так будет, но что он, несмотря на то, все так же навеки связан с ним чувством благодарности за спасение жизни.
Ежели бы этот человек был одарен хоть сколько нибудь способностью понимать чувства других и догадывался бы об ощущениях Пьера, Пьер, вероятно, ушел бы от него; но оживленная непроницаемость этого человека ко всему тому, что не было он сам, победила Пьера.
– Francais ou prince russe incognito, [Француз или русский князь инкогнито,] – сказал француз, оглядев хотя и грязное, но тонкое белье Пьера и перстень на руке. – Je vous dois la vie je vous offre mon amitie. Un Francais n'oublie jamais ni une insulte ni un service. Je vous offre mon amitie. Je ne vous dis que ca. [Я обязан вам жизнью, и я предлагаю вам дружбу. Француз никогда не забывает ни оскорбления, ни услуги. Я предлагаю вам мою дружбу. Больше я ничего не говорю.]