HashMapについてのメモ

HashMapはキーと値のセットを要素として持つデータ構造。

参考

わかりやすいのでこっち見たほうが早い↓
JavaにおけるHashMapの仕組みを深堀り - Qiita

検索がO(1)になる理由

HashMapは要素を格納するメモリアドレスの決定方法が特殊。

キーのハッシュ値を要素数で割った余りをアドレスとする。

キーのハッシュ値　%　要素数 = メモリアドレス

・ハッシュ値とは

ハッシュ関数 (ハッシュかんすう、英: hash function) あるいは要約関数[1]とは、任意のデータから、別の（多くの場合は短い固定長の）値を得るための操作、または、その様な値を得るための関数のこと。ハッシュ関数から得られた値のことを要約値やハッシュ値または単にハッシュという。

ハッシュ関数は、主に検索の高速化やデータ比較処理の高速化、さらには改竄の検出に使われる。例えば、データベース内の項目を探したり、大きなファイル内で重複しているレコードや似ているレコードを検出したり、核酸の並びから類似する配列を探したりといった場合に利用できる。

・引用元
ハッシュ関数 - Wikipedia

アドレス決定の例

例：要素数３　key：suzuki　value：20

suzukiのハッシュ値125（仮）を算出する。

125（ハッシュ値） ÷ 3（要素数） の余り2を取得する。

メモリアドレス2に　key：suzuki value：20を格納する。

という感じ。

検索するときも同様にKeyからアドレスを特定できるのでO(1)で検索可能！
よく考えるよなあこんなこと。