HashMap 源码

构造方法// 默认初始容量 16必须2的幂staticfinalintDEFAULT_INITIAL_CAPACITY14;// 负载因子staticfinalfloatDEFAULT_LOAD_FACTOR0.75f;// 链表转红黑树阈值链表长度8staticfinalintTREEIFY_THRESHOLD8;// 红黑树转回链表阈值节点6staticfinalintUNTREEIFY_THRESHOLD6;// 最小树化容量数组长度64才会树化否则只扩容staticfinalintMIN_TREEIFY_CAPACITY64;publicHashMap(){// 负载因子默认0.75不初始化table数组懒加载this.loadFactorDEFAULT_LOAD_FACTOR;// 0.75}put计算 key 的 hash 值table 为空 → resize 初始化数组默认 16下标 i (n-1) hash数组该位置空 → 直接放 Node下标有元素key 相同覆盖 value是树节点红黑树插入是链表尾插链表长度到 8 执行树化size 自增超过阈值扩容。publicVput(Kkey,Vvalue){returnputVal(hash(key),key,value,false,true);}staticfinalinthash(Objectkey){inth;// key为null则hash0否则高16位异或低16位混合高低位减少碰撞return(keynull)?0:(hkey.hashCode())^(h16);}finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){NodeK,V[]tab;NodeK,Vp;intn,i;// ① table为空 / 长度0 → 调用resize()初始化数组懒加载if((tabtable)null||(ntab.length)0)n(tabresize()).length;// ② 计算数组下标 i (数组长度-1) hash// n是2的次方n-1二进制全1等价取模hash%n效率更高if((ptab[i(n-1)hash])null)// 下标位置无元素直接新建Node放入数组tab[i]newNode(hash,key,value,null);else{// 下标已有元素发生哈希碰撞NodeK,Ve;Kk;// 情况1头节点key完全相等hash相同 equals相等→ 覆盖旧值if(p.hashhash((kp.key)key||(key!nullkey.equals(k))))ep;// 情况2头节点是红黑树节点 → 走红黑树插入逻辑 putTreeValelseif(pinstanceofTreeNode)e((TreeNodeK,V)p).putTreeVal(this,tab,hash,key,value);// 情况3普通链表向后遍历else{for(intbinCount0;;binCount){// 遍历到链表尾部无相同keyif((ep.next)null){// 尾部追加新Nodep.nextnewNode(hash,key,value,null);// binCount从0开始追加后链表长度binCount1// 链表长度达到8触发树化treeifyBinif(binCountTREEIFY_THRESHOLD-1)treeifyBin(tab,hash);break;}// 链表中找到相同key跳出循环覆盖if(e.hashhash((ke.key)key||(key!nullkey.equals(k))))break;pe;}}// e不为null存在重复key覆盖value并返回旧值if(e!null){VoldValuee.value;if(!onlyIfAbsent||oldValuenull)e.valuevalue;afterNodeAccess(e);returnoldValue;}}// 新增节点修改计数1modCount;// 元素数量1超过阈值threshold → 扩容resize()if(sizethreshold)resize();afterNodeInsertion(evict);returnnull;}treeifyBin数组长度 64哪怕链表到 8 也只扩容不树化只有容量≥64 且链表≥8 才生成红黑树finalvoidtreeifyBin(NodeK,V[]tab,inthash){intn,index;NodeK,Ve;// 数组长度小于64不树化直接扩容解决链表过长if(tabnull||(ntab.length)MIN_TREEIFY_CAPACITY)resize();elseif((etab[index(n-1)hash])!null){// 将普通Node链表转为TreeNode双向链表TreeNodeK,Vhdnull,tlnull;do{TreeNodeK,VpreplacementTreeNode(e,null);if(tlnull)hdp;else{p.prevtl;tl.nextp;}tlp;}while((ee.next)!null);// 把双向TreeNode链表转成红黑树if((tab[index]hd)!null)hd.treeify(tab);}}resize首次 puttablenull → 初始化容量 16阈值16*0.7512size threshold → 扩容容量翻倍阈值同步翻倍只判断 e.hash oldCap结果 0 留在原下标1 放到原下标旧容量链表一拆二finalNodeK,V[]resize(){NodeK,V[]oldTabtable;intoldCap(oldTabnull)?0:oldTab.length;intoldThrthreshold;intnewCap,newThr0;// 场景1原数组有容量正常扩容if(oldCap0){// 容量已达最大限制不再扩容if(oldCapMAXIMUM_CAPACITY){thresholdInteger.MAX_VALUE;returnoldTab;}// 容量翻倍elseif((newCapoldCap1)MAXIMUM_CAPACITYoldCapDEFAULT_INITIAL_CAPACITY)newThroldThr1;// 阈值同步翻倍}// 场景2带初始容量构造器进来oldThr存初始容量elseif(oldThr0)newCapoldThr;// 场景3无参构造第一次初始化main走这里else{newCapDEFAULT_INITIAL_CAPACITY;// 16newThr(int)(DEFAULT_LOAD_FACTOR*DEFAULT_INITIAL_CAPACITY);// 12}// 创建新数组NodeK,V[]newTab(NodeK,V[])newNode[newCap];tablenewTab;// 旧数组不为空迁移元素if(oldTab!null){for(intj0;joldCap;j){NodeK,Ve;if((eoldTab[j])!null){oldTab[j]null;// 该下标只有单个节点直接迁移到新下标if(e.nextnull)newTab[e.hash(newCap-1)]e;// 红黑树节点迁移elseif(einstanceofTreeNode)((TreeNodeK,V)e).split(this,newTab,j,oldCap);// 链表拆分原下标j 或 joldCap不用重新计算hashelse{// 低位链表hash第oldCap位是0 → 下标不变jNodeK,VloHeadnull,loTailnull;// 高位链表hash第oldCap位是1 → 下标 joldCapNodeK,VhiHeadnull,hiTailnull;NodeK,Vnext;do{nexte.next;if((e.hasholdCap)0){if(loTailnull)loHeade;elseloTail.nexte;loTaile;}else{if(hiTailnull)hiHeade;elsehiTail.nexte;hiTaile;}}while((enext)!null);// 低位链表放jif(loTail!null){loTail.nextnull;newTab[j]loHead;}// 高位链表放 joldCapif(hiTail!null){hiTail.nextnull;newTab[joldCap]hiHead;}}}}}thresholdnewThr;returnnewTab;}getpublicVget(Objectkey){NodeK,Ve;return(egetNode(hash(key),key))null?null:e.value;}finalNodeK,VgetNode(inthash,Objectkey){NodeK,V[]tab;NodeK,Vfirst,e;intn;Kk;// 数组为空 / 下标无元素直接返回nullif((tabtable)!null(ntab.length)0(firsttab[(n-1)hash])!null){// 头节点就是目标key直接返回if(first.hashhash((kfirst.key)key||(key!nullkey.equals(k))))returnfirst;if((efirst.next)!null){// 红黑树走树查询if(firstinstanceofTreeNode)return((TreeNodeK,V)first).getTreeNode(hash,key);// 普通链表循环查找do{if(e.hashhash((ke.key)key||(key!nullkey.equals(k))))returne;}while((ee.next)!null);}}returnnull;}removepublicVremove(Objectkey){NodeK,Ve;return(eremoveNode(hash(key),key,null,false,true))null?null:e.value;}finalNodeK,VremoveNode(inthash,Objectkey,Objectvalue,booleanmatchValue,booleanmovable){NodeK,V[]tab;NodeK,Vp;intn,index;// 数组为空直接返回if((tabtable)!null(ntab.length)0(ptab[index(n-1)hash])!null){NodeK,Vnodenull,e;Kk;Vv;// 找到待删除节点if(p.hashhash((kp.key)key||(key!nullkey.equals(k))))nodep;elseif((ep.next)!null){if(pinstanceofTreeNode)node((TreeNodeK,V)p).getTreeNode(hash,key);else{do{if(e.hashhash((ke.key)key||(key!nullkey.equals(k)))){nodee;break;}pe;}while((ee.next)!null);}}// 找到节点执行删除if(node!null(!matchValue||(vnode.value)value||(value!nullvalue.equals(v)))){// 红黑树删除if(nodeinstanceofTreeNode)// 删除红黑树节点后若当前桶内节点数 ≤ 6会触发 untreeify 转回普通链表((TreeNodeK,V)node).removeTreeNode(this,tab,movable);// 删除数组头节点elseif(nodep)tab[index]node.next;// 删除链表中间/尾部节点elsep.nextnode.next;modCount;--size;afterNodeRemoval(node);returnnode;}}returnnull;}总结懒加载table 数组第一次 put 才创建下标计算 (n-1) hash要求容量必须是 2 的幂扰动函数高低 16 位异或降低哈希碰撞链表尾插链表节点数 ≥ 8 且数组长度 ≥ 64 转红黑树红黑树节点数 ≤ 6 转回链表扩容时数组长度翻倍链表拆高低两条不用重算 hash阈值 容量 * 负载因子默认 0.75元素数量超过阈值后触发扩容key 允许 nullhash 为 0固定存在数组下标 0put 流程调用 hash () 计算 key 扰动 hash进入 putVal判断 table 为空 → resize 初始化数组计算下标 i(n-1)hash桶为空直接 new Node 放入数组桶不为空发生哈希碰撞头节点 key 完全相等hash/equals→ 覆盖旧值返回 oldValue头节点是 TreeNode → 红黑树 putTreeVal 插入普通单向链表循环遍历找到相同 key 覆盖 value遍历到尾部追加新节点链表长度达到 8 触发 treeifyBin新增节点 sizemodCount快速失败判断 size threshold触发 resize 扩容get 流程hash 计算扰动值调用 getNodetable 为空直接返回 null定位桶下标判断头节点是否匹配 key匹配直接返回头节点 next 不为空TreeNode红黑树查找 getTreeNode O (logn)普通链表循环遍历匹配 key O (n)找不到返回 null相关考点HashMap 底层结构数组 (Node []) 单向链表 红黑树链表尾插底层节点Node普通链表节点hash、key、value、nextTreeNode继承 Node双向红黑树节点prev/left/right/red 标记为什么容量必须是 2 的幂下标计算 i (n - 1) hashn 为 2 次幂时n -1 二进制全 1 等价取模 hash % n位运算效率远高于取模扩容时 e.hash oldCap 快速拆分高低链表无需重算 hash自定义容量构造器内部会向上取最近 2 次幂负载因子为什么不是 0.750.5空间利用率低频繁扩容浪费性能1填满才扩容哈希冲突极多链表超长查询慢0.75平衡空间占用与哈希碰撞概率数学泊松分布最优平衡点new HashMap () 无参构造做了什么仅赋值 loadFactor0.75不创建 table 数组tablenull数组在第一次 putVal 时 resize 懒加载初始化new HashMap (10) 传入非 2 次幂初始容量底层怎么处理内部 tableSizeFor () 方法向上取大于传入值的最小 2 次幂传入 10 最终容量 16keynull 会报错吗不会报错null 的 hash 固定 0永久存在数组下标 0 位置最多存一个 null keytreeifyBin 什么时候转红黑树当前链表长度 ≥ 8 数组容量 ≥ 64数组容量 64只 resize 扩容不树化删除后什么时候红黑树退化为链表removeTreeNode 删除树节点后若当前桶树节点数量 ≤ 6执行 untreeify 转为普通 Node 链表HashMap 为什么线程不安全put/remove 未加锁并发修改 size、table 无同步机制会并发覆盖、丢失元素迭代器不支持并发修改为什么不直接用平衡二叉搜索树选用红黑树AVL 树高度严格平衡旋转次数多插入删除开销大红黑树弱平衡最多 2 次旋转折中查询与增删性能适合 HashMap 高频 put/get 场景