В зависимости от того, как вы реализуете хеш-таблицу и сколько блоков изначально, она может быть разумным недостатком.Хеш-таблицам требуется около половины (или более) корзин, чтобы быть пустыми, иначе коллизии станут намного более вероятными.Все сегменты изначально пустые, но примите во внимание, что после добавления элементов в хеш-таблицу большинство реализаций увеличит количество сегментов, так что по крайней мере половина из них будет свободна.Это означает, что у вас есть O (n) пустых корзин.То, имеет ли это значение, зависит от того, сколько предметов у вас есть и насколько большие корзины.Если сегменты являются структурами, они потенциально могут быть довольно большими, поскольку им потребуется хранить хеш-значение вдоль указателей на ключ и значение (если не фактический ключ и значение).Чаще всего сегменты - это указатели на контейнеры, в которых хранятся хеш и указатели на ключ и значение.Размер каждого сегмента зависит от размера указателя.Это почти всегда 32- или 64-битные (если только вы не используете встроенный процессор).
Таким образом, предполагая, что наилучший случай - 4 байта на одну корзину, вы должны использовать 4 мегабайта памяти дляхеш-таблица с 500 000 объектов (помните: около половины контейнеров пустые).Также представьте, что у каждого из этих полумиллиона использованных сегментов есть узел с указателями на фактические данные.Это будет использовать еще 12 байтов на значение (хотя с ограничениями выравнивания памяти это больше похоже на 16 байтов).Это было бы еще 8 МБ без учета каких-либо фактических данных!
С другой стороны, большинство структур данных имеют большие накладные расходы памяти.Двоичное дерево поиска имеет четыре указателя на узел (один для ключа, один для значения и два для дочерних узлов).При 16 байтах на узел в 32-битной системе это сопоставимо с размером хеш-таблицы (по крайней мере, в пределах порядка).
Если все, что вы храните, это chars, то издержки любогоиз этих структур данных может быть большим по сравнению с фактическими данными, но на практике это не должно быть слишком большой проблемой, если не работать с гигантскими наборами данных и ужасно неэффективными реализациями хеш-таблиц.