HashMapの基本
- Map（key,valueの格納データ形式）の実装クラスで多分一番使われているやつ。
- Hash関数を使って高速にデータの検索が可能（配列・リストの線形検索より計算量が少ないとされる）
HashMap<String, Integer> map = new HashMap<>();
map.put("Sato", 22);
map.put("Takahashi", 24);
map.put("Nomura", 32);
HashMapの仕組み
(1) HashMapの格納できる数が5の例で考える。
(2) key:Sato value:22を格納しようとする。
a. Satoのハッシュ値144を算出する(例なので適当な数字です)
b. 144を要素数の５で割ってあまりを取得 144/5 = 28 ...4
c. 4にkey:Sato value:22を格納する。
[0]
[1] [Nomura, 32]
[2]
[3] [Takahashi, 24]
[4] [Sato,22]
(3) データを取り出すときは同様の計算をしてkeyからどこに目的のデータが格納されているか計算する。
(4) Hash値の余剰が衝突することもあり、同じ場所に複数のデータが格納されることもあり得る（以下の例）
[0]
[1] [Nomura, 32]
[2]
[3] [Takahashi, 24]
[4] [Sato,22] [Ito, 98]
容量の拡張に関して
- 要素数が増えてくるとrehashを行い格納数を増やす。Javaの場合は負荷係数を元に算出される。
- 要素数が
容量 × 負荷係数を超えた時点でrehashが行われる。 - JavaのHashMapは、デフォルトの容量は16、負荷係数は0.75である。