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