Вызывает ли использование хеш-таблиц фрагментацию памяти?

Мое понимание хеш-таблиц заключается в том, что они используют хеш-функции для связывания ключей с ячейками в памяти с общим количеством «сегментов», предварительно выделенных в памяти. Цель состоит в том, чтобы было достаточно сегментов, чтобы мне не приходилось использовать цепочку, замедляя мою идеальную O(1) сложность времени доступа до n/m x O(1), где n — количество уникальных ключей для хранения, а m — количество сегментов.

Поэтому, если у меня есть 1000 уникальных элементов для хранения, мне понадобится не менее 1000 сегментов и, возможно, намного больше, чтобы свести к минимуму вероятность использования моего связанного списка. Если бы это было не так, мы бы ожидали, что средняя хеш-таблица будет иметь много-много коллизий. Теперь, если у нас есть 1000 предварительно выделенных сегментов, это означает, что у меня есть 1000 байт выделенной памяти, распределенной по моей памяти. Таким образом, каждый уникальный ключ в моей хеш-таблице приводит к фрагменту памяти, фрагментирующему мою оперативную память.

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


memory-management hashtable low-level fragmentation memory-fragmentation
person Tal    schedule 31.01.2020    source источник

Ответы (1)


arrow_upward
0
arrow_downward

1000 байт выделенной памяти, распределенной по моей памяти

Нет, у вас есть один массив из 1000 записей (некоторого размера, который почти наверняка превышает 1 байт на запись).

Если каждая запись достаточно велика для обработки случая отсутствия коллизии на месте, дополнительное динамическое выделение не требуется до тех пор, пока не возникнет коллизия. (например, возможно, вы используете объединение и 1-битный флаг, чтобы указать, является ли эта запись автономным сегментом или указателем на связанный список.)

Если нет, то когда вы пишете запись, для нее нужно выделить место и сохранить указатель в самом табличном массиве. (например, хэш-таблица «ключ-значение» с маленькими ключами, но большими значениями). Пустая хеш-таблица может быть заполнена указателями NULL.

Возможно, вы по-прежнему хотите, чтобы он содержал структуры указателя и хеш-значения (для сегментов с одним членом). Затем вы можете отклонить запросы определенно не присутствующих без другого уровня косвенности, если полное хэш-значение не соответствует запросу; например для 32- или 64-битного хэша это намного больше, чем 10 бит для индексации таблицы с 1024 элементами.

Чтобы уменьшить общую фрагментацию, вы можете использовать slab-распределитель или другую технику для вырезания узлов из непрерывного блока, который вы получаете от глобального распределителя. Если хеш-таблица поддерживает свой собственный свободный список, это может помочь с пространственной локализацией узлов связанного списка, поэтому они, по крайней мере, не разбросаны по множеству разных виртуальных страниц (промахи TLB) и, надеюсь, не страницы DRAM (даже более медленные промахи кэша). ).

person Peter Cordes    schedule 31.01.2020