Я пытаюсь понять, как выполняется итерация через хэш-таблицу. Я просто не могу этого себе представить. Меня особенно интересует скорость такой итерации. Например:
QHash<int, std::string> hashTable;
...
for (auto it = hashTable.begin(); it != hashTable.end(); ++it)
std::cout << it.value() << std::endl;
Это операция O(hashTable.size())?
Я попытался выкопать исходный код, но не смог найти правильное определение.
Некоторые реализации хеш-таблиц также поддерживают связанный список всех записей, чтобы обеспечить быструю итерацию (так называемая "связанная хэш-карта" ).
Когда они этого не делают, единственный способ - перебрать все ведра хэш-таблицы, а также итерации по элементам в каждом ковше.
Скорость этой операции зависит от состояния заполнения таблицы. Когда он очень низок, необходимо перезапустить много пустых ведер, которые теряют время. Когда таблица заполнена хорошо, и один или несколько элементов находятся в каждом ведре, это почти похоже на повторение связанного списка. На идеальном хеш-карте, где каждое ведро содержит ровно один элемент, оно подобно итерации массива.