HashMap解析

说明

• 底层采用数组+链表的数据结构存储
• 默认初始16容量，每次扩容2倍，加载因子0.75（即到了最大容量的0.75倍就开始扩容，因为过大的时候hash碰撞严重
• 自定义容量会按照向上取最近2^n数量定义初始容量，如new HashMap(6)，实际初始容量为8
• 初始化时并不会直接分配数组空间，而会在第一次put的时候初始化数组
• 当链表长度超过8时，会在插入数据之后马上执行数组转红黑树（当数组长度不超过64的时候，链表长度超过8会先扩容而不会链表转红黑树）
• 扩容主要是扩容数组的长度（底层为数据的均涉及到扩容，因为数组是连续不可变的）

源码解析

Jdk8源代码

我们直接看put()方法就大致可以知道HashMap的原理了

方法的执行流程大致分为

• 计算Hash，并执行高地位异或得到均匀Hash值
• 判断是否未初始化，执行初始化
• hash取模得到数组位置
• 插入数据
  • 判断数组是否有值，没有值直接插入
  • 判断子节点是否有值，没有直接插入
  • 判断子节点是链表还是红黑树，
    • 红黑树：按照红黑树插入，
    • 链表
      • 通过while循环判断子节点是否有key、是否匹配当前key、是否到了末尾插入
      • 判断是否需要转红黑树
    • （红黑树链表插入）
• 判断是否需要扩容

计算Hash

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

1. 得到通过h=key.hashCode()方法计算key的hashcode的值，
2. h >>> 16
   通过计算出的hashcode的值向右移动16位，使原有的hashcode的值的高16位变低16位，高16位则统一都变为0。这样做的好处是，可以将hashcode高位和低位的值进行混合做异或运算，而且混合后，低位的信息中加入了高位的信息，这样高位的信息被变相的保留了下来。掺杂的元素多了，那么生成的hash值的随机性会增大。
   异或运算：(h = key.hashCode()) ^ (h >>> 16)

   说明	2进制
   原来的hashCode	1111 1111 1111 1111 0100 1100 0000 1010
   移位后的hashCode	0000 0000 0000 0000 1111 1111 1111 1111
   进行异或运算结果	1111 1111 1111 1111 1011 0011 1111 0101

put 操作

// HashMap.java

public V put(K key, V value) {
    // hash(key) 计算哈希值
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; // tables 数组
    Node<K,V> p; // 对应位置的 Node 节点
    int n; // 数组大小
    int i; // 对应的 table 的位置
    //判断是不是未初始化，没初始化则初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize() /*扩容*/ ).length;
    //判断数组位置是否有值，没有则新建Node赋值
    if ((p = tab[i = (n - 1) & hash] /*获得对应位置的 Node 节点*/) == null)
        tab[i] = newNode(hash, key, value, null);

    // <3> 如果对应位置的 Node 节点非空，则可能存在哈希冲突
    //有值则需要遍历Node加入，根据链表或红黑树不一样
    else {
        Node<K,V> e; K k;
        //如果Key和数组Node的key一致，则直接替换value
        //赋值e等于当前节点
        if (p.hash == hash && // 判断 hash 值相等
            ((k = p.key) == key || (key != null && key.equals(k)))) // 判断 key 真正相等
            e = p;
        //如果是红黑树，则添加到红黑树中
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //不是红黑树则是链表，加入到链表中
        else {
            // 顺序遍历链表
            for (int binCount = 0; ; ++binCount) {
                // `(e = p.next)`：e 指向下一个节点，因为上面我们已经判断了最开始的 p 节点。
                // 如果已经遍历到链表的尾巴，则说明 key 在 HashMap 中不存在，则需要创建
                if ((e = p.next) == null) {
                    // 创建新的 Node 节点
                    p.next = newNode(hash, key, value, null);
                    // 链表的长度如果数量达到 TREEIFY_THRESHOLD（8）时，则进行树化。
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break; // 结束
                }
                //如果下一个节点与当前key相等的节点，返回找到的节点
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                //如果都没有找到，则说明此节点不匹配，继续寻找下一个节点
                p = e;
            }
        }
        //找到的节点不为空的话，则说明原来是有值的，需要替换，这里就是替换值
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // 修改节点的 value ，如果允许修改
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 节点被访问的回调
            afterNodeAccess(e);
            // 返回老的值
            return oldValue;
        }
    }
    // <4.2>
    // 增加修改次数
    ++modCount;
    // 如果超过阀值，则进行扩容
    if (++size > threshold)
        resize();
    // 添加节点后的回调
    afterNodeInsertion(evict);
    // 返回 null
    return null;
}

resize()

final Node<K, V>[] resize() {
    Node<K, V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    //如果原数组长度大于0
    if (oldCap > 0) {
        //如果原数组长度大于 1 << 30，将扩容阈值设置为 整形最大值 2<<31 -1 ，不进行扩容，将原数组返回
        //也就是说数组到了最大容量，不能继续扩了
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //扩容 新数组扩容为原数组两倍 并进行边界检测 新数组的扩容阈值也进行加倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    //如果老数组长度 <=0 并且 老数组阈值> 0 
    //（说明new HashMap的时候调用了有参构造函数, 无参构造函数 threshold是为0的），
    //将新表的大小设置为老阈值的大小
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
        //如果老数组长度 <= 0 并且 oldThr <= 0 说明调用了 Hashmap的无参构造函数， 
        //新数组容量和扩容阈值赋予默认值，分别为 16 和 12
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float) newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
                (int) ft : Integer.MAX_VALUE);
    }
    //扩容阈值更新为新数组的扩容阈值
    threshold = newThr;
    @SuppressWarnings({"rawtypes", "unchecked"})
    //开辟新数组
            Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        //进行老数组的遍历
        for (int j = 0; j < oldCap; ++j) {
            Node<K, V> e;
            //如果老数指定下标位置元素不为 null的话, 用变量e接住 ,并将其置为null
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                //如果当前位置元素没有下一个元素的话, 直接将其放入新数组中指定的位置
                //(通过 e.hash & (newCap - 1) 来计算在新数组中的位置 ,相当于  hash%newCap)
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                    //如果有下一个元素并且为红黑树节点 进行特殊的操作 ，本章节不做介绍
                else if (e instanceof TreeNode)
                    ((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
                    //如果有下一个元素并且不是红黑树节点类型的话,进行老数组元素向新数组进行拷贝
                else { // preserve order
                    // loHead  hiHead 用来记录在新数组中桶的位置   loTail  hiTail用来记录链表的尾巴节点
                    //hiHead 可以理解为高位Head 扩容后新索引位置的头  loHead可以理解为低位Head 原索引位置的头
                    Node<K, V> loHead = null, loTail = null;
                    Node<K, V> hiHead = null, hiTail = null;
                    Node<K, V> next;
                    do {
                        next = e.next;
                        //重点 (e.hash & oldCap) == 0 用来判断老数组桶中拉出来的链表 在新数组中是否还在同一个桶中，可能给会分布在两个桶中
                        //如果 == 0 说明当前元素还在原索引位置对应的拉链下 
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        //如果不为0,说明在新索引位置对应的拉链中
                        else {
                            //新索引位置处没有头结点 进行加头操作
                            if (hiTail == null)
                                hiHead = e;
                            else
                                //尾插
                                hiTail.next = e;
                            //更新尾节点
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    //将尾节点 next置null 新数组中下标元素和老数组位置对应
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    //将尾节点置null 新数组中的下标元素位置为老数组位置 + 老数组容量 (这里无需重hash 提高了效率  猜想这也是为什么数组扩容扩两倍的原因)
                    //原因下个章节讲解
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}