そのため、ハッシュマップの削除関数は O(1) であると多くの情報源が言っていますが、リストの削除は O(n) であるため、ハッシュマップがリンクリストによってサポートされていない限り、これがどのようになるかわかりません。誰か説明してくれませんか？
4132 次
2 に答える
4
Hasmap を配列として表示できます。想像してみてください。地球上のすべての人間のオブジェクトをどこかに保管したいとします。全員に固有の番号を取得し、10*10^20 の次元の配列を使用できます。誰かが生まれると、その人は次の空き番号を取得し、末尾に追加されます。誰かが死亡した場合、彼女/彼の番号が使用され、配列エントリが null に設定されます。
誰かを追加したり誰かを削除したりするには、一定の時間が必要であることが簡単にわかります。配列アドレスの計算、完了 (ランダム アクセス メモリがある場合)。
ハッシュマップによって何が追加されますか? 志望動機は2つ。一方では、このような大きな配列は必要ありません。世界中から 10 人だけを保存したい場合、配列のほぼすべてのエントリは無料です。一方で、どこかに保存したいすべてのデータに一意の番号があるわけではありません。同じ数字が複数回表示されることもあれば、全体として表示される数字もあれば、数字が表示されないこともあります。したがって、入力からの大きな数値を使用し、それらをより小さな範囲の数値に減らす関数を定義します。この削減は、結果の数値が異なる入力に対して一意である可能性が最も高い方法である必要があります。
例: 1 から 100000000 までの 10 個の数値を格納するとします。100000000 のインデックスを持つ配列を使用できます。または、100 個のインデックスを持つ配列と関数 f(x) = x % 100 を使用することもできます。数値が 1234 の場合、f(1234) = 34 です。34 を割り当て済みとしてマークします。
では、2234 という数字を持っているとどうなるでしょうか? その時衝突があります。これを処理するには、いくつかの戦略が必要です。いくつかあります。いくつかの文献を研究するか、これについて具体的な質問をしてください。
文字列を保存する場合は、すべての文字の長さまたは ascii 値の合計を使用することを想像できます。
ご覧のとおり、何かを簡単に保存して、簡単にアクセスできます。私たちは何をしなければなりませんか？関数からハッシュを計算し (適切な関数の一定時間)、配列にアクセスし (一定時間)、保存または削除します (一定時間)。
現実の世界では、優れたハッシュ関数はそれほど簡単ではありません。Javaに含まれているものに固執するようにしてください。
詳細を読みたい場合は、ハッシュ テーブルに関するウィキペディアの記事を参考にしてください: http://en.wikipedia.org/wiki/Hash_table
于 2012-10-29T20:20:39.487 に答える