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

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 для сопоставления некоторого целочисленного хеш-кода в диапазоне действительных индексов ковша.

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

EDIT: Ваше описание хэш-таблицы называется прикован хэш-таблицу и использует метод, называемый закрыт адресации. Есть много других реализаций хеш-таблиц помимо того, что вы описали. Если вам интересно - и я надеюсь, что вы! :-) - вы можете проверить the Wikipedia page on the subject.

Answer 2

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

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

Answer 3

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

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

Answer 4

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

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

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

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

См. Приведенную ниже диаграмму, в которой это четко объясняется.

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

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

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

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

Недостатки:

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

Применение:

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