Как устроены хэштаблицы?

Question

[beduin01]

Вопрос простой. Вот к примеру мы наполняет хэш-таблицу данными. В начале хэштаблица пустая. Хэш элемента у нас получается к примеру 42. Т.е. мы должны его на 42 позицию записать. Получается что мы должны дорастить таблицу с 0 до 42? Ведь иначе то позиционный номер аргумента никакого толку не даст. А если хэш следующего будет 100500 то тогда получается придется создать огромную таблицу, но она всего из двух элементов будет состоять?

Или как эту проблема решается?

Comments

[Сергей Соколов]

хэши обычно не числа, а строки

{
  "c2ecdbaeca0428": "Alice",
  "e561b4b6b9ad8c": "Bob",
}

[alexalexes]

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

[mayton2019]

В языках программирования в 99% случаев хешом будет целое 32х битное число integer.

Хотя хеш функции определены для результата типа MD5, SHA1, SHA256 , но на практике нас будет интересовать простота применения. Атомарный тип удобнее чем byte-array.

Кроме того многие реализации хеш таблиц ограничены 32х битным числом части бакетов. Для Java это поряка 1 млрд. (2 << 30). И это ограничение я встречал даже 64х битных языках программирования. Видимо создатели решили что не найдется такого безумца который создаст больше 1 млрд бакетов.

Для моего кейса с социальными номерами всех жителей планеты Земля обычная Java HashMap не подойдет. Уже не будет масштабирования. Хотя мне сложно себе представить такую таблицу. В момент реорганизации она может потребовать в 3 раза больше памяти чем занимает.

Answer 1

[Wataru]

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

Но да, если в таблицу запихать много элементов, а потом почти все оттуда удалить, то она будет большая и почти вся пустая.

Edit:

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

Answer 2

[mayton2019]

Данный вопрос безсмысенно обсуждать только в разделе АЛГОРИТМЫ.

Дело в том что в каждом языке программирования есть своя реализация хеш-таблиц со своими преференциями.
Например в Java создается по умолчанию пустая табличка с 16 buckets и с фактором загрузки 0.75.

Типы данных для ключей и значений - могут быть любые. От них лишь требуется один контракт. Ключи должны позволять на себе посчитать хеш. И ключи нужно сравнивать на равенство и они должны быть иммутабельны. Тоесть ключом не может быть объект представляющий системный таймер например или генератор случайных чисел.

Для случая автора число 42. Мы считаем остаток от деления на 16 это будет 10. Тоесть мы запишем в 10 бакет. А после того как в табличку зайдет большое число ключей и и соотношение ключей и емкости станет больше чем 0.75 - будет создана новая таблица с 32 бакетами и старые данные будут скопированы туда с реогранизацией ключей. Это тяжеловатая процедура поэтому изначально хеш-таблицу рекомендуется создавать уже с заранее известным capacity. Если хотите хранить 6 млрд социальных номеров людей планеты земля - то создавайте соотв такую таблицу. Тогда реорганизации не будет. И load factor можно сделать близким к 1.0.

(Старая таблица с 16 бакетами после этой процедуры будет уничтожена)