W jaki sposób jest iterowane za pośrednictwem hashtable?

Question

Próbuję zrozumieć, w jaki sposób jest iterowanie poprzez zaimplementowane hashtable. Po prostu nie mogę tego sobie wyobrazić. Jestem szczególnie zainteresowany szybkością takiej iteracji. Na przykład:

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

Czy jest to operacja O(hashTable.size())?

Próbowałem zagłębić się w kodzie źródłowym, ale nie mogłem znaleźć właściwej definicji.

Answer 1

Niektóre implementacje tabel mieszania również utrzymują połączoną listę wszystkich wpisów, aby umożliwić szybką iterację (tak zwaną "połączoną mapę skrótów").

Jedynym sposobem jest powtórzenie wszystkich segmentów stołu mieszającego, a także powtórzenie kolejnych elementów w każdym wiadrze.

Szybkość tej operacji zależy od stanu napełnienia tabeli. Gdy jest bardzo niska, wiele pustych wiader musi zostać poddanych iteracji, co marnuje czas. Gdy tabela jest dobrze wypełniona, a jeden lub więcej elementów znajduje się w każdym wiadrze, to prawie tak, jak iterowanie połączonej listy. Na idealnej mapie mieszania, w której każdy zasobnik zawiera dokładnie jeden element, jest to jak iterowanie tablicy.