@beduin01

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

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

Или как эту проблема решается?
  • Вопрос задан
  • 198 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Сначала выделяется массив какого-то размера, например 256. Обычно длина - степень двойки. Потом хеш обрезается до размера таблицы. Если элементов становится слишком много, то происходит перехеширование - размер таблицы увеличивается, и все элементы в нее перезапихиваются.

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

Edit:

Эта "проблема" никак не решается. Это и не проблема вовсе. Просто хеш-таблицы работают быстрее всяких балансированных деревьев или тупо сортированного массива за счет большего расхода памяти. Это нужно знать и дальше уже решать - что вам больше подходит под вашу конкретную задачу.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
@mayton2019
Bigdata Engineer
Данный вопрос безсмысенно обсуждать только в разделе АЛГОРИТМЫ.

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

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

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы