HashMap相关

存储结构

HashMap是数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的

数组是 HashMap 的主体，链表是为了解决hash冲突而存在的，采用的是链地址法

在这里插入图片描述

当数组table中某个元素的链表长度大于8的时候，开始尝试进行树化，如果此时table.length小于64，则对数组扩容，否则对链表进行树化。（重点哦~）

简单的看完了它的存储结构，接下来看看它比较重要的一些参数

Hashmap的一些默认构造参数

 int threshold;             // 所能容纳的key-value对的最大值
 final float loadFactor;    // 负载因子
 int modCount;   //记录当前集合被修改的次数
 int size; //实际存在的键值对的数量

table的初始化长度length(默认值是16)，Load factor为负载因子(默认值是0.75)，threshold是HashMap所能容纳键值对的最大值。threshold = length * Load factor。当存在的键值对达到threshold后，进行扩容，扩容成员来的两倍。

索引计算

了解完了存储结构的一些知识点后，我们再来看看hashmap是如何确定即将添加元素应该放在数组table的哪个节点(索引)的。

首先根据node的key的值计算出hashcode的值，然后根据hashcode计算出hash值，最后通过hash&（length-1）计算得到存储的位置。看看源码的实现：

// jdk1.8
static final int hash(Object key) {   
     int h;
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    /* 
     h = key.hashCode() 为第一步：取hashCode值
     h ^ (h >>> 16)  为第二步：高位参与运算
    */
}

//取key的 hashCode 值、根据 hashcode 计算出hash值、通过取模计算下标。
if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

为什么要 hashcode 异或其右移十六位的值？

可以在数组 table 长度比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销

为什么 hash 值要与length-1相与？

这里的计算和用hash值对数组长度取模的运算时一样的，但是取模运算比与运算慢很多。

put方法

简要流程如下：

首先根据 key 的值计算 hash 值，找到该元素在数组中存储的下标；
如果数组是空的，则调用 resize 进行初始化；（第一次put的时候进行初始化）
如果没有哈希冲突直接放在对应的数组下标里；
如果冲突了，且 key 已经存在，就覆盖掉 value；
如果冲突后，发现该节点是红黑树，就将这个节点挂在树上；
如果冲突后是链表，判断该链表是否大于 8 ，如果大于 8 并且数组容量小于 64，就对数组进行扩容（resize）；如果链表节点大于 8 并且数组的容量大于 64，则将当前节点的链表转换为红黑树；

jdk1.7和1.8put方法有什么不同

①解决哈希冲突时，JDK1.7 只使用链表，JDK1.8 使用链表+红黑树，当满足一定条件，链表会转换为红黑树。

②链表插入元素时，JDK1.7 使用头插法插入元素，在多线程的环境下有可能导致环形链表的出现，扩容的时候会导致死循环。

扩容机制

JDK1.7

使用一个容量更大的数组来代替已有的容量小的数组，transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里，并且需要重新计算数组的下标。

newTable[i] 的引用赋给了 e.next ，也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置；这样先放在一个索引上的元素终会被放到 Entry 链的尾部(如果发生了 hash 冲突的话）

JDK1.8

对比JDK1.7的优化

第一点：

resize 之后，元素的位置在原来的位置，或者原来的位置 +oldCap (原来哈希表的长度）。不需要像 JDK1.7 的实现那样重新计算所有元素的hash 。

只需要看看原来的 hash 值新增的那个bit是1还是0就好了（因为扩容是乘以2，并且是与运算，所以看新增的bit即可），如果新增的Bit是0的话索引不变，是1的话索引变成“原索引 + oldCap ”。省去了重新计算 hash 值的时间。

JDK1.7 中 rehash 的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置（头插法）。JDK1.8 不会倒置，使用尾插法。

相关问题

为什么用在长度为8的时候转换成红黑树呢？

红黑树需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要。

当元素小于 8 个的时候，此时做查询操作，链表结构已经能保证查询性能，超过8了以后，红黑树查询平均时间复杂度为o(nlogn)，查询效率更加快，所以转换成红黑树。

如果一开始就用红黑树结构，元素太少，新增效率又比较慢，浪费性能。

为什么要用红黑树呢，可以用二叉搜索树嘛？

二叉搜索树是一种节点值之间具有一定数量级次序的二叉树，对于树中每个节点：

若其左子树存在，则其左子树中每个节点的值都不大于该节点值；
若其右子树存在，则其右子树中每个节点的值都不小于该节点值。

二叉搜索树在极端情况下会变成线性结构，查找效率会退化的和链表一样o(n).

table数组扩容

static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
/*  会取大于或等于这个数的 且最近的2次幂作为 table 数组的初始容量
解释：位或( | )
int n = cap - 1; 让cap-1再赋值给n的目的是另找到的目标值大于或等于原值。例如二进制1000，十进制数值为8。如果不对它减1而直接操作，将得到答案10000，即16。显然不是结果。减1后二进制为111，再进行操作则会得到原来的数值1000，即8。
*/

用可变类当 HashMap 的 key 有什么问题?

hashcode 可能发生改变，导致 put 进去的值，无法 get 到元素。

为什么hashmap的初始长度是16

为了方便通过hash算法计算key值对应的数组下标。

**Hashmap比较基础的相关知识点就是这些了，后续再补充Currenth