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

Question

beduin01 @beduin01

Алгоритмы

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

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

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

Вопрос задан более двух лет назад
236 просмотров

3 комментария

Подписаться 2 Простой 3 комментария

Сергей Соколов @sergiks Куратор тега Алгоритмы
хэши обычно не числа, а строки
{ "c2ecdbaeca0428": "Alice", "e561b4b6b9ad8c": "Bob", }
Написано более двух лет назад
alexalexes @alexalexes

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

Написано более двух лет назад
mayton2019 @mayton2019

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

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

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

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

Написано более двух лет назад

хэши обычно не числа, а строки
{ "c2ecdbaeca0428": "Alice", "e561b4b6b9ad8c": "Bob", }
Даже если ключами являются числа, то нужна такая структура данных в конкретной среде разработки, которая бы не пыталась создать эти промежутки.
При чтении хэш-таблицы неотъемлемой операцией будет проверка на существование ключа, так что вам никакие промежутки не нужны.
В языках программирования в 99% случаев хешом будет целое 32х битное число integer.

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

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

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

Answer 1 · 2022-09-30 15:08:12

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

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

Edit:

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

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

Войдите на сайт