JavaにおけるHashMapの仕組みを深堀り

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である。

参考文献