JavaのHashMapの実装を眺める会③

HashMap#resizeを読む

とりあえずputValを読んでるがしょっぱなテーブルが初期化される前に呼び出すとresizeが呼ばれる

* Initializes or doubles table size.  If null, allocates in
 * accord with initial capacity target held in field threshold.
 * Otherwise, because we are using power-of-two expansion, the
 * elements from each bin must either stay at same index, or move
 * with a power of two offset in the new table.

テーブルのサイズを初期化もしくは2倍にする。 もしnullの場合、フィールドの閾値に保持している初期キャパシティに合わせてアロケートする。

  • 🍙 フィールドの閾値に保持しているがよくわからん

さもなくば、2のべき乗の拡張を利用しているため、それぞれのbinの要素は同じインデックスに保たれなければならない、もしくは新しいテーブルの2のべき乗のオフセットに移動する。

  • 🍙 2のべき乗の拡張を利用、とかbinが何をさしてるのとかがわからん
  • 🍙 とりあえず初期化時は初期キャパシティでアロケートするし、そうでなければエレメントを同じインデックスか、2のべき乗のオフセットに移動する、という話?
  • 🍙 なんで2のべき乗なのかはわかんないけどとりあえずhashのロジックのあたりとまとめて理解しないとわからん気がする

コードを読む

MAXIMUM_CAPACITYってなんだろ

static final int MAXIMUM_CAPACITY = 1 << 30;

https://stackoverflow.com/questions/21638080/why-is-the-maximum-capacity-of-a-java-hashmap-130-and-not-131 1を左に30ビットシフト

2進数で1000000000000000000000000000000

なぜInteger.MAX_VALUEでないのかがよくわからん

ざっくりやってること

  • thresholdの計算
  • tableの初期化、もしくはリサイズ

thresholdの計算

  • 既存のcapacity > MAXIMUM_CAPACITYなら、Integer.MAX_VALUE
    • ここよくわからん❓
  • 既存のcapacityが0より大きく
    • かつ既存のcapacityの2倍がMAXIMUM_CAPACITYより小さく、DEFAULT_INITIAL_CAPACITY以上なら、既存のthresholdの2倍
      • 要するに限界を超えないなら2倍
      • 拡張するパターン
      • ⭐️基本的にここと初期化以外はオーバーフローしないようにInteger.MAX_VALUEで切ってるだけだと思う⭐️
  • 既存のcapacityが0以下(要するに0?)でかつthresholdが0以下(要するに0?)ならthresholdはDEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY
    • デフォルトコンストラクタもしくはcapacityが0で初期化された後のtable初期化⭐️
  • 既存のcapacityが0以下かつthresholdが0より大きくてかつ、
    • 既存のthresholdがMAXIMUM_CAPACITYより小さくかつ既存のthreshold * loadFactorがMAXIMUM_CAPACITYより小さければ、既存のthreshold * loadFactor
    • 既存のthresholdもしくは既存のthreshold * loadFactorがMAXIMUM_CAPACITYを超えていれば、Integer.MAX_VALUE
      • capacity指定するコンストラクタから呼ばれるケース ⭐️

tableの初期化、もしくはリサイズ

新しいcapacityの計算
  • 既存のcapacityが0以下でかつthresholdが0より大きいなら、capacity=既存のthreshold
  • 既存のcapacityが0以下(要するに0?)でかつthresholdが0以下(要するに0?)ならcapacityはDEFAULT_INITIAL_CAPACITY
tableの初期化

上記capacityの数のNodeの配列を初期化し、tableに代入 // TODO 多分既存の値を入れ直す的なアレだと思う