Почему коэффициент загрузки Hashtable не соответствует описанному в книге CLRS?

Question

Из документа Java о классе Hashtable говорится:

Как правило, коэффициент загрузки по умолчанию (.75) обеспечивает хороший компромисс между временными и пространственными затратами

* 1005.*

Таким образом, коэффициент загрузки для Hashtable составляет 0,75, что означает, что при наличии N ключей Hashtable будет использовать M = N / 0,75 пробела для их хранения.

В книге CLRS также вводится коэффициент загрузки альфа,

Но, насколько я понимаю, CLRS намеревается установить альфа больше 1, т. Е. M = N / alpha

Я говорю, что M

Но Hashtable в Java использует хранилище больше, чем N. Я думаю, что это не согласуется с дизайном CLRS, верно?

Я прав?

спасибо

Answer 1

Ну, коэффициент загрузки должен быть больше, чем добавленные элементы.Деление на число меньше единицы приводит к большему числу, чем исходное.

Если вы хотите добавить 100 элементов, вы можете написать:

AllocationSize = 100 / 0.75; // Your formula: M = N/0.75 

или

AllocationSize = 100 * 1.33333333; // M = N / X -> M = N * (1/X)

, где оба результата дают 133.333333 -> 133.

Весь JavaDoc:

Экземпляр Hashtable имеет два параметра, влияющих на его производительность: начальная емкостьи коэффициент загрузки.Емкость - это количество сегментов в хэш-таблице, а начальная емкость - это просто емкость на момент создания хеш-таблицы.Обратите внимание, что хеш-таблица открыта: в случае «коллизии хешей» в одном сегменте хранятся несколько записей, которые необходимо искать последовательно.Коэффициент загрузки - это мера того, насколько полной хеш-таблице разрешено получать до того, как ее емкость будет автоматически увеличена.Когда число записей в хеш-таблице превышает произведение коэффициента загрузки и текущей емкости, емкость увеличивается путем вызова метода перефразировки.

Как правило, коэффициент загрузки по умолчанию (.75) предлагает хороший компромиссмежду временем и пространственными затратами.Более высокие значения уменьшают затраты пространства, но увеличивают временные затраты на поиск записи (что отражается в большинстве операций Hashtable, включая операции get и put).

Начальная емкость контролирует компромисс между потраченным пространством и потребностью вперефразировать операции, которые отнимают много времени.Операции перефразирования никогда не произойдут, если начальная емкость больше, чем максимальное количество записей, которые будет содержать Hashtable, деленное на коэффициент загрузки.Однако установка слишком высокой начальной емкости может привести к потере места.

Если в Hashtable необходимо сделать много записей, его создание с достаточно большой емкостью может позволить вставлять записи более эффективно, чем выполнять его автоматически.Перефразировка по мере необходимости, чтобы вырастить стол.

Answer 2

Я не слышал о книге CLRS, но могу вам сказать, что использование коэффициента загрузки более 0,75 (даже меньше для некоторых конструкций хэш-карт) приводит к значительному количеству коллизий.

Есливы позволяете HashMap или Hashtable расти естественным образом, их емкость будет пропорциональна количеству записей.Эти ссылки имеют небольшой размер (обычно 4 байта) по сравнению с размером объектов Entry (обычно 16–24 байта), поэтому интересующая вас таблица хеш-индексов всегда будет в несколько раз меньше размера объектов Entry, не говоря уже о ключахи значения.