Как хранятся хэш-таблицы (карты) в памяти?

Этот вопрос специально для hashtables, но может также охватывать другие структуры данных, такие как связанные списки или деревья.

Например, если у вас есть структура следующим образом:

struct Data 
{
 int value1;
 int value2;
 int value3;
}

И каждое целое число 4-байт выровнено и хранится в памяти последовательно, являются ли ключ и значение хэш-таблицы, сохраненной последовательно? Если вы считаете следующее:

std::map<int, string=""> list;
list[0] = "first";
</int,>

Этот первый элемент представлен таким образом?

struct ListNode
{
 int key;
 string value;
}

И если ключ и значение 4-байт выровнены и сохранены последовательно, имеет ли значение, где хранится следующая пара?

Как насчет узла в связанном списке?

Просто попытайтесь визуализировать это концептуально, а также посмотрите, применимы ли те же рекомендации для хранения памяти для хэширования с открытой адресацией (нагрузка меньше 1) или цепочка хэширования (загрузка не имеет значения).

3 ответа

Он очень специфичен для реализации. И этим я имею в виду не только компилятор, архитектуру процессора и ABI, но и реализацию хеш-таблицы. В некоторых хэш-таблицах используется структура, содержащая ключ и значение рядом друг с другом, как вы уже догадались. Другие имеют один массив ключей и один массив значений, так что values[i] являются ассоциированным значением для ключа в keys[i]. Это не зависит от вопроса "открытая адресация против отдельной цепочки".


Обычно, когда значение не такое большое (int), лучше всего сгруппировать его вместе с ключом (который по умолчанию не должен быть слишком большим), в противном случае сохраняется только указатель на него.


Хэш - это сама структура данных. Здесь ваша визуализация:

http://en.wikipedia.org/wiki/Hash_table

http://en.wikipedia.org/wiki/Hash_function

Используя хеш-функцию (специфичную для langauge), ключи превращаются в места, а значения помещаются там (в массив).

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

licensed under cc by-sa 3.0 with attribution.