HashMap 源码-拓冰建站

构造方法

// 默认初始容量 16（必须2的幂）staticfinalintDEFAULT_INITIAL_CAPACITY=1<<4;// 负载因子staticfinalfloatDEFAULT_LOAD_FACTOR=0.75f;// 链表转红黑树阈值：链表长度>=8staticfinalintTREEIFY_THRESHOLD=8;// 红黑树转回链表阈值：节点<=6staticfinalintUNTREEIFY_THRESHOLD=6;// 最小树化容量：数组长度>=64才会树化，否则只扩容staticfinalintMIN_TREEIFY_CAPACITY=64;publicHashMap(){// 负载因子默认0.75，不初始化table数组，懒加载this.loadFactor=DEFAULT_LOAD_FACTOR;// 0.75}

put

计算 key 的 hash 值
table 为空 → resize 初始化数组（默认 16）
下标 i = (n-1) & hash，数组该位置空 → 直接放 Node；
下标有元素：
1. key 相同：覆盖 value；
2. 是树节点：红黑树插入；
3. 是链表：尾插，链表长度到 8 执行树化；
size 自增，超过阈值扩容。

publicVput(Kkey,Vvalue){returnputVal(hash(key),key,value,false,true);}staticfinalinthash(Objectkey){inth;// key为null则hash=0；否则高16位异或低16位，混合高低位减少碰撞return(key==null)?0:(h=key.hashCode())^(h>>>16);}finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){Node<K,V>[]tab;Node<K,V>p;intn,i;// ① table为空 / 长度0 → 调用resize()初始化数组（懒加载）if((tab=table)==null||(n=tab.length)==0)n=(tab=resize()).length;// ② 计算数组下标 i = (数组长度-1) & hash// n是2的次方，n-1二进制全1，等价取模hash%n，效率更高if((p=tab[i=(n-1)&hash])==null)// 下标位置无元素，直接新建Node放入数组tab[i]=newNode(hash,key,value,null);else{// 下标已有元素，发生哈希碰撞Node<K,V>e;Kk;// 情况1：头节点key完全相等（hash相同 + equals相等）→ 覆盖旧值if(p.hash==hash&&((k=p.key)==key||(key!=null&&key.equals(k))))e=p;// 情况2：头节点是红黑树节点 → 走红黑树插入逻辑 putTreeValelseif(pinstanceofTreeNode)e=((TreeNode<K,V>)p).putTreeVal(this,tab,hash,key,value);// 情况3：普通链表，向后遍历else{for(intbinCount=0;;++binCount){// 遍历到链表尾部，无相同keyif((e=p.next)==null){// 尾部追加新Nodep.next=newNode(hash,key,value,null);// binCount从0开始，追加后链表长度=binCount+1// 链表长度达到8，触发树化treeifyBinif(binCount>=TREEIFY_THRESHOLD-1)treeifyBin(tab,hash);break;}// 链表中找到相同key，跳出循环覆盖if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))break;p=e;}}// e不为null：存在重复key，覆盖value并返回旧值if(e!=null){VoldValue=e.value;if(!onlyIfAbsent||oldValue==null)e.value=value;afterNodeAccess(e);returnoldValue;}}// 新增节点，修改计数+1++modCount;// 元素数量+1，超过阈值threshold → 扩容resize()if(++size>threshold)resize();afterNodeInsertion(evict);returnnull;}

treeifyBin

数组长度 < 64，哪怕链表到 8 也只扩容，不树化；只有容量≥64 且链表≥8 才生成红黑树

finalvoidtreeifyBin(Node<K,V>[]tab,inthash){intn,index;Node<K,V>e;// 数组长度小于64，不树化，直接扩容解决链表过长if(tab==null||(n=tab.length)<MIN_TREEIFY_CAPACITY)resize();elseif((e=tab[index=(n-1)&hash])!=null){// 将普通Node链表转为TreeNode双向链表TreeNode<K,V>hd=null,tl=null;do{TreeNode<K,V>p=replacementTreeNode(e,null);if(tl==null)hd=p;else{p.prev=tl;tl.next=p;}tl=p;}while((e=e.next)!=null);// 把双向TreeNode链表转成红黑树if((tab[index]=hd)!=null)hd.treeify(tab);}}

resize

首次 put，table=null → 初始化容量 16，阈值16*0.75=12
size > threshold → 扩容，容量翻倍，阈值同步翻倍
只判断 e.hash & oldCap，结果 0 留在原下标，1 放到原下标+旧容量，链表一拆二

finalNode<K,V>[]resize(){Node<K,V>[]oldTab=table;intoldCap=(oldTab==null)?0:oldTab.length;intoldThr=threshold;intnewCap,newThr=0;// 场景1：原数组有容量，正常扩容if(oldCap>0){// 容量已达最大限制，不再扩容if(oldCap>=MAXIMUM_CAPACITY){threshold=Integer.MAX_VALUE;returnoldTab;}// 容量翻倍elseif((newCap=oldCap<<1)<MAXIMUM_CAPACITY&&oldCap>=DEFAULT_INITIAL_CAPACITY)newThr=oldThr<<1;// 阈值同步翻倍}// 场景2：带初始容量构造器进来，oldThr存初始容量elseif(oldThr>0)newCap=oldThr;// 场景3：无参构造，第一次初始化（main走这里）else{newCap=DEFAULT_INITIAL_CAPACITY;// 16newThr=(int)(DEFAULT_LOAD_FACTOR*DEFAULT_INITIAL_CAPACITY);// 12}// 创建新数组Node<K,V>[]newTab=(Node<K,V>[])newNode[newCap];table=newTab;// 旧数组不为空，迁移元素if(oldTab!=null){for(intj=0;j<oldCap;++j){Node<K,V>e;if((e=oldTab[j])!=null){oldTab[j]=null;// 该下标只有单个节点，直接迁移到新下标if(e.next==null)newTab[e.hash&(newCap-1)]=e;// 红黑树节点迁移elseif(einstanceofTreeNode)((TreeNode<K,V>)e).split(this,newTab,j,oldCap);// 链表拆分：原下标j 或 j+oldCap，不用重新计算hashelse{// 低位链表：hash第oldCap位是0 → 下标不变jNode<K,V>loHead=null,loTail=null;// 高位链表：hash第oldCap位是1 → 下标 j+oldCapNode<K,V>hiHead=null,hiTail=null;Node<K,V>next;do{next=e.next;if((e.hash&oldCap)==0){if(loTail==null)loHead=e;elseloTail.next=e;loTail=e;}else{if(hiTail==null)hiHead=e;elsehiTail.next=e;hiTail=e;}}while((e=next)!=null);// 低位链表放jif(loTail!=null){loTail.next=null;newTab[j]=loHead;}// 高位链表放 j+oldCapif(hiTail!=null){hiTail.next=null;newTab[j+oldCap]=hiHead;}}}}}threshold=newThr;returnnewTab;}

get

publicVget(Objectkey){Node<K,V>e;return(e=getNode(hash(key),key))==null?null:e.value;}finalNode<K,V>getNode(inthash,Objectkey){Node<K,V>[]tab;Node<K,V>first,e;intn;Kk;// 数组为空 / 下标无元素直接返回nullif((tab=table)!=null&&(n=tab.length)>0&&(first=tab[(n-1)&hash])!=null){// 头节点就是目标key，直接返回if(first.hash==hash&&((k=first.key)==key||(key!=null&&key.equals(k))))returnfirst;if((e=first.next)!=null){// 红黑树走树查询if(firstinstanceofTreeNode)return((TreeNode<K,V>)first).getTreeNode(hash,key);// 普通链表循环查找do{if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))returne;}while((e=e.next)!=null);}}returnnull;}

remove

publicVremove(Objectkey){Node<K,V>e;return(e=removeNode(hash(key),key,null,false,true))==null?null:e.value;}finalNode<K,V>removeNode(inthash,Objectkey,Objectvalue,booleanmatchValue,booleanmovable){Node<K,V>[]tab;Node<K,V>p;intn,index;// 数组为空直接返回if((tab=table)!=null&&(n=tab.length)>0&&(p=tab[index=(n-1)&hash])!=null){Node<K,V>node=null,e;Kk;Vv;// 找到待删除节点if(p.hash==hash&&((k=p.key)==key||(key!=null&&key.equals(k))))node=p;elseif((e=p.next)!=null){if(pinstanceofTreeNode)node=((TreeNode<K,V>)p).getTreeNode(hash,key);else{do{if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k)))){node=e;break;}p=e;}while((e=e.next)!=null);}}// 找到节点执行删除if(node!=null&&(!matchValue||(v=node.value)==value||(value!=null&&value.equals(v)))){// 红黑树删除if(nodeinstanceofTreeNode)// 删除红黑树节点后，若当前桶内节点数 ≤ 6，会触发 untreeify 转回普通链表((TreeNode<K,V>)node).removeTreeNode(this,tab,movable);// 删除数组头节点elseif(node==p)tab[index]=node.next;// 删除链表中间/尾部节点elsep.next=node.next;++modCount;--size;afterNodeRemoval(node);returnnode;}}returnnull;}

总结

懒加载：table 数组第一次 put 才创建；
下标计算 (n-1) & hash，要求容量必须是 2 的幂
扰动函数：高低 16 位异或，降低哈希碰撞；
链表尾插
链表节点数 ≥ 8 且数组长度 ≥ 64 转红黑树；红黑树节点数 ≤ 6 转回链表
扩容时数组长度翻倍，链表拆高低两条，不用重算 hash
阈值 = 容量 * 负载因子（默认 0.75），元素数量超过阈值后触发扩容
key 允许 null，hash 为 0，固定存在数组下标 0

put 流程

调用 hash () 计算 key 扰动 hash
进入 putVal，判断 table 为空 → resize 初始化数组
计算下标 i=(n-1)&hash
桶为空：直接 new Node 放入数组
桶不为空发生哈希碰撞：
1. 头节点 key 完全相等（hash+==/equals）→ 覆盖旧值返回 oldValue
2. 头节点是 TreeNode → 红黑树 putTreeVal 插入
3. 普通单向链表循环遍历：
  1. 找到相同 key 覆盖 value
  2. 遍历到尾部追加新节点；链表长度达到 8 触发 treeifyBin
新增节点 size++，modCount++（快速失败）
判断 size > threshold，触发 resize 扩容