HashMap类的申明
HashMap的定义如下：
1publicclassHashMapextendsAbstractMap2implementsMap,Cloneable,Serializable{}
HashMap是一个散列表，用于存储key-value形式的键值对。
从源码的定义中可以看到HashMap继承了AbstractMap抽象类而且也实现了Map接口，AbstractMap类本身也继承了Map接口，Map接口定义了一些map数据结构的基本操作， AbstractMap提供了Map接口的一些默认实现。
HashMap实现了Cloneable接口和Serializable接口，这两个接口本身并没有定义方法，属于申明式接口，允许hashmap进行克隆和序列化。
另外，HashMap不是线程安全的，如果需要使用线程安全的HashMap，可以使用Collections类中的synchronizedMap方法来获得线程安全的HashMap：
Map map = Collections.synchronizedMap(new HashMap());
HashMap主要字段属性说明
1//hashmap的初始容量：162staticfinalintDEFAULT_INITIAL_CAPACITY =1<<4;// aka 1634//hashmap的最大容量，hashmap的容量必须是2的指数值5staticfinalintMAXIMUM_CAPACITY =1<<30;67//默认填充因子8staticfinalfloatDEFAULT_LOAD_FACTOR =0.75f;910//链表转换为树的阀值：如果一个桶中的元素个数超过 TREEIFY_THRESHOLD=8 ，就使用红黑树来替换链表，从而提高速度11staticfinalintTREEIFY_THRESHOLD =8;1213//树还原为链表的阈值：扩容时桶中元素小于UNTREEIFY_THRESHOLD = 6，则把树形的桶元素还原为链表结构14staticfinalintUNTREEIFY_THRESHOLD =6;1516//哈希表的最小树形化容量：当哈希表中的容量大于这个值MIN_TREEIFY_CAPACITY = 64时，哈希表中的桶才能进行树形化，否则桶中元素过多时只会扩容，并不会进行树形化， 为了避免扩容和树形化选择的冲突，这个值不能小于4* TREEIFY_THRESHOLD = 3217staticfinalintMIN_TREEIFY_CAPACITY =64;1819//hashmap用于存储数据的Node数组，长度是2的指数值20transientNode[] table;2122//保存entrySet返回的结果23transientSet> entrySet;2425//hashmap中键值对个数26transientintsize;2728//hashmap对象修改计数器29transientintmodCount;3031// threshold=容量*装载因子，代表目前占用数组长度的最大值，用于判断是否需要扩容32intthreshold;3334//装载因子,用来衡量hashmap装载数据程度，默认值为EFAULT_LOAD_FACTOR = 0.75f，装载因子计算方法size/capacity35finalfloatloadFactor;
查阅资料发现在JDK1.8之前hashmap的通过数组+链表的数据结构实现的，这样在hash值大量冲突时hashmap是通过一个长长的链表来存储的，JDK1.8开始，hashmap采用数组+链表+红黑树组合数据结构来实现，链表和红黑树将会按一定策略互相转换，JDK1.8开始，hashmap的存储结构大致如下：
回顾一下关于红黑树的定义：
1. 每个结点或是红色的，或是黑色的
2. 根节点是黑色的
3. 每个叶结点（NIL）是黑色的
4. 如果一个节点是红色的，则它的两个儿子都是黑色的
5. 对于每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑色结点
HashMap部分方法析
构造函数
无参数构造函数：设置装载因子初始值0.75
1publicHashMap() {2this.loadFactor = DEFAULT_LOAD_FACTOR;// all other fields defaulted3}
HashMap(int initialCapacity) ：指定初始容量
publicHashMap(intinitialCapacity){this(initialCapacity, DEFAULT_LOAD_FACTOR);}
HashMap(int initialCapacity) ：指定初始容量和装载因子
1publicHashMap(intinitialCapacity,floatloadFactor){2//初始容量校验3if(initialCapacity <0)4thrownewIllegalArgumentException("Illegal initial capacity: "+5initialCapacity);6//校验初始容量不能超过hashmap最大容量：2的30次方7if(initialCapacity > MAXIMUM_CAPACITY)8initialCapacity = MAXIMUM_CAPACITY;//初始化为最大容量9//校验装载因子10if(loadFactor <=0|| Float.isNaN(loadFactor))11thrownewIllegalArgumentException("Illegal load factor: "+12loadFactor);13this.loadFactor = loadFactor;14this.threshold = tableSizeFor(initialCapacity);15}16//根据根据初始化参数initialCapacity 返回大于等于该值得最小 2的指数值 作为初始容量17staticfinalinttableSizeFor(intcap){18intn = cap -1;19n |= n >>>1;20n |= n >>>2;21n |= n >>>4;22n |= n >>>8;23n |= n >>>16;24return(n <0) ?1: (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n +1;25}
这个构造函数可以发现初始化hashmap的容量并不是随意指定多少就初始化多少，内部根据传入的容量值做了转换，严格的将hashmap的初始容量转换成的2的指数值，比如我们初始化一个new HashMap(25)，实际初始化处来的容量是32，相当于new HashMap(32)
HashMap(Map m):初始化一个hashmap，使用默认加载因子0.75,并将hashmap参数值复制到新创建的hashmap对象中。
1public HashMap(Map m) {2this.loadFactor = DEFAULT_LOAD_FACTOR;3putMapEntries(m,false);4}
put(K key, V value)
向hashmap中添加健值对
1publicVput(K key, Vvalue){2returnputVal(hash(key), key,value,false,true);3}45//hash：hashkey6//key value :键值对7//onlyIfAbsent:为true则不修改已存在的value8//evict:返回被修改的value9final VputVal(inthash, K key, Vvalue, boolean onlyIfAbsent,10boolean evict){1112Node[] tab;13Node p;14intn, i;15//如果table为null或者空，则进行resize扩容16if((tab = table) ==null|| (n = tab.length) ==0)17//执行resize扩容，内部将初始化table和threshold18n = (tab = resize()).length;19//如果对应索引处没有Node，则新建Node并放到table里面20if((p = tab[i = (n -1) & hash]) ==null)21tab[i] = newNode(hash, key,value,null);//tab[i]==null的情况，直接新创建节点并赋值给tab[i]22else{23//else的情况表示tab[i]不为null24Node e;25K k;26//1：hash值与tab[i]的hash值相等且key也相等，那么覆盖该节点的value域27if(p.hash == hash &&28((k = p.key) == key || (key !=null&& key.equals(k))))29e = p;//暂存tab[i]的节点p到临时变量e30//2：判断tab[i]是否是红黑树31elseif(p instanceof TreeNode) 32 e= ((TreeNode)p).putTreeVal(this, tab, hash, key,value);//添加到树形结构中33else{34//3：不是红黑树 且不是第1中情况，即：hash值一致,但是key不一致，那么需要将新的key-value添加到链表末尾35for(intbinCount =0; ; ++binCount) {36if((e = p.next) ==null) {37//添加到链表末尾38p.next = newNode(hash, key,value,null);39//如果该节点的链表长度大于8，则需要将链表转换为红黑树40if(binCount >= TREEIFY_THRESHOLD -1)// -1 for 1st41treeifyBin(tab, hash);42break;43}44//如果key已经存在该链表中，直接break,执行后续更新逻辑45if(e.hash == hash &&46((k = e.key) == key || (key !=null&& key.equals(k))))47break;48p = e;49}50}51if(e !=null) {// existing mapping for key52V oldValue = e.value;53/hash值和key相等的情况下，更新value54if(!onlyIfAbsent || oldValue ==null)55e.value=value;56//57afterNodeAccess(e);58//返回旧的value值59returnoldValue;60}61}62//修改次数自增63++modCount;64//判断是否需要再次扩容65if(++size > threshold)66resize();67//68afterNodeInsertion(evict);69returnnull;70}
上面的代码即便加了注释，看上不也不是很清晰，csdn有篇文章分析了hash的这个方法，并给出了一个流程图，逻辑很清晰：
上面put方法的实现中用到了一个很重要的方法resize(),这个方法的作用是当hashmap集合中的元素已经超过最大承载容量时，则对hashmap进行容量扩充。最大装载容量threshold=capacity*loadFactor,这个值一般小于数组的长度，下面看一下这个方法的实现过程：
1//初始化或者是扩展table的容量，table的容量时按照2的指数增长的，当扩大table容量时，元素的hash值以及位置可能发生改变4finalNode[] resize() {5Node[] oldTab = table;6//计算当前哈希表 table数组长度7intoldCap = (oldTab ==null) ?0: oldTab.length;8//当前阈值（装载容量=数组长度*装载因子）9intoldThr = threshold;10intnewCap, newThr =0;11//如果table数组长度大于012if(oldCap >0) {13//table数组长度大于等于hashmap默认的最大值： 2的30次方14if(oldCap >= MAXIMUM_CAPACITY) {15//扩充为为int型最大值16threshold = Integer.MAX_VALUE;17returnoldTab;18}19//如果table数据长度>=初始化长度（16） 而且 扩展1倍也小于默认最大长度：2的30次方20elseif((newCap = oldCap <<1) < MAXIMUM_CAPACITY &&21oldCap >= DEFAULT_INITIAL_CAPACITY)22// threshold 阈值扩大一倍23newThr = oldThr <<1;// double threshold24}25//如果原先的装载容量>0,直接将新容量赋值为 原先的装载容量oldThr->oldThreshold26elseif(oldThr >0)// initial capacity was placed in threshold27newCap = oldThr;28else{// zero initial threshold signifies using defaults29//原先的阈值oldThr< =0 而且table长度也=0，这说明hashmap还未初始化，执行初始化30newCap = DEFAULT_INITIAL_CAPACITY;//数组长度赋值1631newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//32}33//计算新的阈值上限34if(newThr ==0) {35floatft = (float)newCap * loadFactor;36newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?37(int)ft : Integer.MAX_VALUE);38}39//更新为新的阈值40threshold = newThr;41//重新分配table容量42@SuppressWarnings({"rawtypes","unchecked"})43Node[] newTab = (Node[])newNode[newCap];44table = newTab;45//把原先table中的复制到新的table中46if(oldTab !=null) {47for(intj =0; j < oldCap; ++j) {48Node e;49if((e = oldTab[j]) !=null) {50oldTab[j] =null;51if(e.next==null)52newTab[e.hash & (newCap -1)] = e;53elseif(einstanceofTreeNode)54((TreeNode)e).split(this, newTab, j, oldCap);55else{// preserve order56Node loHead =null, loTail =null;57Node hiHead =null, hiTail =null;58Nodenext;59do{60next= e.next;61if((e.hash & oldCap) ==0) {62if(loTail ==null)63loHead = e;64else65loTail.next= e;66loTail = e;67}68else{69if(hiTail ==null)70hiHead = e;71else72hiTail.next= e;73hiTail = e;74}75}while((e =next) !=null);76if(loTail !=null) {77loTail.next=null;78newTab[j] = loHead;79}80if(hiTail !=null) {81hiTail.next=null;82newTab[j + oldCap] = hiHead;83}84}85}86}87}88returnnewTab;89}
给大家推荐一个Java技术交流学习群：855355016，欢迎大家加入，群内会有架构视频、笔记、源码等资料。
Hashmap的扩容机制主要实现步骤：
如果当前数组为空，则初始化当前数组（长度16，装载因子0.75）
如果当前数组不为空，则将当前数组容量扩大一倍，同时将阈值（threshold）也扩大一倍，然后将之前table素组中值全部复制到新的table中
get(Object key)
通过key获取对应的value，实现逻辑：根据key计算hash值，通过hash值和key从hashmap中检索出唯一的结果并返回。
点击链接加入群聊【Java进阶高级架构群】：https://jq.qq.com/?_wv=1027&k=59j7tEd
1publicVget(Object key){2Node e;3return(e = getNode(hash(key), key)) ==null?null: e.value;4}5//hash:key对应的hash值6//key:键值对的key7final NodegetNode(inthash, Object key){8Node[] tab; Node first, e;intn; K k;910if((tab = table) !=null&& (n = tab.length) >0&&11(first = tab[(n -1) & hash]) !=null) {// tab[(n - 1) & hash]12// 根据hash值计算出table中的位置,如果该位置第一个节点 key 和 hash值都和传递进来的参数相等，则返回该Node13if(first.hash == hash &&// always check first node14((k = first.key) == key || (key !=null&& key.equals(k))))15returnfirst;16//该键值对在hash表(n - 1) & hash索引处，但是不是第一个节点，多以遍历该链表（也可能是红黑树），不管是链表还是树，顺藤摸瓜就对了17if((e = first.next) !=null) {18//如果是红黑树，则遍历树型结构19if(first instanceof TreeNode)20return((TreeNode)first).getTreeNode(hash, key);21//不是树，遍历链表22do{23if(e.hash == hash &&24((k = e.key) == key || (key !=null&& key.equals(k))))25returne;26}while((e = e.next) !=null);27}28}29returnnull;30}3132//计算hash值33staticfinalinthash(Object key){34inth;35return(key ==null) ?0: (h = key.hashCode()) ^ (h >>>16);36}
get方法逻辑并没有什么难懂得地方，但是过程中有两个地方需要额外注意一下：
tab[(n - 1) & hash])： 根据hash值计算元素位置，其中n为hashmap中table数组长度，这里使用(n-1)&hash的方式计算索引位置，简单解释一下这个含义，hashmap中数组的大小总是2的指数值，这种特殊的情况之下(n-1)&hash等同于hash%n取模运算结果，并且使用(n-1)&hash位运算的方式效率上也高于取模运算。
hash(key)：计算hash值，这个函数并不是直接通过hashCode()获取hash值，而是做了一步位运算(h = key.hashCode()) ^ (h >>> 16)，即将hashcode的高16为与低16位异或运算，为什么这么做呢？因为hashcode()返回的是一个32位的int类型数值，将该数值的高16位与低16位做异或运算主要是想让高位数据参与运算，增加hash值得随机性
网友评论