HashMap源码解析，扩容机制及其思考

1.概述

HashMap是日常java开发中常用的类之一，是java设计中非常经典的一个类，它巧妙的设计思想与实现，还有涉及到的数据结构和算法，，值得我们去深入的学习。

简单来说，HashMap就是一个散列表，是基于哈希表的Map接口实现，它存储的内容是键值对 (key-value) 映射，并且键值允许为null(键的话只允许一个为null)。

1.1 注意事项

①根据键的hashCode存储数据。(String，和Integer、Long、Double这样的包装类都重写了hashCode方法，String比较特殊根据ascil码还有自己的算法计算，Double做位移运算【具体看源码的hashcode实现】，Integer，Long包装类则是自身大小int值)，

HashMap中的结构不能有基本类型，一方面是基本类型没有hashCode方法，还有HashMap是泛型结构，泛型要求包容对象类型，而基本类型在java中不属于对象。

②HashMap的存储单位是Node<k,v>,可以认作为节点。

③Hashmap中的扩容的个数是针对size(内部元素(节点)总个数)，而不是数组的个数。比如说初始容量为16，第十三个节点put进来，不管前面十二个占的数组位置如何，就开始扩容。

1.2 hashmap几个特征

2.一些概念

2.1.位运算

位运算是对整数在内存中的二进制位进行操作。

在java中 >> 表示右移 若该数为正，则高位补0，若为负数，高位补1

<<表示左移 跟右移相反 如果是正数在低位补0

例如20的二进制为0001 0100 20>>2为 0101 0000 结果为5(左高右低)

20<<2 为 0101 0000 则为80

java中>>>和>>的区别

>>>表示无符号右移，也叫逻辑右移。不管数字是正数还是负数，高位都是补0
复制代码

在hashMap源码中有很多使用位运算的地方。例如:

//之所以用1 << 4不直接用16，0000 0001 -> 0001 0000 则为16，如果用16的话最后其实也是要转换成0和1这样的二进制，位运算的计算在计算机中是非常快的，直接用位运算表示大小以二进制形式去运行，在jvm中效率更高。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;  //初始化容量
复制代码

注意:左移没有<<<运算符

2.2 位运算符-(与(&)、非(~)、,或(|)、异或(^))

①与运算(&)

我们都知道&在java中表示与操作&表示按位与，这里的位是指二进制位。都为1才为真(1),否则结果为0，举个简单的例子

System.out.println(9 & 8); //1&1=1，1&0 0&1 0&0都=0，因此1001 1000 -> 1000 输出为8
复制代码

②非运算(~)

源码 -> 取反 -> 反码 -> 加1 -> 补码 -> 取反 -> 按位非值

在Java中，所有数据的表示方法都是以补码的形式表示，如果没有特殊说明，Java中的数据类型默认是int,int数据类型的长度是8位，一位是四个字节，就是32字节，32bit.

例如5的二进制为0101

补码后为 00000000 00000000 00000000 00000101

取反后为 11111111 11111111 11111111 11111010

【因为高位为1 所以源码为负数，负数的补码是其绝对值源码取反，末尾再加1】

所以反着来末尾减1得到反码然后再取负数

末位减1：11111111 11111111 11111111 11111001

【后八位前面4位不动 后面 减1 1010减1 相当于 10-1为9 后四位就是 1001 】

取反后再负数： 00000000 00000000 00000000 00000110 为-6

System.out.println(~ 5); //输出-6
复制代码

③或运算(|)

只要有一个为1，结果为1，否则都为0

System.out.println(5 | 15); //输出为15，0101或上1111,结果为1111
复制代码

④异或运算(^)

相同为0(假)，不同为真(1)

System.out.println(5 ^ 15); //输出10 0101异或1111结果为1010
复制代码

2.3 hashcode

hash意为散列，hashcode是jdk根据对象的地址或者字符串或者数字算出来的int类型的数值，顶级父类Object类中含hashCode方法(native本地方法，是根据地址来计算值)，有一些类会重写该方法，比如String类。

重写的原因。为了保证一致性，如果对象的equals方法被重写，那么对象的hashcode()也尽量重写。

简单来说 就是hashcode()和equals()需保持一致性，如果equals方法返回true，那么两个对象的hashCode 返回也必须一样。

否则可能会出现这种情况。

假设一个类重写了equals方法，其相等条件为属性相等就返回true，如果不重写hashcode方法，那么依据就是Object的依据比较两个对象内存地址，则必然不相等，这就出现了equals方法相等但是hashcode不等的情况，这不符合hashcode的规则，这种情况可能会导致一系列的问题。

因此，在hashMap中，key如果使用了自定义的类，最好要合理的重写Object类的equals和hashcode方法。

2.4 哈希桶

哈希桶的概念比较模糊，个人理解是数组表中一块区域结果下面的单向链表组成的，在hashmap中，这个单向链表的头部是所在数组上第一个元素，单向链表如果过长超过8，那么这个"桶"就可能变成了红黑树(前提是数组长度达到64）。

2.5 hash函数

在程序设定中，把一个对象通过某种算法或者说转换机制对应到一个整形。

主要用于解决冲突的。

2.6 哈希表

也称为散列表，这也是一种数据结构，可以根据对象产生一个为整数的散列码(hashCode)。

hash冲突

HashMap之所以有那么快的查询速度，是因为他的底层是由数组实现，通过key计算散列码(hashCode)决定存储的位置，HashMap中通过key的hashCode来计算hash值，只要hashCode相同，hash值也一样，但是可能存在存的对象多了，不同对象计算出的hash值相同，这就是hash冲突。

举个例子

HashMap<String,String> map = new HashMap<String,String>();
map.put("Aa", "haha");
map.put("BB","heihei");
System.out.println("Aa".hashCode()); //2112
System.out.println("BB".hashCode()); //2112
//这里的Aa和BB为String型，String类重写了hashCode方法(根据ascil码和特定的算法来计算，虽然很巧妙但也难以避免不对对象hashCode相同的情况)，Aa和BB的hashCode值相同，相同的HashCode的hash值相同 
//根据源码就算key不相同 但key.hashCode()相同 则会返回相同的hash，导致hash冲突
static final int hash(Object key) {//取关键key的hash值
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//任何小于2的16次方的数 右移16位都为0 2的16次方>>>16刚好为1 任何一个数和0按位异或都为这个数本身(1和0为1 0和0为0)，所以这个hash()函数对于null的hash值 仅在hashcode大于2的16次方才会调整值,这边16设计的很巧妙，因为int刚好是32位的取中间位数
}
复制代码

2.7 二叉查找树和红黑树

红黑树是一种自平衡二叉查找树。是一种数据结构，又称二叉b树，（→_→ 2b树？），红黑树本质上也是二叉查找树。所以先理解下二叉查找树。

2.7.1二叉查找树

二叉查找树，又称有序二叉树，已排序二叉树
它的三大特点如下
1.左子树上所有结点的值均小于或等于它的根结点的值。
2.右子树上所有结点的值均大于或等于它的根结点的值。
3.左、右子树也分别为二叉排序树。
复制代码

二叉树.png

2.7.2 红黑树(RBTree)

由于二叉查找树可能存在难以平衡呈线性的缺陷，所以出现的红黑树的概念。顾名思义，红黑树是只有红色和黑色节点的二叉树。
它的5大性质如下。
1.节点是红色或黑色。
2.根节点是黑色。
3.每个叶子节点都是黑色的空节点（NIL节点）。
4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
复制代码

简单来说红黑树是一种自平衡二叉查找树，相比于普通的二叉查找树，它的数据结构更为复杂，但是在复杂的情况也能通过自平衡(变色，左右旋转)保持良好的性能。

关于红黑树，很形象的一组漫画，查看这里

在线模拟红黑树增删的地址地址1、 地址2

红黑树的时间复杂度为【吐槽下简书这边如果用数学公式太蛋疼了】：

O(logn)

它的高度为:[logN,logN+1]（理论上，极端的情况下可以出现RBTree的高度达到2

*

此外，由于它的设计任何不平衡将在三次旋转内解决。

红黑树和avl树(最早的自平衡二叉树)的比较：
avl更加平衡，查询速率稍强于红黑树，但是插入和删除红黑树完爆avl树，可能由于hashMap的增删也挺频繁的，所以综合考虑而选择红黑树。
复制代码

总结：红黑树是种可以通过变色旋转的自平衡二叉查找树，对于hashMap来说，使用红黑树的好处在于，当有多个元素hash相同在同一数组下标的时候，使用红黑树在查找这些hash冲突的元素更快，它的时间复杂度从遍历链表O(n)降到O(logN)。

2.8 复杂度

算法复杂度分时间复杂度和空间复杂度。

时间复杂度：执行算法所需要的计算工作量
空间复杂度：执行算法所需要内存空间大小
时间和空间都是计算机资源的体现，算法的复杂性体现在运行该算法时计算机所需资源的大小。
复制代码

这里重点讲下时间复杂度

(1)时间频度
用T(n)表示
一个算法执行所消耗的时间，理论上不能算出来而是通过运行测试得知，但不可能也没必要对每个算法都做上机测试，只需知道哪个算法花费时间多哪个花费少即可。在算法中一个算法花费的时间和这个算法执行的次数成正比。
在一个算法中，语句执行次数称为时间频度(或称为语句频度)，记做为T(n)，这里的n代表问题的规模。暂且不考虑这个T是啥，把它理解为一个函数。
(2)时间复杂度 
用Ｏ(f(n))表示
当n变化时，时间频度T(n)也会不断变化，但是它是个不确定的函数，我们想知道它呈现的规律是什么样的。这个时候引入了时间复杂度的概念。
前面说T(n)是个不确定的函数，它代表算法中基本操作重复执行的次数是问题规模n的某个函数。
假设有某个辅助函数f(n),当n趋近∞，T(n)/f(n)的极限值不为0切位常数，那么可以认为f(n)和T(n)为同一数量级的函数，记做为T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

f(n)虽然没有规定但一般都尽可能取简单的函数
例如 O(2n²+n +1) = O (3n²+n+3) = O (7n² + n) = O ( n² ) 省去了系数,只保留最高阶项。
时间频度不同时，时间复杂度有可能相同，例如T(n)=n²+3n+4与T(n)=4n²+2n+1它们的频度不同，但时间复杂度相同，都为O(n²)。

总结两者关系:时间复杂度就是对时间频度函数的一层包装，它的特点(大O表示法)为
①省去系数为1处理②保留最高项
如果把T(n)当做为一棵树，那么O(f(n))只关心其主干部分。
复制代码

常见算法的时间复杂度从小到大依次为

复杂度比较

求解算法的时间复杂度具体步骤为：
①找出算法中执行次数最多的基本语句，一般是最内层的循环体。
②计算基本语句的数量级
③将基本语句执行次数的数量级放入大O记号中
复制代码

举几个例子

O(1),又称常数阶，一般来说算法中没有循环体，执行次数为常数那么时间复杂度就为O(1)，例如

int sum = 0,n = 100; //执行一次  
sum = (1+n)*n/2; //执行一次  
System.out.println (sum); //执行一次 
//上面的算法运行次数为f(n)=3,那么根据大O表示法，该算法的时间复杂度为O(1)
复制代码

为什么O(logN)，对数阶不用底数

如红黑树的查找复杂为O(logN)

这里面有个可能存在的疑问，有时候时间复杂度都用包含O(logN)这样的描述 但是没有明确说明n的底数是多少，通常底数为2来计算

这种描述其实也是合理的，算法中log级别的时间复杂度都是由于使用了分治思想,这个底数直接由分治的复杂度决定。当n趋近于无穷大，两个大小比较也只是一个常数，所以这种时候O(logN)统一代表对数复杂度。

/lim_{n/rightarrow+/infty} Ο(/log_x{n})/Ο(/log_y{n}) = C

其它简单举例

3. HashMap的内部实现(基于jdk1.8)

刚开始看hashMap源码的时候，感觉思路很乱不知道写的啥东西，所以还是得从它的【数据结构】开始入手。

不同于一般类的数据结构，从结构来讲 HashMap = 数组 + 链表 + 红黑树(1.8开始加入，大程度的优化了HashMap的性能)
arrayList  数组
linkedList 双向链表 查询效率慢，需通过遍历，新增或删除快，比如说删除一个元素 知道那个元素的上下引用 并改变关联上下元素的引用指向即可。
复制代码

3.1 数组和链表

数组和链表.png

3.2 HashMap数据结构(数组+链表+红黑树)

在jdk8以前，如果发生频繁碰撞的话，查找时间复杂度是O(1) + O(n) (先找在数组的位置再找链表)，n如果比较大则严重影响了查找性能，而到了jdk8引入红黑树,O(1) + O(logN)。

hashmap.png

大致思路

①数组的优点是查询快，链表的优点是增删快，红黑树查询性能较好，hashMap的存储方式结合了它们的优点，那么hashMap的存储单元又可以在数组里，又可以在某个数组下的链表里。还有可能在红黑树当中。
②我们已经知道HashMap是键值对的存在，且可以为各种类型，那么它又是以键值对的方式存在，它的最小存储单位是以Node节点为存储单位。
这个Node结构大概有Key，Value，记录所在数组索引，以及记录链表指针的东西。
大概结构如下
static class Node<K,V> implements Map.Entry<K,V> {
  final int hash;
  final K key;
  V value;
  Node<K,V> next;
  ...
}

③新来的Node节点怎么放?
HashMap利用hashcode来确定存放的位置，但是又有个疑问，假设map对象key为String型
HashMap<String, String> map = new HashMap<String, String>();
map.put("1", "first");

//这个时候看put方法 
put方法的大致思路为
①对key做hash运算，通过hash值计算index下标位置
②如果没冲突直接放在桶上
③如果冲突了，以链表的形式存在桶里面，达到一定条件链表变为红黑树
④如果节点已经存在，则替换旧的value(保证唯一性)
⑤如果桶的个数超过了 加载因子乘当前容量，则做resize操作

//可以注意到有个hash函数
public V put(K key, V value) {
   return putVal(hash(key), key, value, false, true);
}

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

//上述代码String类型的1的Hashcode为49超过了HashMap的初始长度16，这个时候"1"这个key放在哪。这里
//通过巧妙的设计存放在合适的位置 4.3.3做分析
p = tab[i = (n - 1) & hash]，


//这里的p为Node<K,V>对象，n为当前哈希桶数组长度，进行与运算后，因为这是第一个插入的元素，无需扩容长度为16,那么49 & 15 = 1，说明在的第二个位置。

④新节点插入后什么时候开始扩容
接下来不断的插入的元素 经过hash函数和计算索引位置后，都可以根据它的散列性插入到不同的16个位置，
当元素个数达到16 * 0.75 即12时，继续插入新的时候，开始扩容。
【这里注意一下并不是说占满12个位置才开始扩容，而是12个节点，根据散列性分布12个节点，占...5，6，7，8...个位置都有可能,比如说key为Integer类型，假如key为Integer类型，有五个节点key分别为3，19，12，28，44这个时候3，19在同一个位置，12，28，44在同一个位置，这个时候5个节点就占了两个位置】


⑤resize()方法进行扩容操作。
1.先判断节点数组是否为空，并取它的容量(节点个数)，创建新数组，大小时新的capacity
如果不为空：
如果容量超过最大值不做扩容，否则位运算一位做容量乘2处理，
如果为空：
桶数组容量为默认容量16，即有默认放16个桶，阈值默认为默认容量乘默认加载因子 12
2.将旧数组的元素放到新数组中，重新做映射
如果旧的数组不为空，则遍历桶数组，并将键值对映射到新的桶数组中[树节点和链表节点做不同操作]
复制代码

4.源码分析

4.1 基本存储单位Node节点

static class Node<K,V> implements Map.Entry<K,V> { //实现Entry接口 存储的是键值对的映射
    final int hash; //hash值，用于记录数组所在位置
    final K key; //用于匹配
    V value; //值
    Node<K,V> next; //用于记录单链表下一节点 用于解决hash冲突(即hash值一样该存在哪里的问题)
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }
    public final V setValue(V newValue) {//赋值
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}
复制代码

4.2 HashMap中的几个重要实现：hash函数，put、get、resize

//put
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;
    //如果为空 调用resize以默认大小16扩容 
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //通过(n - 1) & hash计算存放索引位置 此处设计很巧妙
    if ((p = tab[i = (n - 1) & hash]) == null)
      //如果tab[i]为空 该下标下没有节点 则直接新建一个Node放在该位置 
        tab[i] = newNode(hash, key, value, null);
    else {
        //下标上有节点 说明有hash冲突
        Node<K,V> e; K k;
        //如果插入的新节点key已经存在，那么直接覆盖整个节点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //如果为红黑树节点
        else if (p instanceof TreeNode)
            //调用红黑树插入键值对的putTreeVal方法
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            //不管tab[index]是否为空，p节点已经为 tab[index]上
            //如果有冲突 且不为红黑树节点 那么此时遍历链表节点 binCount计算链表长度
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                   //链表长度大于等于7，调用treeifyBin对链表进行树化
                    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;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //插入成功后 再根据实际判断是否到到阈值 比如说现在容量16(桶的个数16) 正在插第13个元素时 到达则扩容 
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
复制代码

get方法

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;
    //先定位键值对在所在桶的位置
    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;
        if ((e = first.next) != null) {
            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;
}
复制代码

4.4.5 resize()

扩容就是重新定义容量，在hashmap中，如果不断的put元素，而hashMap对象中的数组无法装得下更多对象时，对象就需要进行扩容，扩大数组长度。这边注意的是：

①假如初始大小为默认值16，什么时候扩容，我们可以知道阈值是16

*

② 在java中数组是不能够自动扩容的，是采用一个新的大容量数组代替原有的小数组，就好比用一个小桶装水，如果想用一个桶装更多的水，就换一个大桶再把原来小桶的水装过去。

③扩容后，普通链表上的节点包括红黑树都得重新映射。

对于hashmap来说

什么时候换大桶：达到阈值的时候

换多大的桶：原有小桶的两倍大小

但桶的大小也是有限的，对于hashMap，最大的桶能容纳包含2^30个数，大于的话就不再扩容，就随里面碰撞了。(实际上也很难用到这么大的容量)

final Node<K,V>[] resize() {
    //table为全局变量transient Node<K,V>[] table; 赋值给oldTab
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;//旧表数组个数
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) { //如果旧容量大于0    
        //超过最大值就不扩容了，随它碰撞去吧 -。-
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //×2还没超过最大值，新数组就扩容为原来两倍 阈值也做×2处理
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold 
    }
    //如果原来的阈值 > 0且旧容量为0，则将新容量设为原来的阈值，初始化有参给threshold赋值会有此情况
    else if (oldThr > 0) 
        newCap = oldThr;
    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;
            //数组中的节点不为空
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                //如果该桶只有一个节点(说明下面没有链表，或者说只有一个链表节点)
                if (e.next == null)
                    //e.hash & (newCap - 1)确定元素存放位置
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    //红黑树节点
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { 
                    //链表节点且当前链表节点不止1个
                    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 扩容还在原来位置 如果为1 新的位置为 旧的index + oldCap 下面如何扩容有做介绍
                        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;//将链表的尾节点的next设置为空
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;// 将链表的尾节点 的next 设置为空
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
复制代码

4.3 HashMap经典代码 p = tab[i = (n - 1) & hash])

p = tab[i = (n - 1) & hash])
复制代码

当hashCode小于65536，散列是很规律的，基本上索引的位置就是

因为小于这个数右移16为都为0，且和占位符都为0的值异或后的hashcode就是自身的值。

这个值比较特殊

转换为二进制：00000000000000010000000000000000，右移16的话00000000000000000000000000000001并不全为0

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

key的hashcode为65536

转为二进制：h=key.hashCode() 00000000000000010000000000000000

跟右移16位的再做异或操作 00000000000000000000000000000001

hash = h ^(h>>>16) 00000000000000010000000000000001

​

计算hash 00000000000000010000000000000001

​ 00000000000000000000000000001111

结果 1

但是65536 % 16 = 0

key的hashcode为17 异或相同为0 不同为假

转为二进制：h=key.hashCode() 00000000000000000000000000010001

跟右移16位的再做异或操作 00000000000000000000000000000000

hash = h ^(h>>16) 00000000000000000000000000010001

计算hash 00000000000000000000000000010001

​ 00000000000000000000000000001111

​ 00000000000000000000000000000001

做个小测试，假设这个时候桶的个数为16，代码如下

for (int key = 65533; key < 65543; key++) { //从65536开始变得有点"特别"
    System.out.println("key为：" + key +  "，索引位置：" + ((key ^ (key >>> 16)) & 15));//假设初始容量为16 测试没扩容时这些数的索引位置
}
//输出结果为，可以发现从65536开始不为0而是1，有点特殊，然后相邻两个索引位置呈1,3的增长，具体可画图尝试
i为：65533，输出13
i为：65534，输出14
i为：65535，输出15
i为：65536，输出1
i为：65537，输出0
i为：65538，输出3
i为：65539，输出2
i为：65540，输出5
i为：65541，输出4
i为：65542，输出7
复制代码

这段代码主要是计算索引位置的，HashMap 底层数组的长度总是 2 的 n 次方

当 length 总是 2 的倍数时，h& (length-1)，将是一个非常巧妙的设计：

可以看到计算得到的索引值总是位于 table 数组的索引之内。并且通常分布的比较均匀

4.4 树形化treeifyBin()

在jdk8以前，如果发生频繁碰撞的话，查找时间复杂度是O(1) + O(n) (先找在数组的位置再找链表)，n如果比较大则严重影响了查找性能，而到了jdk8引入红黑树,O(1) + O(logN)。

jdk1.8中，如果一个桶中元素个数超过TREEIFY_THRESHOLD(8)时，就用红黑树替换链表以提升速度(主要是查找)

//将桶内所有链表节点换成红黑树节点
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    //如果当前哈希表为空 或者哈希表中元素 MIN_TREEIFY_CAPACITY默认为64，对于这个值可以认为，如果节点数组长度小于64，就没必要去进行结构转换，而是通过resize()操作，这样原先一个链表的元素可能会进行重新分配。
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize(); //扩容
    //大于等于64 就树化 链表上的普通节点变成树节点
    else if ((e = tab[index = (n - 1) & hash]) != null) {      
        TreeNode<K,V> hd = null, tl = null; //定义首、尾节点
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null); //普通节点 -> 树节点
            if (tl == null) //如果尾节点为空 说明还没有根节点
                hd = p; //首节点(根节点) 指向当前节点
            else { //尾节点不为空 
                p.prev = tl; //当前树节点前一个节点指向尾节点
                tl.next = p; //尾节点后一个节点 指向当前节点
            }
            tl = p; 
        } while ((e = e.next) != null); //继续遍历链表
      
        //这个时候只是把Node对象变成TreeNode对象，把单向链表变成双向链表
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}
复制代码

5.思考

1.HashMap和HashTable的区别是什么

HashMap和Hashtable都实现了Map接口

HashMap功能上几乎可以等价于Hashtable，除了HashMap是非synchronized的，并可以接受null(HashMap可以接受为null的键值(key)和值(value)，而Hashtable则不行)。

HashMap是非synchronized，而Hashtable是synchronized，这意味着Hashtable是线程安全的

由于Hashtable是线程安全的也是synchronized，所以在单线程环境下它比HashMap要慢。如果你不需要同步，只需要单一线程，那么使用HashMap性能要好过Hashtable。

HashMap不能保证随着时间的推移Map中的元素次序是不变的。

由于性能问题，以及HashTable处理Hash冲突比HashMap逊色很多，现在HashTable已经很少使用了。但由于线程安全以及以前的项目还在使用，SUN依然还保留着它并没有加Deprecated过时注解。

摘自hashtable源码

If a thread-safe implementation is not needed, it is recommended to use HashMap in place of Hashtable. If a thread-safe highly-concurrent implementation is desired, then it is recommended to use java.util.concurrent.ConcurrentHashMap in place of Hashtable.

简单来说就是不需要线程安全，那么使用HashMap，如果需要线程安全，那么使用ConcurrentHashMap。

2.HashMap为什么线程不安全，如果想要线程安全怎么做

因为hashmap为了性能，它的put，resize等操作都不是同步的，假设两个线程同一时间做put操作,可能最后计算的size并不正确，值得一提的是jdk1.8以前多线程put甚至会导致闭环死循环，1.8开始不会有这个问题但依然存在线程安全问题。

jdk8前的闭环死循环。

这种问题在单线程下不存在，但在多线程下可能引起死循环导致cpu占用过高。

如果hash冲突大，同一链表下下有多个节点容易出现这种问题。具体参考 老生常谈，HashMap的死循环

若想要线程安全
1、使用ConcurrentHashMap。(线程安全的hashMap)
2、使用Collections.synchronizedMap(Mao<K,V> m)方法把HashMap变成一个线程安全的Map。
复制代码

3.HashMap是怎么解决Hash冲突的

在实际应用中，无论怎么构造哈希函数，冲突也难以完全避免。
HashMap根据链地址法(拉链法)来解决冲突,jdk8中如果链表长度大于8且节点数组长度大于64的时候，就把链表下所有节点转为红黑树，位于数组上的节点为根节点，来维护hash冲突的元素，链表中冲突的元素可以通过key的equals()方法来确定。
复制代码

4.HashMap是怎么扩容的

先写个例子测试hashMap有没有在扩容。

public static void main(String[] args) throws NoSuchMethodException, InvocationTargetException, IllegalAccessException {
    HashMap<Integer,String> o = new HashMap<>(1);
    System.out.println(o.size()); //0 size为元素个数
    //扩容条件是 如果没有定义初始容量 默认扩容至16 如果没有 根据put的情况扩容
    //put的过程中 如果插入一个元素过后的size > 阈值(加载因子 * 最近容量)
    /**
     * 代码体现 put后执行
     *   if (++size > threshold)
     *         resize();
     */
    //有定义容量的话会采用大于这个数的最小二次幂 第一次初始化为1 则输出为2 4 5 11  111 11
    HashMap<Integer,String> map = new HashMap<>(1);
    map.put(1, "一");
    //由于方法由final修饰 利用反射机制获取容量值
    Class<?> mapType = map.getClass();
    Method capacity = mapType.getDeclaredMethod("capacity");
    capacity.setAccessible(true); //由于capacity方法由final修饰 暴力获取
    System.out.println("capacity : " + capacity.invoke(map)); //capacity : 2
 
    map.put(2, "二");
    capacity = mapType.getDeclaredMethod("capacity");
    capacity.setAccessible(true);
    System.out.println("capacity : " + capacity.invoke(map)); //capacity : 4 当前容量为2 插入该元素后size为 2 > 2 * 3/4 开始扩容

    //当前容量为4 此时已有2个 3 = 4 * 3/4 不进行扩容
    map.put(3, "三");
    capacity = mapType.getDeclaredMethod("capacity");
    capacity.setAccessible(true);
    System.out.println("capacity : " + capacity.invoke(map)); //capacity : 4 当前容量为2 插入该元素后size为 3 = 4 * 3/4 不扩容

    map.put(4, "四");
    capacity = mapType.getDeclaredMethod("capacity");
    capacity.setAccessible(true);
    System.out.println("capacity : " + capacity.invoke(map));//capacity : 8  当前容量为4 此时已有4个 4 > 4 * 3/4 开始扩容
}
复制代码

上面的例子可以看出put后，hashmap确实有进行扩容，hashMap的扩容机制与其它的集合边长不太一样，它是通过当前hash桶个数乘2进行扩容

hashMap主要是通过resize()方法扩容

假设oldTable的key的hash为15，7，4，5，8，1，hashMap为初始容量为8的数组桶，存储位置如下

当put一个新元素 假设为9，且加载因子使用默认的0.75，在内存空间中新的存储位置如下

可以看到扩容之后8跑到了第9个位置，15跑到了第16个位置，旧的8，1，4，5在各自的链表上只有一个节点

根据 e.hash & (newCap - 1) 相当于 与上15后，都为自己本身所以位置保持不变

但是链表上不止有一个节点的情况，比如说上面的7，15存放的位置

这个时候是先根据 e.hash & oldCap 判断元素在数组的位置是否需要移动

比如说 7 & 8 = 0111 & 1000 = 0 ; 15 & 8 = 1111 & 1000 = 1，规律是比较高位的第一个 比如说15为高位，第一个为1，如果高位为1那么与后结果也为1

当e.hash & oldCap == 0时

链表上节点位置保持不变

当e.hash & oldCap == 1时

链表上节点的位置为原位置的index + oldCap 比如说15，新的索引位置为7+8为15

值得一提的是，jdk1.8的resize()方法相比与之前做了点优化，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但JDK1.8不会倒置，jdk8通过e.hash & oldCap，通过0和1的值均匀把之前的冲突的节点分散到新的bucket了，这样做更为高效。

代码见【4.4.5 resize()方法】

5.loadFactor加载因子为何为0.75f

加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之越小。

简单来说就是如果加载因子太小，空间利用率低，且太容易扩容对性能不太友好，设置太高，不及时扩容容易导致冲突几率大，将提高了查询成本。所以0.75是很合适的值，经过试验，在理想情况下,使用随机哈希码,节点出现的频率在hash桶中遵循泊松分布【在频率附近发生概率高，向两边对称下降。】

详细见 为什么HashMap中默认加载因子为0.75

6.hashMap中一般使用什么类型的元素作为key，为什么？

常用String，Integer这样的key

主要原因为

这些类是Immutable(不可变的)，String和基本类型的包装类规范的重写了hashCode()和equals()方法。作为不可变类天生是线程安全的，而且可以很好的优化比如可以缓存hash值，避免重复计算等等，如果采用可变的对象类型，可能出现put进去就无法查询到的情况。

如果想用自定义的类型作为键，那么需要遵守equals()和hashCode()方法的定义规则且不可变，对象插入到map后就不会再改变。

HashMap的key可以是可变对象吗？

7.源码中为什么要用transient修饰桶数组table

transient Node<K,V>[] table;
复制代码

在java中，被transient关键字修饰的变量不会被默认的序列化机制序列化。

hashMap实现了Serializable接口，通过实现 readObject/writeObject 两个方法自定义了序列化的内容，size不用多说了，一般涉及到大小可以直接计算的就没必要再序列化。

为什么不序列化table？原因有下

1.table大多数情况是无法存满的。比如说桶数组容量是16，只put了一个元素，这会造成序列化未使用的部分。造成浪费。
2.同一个键值对在不同jvm下，所处桶的位置可能是不同的，在不同的jvm下反序列化可能发生错误。(hashmap的get/put/remove等方法刚开始都是通过hash找到键所在的桶位置，就是数组下标，但如果键没有重写hashCode方法，就会调用Object的hashCode方法，而Object的hashcode方法是navtive(本地方法)的，这里的hashcode是对对象内存地址的映射得出的int结果，具体怎么计算不得而知，但是在不同jvm下，可能有不同的hashcode实现，这样产生的hash也不一样)。

8.HashMap的key如果为null，怎么查找值

我们知道hashMap只允许一个为null的key，如果key为null，因为key为null，那么hash为0，那么p = tab[i = (n - 1) & hash 也一定为0，所以是从数组上第一个位置的链表下查找。

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

6.使用建议

1.默认情况下HashMap的容量是16，但是，如果用户通过构造函数指定了一个数字作为容量，那么Hash会选择大于该数字的第一个2的幂作为容量。(1->2、7->8、9->16)

在初始化HashMap的时候，应该尽量指定其大小。尤其是当你已知map中存放的元素个数时。（《阿里巴巴Java开发规约》）

这边可以看下hashMap的4个构造方法，一般采用3，但如果已经知道个数，建议用2(加载因子0.75很合适不建议改动)

//1 自定义传初始容量和加载因子
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);
}

//2 自定义初始大小 调1构造方法，加载因子使用默认大小
public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

//3 最常用的无参构造方法
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

//4 将别的map对象映射到自身存储，很少用
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}
复制代码

这边讲解一下tableSizeFor方法。简述一下该方法的作用：

如果自定义容量大小时(调1或2的构造方法)，传入一个初始容量大小， 大于输入参数且最近的2的整数次幂的数 。比如10，则返回16，75返回128

不这么做的缺点

假设HashMap需要放置1024个元素，由于没有设置初始容量大小，随着元素不断增加，容量7次被迫扩大。而resize过程需要重建hash表，这会严重影响性能。

/**
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap) {
    //cap-1的目的是因为如果cap是2的幂数不做-1操作的话 那么最后执行完右移操作的话，返回的值将会是原有值得两倍。如果n为0的话，即cap=1，经过后面几次操作返回的为0，最后返回的capacity仍然为1(最后有加1的操作)
    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;
}
复制代码

解释一下这段代码

在java中，|=的作用是比较两个对象是否相等

a|=b的意思就是把a和b按位或然后赋值给a

以10为例整体流程大致如下

算法流程

简单来说，这种运算最后会导致1占满了它自己所占位，比如说250，它的二进制为

11111010，经过上面的或运算之后，最终将变为11111111，这种情况在加上1，就是大于这个数的最小二次幂。

7.总结

HashMap的设计与实现十分的巧妙。jdk8更是有很多提升，还没写这篇博客对于HashMap的理解仅仅只在表面。阅读源码后才发现里面还有不少的学问，由于本人水平有限，虽然花了很多时间写了很多但还有很多细节并不了解，比如说红黑树的代码实现细节，也有可能有几个地方描述错误或者不到位，如果文章有误请指正，以便于我及时修改和学习。

8.参考链接

HashMap 源码详细分析(JDK1.8)

HashMap resize方法的理解（一)

JDK 源码中 HashMap 的 hash 方法原理是什么

hashMap死循环问题

浅谈jdk8为何线程不安全

yq.aliyun.com/articles/65…