JDK8源码解析 -- HashMap（一）

      最近一直在忙于项目开发的事情，没有时间去学习一些新知识，但用忙里偷闲的时间把jdk8的hashmap源码看完了，也做了详细的笔记，我会把一些重要知识点分享给大家。大家都知道，hashmap类型也是面试题百分之九十的概率会考到的一种类。如果有人想要看我在源码中的详情笔记的话，可以去我的github上面去下载看（https://github.com/javjoker/jdk8/blob/master/src/main/java/java/util/hashmap.java）。知识在于分享，进步在于学习和讨论，各取所长，这样我们才能更加高效率的学习，这样我们才能走的更远。如果有什么写的不对的地方，也希望大家指出来。在看源码中我也遇到了一些不懂的地方，如果有人知道的话也希望解扰我的困惑。

 

 

   1.hashmap的key、value可以null，并且它也不是线程安全的，它也是无序的，这些要点在hashmap源码的类头上注释部分都可以知道的。那为什么hashmap的key、value可以为null存储到hashmap中去呢？因为在hashmap的put方法没有对这两个进行null值得校验。下面图一为hashmap的putval方法，其实我们使用的put方法底层调用的就是putval方法，图二是concurrenthashmap的putval,它会先进行null的校验，key和value为空的时候会跑出异常nullpointerexception。左图为：hashmap的putval方法，有图为：concurrenthashmap的putval方法。

 

我也整理map几种子类型中哪些类的key、value可以为null，哪些不可以为null。如下：

 

 

      2.通过key值获取hashmap中的value的值，hashmap的key和穿过来的参数是通过hashcode值和equals方法比较的，如果你需要声明一个你自己的对象作为hashmap的key的话，需要重写作为key对象的生成hashcode值和equals的方法，这样我们才能通过get方法获取你想要的value的值。说到这里hashmap生成hashcode的方法太机智了，使用2的幂次掩码仅在当前掩码上方的位中变化的哈希集将始终发生冲突，它将哈希的较高位（xor）扩展为较低，向下传播较高位的影响。这样减少哈希值的碰撞次数，均匀分布在桶里面。

 

 

   3.我们着重讲hashmap的putval方法，hashmap的put方法底层调用的是putval方法，因为许多知识都会在这个方法中展现出来，如hashmap什么时候扩容？什么时候树化（hashmap其实就是node的节点数组和链表或者红黑树的形式构成的，node数组我们成为桶，数组中每个节点称为桶槽。树化这个词可以理解为将链表转化为树，链化可以认为是树转化为链表的形式）？注意jdk8之后put的新值是在链表尾部进行插入的，jdk7是在头部进行插入，在此点上面两者不同，至于为什么吗？曾看到过一篇文章说尾部插入可以防止引用链式循环，我也没有明白个所以然来，如果有谁知道的可以留言给我。下面这个图在网上找的，方便大家理解hashmap的结构是怎样的的。

 

 

 （1）我整理一下hashmap的put方法的机制    

         a.判断table是否初始化了并且length是否为零，如果未进行初始化，会去调用resize()方法进行初始化大小，用户没有手动设置容器大小（cap）会去使用默认值为16，threshold（是下次需要调整大小的值）为 cap * default_initial_capacity = 16 * 0.75 = 12，threshold是和hashmap的size进行比较大小，如果size大于threshold的值就会调用resize()方法进行扩容。resize()之后map的容量大小是原来的2倍（除了初始化的时候），原来的node节点位置可能发生变化，这里需要重新计算index的下标。我们都知道每个node的index值是根据hashcode与容量大小进行取模得到的，这里实在佩服那些大佬想出来的方法，扩容之后不需要重新计算hash值，而是只需要当前节点的hash值与扩容前的容量大小的二进制进行与运算就可以了，因为扩容的容量是原来的2倍，也就是左移一位增加一位数（二进制的时候），扩容之后就是在原来的基础上多一位数，新添加的这位数判断是0还是1就可以决定在新数组上面的位置了，0表示原位置，1表示在原来的位置上加上一个原来数组的长度（原索引+oldcap）。发生hashmap扩容后，遍历hashmap每个桶里的链表，每个链表可能会被拆分成两个链表，不需要移动的元素置入lohead为首的链表，需要移动的元素置入hihead为首的链表，lohead在新table的原来的index桶槽里面，hihead则放在新tab的（原索引+oldcap）的桶槽中。如下图：

 

 

注意如果节点类型node和treenode两者的计算方式有些不同，如果是node类型的话，说明为链表形式，但是如果treenode类型化是树形的，那么就会调用((treenode<k,v>)e).split(this, newtab, j, oldcap);这个方法，也是当前桶槽下面遍历所有的树形节点，不需要移动的元素置入lohead
为首的链表，需要移动的元素置入hihead为首的链表，计算两个链表的node大小，如果小于等于untreeify_threshold（值为6）就将树转化为链表，且类型从treenode转化为node类型，如果大于阀值的话需要进行树化。

 

 

这个treeify()方法中有一个知识点需要说明一下，treeify()方法中调用了moveroottofront(tab, root)里面是将root移动tab数组index位置插入到第一个位置，原来tab数组index位置放到root的next的位置中，而不是把需要插入index的root和tab中index位置的原来的数据一起进行
树化重排序之后插入到index的位置上面。

 

 

      b.计算当前插入值得key的hashcode值（hash(object key)），插入值得时候分一下情况：

         1）如果在hash值在tab的桶槽中没有节点，直接插入就可以了

         2）如果有节点话，又分情况，返回值为key对应的旧值（e为旧值）：

             aa.此桶槽中的第一个节点key相等的时候，判断条件p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))，这里先比较比较hash值是否相等，再进行比较key（(k = p.key) == key判断key是不是指向同一块内存， (key != null && key.equals(k)是key不指向同一块内存key不为空的时候判断值是不是相等），为true的时候把这个节点复制给e返回去

             ab.第一个节点的key不相等的时候，判断这个节点类型是treenode的时候，通过puttreeval方法将此节点转化树节点插入树中， 如果有key相等的树节点，覆盖value并返回旧的树节点，否则返回null，puttreeval()方法有一个细节，key不仅通过了

((pk = p.key) == k || (k != null && k.equals(pk)))判断是否相等，还判断key是否实现了comparable比较方法，实现了还用这个方法判断key的大小。

 

 

           ac.第一个节点的key不相等的时候，这个节点类型是node的时候，遍历此节点的下个节点，如果有key相等的节点则赋值给e，没有的话就插入到末尾，并且判断桶槽节点个数是否大于树化阀值8（treeify_threshold），大于8（其实是第九个节点进行树化，下标从0开始，新添加的节点后此次循环中计算器未加一）进行树化treeifybin方法，下图一。注意treeifybin此方法中table的length小于64（min_treeify_capacity，下图二）的时候只是进行了resize()，没有进行树化，当大于等于64的时候才把node节点转化为treenode === 》treenode<k,v> p = replacementtreenode(e, null)，再进行treeify树化。

 

                                                              图一

 

 图二

        3）e不为空的时候，说明有key相等的节点，覆盖旧值并返回

   c.执行下面的步骤说明e为空的时候，没有相等的节点，就是把这个key、value当做新增到map中去，modcount、size自增，并判断size > threshold为true就resize()大小，并返回为null

    hashmap先讲到这里，还有一些内容没有介绍，我会出第二篇关于hashmap。我怕写的内容太多了，大家不容易消化掉。大家先把上面的知识点消化消化吧，我认为上面写的每一个都是知识点。如果你去面试的话，上面每个点都可能作为考点被问到，即使没有被问到，你也可以在面试到hashmap的时候，自己进行扩展，可能面试官自己都不知道，比如说大部分的人都知道转化为链表和转化为树的阀值为6和8，但是有谁知道64这个数字呢，hashmap的size不大于等于64，桶槽下面的链表不会进行树化，只是进行扩容而已，链表转化为树的阀值是8，其实是节点为第9个的时候才会调用树化的方法。