Java中的HashMap

一、通过Key定位在table数组中的位置bucketIndex

hash方法源码.png

以getEntry(Object key)方法为例：

getEntry方法.png

二、put操作

分三种情况：

1. key == null

将该key-value添加到table[0]的Entry链表中；

2. key != null 且 key 已经出现在 table[] 中

更新value，并返回table[]中的该key对应的oldValue；

3. key != null 且 key 未出现在 table[] 中

（1）如果 size > threshold 且table[bucketIndex] != null:
需要考虑table的resize操作，详细流程如下：
① 将table数组长度改为原来的2倍，并将原table中的所有元素迁移到新的table中，然后更新threshold；由resize(int newCapacity) 方法实现；
注意：原来处于同一table[bucketIndex]的Entry重新计算后，新的bucketIndex可能不相同，因此可能会被移到新的位置。移动过程中，针对相同的bucketIndex, 后面的Entry会添加到table[bucketIndex]的链表头部；
② 重新计算更新待插入的key对应的bucketIndex;
③ 创建一个新的Entry, 添加到table[bucketIndex]的链表头部，并更新size变量（HashMap中key-value对的数量。
（2）如果size < threshold 或 table[bucketIndex] == null:
不需要考虑table的resize操作，仅需执行1中第③步。