Java HashMap源码分析

文章目录Java HashMap源码分析概述数据结构储存流程源码分析继承关系基本属性HashMap 构造函数Node 单链表节点TreeNode 红黑树节点hash() 哈希算法put()resize()remove()Java HashMap源码分析概述HashMap 实现MapK,V接口基于哈希表实现提供键值对的存储和快速查找。数据结构JDK1.7数组链表。JDK1.8数组链表红黑树。初始化JDK1.7创建 HashMap 实例时内部数组会立即初始化。JDK1.8懒加载策略第一次插入数据时数组才会初始化减少创建时开销。hash冲突JDK1.7当发生哈希冲突时使用链表解决冲突每个桶都是一个链表的头节点新元素会添加到链表头部。JDK1.8Java 8 引入红黑树当链表的长度超过阈值(默认为8)时链表转为红黑树当红黑树节点数小于6时退化为链表。数据插入方式JDK1.7头插法。新元素会插入到链表的头部。缺点在多线程环境下HashMap 进行扩容操作时会出现环状链表导致死循环。JDK1.8尾插法。新元素会插入到链表的尾部。优点避免环状链表。链表循环引用问题旧链表[] - A - B - null头插法在单线程下会变成[] - B - A - null在多线程下线程 A 和线程 B 同时开始操作线程 A 处理新链表 - A - null记录 A - B线程 B 处理新链表 - B - A - null线程 A 继续处理B - B线程 A 继续处理A - B最终新链表 - B - A - B 形成循环引用JDK1.8 哈希计算根据 key 的 hash 值进行扰动计算均匀分布减少碰撞几率。代码(h key.hashCode()) ^ (h 16)获取 hash 值并位移16位进行异或运算。JDK1.8 扩容机制默认容积16默认负载因子0.75新容量 旧容量 * 2双倍扩容。扩容之后一部分元素在原位置另外一部分元素移动到合适的位置上。新阈值 旧容量 * 负载因子。哈希表和哈希桶采用哈希函数将记录储存在一块连续的存储空间中这块连续的储存空间就称之为哈希表。哈希桶是解决哈希表冲突的一种方法哈希表中同一个位置可能存有多个元素为应对哈希冲突问题将哈希表中的每个位置表示一个哈希桶。红黑树红黑树是一种特殊的二叉树。链表不支持随机存取只能单向遍历效率很低如果冲突比较严重同一个index上的节点很多那么链表就会很长此时查找效率就会很低。使用红黑树可以将查找效率由原来的线性时间变为对数时间也就是O(n)变为O(logn)所以为了效率问题 这里直接使用了红黑树也就是二分的思想。冲突越严重红黑树的效果就越明显比如链表长度为1024时采用链表的效率就是1024而红黑树就是log(1024)10差了100倍!数据结构储存流程源码分析继承关系publicclassHashMapK,VextendsAbstractMapK,VimplementsMapK,V,Cloneable,Serializable基本属性publicclassHashMapK,V{// 认初始容量为16staticfinalintDEFAULT_INITIAL_CAPACITY14;// aka 16// 大容量2的30次方,2,147,483,648staticfinalintMAXIMUM_CAPACITY130;// 默认负载因子staticfinalfloatDEFAULT_LOAD_FACTOR0.75f;// 链表转红黑树的阈值staticfinalintTREEIFY_THRESHOLD8;// 红黑树转链表的阈值staticfinalintUNTREEIFY_THRESHOLD6;// 桶数组树化的阈值staticfinalintMIN_TREEIFY_CAPACITY64;// hash桶数组transientNodeK,V[]table;// 负载因子finalfloatloadFactor;// 阈值超过则双倍扩容threshold 容积 * 负载因子intthreshold;// 元素数量transientintsize;}HashMap 构造函数publicHashMap(){this.loadFactorDEFAULT_LOAD_FACTOR;// all other fields defaulted}publicHashMap(intinitialCapacity){this(initialCapacity,DEFAULT_LOAD_FACTOR);}publicHashMap(intinitialCapacity,floatloadFactor){if(initialCapacity0)thrownewIllegalArgumentException(Illegal initial capacity: initialCapacity);if(initialCapacityMAXIMUM_CAPACITY)initialCapacityMAXIMUM_CAPACITY;if(loadFactor0||Float.isNaN(loadFactor))thrownewIllegalArgumentException(Illegal load factor: loadFactor);this.loadFactorloadFactor;this.thresholdtableSizeFor(initialCapacity);}publicHashMap(Map?extendsK,?extendsVm){this.loadFactorDEFAULT_LOAD_FACTOR;putMapEntries(m,false);}Node 单链表节点Node 是 HashMap 的一个内部类用于存储 key-value 值Node是一个单向链表结构。staticclassNodeK,VimplementsMap.EntryK,V{finalinthash;finalKkey;Vvalue;NodeK,Vnext;publicfinalinthashCode(){returnObjects.hashCode(key)^Objects.hashCode(value);}}TreeNode 红黑树节点staticfinalclassTreeNodeK,VextendsLinkedHashMap.LinkedHashMapEntryK,V{TreeNodeK,Vparent;// 父节点TreeNodeK,Vleft;// 左子节点TreeNodeK,Vright;// 右子节点TreeNodeK,Vprev;// 前一个节点booleanred;// 标识TreeNode(inthash,Kkey,Vval,NodeK,Vnext){super(hash,key,val,next);}}hash() 哈希算法减少哈希冲突staticfinalinthash(Objectkey){inth;return(keynull)?0:(hkey.hashCode())^(h16);}说明先计算hash值再无符号右移16位最后异或运算获取最终的hash值。hash: 1011 1001 hash 4: 0000 1011 ^: 1011 0010put()HashMap调用put()方法会先将key值转hash值通过二次哈希算法高位运算和取模运算目的是分散均匀避免hash冲突通过hash值计算存储位置。如果没有hash冲突则将value值存放在指定位置如果存在hash冲突则尾插法放入单链表中当单链表长度大于8时会转红黑树。publicVput(Kkey,Vvalue){returnputVal(hash(key),key,value,false,true);}finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){NodeK,V[]tab;NodeK,Vp;intn,i;// 如果桶数组table为空则通过resize()创建// 所以哈希表的创建是在第一次调用put()时if((tabtable)null||(ntab.length)0)n(tabresize()).length;// 先判断桶数组如果没有hash冲突则通过hash值找到指定坐标插入桶数组if((ptab[i(n-1)hash])null)tab[i]newNode(hash,key,value,null);// 如果有hash冲突else{NodeK,Ve;Kk;// 如果hash值、key引用地址、key值都相等则新值覆盖旧值if(p.hashhash((kp.key)key||(key!nullkey.equals(k))))ep;// 如果是红黑树则向树中插入值elseif(pinstanceofTreeNode)e((TreeNodeK,V)p).putTreeVal(this,tab,hash,key,value);// 如果是链表else{// 遍历链表节点for(intbinCount0;;binCount){if((ep.next)null){// 尾插法在末尾插入新的节点p.nextnewNode(hash,key,value,null);// 如果链表长度8则转红黑树if(binCountTREEIFY_THRESHOLD-1)treeifyBin(tab,hash);break;}// 判断链表中的元素查找到相同的key值if(e.hashhash((ke.key)key||(key!nullkey.equals(k))))break;// 更新p指向下一个节点pe;}}// 新值覆盖旧值操作if(e!null){VoldValuee.value;if(!onlyIfAbsent||oldValuenull)e.valuevalue;afterNodeAccess(e);returnoldValue;}}modCount;// 如果容量大于阀值则resize()扩容操作if(sizethreshold)resize();afterNodeInsertion(evict);returnnull;}说明插入数据时如果桶数组为空则通过 resize() 方法初始化table。先判断桶数组中的元素是否存在如果不存在则直接插入桶数字如果存在则插入链表如果链表长度达到阈值则转红黑树。如果元素数量达到阈值则通过 resize() 方法扩容。resize()扩容操作//resize使用情况1.初始化哈希表2.扩容finalNodeK,V[]resize(){// 扩容前的旧数组NodeK,V[]oldTabtable;// 旧数组容量intoldCap(oldTabnull)?0:oldTab.length;// 扩容前的阈值intoldThrthreshold;intnewCap,newThr0;if(oldCap0){// 如果旧数组的容量大于最大值则不扩容if(oldCapMAXIMUM_CAPACITY){thresholdInteger.MAX_VALUE;returnoldTab;}// 双倍扩容通过旧容积和阈值计算新容积和阈值elseif((newCapoldCap1)MAXIMUM_CAPACITYoldCapDEFAULT_INITIAL_CAPACITY)newThroldThr1;// double threshold}elseif(oldThr0)// 初始化容积newCapoldThr;else{// 使用默认容积和负载因子newCapDEFAULT_INITIAL_CAPACITY;newThr(int)(DEFAULT_LOAD_FACTOR*DEFAULT_INITIAL_CAPACITY);}// 如果新阈值为0则重新计算if(newThr0){floatft(float)newCap*loadFactor;newThr(newCapMAXIMUM_CAPACITYft(float)MAXIMUM_CAPACITY?(int)ft:Integer.MAX_VALUE);}// 更新阀值thresholdnewThr;// 创建新的桶数组并设置容积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);// 如果元素是链表节点则遍历链表重新分组else{// 低位NodeK,VloHeadnull,loTailnull;// 高位NodeK,VhiHeadnull,hiTailnull;NodeK,Vnext;do{nexte.next;// 链表元素重新分组通过hash值和旧数组容量进行于操作// 如果结果值为0则元素的坐标不变// 如果结果值为1则元素的新坐标是原位置旧数组长度// 原坐标if((e.hasholdCap)0){if(loTailnull)loHeade;elseloTail.nexte;loTaile;}// 新坐标else{if(hiTailnull)hiHeade;elsehiTail.nexte;hiTaile;}}while((enext)!null);// 位置不变if(loTail!null){loTail.nextnull;newTab[j]loHead;}// 新位置if(hiTail!null){hiTail.nextnull;newTab[joldCap]hiHead;}}}}}returnnewTab;}说明计算新容积和阈值并创建新的桶数组。遍历旧数组的元素并重新分组到新数组中如果是桶数组的元素则通过e.hash (newCap - 1)计算后插入新数组中。如果是红黑树节点则插入红黑树中。如果是链表节点则通过e.hash oldCap计算如果结果值为0则元素位置不变如果结果值为1则位置是原位置旧数组长度。remove()publicVremove(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)((TreeNodeK,V)node).removeTreeNode(this,tab,movable);elseif(nodep)tab[index]node.next;elsep.nextnode.next;modCount;--size;afterNodeRemoval(node);returnnode;}}returnnull;}