Понимание хеш-таблиц

Question

Я понимаю, что некоторые хеш-таблицы используют "сегменты", которые представляют собой связанный список "записей".

HashTable
  -size    //total possible buckets to use
  -count   // total buckets in use
  -buckets //linked list of entries

Entry
  -key   //key identifier
  -value // the object you are storing for reference
  -next  //the next entry

Чтобы получить корзину по индексу, вы должны позвонить:

myBucket = someHashTable[hashIntValue]

Затем вы можете перебирать связанный список записей, пока не найдете тот, который ищете, или ноль.

Всегда ли хэш-функция возвращает NUMBER % HashTable.size? Таким образом, вы остаетесь в пределах лимита? Так должна работать хеш-функция?

Answer 1

Говоря математически, хеш-функция обычно определяется как отображение из юниверса элементов, которые вы хотите сохранить в хеш-таблице, в диапазон {0, 1, 2, .., numBuckets - 1}. Это означает, что теоретически не требуется, чтобы вы использовали оператор mod для отображения некоторого целочисленного хеш-кода в диапазон допустимых индексов сегмента.

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

РЕДАКТИРОВАТЬ : Ваше описание хеш-таблицы называется хеш-таблицей и использует технику под названием закрытая адресация . Есть много других реализаций хеш-таблиц помимо той, что вы описали. Если вам интересно - и я надеюсь, что вы есть! :-) - возможно, вы захотите проверить страницу Википедии по теме .

Answer 2

что такое хеш-таблица ?

Он также известен как хеш-карта - это структура данных , используемая для реализации ассоциативного массива . Это структура, которая может сопоставлять ключи со значениями.

Как это работает?

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

См. Диаграмму ниже, это ясно объясняет.

Преимущества:

В хеш-таблице с большими размерами средняя стоимость для каждого поиска не зависит от количества элементов , хранящихся в таблице.

Многие конструкции хеш-таблиц также допускают произвольные вставки и удаления пар ключ-значение.

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

Недостатки:

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

Использование:

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

Answer 3

Нет, таблица обычно представляет собой массив записей.Вы не выполняете итерацию до тех пор, пока не найдете тот же хеш, вы используете результат хеширования (или обычно хеш по модулю numBuckets) для непосредственного индексирования в массив записей.Это дает вам поведение O (1) (итерация будет O (n)).

Когда вы пытаетесь сохранить два разных объекта с одинаковым результатом хеширования (так называемое «коллизия хешей»), вы должнынайти способ освободить место.Различные реализации различаются в том, как они обрабатывают коллизии.Вы можете создать связанный список всех объектов с одинаковым хешем или использовать некоторую перефразировку для сохранения в другой записи таблицы.

Answer 4

Нет предопределенного правила поведения хэш-функции. Вы можете сделать так, чтобы все ваши значения отображались в индекс 0 - совершенно допустимая хеш-функция (работает плохо, но работает).

Конечно, если ваша хеш-функция возвращает значение вне диапазона индексов в вашем связанном массиве, она не будет работать правильно. Однако нельзя сказать, что вам нужно использовать формулу (number % TABLE_SIZE)