Почему хеш-таблица занимает больше памяти, чем другие структуры данных?

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

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

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


dictionary memory data-structures hashtable space-complexity
person rex    schedule 19.03.2014    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Как вы говорите, все дело в компромиссе между временем поиска и пространством. Чем больше количество пробелов (сегментов) в базовой структуре данных, тем больше местоположений у хеш-функции, где она потенциально может хранить каждый элемент, и, следовательно, вероятность коллизии (и, следовательно, хуже, чем производительность с постоянным временем) уменьшен. Однако наличие большего количества сегментов, очевидно, означает, что требуется больше места. Отношение количества элементов к количеству сегментов известно как коэффициент загрузки и более подробно объясняется в этом вопросе: Каково значение коэффициента загрузки в HashMap?

В случае минимальной идеальной хеш-функции можно достичь производительности O(1). хранение n элементов в n сегментах (коэффициент загрузки равен 1).

person mtripp100    schedule 19.03.2014
comment
Извините, я думаю, что я немного туп, но скажем, в худшем случае (для места) каждое ведро хранит 1 элемент. Разве это не похоже на массив и, следовательно, того же размера, что и массив, а НЕ больше? - person rex; 19.03.2014
comment
Да, в идеальном случае в каждой корзине хранится ровно 1 элемент, поэтому N элементов сопоставляются с N корзинами. Однако на практике это почти никогда не происходит, потому что по мере того, как количество занятых сегментов заполняется, любая разумная реализация хеш-таблицы будет «выращивать» базовую структуру данных, чтобы включить больше сегментов, чтобы свести к минимуму возможность хэширования двух элементов в один и тот же. пространство. Если пространство важнее времени, хеш-таблица, вероятно, не то, что вам нужно. - person mtripp100; 20.03.2014
comment
но общее количество элементов во всех сегментах по-прежнему будет равно N, так почему же это занимает больше места, чем массив из N элементов? - person rex; 21.03.2014
comment
Вы подразумеваете, что мы добавляем дополнительные сегменты, которые могут оставаться пустыми, и накладные расходы, связанные с этими сегментами, представляют собой дополнительную память, занимаемую хэш-таблицей? - person rex; 21.03.2014
comment
@ArmenSafieh-Garabedian да, это основная причина дополнительного использования, хотя вам, возможно, также придется учитывать дополнительную память, используемую метод разрешения конфликтов, например связанные списки. - person mtripp100; 21.03.2014