java使用HashMap容器添加元素的过程分析
//逐步分析HashMap类中.put()添加结点的过程
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//将key和value传参进put方法中 onlyIfAbsent=false evict=true 对key进行.hash()方法计算 .hash()方法如下
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//返回类型int占用4字节共32位 key.hashCode()计算哈希值返回int类型即32位二进制数 哈希值赋值给h ^异或位运算 0^0=0 1^0=1 1^1=0相同为0相异为1
//h >>> 16 三个>为无符号右移，将所有位包含符号位全部右移 >>右位移不移动符号位，正数符号位补0负数符号位补1
//h为int 32位 >>>16即取前16位右移至后16位的位置，前16位补0 将结果和h做^运算 返回处理后的hash值 这一步的目的是使元素在哈希表中的分布更分散
//putVal(hash(key), key, value, false, true)方法如下
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//hash即hash(key)处理后的hash值
//onlyIfAbsent – if true, don't change existing value
//evict – if false, the table is in creation mode.
Node<K,V>[] tab; Node<K,V> p; int n, i;
//定义了结点数组tab对应哈希表table 结点p
if ((tab = table) == null || (n = tab.length) == 0) //在判断==前括号内将哈希表赋值给tab 第一次put结点时哈希表为空 往下执行初始化
n = (tab = resize()).length; //.resize()方法用于数组的初始化及扩容 初始化后tab为长度16的数组 短路或||当tab==null为false时会执行n=tab.length 如果前面true则不执行该赋值 进而在语句块内赋值16 所以再往下时无论哪种情况n都代表哈希表的长度 .resize()方法之后分析
if ((p = tab[i = (n - 1) & hash]) == null) //哈希表的长度固定为2的n次幂，用二进制表示均为10000后面n个0的格式 n-1会使原来1的后面所有0变为1 15为1111 31为11111 从0到1111即15总共为16个数对应index0到15 用1111和处理后的hash值做&与运算和hash%16是同样的效果,因为16为10000，所有高于五位的部分都是16的2^n倍，实际的余数就是最后四位的值 这也是强制规定哈希表长度必须为2的n次幂的目的，用1111n个1&hash代替hash%capacity计算以提高计算效率 &与运算的最小值为0最大值为长度-1和index对应 将index赋值给i，将tab[i]赋值给p，判断p是否为空，为空则直接添加结点，不为空需要进行比较是否重复
tab[i] = newNode(hash, key, value, null); //当p即tab[i]为空执行语句，newNode()方法会生成新的结点存储KV 这里存储的是处理后的hash值，并不是%length的余数，存储hash值用于哈希表扩容或同index元素的hash比较或链表与红黑树转换等 最后一个参数next=null，put结点会放在表尾，所以将next设为null
else { //p不为空的情况
Node<K,V> e; K k; //定义结点e key的k
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) //如果p的hash和新put的hash相等&&短路与(如果false就不对k赋值) 将p.key赋值给k，判断两个key是否相同||短路或 新put的key不为空&&短路与两个key调用equals()方法判断是否相同 所以先判断hash，为true才会调用equals()方法，如果自定义对象要使用HashMap/HashSet的话不仅要重写.equals()还要重写.hashCode()
e = p; //当判断两个key相同后会将p赋值给e
else if (p instanceof TreeNode) //如果两个key不同，再判断当前索引位是否为红黑树结构，如果为红黑树则执行红黑树添加树结点的方法
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //引用变量p为Node<K,V>类型，强转为树结点 如果为红黑树结构，这里的p即tab[i]不再是表头结点，是树的根节点root
else { //如果两个key不同，并且当前结构为单向链表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) { //binCount计数器，将e设为p的直接后继结点，当直接后继结点为null即遍历到达表尾时，链表中所有的结点都和新put的key不同，则将新结点添加至表尾
p.next = newNode(hash, key, value, null); //将原表尾结点的next指向新结点，完成表尾的变更 虽然这里将p.next从null变为新结点，但e仍然指向null，当p.next赋值给e时e指向的是null而不是表尾.next，表尾变更了但e没有变
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st //从表头至表尾为size，当只有表头结点时binCount为0，size为1，即binCount为size-1 当size-1大于等于转换为红黑树的阈8-1时
treeifyBin(tab, hash); //treeifyBin()方法先判断哈希表长度是否达到MIN_TREEIFY_CAPACITY=64，false则进行扩容resize，true则将链表转换为红黑树，转换操作是哈希表中每个哈希桶单独进行的，别的哈希桶如果size没有达到8仍然是单向链表
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) //比较链表中的每一个结点，如果某一个结点和新put的key相同则break，这时e指向的是和key相同的这个结点
break;
p = e; //迭代，结点e比较完赋值给p，下一轮e变为后继结点继续判断
}
} //从上边表头结点的if判断到elseif到else，e分为两种情况，一种是key重复时e指向和key相同的原结点，一种是key不重复所以新增了结点时e为null
if (e != null) { // existing mapping for key
V oldValue = e.value; //将结点原来的value元素缓存，之后返回
if (!onlyIfAbsent || oldValue == null)
e.value = value; //这里用到了之前设定的onlyIfAbsent=false，非运算后为true，执行重复key的value覆盖，不增加新的结点，修改原key对应的value元素，返回原来的value
afterNodeAccess(e);
return oldValue; //如果是发生value的替换会在这里返回原value结束方法，如果是新增结点会跳过这个if语句执行后面的操作
}
}
++modCount; //修改操作的计数器
if (++size > threshold) //前面的操作如果是key重复进行覆盖，到这里之前已经return结束方法了，只有增加新结点时才会继续执行，这里的size指结点的总数，因为新增了一个结点所以++size，threshold是通过前面调用的resize()方法赋值的属性，是load factor负载因子0.75f*数组长度capacity的值，if条件的意思为当结点总数大于阈值时进行resize扩容
resize();
afterNodeInsertion(evict);
return null; //没有发生value覆盖会返回null
}
//进一步分析.resize()方法的扩容过程
final Node<K,V>[] resize() { //返回结点数组，即扩容后的哈希表
Node<K,V>[] oldTab = table; //将原哈希表赋值给oldTab
int oldCap = (oldTab == null) ? 0 : oldTab.length; //原哈希表容量，初次put结点时数组为null
int oldThr = threshold; //将原哈希表的负载因子的阈值赋值给oldThr
int newCap, newThr = 0; //初始化新的容量和阈值
if (oldCap > 0) { //当原容量大于0，即集合已经添加过结点时
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab; //MAXIMUM_CAPACITY=1<<30，哈希表的最大容量，如果原容量已经达到最大，则不再扩容，将阈值调整为int最大值(1<<31)-1，这样size永远不会大于阈值，不会再触发扩容，将原哈希表返回，没有对哈希表进行变更
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) //这里对新容量进行赋值，左移1即*2，通过左移保证容量永远是2的n次幂(二进制为10000后面n个0)，而最大容量之所以是1<<30是因为再往左移的话1会被移至首位即符号位，int32位，1000后面31个0为-2^31，1<<30为01000后面30个0
newThr = oldThr << 1; // double threshold //elseif判断为当新容量小于最大容量&&短路与 原容量大于等于默认初始容量16时，将原阈值<<1左移1赋值给新阈值，阈值是负载因子0.75f*容量，0.75即3/4，容量为2^n，所以乘法结果一定为整数，每一次扩容都是左移1即*2，阈值的增加也使用左移1代替oldThr*2或者0.75*newCap使计算效率提高
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr; //当原容量等于0而原阈值大于0时，将新容量变为阈值
else { // 当原容量和原阈值都为0，即初次添加结点时调用的扩容
newCap = DEFAULT_INITIAL_CAPACITY; //将容量变为默认初始容量16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //将阈值变为0.75f*16即12，虽然结果一定是整数，但数据类型为float，需要强转int，只有初次扩容会进行乘法运算，之后的阈值都随容量做左移运算
}
if (newThr == 0) { //这里对新阈值进行判断，上面的语句中只有一种情况没有对newThr赋新的值，即else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)为false，这意味着原容量在[1,15]或[(1<<29)+1,(1<<30)-1]区间内，这时容量不是2^n，不属于正常情况这里不再分析
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; //将新阈值赋值给阈值属性，用作以后的size和threshold比较
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //创建新的结点数组，泛型类数组需要强转
table = newTab; //将哈希表数组变为新数组
if (oldTab != null) { //判断原数组是否不为空，当初次put结点时不执行
for (int j = 0; j < oldCap; ++j) { //遍历原哈希表
Node<K,V> e;
if ((e = oldTab[j]) != null) { //将表头结点/根节点取出
oldTab[j] = null; //将该位置赋null
if (e.next == null) //如果只有表头结点
newTab[e.hash & (newCap - 1)] = e; //用结点的处理后的hash值和新容量-1即n个111进行与运算即%newCap，计算出结点在新哈希表中的索引，将结点放入，每次扩容都要对集合内所有结点重新计算位置，在单向链表内只有表头的情况下不需要担心新哈希表的对应位置会不会在遍历过程中已存有结点造成覆盖，扩容是左移1，索引位的范围也跟着向左扩展1位二进制数，新的索引位只有两种数的可能，一种是新增的最高位为0，新的索引=原索引，另一种是为1，所有可能与表头结点索引位冲突的结点都一定在原表中与表头结点冲突，即被链至表头结点next，但因为表头next=null，所以一定没有别的结点和表头结点冲突，新索引位一定为null
else if (e instanceof TreeNode) //判断当前哈希桶是否为红黑树结构，红黑树结构当结点数降至6会转回单向链表，所以上面只有表头结点的情况一定是单向链表结构
((TreeNode<K,V>)e).split(this, newTab, j, oldCap); //引用变量e编译类型为Node类，需要强转树结点，对所有树结点进行索引的转换操作
else { // preserve order保持秩序 //当单向链表内有多个结点的情况
Node<K,V> loHead = null, loTail = null; //head头即表头结点，tail尾即表尾结点
Node<K,V> hiHead = null, hiTail = null; //lo即low，hi即high
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) { //原容量为1000后面n个0，所以&与运算的目的就是看索引位范围向左扩展的那一位是不是0，因为新的索引位受那一位影响只有两种可能，一种是和原索引位相同即low位对应当前for循环的j，一种是比原索引位高oldCap位即high位 与运算结果为0时，结点e会放到low位
if (loTail == null) //e放low位时判断low位的表尾结点loTail是否null
loHead = e; //如果low位为空将e设为表头结点
else
loTail.next = e; //如果表尾存在结点则将e链至表尾
loTail = e; //初次添加表头后表尾也指向表头结点，之后每次新增结点都会指向新的表尾结点
}
else { //e放high位的情况
if (hiTail == null) //原理同上，如果表尾为null则存表头，如果表尾有结点则链至表尾
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null); //单向链表中只有表尾结点.next为null，当e变为null即链表遍历结束
if (loTail != null) {
loTail.next = null; //当low位有结点时将表尾结点.next赋null，因为原单向链表中该结点可能有后继结点(后继结点放到high位的情况)
newTab[j] = loHead; //将表头赋值给新表的原索引位
}
if (hiTail != null) {
hiTail.next = null; //原理同上，将high位表尾结点.next赋null
newTab[j + oldCap] = hiHead; //以oldCap=16为例，oldCap二进制为10000，原结点的索引从0000到1111即0-15位，e.hash & oldCap即判断10000的1的那一位，如果结果为1，新的索引位为1xxxx即原索引位+10000(十进制为16即原容量oldCap)，即新的索引位为原索引位+oldCap，所以low位为j，high位为j+oldCap
}
}
}
}
}
return newTab; //扩容和秩序维护完成，返回新哈希表
}
