Как реализовать хеш-таблицу динамического размера?

Question

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

Но на самом деле большинство языков имеют встроенные типы хеш-таблиц.Когда я их использую, мне не нужно заранее знать размер хеш-таблицы.Я просто вкладываю в нее все, что хочу.Например, в Ruby:

h = {}
10000000.times{ |i| h[i]=rand(10000) }

Как это можно сделать?

Answer 1

См. Динамическое изменение размера раздела Хеш-таблицы Статья в Википедии .

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

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