Как храняться данные в хеш-таблице?

Question

[Cexhaif]

Берем в качестве хеш-функции java-вский Object::hashCode. Тогда(принебрегая коллизией) у нас будет максимум Integer.MAX_VALUE (2,147,483,647) уникальных обьектов. И получается, что нам надо аллоцировать массив такого размера для хранения обьектов. Но такой массив, даже пустой, занял бы очень и очень много памяти. Как решается данная проблема?

Answer 1

[lega]

2,147,483,647

В 32 битном числе ~4 млрд значений, а не ~2

Массив выделяется под кол-во данных, в разных системах по разному, например в питоне когда массив заполнен на ~70%, тогда выделяется больший массив под эти данные.
Результирующий хеш подстраивается под размер массива, например под 500 элементов, может быть выделен массив в 1024 элементов, в итоге результирующая позиция может быть вычислена так = hash_value %mod table_length, пример: 55555 % 1024 -> 259, итого значение будет записано в 259 ячейку (если нет коллизии)

Answer 2

[sirs]

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