Если вам нужна хеш-таблица с миллионом записей, обычно у вас будет как минимум 2 миллиона блоков. Я не помню всю статистику (ключевой термин «парадокс дня рождения»), но подавляющее большинство ведер будет иметь ноль или один предмет. В принципе, вы можете быть очень невезучим и получить все предметы в одном ведре, но вам, возможно, придется повезти еще больше, чем тем людям, которые, похоже, поражаются молнией через день.
Для растущих хеш-таблиц обычным трюком является рост на постоянный процент - обычным делом учебника является рост путем удвоения размера хеш-таблицы. Вы делаете это всякий раз, когда количество элементов в хеш-таблице достигает определенной пропорции от размера хеш-таблицы, независимо от того, сколько блоков фактически используется. Это дает ожидаемую амортизированную производительность O (1) для вставок, удалений и поисков.
Связанный список в каждом сегменте хеш-таблицы - это просто способ обработки коллизий - маловероятно для каждой операции, но в течение жизни значимой хеш-таблицы они делают случаются - тем более что хеш-таблица заполняется более чем наполовину.
Связанные списки - не единственный способ справиться с коллизиями - в этой теме есть огромное количество знаний. Уолтер Брайт (разработчик языка программирования D) выступает за использование двоичных деревьев, а не связанных списков, утверждая, что его Dscript значительно улучшил производительность по сравнению с Javascript благодаря этому выбору дизайна.
Он использовал простые (несбалансированные) двоичные деревья, когда я спросил, поэтому производительность в худшем случае была такой же, как и для связанных списков, но я думаю, что ключевой момент заключается в том, что код обработки двоичного дерева прост, и сама хеш-таблица делает шансы на создание больших несбалансированных деревьев очень маленькими.
В принципе, вы можете так же легко использовать трепы, красно-черные деревья или деревья AVL. Интересным вариантом может быть использование Splay-деревьев для обработки столкновений. Но в целом, это небольшая проблема для некоторых проектировщиков библиотек и несколько настоящих навязчивых идей, о которых нужно беспокоиться.