Как выполняется итерация через хэш-таблицу?

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

QHash<int, std::string> hashTable;
...
for (auto it = hashTable.begin(); it != hashTable.end(); ++it)
    std::cout << it.value() << std::endl;

Это операция O(hashTable.size())?

Я попытался выкопать исходный код, но не смог найти правильное определение.

Ответы

Ответ 1

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

Когда они этого не делают, единственный способ - перебрать все ведра хэш-таблицы, а также итерации по элементам в каждом ковше.

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