Реализация хеш-таблицы

Question

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

Мое понимание того, как реализована хеш-таблица: Ключ K передается хеш-функции H, которая возвращает хешированную версию K, HK. HK, вероятно, должен быть, по крайней мере, uint32_t для учета коллизий, у нас есть массив размера X, элемент хранится по индексу HK этого массива ... но, для этого не потребуется предварительно выделенный массив длины uint32_t по крайней мере (или каким бы ни было возвращаемое значение H)? если предположить, что мы не храним сами данные в этом массиве, а вместо этого храним ptr для данных, то нам нужен массив ptr_t длины uint32_t ... это кажется довольно расточительным, на 64-битной, что означало бы использование памяти : 2 ^ 32 * 8 = 34359738368 байт или ~ 32 ГБ только для массива ptrs к данным, что, очевидно, не так, как это на самом деле реализовано в реальной жизни ..

Так чего мне не хватает?

Answer 1

Это зависит от реализации. Есть три основных способа сделать это:

1) Используются небольшие хэши. Поэтому вместо использования 32-битного хеша, скажем, используется 8-битный хеш.

2) Используется несколько уровней хеширования. Так, например, 12-битный хеш может определить, в какой «сегмент» входит запись, но коллизия происходит, только если совпадает полный 32-битный хэш. Каждый сегмент хранится в связанном списке или аналогичной структуре. (Возможно, он оптимизирован для поиска полного 32-битного хеша внутри него.)

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

Answer 2

Реально, у вас есть массив с небольшим фиксированным количеством сегментов, которые либо используют цепочку (результат в связанном списке) или зондирование (худший пример: если взята хеш (x), попробуйте хеш (x) +1 ) на столкновения. Вы берете свой uint32 и мод по размеру корзины, простейший случай.

Вы можете определить коэффициент загрузки - как только вы доберетесь до N% заполненного массива, мы, скажем, удвоим размер массива и перефразируем все в новый массив. Скажем, где-то между 50% и 75% использования.

Ну, разве это не дорого, говорите? Ну не совсем. Допустим, вы удваиваете размер массива каждый раз. Итак, вы добавляете N элементов, последний из которых вызывает копию. N добавляет в O (1), а затем одну O (N) копию. Но подождите - O (N) / N составляет в среднем O (1), поэтому амортизированная средняя стоимость добавления по-прежнему равна O (1), при условии, что ваш коэффициент загрузки выбран правильно.

Answer 3

Вы должны создать свою хеш-таблицу, чтобы ее можно было расширить. Есть несколько способов сделать это. Прочитайте это , это будет полезно. В этом примере используется связанный список. И вам также нужно расширить таблицу, если больше нет пустых значений. Возникнет следующая проблема: если вы расширите свою карту, ваша функция H может вернуть новые значения HK для старых ключей K. Поэтому вы должны подумать, как решить эту проблему. Один из методов - перезагрузить все значения, когда таблица была расширена. Это нормально, если вы расширяете его не часто.

Answer 4

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

Идея проста:

class HashTable {
public:


private:
  std::vector<Bucket*> _array;
};

Затем вы берете HKи уменьшите , чтобы он поместился в массив, обычно по модулю: HK % size(_array), который дает индекс используемого сегмента.