本文共 3415 字，大约阅读时间需要 11 分钟。

背景

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);    }1234

1. 1.7 的计算方式

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

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

从上面的两种通过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
   
     s;         HashEntry
    
     [] tab;        int h = hash(key);        long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;        if ((s = (Segment
     
      )UNSAFE.getObjectVolatile(segments, u)) != null &&  //获取volatile            (tab = s.table) != null) {            for (HashEntry
      
        e = (HashEntry
       
        ) 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;    }1234567891011121314151617
       
      
     
    
   

HashTable

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