ハッシュマップとマップの違いは、ハッシュマップはハッシュ関数で実装されていますが、マップはツリーで実装されていることだけを知っています。体はこれ以上何か追加できますか?
これに基づいて、ハッシュマップはできるがマップはできないことはありますか?
3 に答える
10
ハッシュマップは、平均的なケースではアクセスのパフォーマンスが向上しますが (O(1))、最悪のケースではパフォーマンスが低下します (O(n))。マップは常に O(lg(n)) です。
マップはキー順に並べられますが、ハッシュマップはそうではありません。
一般に、ハッシュマップはマップよりも多くのメモリを使用します。
マップは通常、より高速な反復を可能にします。
優れたハッシュ関数は、優れた順序付け関数よりも書くのが難しくなります (そして分析するのも難しくなります)。
マップにできないことでハッシュマップにできることはないと思います。
于 2010-03-30T00:24:28.047 に答える
3
マップでは、キーが厳密な弱い順序付けを持っている必要がありますが、これはおそらく存在しない可能性があります。ハッシュマップにはハッシュ関数のみが必要です。したがって、このようにして、厳密な弱い順序付けを持たないキーでハッシュマップを使用できます。
于 2010-03-30T01:09:37.927 に答える
0
ツリーに対するハッシュマップの利点の 1 つは、マルチスレッド環境では、単一のキーを追加または削除するためにコンテナー全体をロックする必要がないことです。ハッシュ テーブル内の単一の関連エントリをロックするだけで (ほぼ) 十分です。
ほとんどの場合、更新するメタデータ (たとえば、ハッシュテーブル内のアイテムの数) が存在する可能性があるためです。もちろん、テーブルを拡大または縮小するには、おそらくテーブル全体をロックする必要があります。
于 2010-03-30T01:14:23.393 に答える