HashTableと配列

Question

私はJavaで作業していましたが、一般的に、配列を持つときにハッシュテーブルに要素を保存する利点は何ですか？

私はarr [100]がある場合、arr自体の基本ポインタに（arr type）*（i）を追加するだけで、i番目の要素にアクセスするのはO（1）です。それでは、ハッシュテーブルはどのように役立ち、配列とは対照的にいつ有用でしょうか？

ありがとうございました

Answer 1

Javaでは、HashMapsを使用する必要があります。 JavaのObjectクラスにはint hashcodeメソッドがあり、個のオブジェクトを念頭に置いての番号を作成します。

For example, this is the hashcode of a String in java.

は、ハッシュマップでは、キーに値を割り当てることができます。たとえば、次のようにすることができます。<Username(String), Customer(Custom Object)>。配列では、特定の顧客（インデックスがわからない場合）を見つけるには、最悪の場合に配列全体（O（n））を調べなければなりません。 ハッシュマップがなく、バイナリ検索ツリーのような検索に最適化されたデータ構造をいくつか使用すると、log（n）（O（log n））時間がかかります。

ハッシュマップを使用すると、顧客のオブジェクトをすぐに取得できます。顧客のコレクション全体を通過する必要はありません。

基本的に、ハッシュマップは「ハッシュ」整数値をキーに「マップ」し、そのキーを使用して値を検索します。

また、小さな整数の中に大きな情報を入れているので、2つのキーが同じハッシュ値を持つが、実際のものと同じではない、いわゆるハッシュコリジョンに直面することに注意してください。もの。この場合、明らかに瞬時に情報を見つけることはできませんが、再度、特定のレコードを探すためにすべてのレコードを検索するのではなく、より小さい「バケット」の値を検索する必要があります。私たちの実際のコレクション。