Hash Table Bucket Array

Question

Если у меня 50 000 записей и, скажем, 100 000 слотов доступно в хеш-таблице.Как лучше всего выбрать подходящий размер массива сегмента для каждого индекса, если не использовать LinkedLists, чтобы массив никогда не «переполнялся»?Подойдет ли 30% избыток?

Answer 1

Если вы используете массив с фиксированным размером для своих сегментов, то нет размера сегмента менее 50 000, который не гарантировал бы никогда переполнения, если у вас нет дополнительной информации о распределении ключей в 50 000 (т.е. если вы знали, что они были целые числа 1 .. 50000, то это было бы тривиально).

Но обычно вы не хотите полагаться на большие сегменты, потому что это O (n) для поиска блоков. Вместо этого лучше использовать таблицу переменного размера и сегменты переменного размера. Ковши могут быть просто массивами, размер которых вы удваиваете каждый раз, когда они заполняются. Аналогично, хэш-таблица может быть увеличена в два раза каждый раз, когда вы заполняете ее на 90%. Это стандартный тип подхода.

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

Answer 2

Если вы знаете ключи априори , вы можете вычислить минимальный идеальный хеш . Следовательно, достаточно одного размера корзины, если вы знаете ключи и можете настроить хеш-функцию.

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

Answer 3

Некоторые языки поддерживают динамический размер для массива (не нужно объявлять размер массива). Данные определяли размер массива динамически. И языки, которым нужен размер, также поддерживают динамический массив.