Здравствуйте, T4r4sB, Вы писали:

TB>Здравствуйте, netch80, Вы писали:

N>>Ну если в большинстве корзин 0 или 1 элемент (GCC поддерживает по умолчанию load factor, равный 1) — это совмещено с самими корзинами.

TB>Каждая корзина — в своей области памяти. Все равно по аллокации на элемент

Почему ты так думаешь?
Смотрю на реализацию GCC. Есть массив корзин, динамически аллоцируемый целым куском. Каждый элемент корзины — структура из значения и указателя на следующий такой же элемент. Для простоты демонстрации это выглядит где-то так:

[c++]
struct bucket_element {
Value value; // по факту просто область памяти, если !present
bool present;
struct bucket_element *next;
};
struct hash_map {
struct bucket_element *bucket_array;
size_t bucket_array_size;
};
[/c++]

Массив выделяется куском.

Дополнительные аллокации bucket_element происходят только там, где в корзине более одного элемента. Первая в каждой корзине делается по месту.