HashMap源码分析

基于jdk8

先来一张HashMap的结构图

Map是"key-value键值对"接口

AbstractMap实现了"键值对"的通用函数接口

HashMap的基本参数

/**     * 初始化容量16     */    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16    /**     * 容量最大值     */    static final int MAXIMUM_CAPACITY = 1 << 30;    /**     * 加载因子到75%的时候扩充     */    static final float DEFAULT_LOAD_FACTOR = 0.75f;    /**     * 链表长度大于8的时候转换成红黑树     */    static final int TREEIFY_THRESHOLD = 8;    /**     * 链表长度小于6的时候重新转换成链表     */    static final int UNTREEIFY_THRESHOLD = 6;    /**     * 当哈希表中的容量大于这个值时，表中的桶才能进行树形化     * 否则桶内元素太多时会扩容，而不是树形化     * 为了避免进行扩容、树形化选择的冲突，这个值不能小于4*TREEIFY_THRESHOLD     */    static final int MIN_TREEIFY_CAPACITY = 64;    //第一次使用是初始化，数组长度总是2的幂次    transient Node
    
     [] table;    //集合的长度    transient int size;    //修改次数  增删改的次数    transient int modCount;    //长度大于threshold 的时候进行扩充     int threshold;    //初始化容量    final float loadFactor;复制代码

//构成链表的基本元素static class Node
    
      implements Map.Entry
     
       {      final int hash;      final K key;      V value;      Node
      
        next;}复制代码

//构成红黑树的基本结构元素static final class TreeNode
    
      extends LinkedHashMap.Entry
     
       {      TreeNode
      
        parent; //父亲节点    TreeNode
       
         left;   //左儿子节点     TreeNode
        
          right;  //右儿子节点      TreeNode
         
           prev; //前方节点 boolean red; //是否是红色 }复制代码

HashMap的数据结构

采用数组加链表的方式存储,在jdk1.8中当链表长度达到8的时候会把链表转换成红黑树

红黑树

红黑树就是一种平衡的二叉查找树

二叉查找树

二叉查找树的特性

左子树上所有的节点的值均小于或等于他的根节点的值

右子数上所有的节点的值均大于或等于他的根节点的值

左右子树也一定分别为二叉排序树

下图就是个典型的二叉树

二叉树有什么好处呢? 假如我们要查找8

从跟节点9开始 8小于9 根据二叉树的特性找到5

8大于2 找到 7

8大于7找到 8

三步就找到需要查找的节点了如何是用链表呢需要从1一直找到8

但是这种二叉树也是有缺点的看下图

如果根节点足够大，那是不是“左腿”会变的特别长，也就是说查找的性能大打折扣，几乎就是线性查找了

那有没有好的办法解决这个问题呢？解决这种多次插入新节点而导致的不平衡？这个时候红黑树就登场了。

红黑树就是一种平衡的二叉查找树，说他平衡的意思是他不会变成“瘸子”，左腿特别长或者右腿特别长。除了符合二叉查找树的特性之外，还具体下列的特性：

节点是红色或者黑色

根节点是黑色

每个叶子的节点都是黑色的空节点（NULL）

每个红色节点的两个子节点都是黑色的。

从任意节点到其每个叶子的所有路径都包含相同的黑色节点。

下图就是个典型的红黑树

当插入和删除节点，就会对平衡造成破坏，这时候需要对树进行调整，从而重新达到平衡。那什么情况下会破坏红黑树的规则呢？

向原来的红黑树插入值为14的新节点，由于父节点15是黑色节点，所以这种情况没有破坏结构，不需要做任何的改变。

向原树插入21呢？，看下图

由于父节点22是红色节点，因此这种情况打破了红黑树的规则4，必须作出调整。那么究竟该怎么调整呢？有两种方式【变色】和【旋转】分为【左旋转】和【右旋转】。

这些在HashMap中都有实现

继续回到源码中先来看下put方法

put源码分析

put

public V put(K key, V value) {      return putVal(hash(key), key, value, false, true);  }复制代码

由此可见 put只是方便使用的具体实现都在putVal中

我们先看下 hash(key) 方法的实现

hash

static final int hash(Object key) {      int h;      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);  }复制代码

如果key为空，那么hash值置为0。HashMap允许null作为键，虽然这样，因为null的hash值一定是0，而且null==null为真，所以HashMap里面最多只会有一个null键。而且这个null键一定是放在数组的第一个位置上。但是如果存在hash碰撞，该位置上形成链表了，那么null键对应的节点就不确定在链表中的哪个位置了（取决于插入顺序，并且每次扩容其在链表中的位置都可能会改变）。

如果key是个不为空的对象，那么将key的hashCode值h和h无符号右移16位后的值做异或运算，得到最终的hash值。

从代码中目前我们可确定的信息是：hashCode值（h）是计算基础，在h的基础上进行了两次位运算（无符号右移、异或）

putVal

/**     * @param hash key的hash值     * @param key 键     * @param value 值     * @param onlyIfAbsent 设为true表示如果键不存在，才会写入值。     * @param evict evict参数用于LinkedHashMap中的尾部操作，这里没有实际意义。     * @return 返回value     */    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                   boolean evict) {        Node
    
     [] tab; Node
     
       p; int n, i; // 定义元素数组、当前元素变量        // 如果当前Map的元素数组为空 或者 数组长度为0，那么需要初始化元素数组        // tab = resize() 初始化了元素数组，resize方法同时也可以实现数组扩容，可参见：resize方法解析        if ((tab = table) == null || (n = tab.length) == 0)                 n = (tab = resize()).length; // n 设置为 数组长度        // 根据hash值和数组长度取摸计算出数组下标        if ((p = tab[i = (n - 1) & hash]) == null)  // 如果该位置不存在元素，那么创建一个新元素存储到数组的该位置。            tab[i] = newNode(hash, key, value, null); // 此处单独解析        else { // 如果该位置已经存在元素，说明有以下情况            Node
      
        e; K k; // e 用来指向根据key匹配到的元素            // 如果要写入的key的hash值和当前元素的key的hash值相同，并且key也相等            if (p.hash == hash &&                ((k = p.key) == key || (key != null && key.equals(k))))                e = p; // 用e指向到当前元素            // 如果要写入的key的hash值和当前元素的key的hash值不同，或者key不相等，说明不是同一个key，要通过其他数据结构来存储新来的数据            else if (p instanceof TreeNode)                e = ((TreeNode
       
        )p).putTreeVal(this, tab, hash, key, value); // 参见：putTreeVal方法解析            else { // 运行到这里，说明采用链表结构来存储                for (int binCount = 0; ; ++binCount) {  // 要逐一对比看要写入的key是否和链表上的某个key相同                    if ((e = p.next) == null) { // 如果当前元素没有下一个节点                        // 根据键值对创建一个新节点，挂到链表的尾部                        p.next = newNode(hash, key, value, null);                        //  如果链表上元素的个数已经达到了阀值（可以改变存储结构的临界值），                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                            // 将该链表上所有元素改为TreeNode方式存储（是为了增加查询性能，元素越多，链表的查询性能越差） 或者 扩容                            treeifyBin(tab, hash); // 参见：treeifyBin方法解析                        break;// 跳出循环，因为没有可遍历的元素了                    }                    // 如果下一个节点的 hash值和key值都和要写入的hash 和 key相同                    if (e.hash == hash &&                        ((k = e.key) == key || (key != null && key.equals(k))))                        break;    // 跳出循环，因为找到了相同的key对应的元素                    p = e;                }            }            if (e != null) { // 说明找了和要写入的key对应的元素，根据情况来决定是否覆盖值                V oldValue = e.value; // 旧值                if (!onlyIfAbsent || oldValue == null)    // 如果旧值为空  后者  指定了需要覆盖旧值，那么更改元素的值为新值                    e.value = value;                afterNodeAccess(e); // 元素被访问之后的后置处理， LinkedHashMap中有具体实现                return oldValue; // 返回旧值            }        }        // 执行到这里，说明是增加了新的元素，而不是替换了老的元素，所以相关计数需要累加        ++modCount; // 修改计数器递增        // 当前map的元素个数递增        if (++size > threshold) // 如果当前map的元素个数大于了扩容阀值，那么需要扩容元素数组了            resize(); // 元素数组扩容        afterNodeInsertion(evict); // 添加新元素之后的后后置处理， LinkedHashMap中有具体实现        return null; // 返回空    }// resize方法解析        if ((tab = table) == null || (n = tab.length) == 0)                 n = (tab = resize()).length; // n 设置为 数组长度        // 根据hash值和数组长度取摸计算出数组下标        if ((p = tab[i = (n - 1) & hash]) == null)  // 如果该位置不存在元素，那么创建一个新元素存储到数组的该位置。            tab[i] = newNode(hash, key, value, null); // 此处单独解析        else { // 如果该位置已经存在元素，说明有以下情况            Node
        
          e; K k; // e 用来指向根据key匹配到的元素            // 如果要写入的key的hash值和当前元素的key的hash值相同，并且key也相等            if (p.hash == hash &&                ((k = p.key) == key || (key != null && key.equals(k))))                e = p; // 用e指向到当前元素            // 如果要写入的key的hash值和当前元素的key的hash值不同，或者key不相等，说明不是同一个key，要通过其他数据结构来存储新来的数据            else if (p instanceof TreeNode)                e = ((TreeNode
         
          )p).putTreeVal(this, tab, hash, key, value); // 参见：putTreeVal方法解析 else { // 运行到这里，说明采用链表结构来存储 for (int binCount = 0; ; ++binCount) { // 要逐一对比看要写入的key是否和链表上的某个key相同 if ((e = p.next) == null) { // 如果当前元素没有下一个节点 // 根据键值对创建一个新节点，挂到链表的尾部 p.next = newNode(hash, key, value, null); // 如果链表上元素的个数已经达到了阀值（可以改变存储结构的临界值）， if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st //此时链表已经有至少9个节点了(binCount>=7，说明已经遍历了至少8次，p至少已经至少到了第8个节点，因为新的节点已经挂到p的后面了，所以链表当前至少9个节点了。这里面判断用了>=，个人理解是一种必须的防御式判断，因为由于并发问题是有可能会导致超出8个的情况的) // 将该链表上所有元素改为TreeNode方式存储（是为了增加查询性能，元素越多，链表的查询性能越差） 或者 扩容。 treeifyBin(tab, hash); // 参见：treeifyBin方法解析 break;// 跳出循环，因为没有可遍历的元素了 } // 如果下一个节点的 hash值和key值都和要写入的hash 和 key相同 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; // 跳出循环，因为找到了相同的key对应的元素 p = e; } } if (e != null) { // 说明找了和要写入的key对应的元素，根据情况来决定是否覆盖值 V oldValue = e.value; // 旧值 if (!onlyIfAbsent || oldValue == null) // 如果旧值为空 后者 指定了需要覆盖旧值，那么更改元素的值为新值 e.value = value; afterNodeAccess(e); // 元素被访问之后的后置处理， LinkedHashMap中有具体实现 return oldValue; // 返回旧值 } } // 执行到这里，说明是增加了新的元素，而不是替换了老的元素，所以相关计数需要累加 ++modCount; // 修改计数器递增 // 当前map的元素个数递增 if (++size > threshold) // 如果当前map的元素个数大于了扩容阀值，那么需要扩容元素数组了 resize(); // 元素数组扩容 afterNodeInsertion(evict); // 添加新元素之后的后后置处理， LinkedHashMap中有具体实现 return null; // 返回空 }复制代码