Вставка элемента в полную хеш-таблицу с постоянным количеством сегментов

Question

Я сейчас изучаю хеш-таблицу и получил вопрос о ее реализации с фиксированным размером сегментов.

Предположим, у нас есть хеш-таблица с 23 элементами (например). Давайте используем простейшую хэш-функцию (hash_value = key%table_size), а ключи являются целыми числами только . Если мы говорим, что в одном сегменте может быть не более 1 элемента (без отдельной цепочки), означает ли это, что когда все сегменты заполнены, мы больше не сможем вообще вставить какой-либо элемент в таблицу? Или нам придется заменить элемент с таким же значением хеш-функции новым элементом?

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

Answer 1

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

Или нам придется фактически заменить элемент с таким жезначение хеша с новым элементом?

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

Answer 2

Да. «Открытая» хеш-таблица, которую вы описываете, имеет фиксированный размер, поэтому она может заполняться.

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

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

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