HashMap

一、基础概念

在JDK8及以后的版本中，HashMap引入了红黑树结构，其底层的数据结构变成了由数组+链表变成数组+链表和数组+红黑树

HashMap整体结构:

JDK1.8 后 HashMap的红黑树结构

红黑树的转换

参考: https://juejin.im/entry/5839ad0661ff4b007ec7cc7a
几个参数:

//一个桶的树化阈值, 当桶中元素个数超过这个值时，需要使用红黑树节点替换链表节点
static final int TREEIFY_THRESHOLD = 8;
//一个树的链表还原阈值, 当扩容时，桶中元素个数小于这个值，就会把树形的桶元素 还原（切分）为链表结构
static final int UNTREEIFY_THRESHOLD = 6;
//哈希表的最小树形化容量, 当哈希表中的容量大于这个值时，表中的桶才能进行树形化,否则桶内元素太多时会扩容，而不是树形化
//为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;

添加元素时，默认如果桶中链表个数超过7，链表会尝试转换成红黑树：

// 如果HashMap容量小于64，会选择扩容而不是直接将其转变成红黑树
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) {
            resize();
}
// TREEIFY_THRESHOLD 默认为8
if (binCount >= TREEIFY_THRESHOLD - 1) {
    treeifyBin(tab, hash);
}

当调用risize方法()扩容时，如果当前桶中元素结构是红黑树，并且元素个数小于链表还原阈值 UNTREEIFY_THRESHOLD （默认为 6），就会调用split()方法把桶中的树形结构缩小或者直接还原（切分）为链表结构:

if (lc <= UNTREEIFY_THRESHOLD) {
    tab[index] = loHead.untreeify(map);
}

二、HashMap的默认参数理解

为什么HashMap的Entry数组长度默认为16呢?为什么数组长度一定要是2的n次幂呢？

首先看HashMap计算hashcode的方法获取存储的位置方法：

static int indexFor(int h, int length) {
    return h & (length-1);
}

长度16或者其他2的幂,length - 1的值是所有二进制位全为1,这种情况下,index的结果等同于hashcode后几位的值，只要输入的hashcode本身分布均匀,hash算法的结果就是均匀的
所以：HashMap的默认长度为16和规定数组长度为2的幂,是为了降低hash碰撞的几率

HashMap扩容限制的负载因子为什么是0.75？

HashMap中扩容方式是通过新建一个长度为之前数组2倍的新的数组，然后将当前的Entry数组中的元素全部传输过去，扩容后的新数组长度为之前的2倍，所以扩容相对来说是个耗资源的操作
扩容的触发条件是: 临界值 = 数组默认的长度 x 负载因子

• 如果负载因子为0.5甚至更低的可能的话，最后得到的临时临界值明显会很小，这样的情况就会造成分配的内存的浪费，存在多余的没用的内存空间，也不满足了哈希表均匀分布的情况
• 如果负载因子达到了1的情况，也就是Entry数组存满了才发生扩容，这样会出现大量的哈希冲突的情况，出现链表过长，影响get查询数据的效率
• 因此选择了0.5~1的折中数也就是0.75，均衡解决了上面出现的情况

三、HashMap的基本操作

get 操作

/**
 * 通过 hash(key) 方法计算 key 的哈希值
 * 通过 getNode() 方法获取 node
 * 如果 node 为 null, 返回null, 否则返回 node.value
 */
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

/**
 * getNode 可以分为以下几步:
 * 1. 如果哈希表为空，或 key 对应的桶为空，返回 null
 * 2. 不为空的话，如果桶中第一个节点就和指定参数hash和key匹配上了，直接返回这个节点
 * 3. 第一个节点没匹配上的话进行后续查找:
 *  3.1、如果当前的桶采用红黑树，调用红黑树的 getTreeNode 去获取节点值
 *  3.2、 如果为链表结构，直接遍历链表查询查找
 * 4. 找到节点返回 value, 否则返回 null
 */
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 如果哈希表和 key 对应的桶不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 优化点 1: 减少不必要的查询
        // 如果桶中第一个节点就和指定参数hash和key匹配上了，直接返回这个节点
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 第一个节点没匹配上的话进行后续查找
        if ((e = first.next) != null) {
            // 如果当前的桶采用红黑树，调用红黑树的 getTreeNode 去获取节点值
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 如果为链表结构，直接遍历链表查询查找
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

put 操作

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

/**
 * putVal方法可以分为以下几个步骤
 * 1. 如果哈希表为空，调用 resize 方法创建
 * 2. 如果指定 key 值不冲突，即不存在哈希冲突的情况直接插入键值对
 * 3. 如果有冲突，找到这个冲突节点
 *  3.1 如果第一个节点就匹配了，记录起来否则继续查找下去
 *  3.2 如果当前为红黑树结构，调用 putTreeVal 方法插入
 *  3.3 如果为链表结构，循环遍历链表查找, 找到最后还没有的话利用尾插法插入节点，找到了的话记录这个节点，然后退出循环
 * 4. 找到了冲突节点的话，判断 onlyIfAbsent是否为 true, 即代表是否允许修改旧值
 * 5. HashMap修改次数modCount 和 容量大小size 自增运算 + 1, 如果 size > threshold, 即达到了 临界值，进行扩容
 *
 * @param hash 指定 key 的 hash 值
 * @param key 指定 key
 * @param value 需要插入的 value 值
 * @param e, 表示不允许替换旧值
 * @param evict 代表 HashMap 是否处于创建模式
 * @return 指定 key 存在的情况下，如果替换了旧值，返回这个值，否则返回 null，当然也有可能 value 值就是 null
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 如果哈希表为空，调用 resize 方法创建
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 如果指定 key 值不冲突，即不存在哈希冲突的情况直接插入键值对
    // (n - 1) & hash 等价于 hash % n，不过位运算更快
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 如果有冲突，找到这个冲突节点
    else {
        Node<K,V> e; K k;
        // 如果第一个节点就匹配了，记录起来否则继续查找下去
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果当前为红黑树结构，调用 putTreeVal 方法插入
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 如果为链表结构，循环遍历链表查找, 找到最后还没有的话利用尾插法插入节点
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 检查链表长度是否达到临界值，达到的话转变成红黑树结构
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 找到了的话记录这个节点，然后退出循环
                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;
            // 判断 onlyIfAbsent是否为 true, 即代表是否允许修改旧值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 判断 size 是否达到了临界值需要进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

扩容操作

/**
 * 对 table 进行初始化或者扩容，扩容的话每次都是容量翻倍，二进制计算后，原来的节点要么就在原来的位置，要么就被分配到 “原位置 + 旧容量” 这个位置
 * resize 的步骤总结:
 * 1. 计算扩容后的容量，临界值
 * 2. 更新HashMap的临界值
 * 3. 根据计算得出的扩容容量，创建新数组，然后将 HashMap 的 table 引用指向新数组
 * 4. 将旧数组的元素复制到 table 中
 */
final Node<K,V>[] resize() {
    // 新建一个 oldtab 数组保存扩容前的数组 table
    Node<K,V>[] oldTab = table;
    // 获取旧数组的长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 旧数组的临界值
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 如果旧数组容量大于0
    if (oldCap > 0) {
        // 如果旧数组容量超过最大值, 将其临界值设为整型最大值
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 如果旧数组容量大于默认容量(16)且翻倍后得到的新数组容量小于最大值，将旧数组的临界值也翻倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // 如果旧容量 <= 0, 而且临界值 > 0
    else if (oldThr > 0) // initial capacity was placed in threshold
        // 将新数组容量设为旧数组的临界值
        newCap = oldThr;
    // 如果旧容量 <= 0, 而且临界值 <= 0
    else {
        // 新容量设为默认值(16)
        newCap = DEFAULT_INITIAL_CAPACITY;
        // 新临界值设为默认容量 * 默认负载因子 (16 * 0.75) = 12
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 在上面的条件判断中，只有 oldThr > 0 时， newThr == 0
    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;
            // 用 e 记录下旧节点的值
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 如果旧 bucket 的存储冲突 hash值的结构为 红黑树
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 如果旧 bucket 的存储冲突 hash值的结构为 链表结构
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // java 7 是在 while 循环里面，单个计算好数组索引位置后，单个的插入数组中，在多线程情况下，会有成环问题
                    // java 8 是等链表整个 while 循环结束后，才给数组赋值，所以多线程情况下，也不会成环

                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 节点还在原来的位置
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 节点被分配到 “原位置 + 旧容量” 这个位置
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

四、Java中HashMap的key值要是为类对象则该类需要满足什么条件

一般使用String、Integer这样的包装类作为 key 键, 原因是:

• 这种包装类型为 final 类型, 具有不可更改性, 因此保证了 hash 值的不可更改性和计算准确性
• 内部重写了 equals(), hashcode() 方法

因此若 HashMap 中的 key 为类对象的话，需要重写 hashcode 和 equals() 方法

五、HashMap是怎么解决哈希冲突的？

解决哈希冲突的方法

解决哈希冲突的常用方法分析

开放定址法

从发生冲突的那个单元起，按照一定的次序，从哈希表中找到一个空闲的单元。然后把发生冲突的元素存入到该单元的一种方法，需要的表长度要大于等于所需要存放的元素
包括以下几种方法

• 线性探查法
  从发生冲突的单元起，依次判断下一个单元是否为空，当达到最后一个单元时，再从表首依次判断。直到碰到空闲的单元或者探查完全部单元为止
• 平方探查法
  发生冲突时，用发生冲突的单元d[i], 加上 1²、 2²等。即d[i] + 1²，d[i] + 2², d[i] + 3²…直到找到空闲单元
• 双散列函数探查法

链地址法(拉链法)

链接地址法的思路是将哈希值相同的元素构成一个同义词的单链表，并将单链表的头指针存放在哈希表的第i个单元中，查找、插入和删除主要在同义词链表中进行

再哈希法

就是同时构造多个不同的哈希函数：
Hi = RHi(key) i= 1,2,3 … k;
当H1 = RH1(key) 发生冲突时，再用H2 = RH2(key) 进行计算，直到冲突不再产生，这种方法不易产生聚集，但是增加了计算时间

六、HashMap在JDK1.7和JDK1.8中有哪些不同

• 1.8 加入了 红黑树，遍历查询时间复杂度由原来链表的 O(n) 变为 O(logn)

• 在插入数据的时候, 1.7基于头插法，这会产生逆序且环形链表死循环问题, 而1.8基于尾插法避免了这个问题，详见: jdk1.7HashMap链表成环的原因和jdk1.8的解决方案

• 扩容后数据存储位置的计算方式不一样

  1. JDK 1.7 使用hashCode() + 4次位运算 + 5次异或运算（9次扰动）

     static final int hash(int h) {
             h ^= k.hashCode();
             h ^= (h >>> 20) ^ (h >>> 12);
             return h ^ (h >>> 7) ^ (h >>> 4);
      }

  2. JDK 1.8 简化了扰动函数,只做了2次扰动 = 1次位运算 + 1次异或运算

        static final int hash(Object key) {
           int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
            // a. 当key = null时，hash值 = 0，所以HashMap的key 可为null
            // 注：对比HashTable，HashTable对key直接hashCode（），若key为null时，会抛出异常，所以HashTable的key不可为null
            // b. 当key ≠ null时，则通过先计算出 key的 hashCode()（记为h），然后 对哈希码进行 扰动处理： 按位 异或（^） 哈希码自身右移16位后的二进制
     }

七、HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标？

不直接使用hashCode(), 而选择扰动函数处理, 使得根据key生成的哈希码（hash值）分布更加均匀、更具备随机性，避免出现hash值冲突

八、HashMap、LinkHashMap 和TreeMap的差别

• 遍历 HashMap 时，其输出是无序的
• LinkedHashMap 继承自 HashMap，具有高效性，同时在 HashMap 的基础上，又在内部增加了一个链表，用以存放元素的顺序
• TreeMap实现了 SortedMap 接口，它可以对元素进行排序
• LinkedHashMap 是基于元素进入集合的顺序或者被访问的先后顺序排序，TreeMap 则是基于元素的固有顺序 (由 Comparator 或者 Comparable 确定)

九、HashMap数据丢失问题

参考: HashMap源码和多线程情况下的数据丢失的问题

十、参考链接

• Java源码分析：关于 HashMap 1.8 的重大更新