前言

文章仅是笔者个人的学习笔记，存在一些只有笔者个人能看到的用词或者描述，如果有不明确的地方，欢迎留言，理性讨论。

一、概述

1. HashMap是Map的一种，它的继承结构如下：

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable{
...
}

2. Map是一种多对多的结构，Java里面的Map是Key-value结构，由于可以使用泛型，所以实际也能做到多对多。
   • 所谓Key-Value，在HashMap中的具体存在形式，就是Entry 对象(同时包含了 Key 和 Value)。
   • 同时注意，包括Map和List在内的所有容器，它们存的都是引用对象，也就是实际对象的地址数据。
3. 以上继承和实现需要注意：
   • Cloneable：表明可以实现clone方法
   • AbstractMap：基本上Map都会继承它，它完成了Map类型集合的骨干方法

二、基础的哈希知识

• 哈希和拉链法

  • 哈希的定义：Hash 就是把任意长度的输入(又叫做预映射， pre-image)，通过哈希算法，变换成固定长度的输出(通常是整型)
  • 拉链法：
    • 数组的特点是：寻址容易，插入和删除困难；
    • 链表的特点是：寻址困难，插入和删除容易
    • 结合两者优点，数组+链表+哈希 = 拉链法：

  

  • HashMap使用的就是拉链法，它的底层实现还是数组。
    • 数组的每一项都是一条链。
    • 其中参数initialCapacity 就代表了该数组的长度，也就是桶的个数。

• 链表与红黑树

  • 在jdk1.8之前使用的就是纯拉链法，在jdk1.8开始，链的长度如果>=8，会转换成红黑树。
  • 关于红黑树，可以去看 TreeMap 探究 ，TreeMap 实现就是红黑树，里面解析了一些红黑树的知识。

• 哈希位置定位

  • 不管增加、删除、查找键值对，定位到哈希桶数组的位置都是很关键的第一步。
  • 先看源码：

// 代码1
static final int hash(Object key) { // 计算key的hash值
    int h;
    // 1.先拿到key的hashCode值; 2.将hashCode的高16位参与运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 代码2
int n = tab.length;
// 将(tab.length - 1) 与 hash值进行&运算
int index = (n - 1) & hash;

  - ~~（这部分算法感觉可以单独写一篇来学了，实际原理有点复杂啊~~
  - 不行，就是干！冲就完事了，一定要搞懂

• 步骤1：拿到key的hashCode值
• 步骤2：将hashCode的高位参与运算，重新计算hash值
  • 这里首先要说一下，求取hash值对应的数组位置（桶位置），在java里面用的是 & 的方法，也就是位运算。没有用 % 的方法，也就是取余，是因为取余的开销是远大于位运算的（相当于要做大数除法，这还是比较好理解的）
  • hashCode() 是int类型，取值范围是非常大的（int的最大值-最小值），只要哈希函数映射的比较均匀松散，碰撞几率是很小的。
  • 由于存放的数组本身长度是有限的，远小于hashCode() 的数量，且如上文所说，求取桶位置的方法是位运算，这就导致只有 hash 值的低位会参与运算，那么就算 hashCode() 取的很完美，最后得到相同 Index 几率也是会大大增加的。
  • 在jdk 1.8 以下，会通过 扰动方法 ，对 hasd值 多次进行右移，以使得低位的数据尽可能不同
  • 在jdk 1.8以上，会通过将高位数据与低位数据异或的方式，让hash值高低位都参与运算，从而增加随机性
• 步骤3：将计算出来的hash值与(table.length - 1)进行&运算
  • 这里就是上面所说的，为了减少开销，用位运算的方式得到最后的index

三、源码分析

• 构造方法：
  • HashMap(int initialCapacity, float loadFactor)：自定义属性的构造方法（默认构造方法其实和它是一样的，只是使用默认值）

//以下是 jdk 1.8 以下的方法！
public HashMap() {
 
        //负载因子:用于衡量的是一个散列表的空间的使用程度，默认0.75
        this.loadFactor = DEFAULT_LOAD_FACTOR; 
 
        //HashMap进行扩容的阈值，它的值等于 HashMap 的容量，默认16，乘以负载因子
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
 
        // HashMap的底层实现仍是数组，只是数组的每一项都是一条链
        table = new Entry[DEFAULT_INITIAL_CAPACITY];
 
        init();
    }

//以下是 jdk1.8的方法！
public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

  - 可以传入自定义的初始大小和负载因子，不过需要注意：
     - jdk 1.8 之前，构造方法中就进行了 数组的初始化，但是 1.8 开始，只是记录初始容量和负载因子的值，到第一次put的时候才会真正去初始化数组，等于是有懒加载的机制
     - 初始容量和负载因子对HashMap性能的影响是非常大的，对于 拉链法 的哈希表（jdk 1.7及以下是纯链表），查找一个元素的平均时间是 O(1+a)，a 指的是链的长度，是一个常数。若负载因子越大，那么对空间的利用更充分，但查找效率的也就越低

• 剩余的两个构造方法就不用多说了：
  • 一个是自定义初始大小，但是用默认的负载因子
  • 一个是传入一个已有的Map集合进行Copy然后初始化
• 扩容：resize() 方法
  • 扩容和赋值的时机与顺序问题：
    • 第一次Put的时候，会调用一次扩容，这一次其实等于是初始化，所以是先扩容后赋值
    • 第二次开始，如果触发扩容，才是真正的扩容，是先完成赋值，后扩容
  • 扩容的时候，所有的元素，包括链表/红黑树里面的，都要重新判定index位置！
    • 所以这里也会判断是否要将，红黑树–>链表（<=6），或者 链表 --> 红黑树 (>=8)
  • 扩容的步骤解析，我们假定数组为 tabel , 其大小是 n ，新数组为 newTabel ：
    • 扩容其实就是把数组 tabel 中的元素，分散映射到大小为 n*2 的 newTabel 的过程
    • 那么很显然，newTabel 的下标是包含了 tabel 的 (4包括3，8当然也包括3)，所以一部分元素是不用动的，一部分元素要移动
    • 那么这里有三个问题需要判断：
      1. 哪些元素不用移动，哪些元素要移动？
      2. 移动的偏移量是多少？
    • 扩容的方法 resize () ，主要就是解决这几个问题的：
      1. 判断是否需要移动，就是判断：元素的 hash值 & n == 0，这是因为：
         • HashMap 计算 hash值对应下标的方法是 hash值 & (n-1)
         • 例如扩容前 n = 4 的时候，n-1=3，对应的二进制为 ：011
           • 那么很显然，这时候只有 hash值的最后两位会起作用，前面的高位都被抛弃了
         • 而扩容之后 n=8 ，n-1=7，对应的二级制为：0111
           • 这时候是 hash 的后三位起作用了，多了一位，
           • 如果hash值对应的多出的这一位是 1 ，那么，它对应的 Index 就变了，变成oldIndex + n
           • 如果hash值对应的多出的这一位是 0 ，那么，它对应的 index 还是原来的值，不用变。
         • 那么如何判断 hash 值的这一位是 0 还是 1 呢？
           • 这里也很明显了，tabel 的长度 n 必然是 2的幂次方，所以 n-1 的二进制，必然比n小一位，n 和 2*n-1 的最高位是同样的
           • 例如 n =4 , 0100；2*n-1= 7，0111
         • 所以，直接用 hash值 & n == 0 ，判断需要移动还是不需要移动，是最快的。
      2. 处理需要移动的数组元素。
      3. 其实感觉现在我已经理解透彻了，要是后面又忘了，可以看下面这段解析，很详细了

    /**
     * 测试目的：理解HashMap发生resize扩容的时候对于链表的优化处理：
     * 初始化一个长度为8的HashMap，因此threshold为6，所以当添加第7个数据的时候会发生扩容；
     * Map的Key为Integer，因为整数型的hash等于自身；
     * 由于hashMap是根据hash &（n - 1）来确定key所在的数组下标位置的，因此根据公式 m（m >= 1）* capacity + hash碰撞的数组索引下标index，可以拿到一组发生hash碰撞的数据；
     * 例如本例子capacity = 8， index = 7，数据为：15，23，31，39，47，55，63；
     * 有兴趣的读者，可以自己动手过后选择一组不同的数据样本进行测试。
     * 根据hash &（n - 1）， n = 8 二进制1000 扩容后 n = 16 二进制10000， 当8的时候由后3位决定位置，16由后4位。
     *
     * n - 1 :    0111  &  index  resize-->     1111  &  index
     * 15    :    1111  =  0111   resize-->     1111  =  1111
     * 23    :   10111  =  0111   resize-->    10111  =  0111
     * 31    :   11111  =  0111   resize-->    11111  =  1111
     * 39    :  100111  =  0111   resize-->   100111  =  0111
     * 47    :  101111  =  0111   resize-->   101111  =  1111
     * 55    :  110111  =  0111   resize-->   110111  =  0111
     * 63    :  111111  =  0111   resize-->   111111  =  1111
     *
     * 按照传统的方式扩容的话那么需要去遍历链表，然后跟put的时候一样对比key，==，equals，最后再放入新的索引位置；
     * 但是从上面数据可以发现原先所有的数据都落在了7的位置上，当发生扩容时候只有15，31，47，63需要移动（index发生了变化），其他的不需要移动；
     * 那么如何区分哪些需要移动，哪些不需要移动呢？
     * 通过key的hash值直接对old capacity进行按位与&操作如果结果等于0，那么不需要移动反之需要进行移动并且移动的位置等于old capacity + 当前index。
     *
     * hash & old capacity（8）
     * n     :    1000  &  index
     * 15    :    1111  =  1000
     * 23    :   10111  =  0000
     * 31    :   11111  =  1000
     * 39    :  100111  =  0000
     * 47    :  101111  =  1000
     * 55    :  110111  =  0000
     * 63    :  111111  =  1000
     *
     * 从下面截图可以看到通过源码中的处理方式可以拿到两个链表，需要移动的链表15->31->47->63，不需要移动的链表23->39->55；
     * 因此扩容的时候只需要把loHead放到原来的下标索引j（本例j=7），hiHead放到oldCap + j（本例为8 + 7 = 15）
     *
     * @param args
     */
    public static void main(String[] args) {
        HashMap<Integer, Integer> map = new HashMap<>(8);
        for (int i = 1; i <= 7; i++) {
            int sevenSlot = i * 8 + 7;
            map.put(sevenSlot, sevenSlot);
        }
    }

• 引申：死循环问题：jdk 1.8之前HashMap扩容可能导致死循环。
  • 本质是因为HashMap是非线程安全的，同时 1.8 之前扩容之后的链表顺序会和扩容前不同，所以导致多线程操作会有严重问题。
  • 这个虽然在1.8解决了，但是 HashMap 本身还是非线程安全的，所以不要在多线程环境下使用
• 查找：
  • get(Object key)
  • 先看代码：

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
 
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // table不为空 && table长度大于0 && table索引位置(根据hash值计算出)不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {    
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k)))) 
            return first;	// first的key等于传入的key则返回first对象
        if ((e = first.next) != null) { // 向下遍历
            if (first instanceof TreeNode)  // 判断是否为TreeNode
            	// 如果是红黑树节点，则调用红黑树的查找目标节点方法getTreeNode
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 走到这代表节点为链表节点
            do { // 向下遍历链表, 直至找到节点的key和传入的key相等时,返回该节点
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;    // 找不到符合的返回空
}

• 总的来说，查找的代码是比较清晰的，分以下几步：
  • 算出传入的 target 的hash值
  • 根据hash值定位到数组的index
  • 取出对应的 Index 的数据进行判断
    • 如果是第一个 Entry 的 Key 就是 target ，那么等于直接找到了
    • 如果第一 Entry 不符合要求，那么要进行判断了
      • 如果Entry 的类型是 TreeNode ，也就是红黑树，那么调用红黑树的遍历方法去找
      • 如果Entry 的类型不是 TreeNode，那么就是链表了，顺着链条遍历一遍去找即可
  • 将找到的数据返回即可，如果找不到数据，那么就返回 null 了
• 增加
  • put(K key, V value)
  • 同样先看代码：

public V put(K key, V value) {
    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; Node<K,V> p; int n, i;
    // table是否为空或者length等于0, 如果是则调用resize方法进行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;    
    // 通过hash值计算索引位置, 如果table表该索引位置节点为空则新增一个
    if ((p = tab[i = (n - 1) & hash]) == null)// 将索引位置的头节点赋值给p
        tab[i] = newNode(hash, key, value, null);
    else {  // table表该索引位置不为空
        Node<K,V> e; K k;
        if (p.hash == hash && // 判断p节点的hash值和key值是否跟传入的hash值和key值相等
            ((k = p.key) == key || (key != null && key.equals(k)))) 
            e = p;  // 如果相等, 则p节点即为要查找的目标节点，赋值给e
        // 判断p节点是否为TreeNode, 如果是则调用红黑树的putTreeVal方法查找目标节点
        else if (p instanceof TreeNode) 
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {	// 走到这代表p节点为普通链表节点
            for (int binCount = 0; ; ++binCount) {  // 遍历此链表, binCount用于统计节点数
                if ((e = p.next) == null) { // p.next为空代表不存在目标节点则新增一个节点插入链表尾部
                    p.next = newNode(hash, key, value, null);
                    // 计算节点是否超过8个, 减一是因为循环是从p节点的下一个节点开始的
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);// 如果超过8个，调用treeifyBin方法将该链表转换为红黑树
                    break;
                }
                if (e.hash == hash && // e节点的hash值和key值都与传入的相等, 则e即为目标节点,跳出循环
                    ((k = e.key) == key || (key != null && key.equals(k)))) 
                    break;
                p = e;  // 将p指向下一个节点
            }
        }
        // e不为空则代表根据传入的hash值和key值查找到了节点,将该节点的value覆盖,返回oldValue
        if (e != null) { 
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e); // 用于LinkedHashMap
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold) // 插入节点后超过阈值则进行扩容
        resize();
    afterNodeInsertion(evict);  // 用于LinkedHashMap
    return null;
}

• 梳理步骤如下：
  • 算出传入的 Key 的hash值
  • 判断当前数组是否为空或者大小是0，是的话进行初始化
    • 需要注意，这里包括下面的代码有很多的在 if() 判断中进行赋值的操作，这个做法是不规范的
  • 根据hash值定位到数组的index
  • 取出对应的 Index 的数据进行判断
    • 如果数据为Null，说明当前put的数据，是这个 index 的第一个数据，直接 new 一个新的节点，并将值赋给新的这个节点。
      • 这时候要判断，新增一个数组元素后，数组元素的个数，如果超出阈值（概述中有说），那么就要resize，扩大数组的容量。
      • 因为没有旧值，所以返回的旧值是 Null。
    • 如果不是 Null， 证明数组要加入新的一个item了，按以下流程做出判断：
      • 如果数据是 TreeNode，那么证明当前的 index 数据达到8个已经转成红黑树了，调用红黑树查找并加入子节点的方法，并持有最终的节点的对象 e
      • 其他情况就是对应数据是链表，这时候要做以下操作
        • 遍历链表去找是否有对应key的节点
        • 如果到链表尾部都没找到，那么就新建一个节点 e ，新建之后注意要判断当前链表的长度，如果长度已经是7了（加入新节点就=8了），那么要把链表转成红黑树。
          • 这里会校验数组是否为空，或者长度小于转树的最小长度64，如果是则调用resize方法进行扩容。原因应该是要转成树了，数组长度还这么短，那么说明可能是数组太小了，导致碰撞的概率很高，所以要扩容。
        • 如果中途找到了，那么同样是持有找到的这个节点对象 e，跳出循环
      • 最后判断 e 是否非空，非空代表找到已有节点/插入新节点成功了，这时候将put 传入的value 赋值给 e.value，然后将旧值返回。
  • 至此，完成put的流程
• 删除
  • remove(Object key)
  • 再次看代码：

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}
 
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    // 如果table不为空并且根据hash值计算出来的索引位置不为空, 将该位置的节点赋值给p
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        // 如果p的hash值和key都与入参的相同, 则p即为目标节点, 赋值给node
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {    // 否则向下遍历节点
            if (p instanceof TreeNode)  // 如果p是TreeNode则调用红黑树的方法查找节点
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {    // 遍历链表查找符合条件的节点
                	// 当节点的hash值和key与传入的相同,则该节点即为目标节点
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;	// 赋值给node, 并跳出循环
                        break;
                    }
                    p = e;  // p节点赋值为本次结束的e
                } while ((e = e.next) != null); // 指向像一个节点
            }
        }
        // 如果node不为空(即根据传入key和hash值查找到目标节点)，则进行移除操作
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) { 
            if (node instanceof TreeNode)   // 如果是TreeNode则调用红黑树的移除方法
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            // 走到这代表节点是普通链表节点
            // 如果node是该索引位置的头结点则直接将该索引位置的值赋值为node的next节点
            else if (node == p)
                tab[index] = node.next;
            // 否则将node的上一个节点的next属性设置为node的next节点, 
            // 即将node节点移除, 将node的上下节点进行关联(链表的移除)    
            else 
                p.next = node.next;
            ++modCount; // 修改次数+1
            --size; // table的总节点数-1
            afterNodeRemoval(node); // 供LinkedHashMap使用
            return node;	// 返回被移除的节点
        }
    }
    return null;
}

• 步骤解析如下：
  • 首先还是算出传入的Key的hash值
  • 然后判断数组是否为空，hash值对应的数组元素是否为空
    • 很明显，为空就结束了，因为Map不存在该Key
  • 将hash值对应的数组元素赋值给 P，判断 P 的 Key 是否和传入的 Key 相等
  • 如果相等，那么需要移除的元素就直接找到了，赋值给 node
  • 如果不相等，那么要查找一下了：
    • 如果P是TreeNode，那么证明链表已经转成红黑树了，调用红黑树的查找方法，将返回值赋值给node
    • 如果不是，则当前结构是链表，遍历链表查找符合的元素，将找到的值赋值给node
  • 完成上述查找流程之后，判断node的属性
    • 如果node为空，那么当前map中没有对应元素，直接返回null，方法结束
    • 如果node是TreeNode，那么调用红黑树的remove方法，把这个节点remove掉。
      • 要维持红黑树的特性，各种左旋右旋什么的。
      • 需要注意，这里也包含一个红黑树长度判断，是否要转成链表，看下面这段代码
      • 上面这个得说明，这里看起来只是一个兜底的判断，实际触发概率应该很小

final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                          boolean movable) {
	// 链表的处理start
    // ...代码省略...
    
    // 如果root的父节点不为空, 则将root赋值为根结点
    // (root在上面被赋值为索引位置的头结点, 索引位置的头节点并不一定为红黑树的根结点)
    if (root.parent != null)
        root = root.root();
    // 通过root节点来判断此红黑树是否太小, 如果是则调用untreeify方法转为链表节点并返回
    // (转链表后就无需再进行下面的红黑树处理)
    if (root == null || root.right == null ||
        (rl = root.left) == null || rl.left == null) {
        tab[index] = first.untreeify(map);  // too small
        return;
    }
    // 链表的处理end
    
    // 以下代码为红黑树的处理, 上面的代码已经将链表的部分处理完成
    // 上面已经说了this为要被移除的node节点,
    // 将p赋值为node节点,pl赋值为node的左节点,pr赋值为node的右节点
    // ...代码省略...
}

        - 红黑树不是节点数量小于8就立马又变成链表的，这个应该很好理解，等于是有个缓冲区！
     - 如果node不是TreeNode，那么就用链表的删除方法即可，这个是很简单的，直接改指针的指向就行。
  - 最后结束流程，返回被删除的节点node的value值。

• 修改：这个应该不用说了，HashMap里面存的是对象的引用。
  • 通过get方法拿到对象的引用之后，直接修改对象就行了。
  • 或者通过put方法修改对应的Value值也可以。
    

四、总结

• HashMap，底层实现就是数组，不过数组的元素，是链表或者红黑树，因此如概述中所说，它是数组+链表/红黑树的结合体。
• HashMap的 hash算法：
  • 计算Key对应的hash值
  • 定位hash值对应的数组元素的index
• HashMap 判断数组中元素的属性
  • 链表 --> 走链表的相关 增、删、查 方法
    • 注意新加入值保存在链表的尾部（JDK1.7保存在首部）
  • 红黑树 --> 走红黑树相关的 增、删、查 方法
• HashMap 增、删、扩容时，链表和红黑树要处理相互转换的情况：
  • 链表长度 >8 --> 转成红黑树
    • 如果转成红黑树时候，数组长度 <64，会触发扩容
  • 红黑树节点数过少
    • 看源码，remove是通过判断根节点的左右子树情况来判断的，应该是<4，（来自8.16的yyj：这个应该只是兜底判断吧，实际几率是很小的。
    • 而扩容的时候，是通过阈值来判断的，<=6
    • –> 转成链表
• HashMap 的数组的初始化，实际是在第一次 put 之后实现的。
  • 初始化时会将此时的threshold值（构造方法传入的 capacity值）作为新表的capacity值。
  • 然后用capacity和loadFactor计算新表的真正threshold值。
• HashMap 的扩容方法：
  • 扩容其实就是把 tabel 中的元素，分散映射到大小为 n*2 的 newTabel 的过程
  • 判断是否需要移动，就是判断：元素的 hash值 & n == 0
    • 如果等于0，则不用移动，保持原位置
    • 如果不等于0，那么就要移动到 oldIndex + n 的位置上去
  • 当然，如果达到最大容量了，也就是 Integer.MAX 了，那就不能扩容了，这个也是很显然的。
    

五、引用

• HashMap 解析（JDK 1.8）
• HashMap 原码及扩容机制详解