13

実装されたハッシュテーブルをどのように反復しているかを理解しようとしています。想像することしかできません。私が特に興味を持っているのは、その反復の速さです。例えば：

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

これはO(hashTable.size())操作ですか？

ソースコードを掘り下げようとしましたが、適切な定義が見つかりませんでした。

4

1 に答える 1

13

ハッシュ テーブルの一部の実装では、高速反復を可能にするためにすべてのエントリのリンク リストも維持します (いわゆる「リンク ハッシュ マップ」)。

そうでない場合、唯一の方法は、ハッシュ テーブルのすべてのバケットを反復処理すると同時に、各バケット内の要素を反復処理することです。

この操作の速度は、テーブルの塗りつぶし状態によって異なります。値が非常に低い場合、多くの空のバケットを反復する必要があり、時間が無駄になります。テーブルが十分に満たされ、1 つまたは複数の要素が各バケットにある場合、リンクされたリストを反復するようなものです。各バケットに要素が 1 つだけ含まれる完全なハッシュ マップでは、配列を反復するようなものです。

于 2013-01-08T10:53:55.983 に答える