终于搞懂HashMap的源码了!!!

背景

HashMap是我们在平时开发最常用的容器之一，但是我们有真正了解过他吗？他是线程安全的吗？他是以何种方式来存储的呢？为什么初始化的容器大小时2的n次幂呢？他是如何进行扩容的呢？他是如何实现并发安全呢？等等一系列问题。正是知己知彼才能百战百胜，所以我打算深入理解一下hashMap

hashMap脑图

• 为了理清思路和能快速记住hashMap的“面貌”就大概列了一下

• 看完脑图，其中很多还是不够详细的。只是概述了内容。

HashMap

hashMap的概述

hashMap，继承Map集合，以key-value形势存储，其中key可以为null ，value是可以重复，其数据是无序的，且会在扩容的时候发生改变。

hashMap在进行存储的时候的步骤

链表转红黑树

• 在1.8的时候，hashMap加用了红黑树的数据结构，当某一数组的某一个位置hash冲突达到8个的时候，就会将链表转为红黑树，其原因就是提高插入和查找的效率，使用链表的插入尾节点的效率是o（n），而使用了红黑树的话插入和查找都是O（logn）我们来看一下详细的插入流程：

JDK1.7和1.8的扩容

• 触发条件：数组长度X负载因子（默认0.75）达到这个数值时在1.8会直接出发扩容，而在1.7会出现再判断一个这个节点是否有占用，如果没有就插入，有的话就扩容
• 1.7和1.8 的时候在扩容的时候会将新建一个为原数组两倍的数组，
• 1.7将原数组中的hash进行重新计算hash加入到新数组，然后将hash碰撞的链表数据，以头插法进行插入到新的数组上，然后移动。这个过程在并发情况下会有可能出现循环依赖的情况，导致无限循环耗尽CPU。
• 而1.8 如果这个计算出来的hash值在原有数组位置+旧数组长度则放在新的数组上的这个原有数组位置+旧数组长度上面，新数组没有则放在原来的位置上，新的插入的数据

hash计算的方式

1. 1.8

• 如果key为null的话就放在第一个数组的下标为0的位置。
• 如果不为先计算出hashCode，在将hashCode 无符号右移，忽略符号位，空位都以0补齐。然后再进行异或运算。

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

1. 1.7 的计算方式

• 将计算出来得hash值和数组的长度减1进行与运算，计算出来

static int indexfor(int h,int length) {
// 其中的legth-1 也是为什么 hashMap的容量为2的n次幂的原因
return h & (length-1);
}

从上面的两种通过hash值计算数组下表位置index的方式都可以将计算出来的值在数组length的长度内。至于那种性能更高速度更快，散列的空间更加均匀，那毋庸置疑，肯定1.8里面的。

上面说到可负载因子是0.75，为什么默认的负载因子是0.75呢？

• 个人理解：首先0.75 会用作扩容，这个值越大直到1，那扩容的次数是不是概率越低，hash冲突是不是越小？因为他这个值决定了达到多大值就会扩容。如果设置一个0.1,那么在第一次存储完成后就扩容了，那肯定第二次进行计算hash的时候由于数组很大，那也就降低了hash碰撞。我的理解就是在扩容次数和hash冲突之间起到一个平衡的作用
• jdk1.7 中的注解说明：作为一般规则，默认负载因子（0.75）在时间和空间成本上提供了很好的折衷。较高的值会降低空间开销，但提高查找成本（体现在大多数的HashMap类的操作，包括get和put）。设置初始大小时，应该考虑预计的entry数在map及其负载系数，并且尽量减少rehash操作的次数。如果初始容量大于最大条目数除以负载因子，rehash操作将不会发生。
• jdk 1.8中 ：理想状态下，在随机哈希值的情况，对于loadfactor = 0.75 ，虽然由于粒度调整会产生较大的方差，桶中的Node的分布频率服从参数为0.5的泊松分布。

hash冲突的几种解决方式

1. 开放定址法

• 从发生冲突的那个单元起，按照一定的次序，从哈希表中找到一个空闲的单元。然后把发生冲突的元素存入到该单元的一种方法。

1. 链地址法（拉链法）hashMa也就是用的这种方式

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

1. 再哈希法

• 就是同时构造多个不同的哈希函数： Hi = RHi(key) i= 1,2,3 … k; 当H1 = RH1(key) 发生冲突时，再用H2 = RH2(key) 进行计算，直到冲突不再产生，这种方法不易产生聚集，但是增加了计算时间。 既然已经看了hashMap的源码我们再联系一下线程安全的hashMap都有哪些呢

ConcurrentHashMap

1. 不用说我们都知道concurrentHahMap是线程安全版的hashmap ，其底层源码与hashMap类似，但是在数据结构上改变了一下，加了一个sagment[] ,这个sagement对象数组里面有多个小的hashMap，在进行操作的时候会对sagment进行加锁，让其同步执行。由于当sagment里面hashMap越多得时候那么这个并发安全系数就越低，所以在ConcurrentHashMap里面又一个并发安全系数。来控制sagment里面的hashMap的数量。其上面的说法是jdk1.7版本，这个锁采用的是rentrantLock。但是在JDK1.8中使用的是更细粒度的锁使用Sychronized和CAS来进行枷锁。
2. 1.8中的一个列子

1. 1.7中的sagement[] //get方法是不加锁的，所有共享变量都是通过volatile修饰的，确保或许最新值

public V get(Object key) {
        Segment<K,V> s; 
        HashEntry<K,V>[] tab;
        int h = hash(key);
        long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
        if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&  //获取volatile
            (tab = s.table) != null) {
            for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile  //获取volatile
                     (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
                 e != null; e = e.next) {
                K k;
                if ((k = e.key) == key || (e.hash == h && key.equals(k)))
                    return e.value;
            }
        }
        return null;
    }

HashTable

1. HashTable也是hashMap的线程安全版本，由于自身性能的问题，也一直没有被优化，所以其版本一致没改变。
2. HashTable是给其各个方法加了sychronized关键字所有的执行都会同步执行。hashTable慢的相对于ConcurrentHashMap来说。

参考文章

https://blog.csdn.net/qq_36520235/article/details/82417949（强力推荐！上面两个流程图来源） https://www.jianshu.com/p/8cf5af30f245（得补补运算符了） https://www.zhihu.com/question/20733617 （hash算法） https://www.jianshu.com/p/4d3cb99d7580 （hash冲突的解决方案）