Как реализуется std:: unordered_map

c++ unordered_map обработка коллизий, изменение размера и перефразировка

Это предыдущий вопрос, открытый мной, и я видел, что у меня много путаницы в том, как реализована unordered_map. Я уверен, что многие другие люди разделяют эту путаницу со мной. Основываясь на информации, которую я знаю, не читая стандарт:

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

Я надеялся, что кто-то может объяснить реализацию и то, как она соответствует стандартному определению c++ (с точки зрения требований к производительности), и если это действительно не самый эффективный способ реализации структуры данных хэш-карты, как ее можно улучшить?

Ответ 1

Стандарт эффективно предусматривает реализации std::unordered_set и std::unordered_map, которые используют открытое хэширование, что означает массив ведер, каждый из которых содержит головку логического (и обычно фактического) списка. Это требование является тонким: это связано с максимальным коэффициентом нагрузки по умолчанию, равным 1,0, и гарантией того, что таблица не будет перефразирована, если она не будет расти за пределами этого коэффициента загрузки: это было бы нецелесообразно без цепочки, поскольку столкновения с закрытым хешированием стали подавляющими, поскольку коэффициент нагрузки приближается 1:

23.2.5/15: Члены insert и emplace не должны влиять на действительность итераторов, если (N+n) < z * B, где N - количество элементов в контейнере до операции вставки, N - количество вставленных элементов, B - количество контейнеров в контейнерах, а z - максимальный коэффициент загрузки контейнеров.

среди эффектов конструктора в 23.5.4.2/1: max_load_factor() возвращает 1.0.

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

Относительно текста, который вы указываете:

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

Нет "надзора"... то, что сделано, было очень преднамеренным и сделано с полным осознанием. Верно, что другие компромиссы могли быть удалены, но подход с открытым хэшированием/цепочкой является разумным компромиссом для общего использования, который разумно изящно справляется с столкновениями с посредственными хеш-функциями, не слишком расточительно с малыми или большими ключами/значениями, и обрабатывает произвольно-многие пары insert/erase без постепенного ухудшения производительности, как это делают многие закрытые реализации хэширования.

В качестве доказательства осознания, из предложения Мэтью Фостерна здесь:

Мне не известно о какой-либо удовлетворительной реализации открытой адресации в общей структуре. Открытая адресация представляет собой ряд проблем:

• Необходимо различать свободную позицию и занятую.

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

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

• Управление столкновением особенно усложняется при разрешении стирания элементов. (См. Knuth для обсуждения.) Класс контейнера для стандартной библиотеки должен допускать стирание.

• Схемы управления столкновением для открытой адресации имеют тенденцию предполагать массив фиксированного размера, который может содержать до N элементов. Класс контейнера для стандартной библиотеки должен быть способен расти по мере необходимости, когда вставлены новые элементы, вплоть до предела доступной памяти.

Решение этих проблем может быть интересным исследовательским проектом, но при отсутствии опыта реализации в контексте С++ было бы нецелесообразно стандартизировать класс контейнера с открытым адресом.

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

Полное сравнение и разработка вариантов дизайна хеш-таблиц и их последствий не соответствует теме S.O. поскольку он слишком широк, чтобы правильно обращаться здесь.