Как устроены хэштаблицы?
Сначала выделяется массив какого-то размера, например 256. Обычно длина - степень двойки. Потом хеш обрезается до размера таблицы. Если элементов становится слишком много, то происходит перехеширование - размер таблицы увеличивается, и все элементы в нее перезапихиваются.

Но да, если в таблицу запихать много элементов, а потом почти все оттуда удалить, то она будет большая и почти вся пустая.

Edit:

Эта "проблема" никак не решается. Это и не проблема вовсе. Просто хеш-таблицы работают быстрее всяких балансированных деревьев или тупо сортированного массива за счет большего расхода памяти. Это нужно знать и дальше уже решать - что вам больше подходит под вашу конкретную задачу.
Данный вопрос безсмысенно обсуждать только в разделе АЛГОРИТМЫ. 

Дело в том что в каждом языке программирования есть своя реализация хеш-таблиц со своими преференциями.
Например в Java создается по умолчанию пустая табличка с 16 buckets и с фактором загрузки 0.75.

Типы данных для ключей и значений - могут быть любые. От них лишь требуется один контракт. Ключи должны позволять на себе посчитать хеш. И ключи нужно сравнивать на равенство и они должны быть иммутабельны. Тоесть ключом не может быть объект представляющий системный таймер например или генератор случайных чисел. 

Для случая автора число 42. Мы считаем остаток от деления на 16 это будет 10. Тоесть мы запишем в 10 бакет. А после того как в табличку зайдет большое число ключей и и соотношение ключей и емкости станет больше чем 0.75 - будет создана новая таблица с 32 бакетами и старые данные будут скопированы туда с реогранизацией ключей. Это тяжеловатая процедура поэтому изначально хеш-таблицу рекомендуется создавать уже с заранее известным capacity. Если хотите хранить 6 млрд социальных номеров людей планеты земля - то создавайте соотв такую таблицу. Тогда реорганизации не будет. И load factor можно сделать близким к 1.0.

(Старая таблица с 16 бакетами после этой процедуры будет уничтожена)