转载

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<K,V>[] table;
    //集合的长度

    transient int size;
    //修改次数  增删改的次数
    transient int modCount;

    //长度大于threshold 的时候进行扩充 
    int threshold;

    //初始化容量

    final float loadFactor;
复制代码

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

//构成红黑树的基本结构元素
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {  
    TreeNode<K,V> parent; //父亲节点
    TreeNode<K,V> left;   //左儿子节点 
    TreeNode<K,V> right;  //右儿子节点  
    TreeNode<K,V> 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<K,V>[] tab; Node<K,V> 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<K,V> 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<K,V>)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<K,V> 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<K,V>)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; // 返回空
    }
复制代码