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

Question

c++ unordered_map collision handling , resize and rehash

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

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

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

Answer 1

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

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

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

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

что касается текста, который вы цитируете:.

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

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

В качестве доказательства осведомленности, от Matthew Austern's proposal here:

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

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

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

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

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

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

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

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

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