私が理解している限りでは、ハッシュマップは O(1) 時間に近い時間で要素を見つけることができるため、標準マップよりも望ましいです。これは、ハッシュまたはキーを配列ルックアップとして使用することによって行われます。次に、衝突を解決し、値を取り出します。
これはルックアップにはうまく機能しますが、ハッシュ ルックアップを行う配列空間がまばらに入力されている場合、ハッシュマップ/順序付けされていないマップは、配列空間を徹底的に調べることなく、ハッシュマップ内のすべての要素をどのように効率的に反復するのでしょうか?
編集: まだブースト、SGI、および C++11 ハッシュマップ/順序付けられていないマップには反復子がありますが、どのように機能しますか?
並列構造 (たとえば、のようなリンクされたリストLinkedHashMap) がない限り、それはできません。反復では、各バケットの内容をチェックする必要があります。
そのため、バケットのデータが非常にまばらである場合、これが要因になる可能性があります。これが、高すぎるバケット数を選択したくない理由の 1 つです(より大きなバケット数は明らかにメモリを無駄にします)。
反復は O(n) です。ここで、n はマップの容量 (つまり、バケットの数) です。ただし、通常、6 つのキーを格納するために 100000 の容量は必要ありません。これは、O(サイズ) が O(容量) であるべきであることを意味します。これは、反復も通常 O(サイズ) であることを意味します。