TIL #4 220130

今日習った資料の構造を書きたいです.
ハッシュ表

Keyのデータ構造

に値をマッピングできる

ハッシュ関数を用いて、配列に鍵データを格納可能なアドレス(インデックス番号)

を算出する.

Keyでは、データが格納されているアドレスをすぐに知ることができます.そのため、ストレージとブラウズが高速です.

プリセットハッシュ関数は、生成可能なアドレス(インデックス番号)に空間を割り当て、その後、キー記憶およびブラウズデータ

をサポートする.
単純ハッシュ関数

String name = "Donuts";
(int)(name.charAt(0)) % 20 //8

キーワードが文字列の場合、Divisionテクノロジーを使用して前の文字を数値に変換し、キーワードのアドレス(インデックス番号)を計算します.

Divisionテクノロジー:残りの値を分割して使用するテクノロジー

ハッシュテーブルの長所と短所と用途
長所

データ格納/読み出し速度が速い(検索速度が速い)

.

ハッシュキーに関するデータがあるかどうかを繰り返しチェックしやすい

短所

は一般的により多くの記憶領域

を必要とする.

複数の鍵のアドレスが同じである場合、競合を解決するために別のデータ構造が必要である
用途

大量の検索が必要な場合は、

が必要です.

頻繁に保存、削除、読み取り

キャッシュ(再検証が容易)

考える
Q.必要な要素を探すとき、リストとハッシュを接続する時間の複雑さは?
A.接続リストはO(n)、ハッシュはO(1)
Q.ハッシュ関数を作成するときに、コードを再実行すると、オブジェクトが同じであっても異なる値になることがあります.どうしたんですか.
A.オブジェクトのhashcod関数は、オブジェクト(hip)メモリのアドレス値を返します.したがって、同じオブジェクトでも、コードが新しく実行されるたびにメモリアドレス値が変更され、異なる値が返されます.オブジェクトクラスのtoString、equals、hashCodeなどのメソッドは、上書きしない場合、デフォルトではメモリ位置に基づいてコードが実行されます.
Q.ハッシュ競合を回避するためにハッシュサイズを最適化
A.
1.ハッシュ・サイズを奇数に設定し、%演算子を使用すると複数の結果が得られます.
2.ハッシュのサイズを小数点以下に設定し、残りの数値が異なるようにします.