深入分析HashMap的实现原理

电玩女神 2022-11-14 14:42 203阅读 0赞

## 公共参数 ##

*  负载因子：0.75

为什么是0.75？

时间和空间的权衡。如果为1，增加了hash冲突，增加了红黑树的复杂度。如果为0.5，hash冲突降低了，浪费了更多的空间。

源码上说了，负载因子是0.75的时候，空间利用率比较高，而且避免了相当多的Hash冲突，使得底层的链表或者是红黑树的高度比较低，提升了空间效率。

*  初始容量：16

若指定容量，变成他的2的指数次幂。（为了性能，尽量提前预估大小，而且要考虑实际元素大小要 小于 HashMap算得2指数次幂\*0.75，否则容易触发扩容机制）

*  为什么2的指数次幂容量，及二倍扩容？

计算索引：当 length 为 2 的次幂时，num & (length - 1) = num % length 等式成立，位运算更高效

*  懒加载（延时加载）
    
    put()调用的时候先判断初始数组是否为空，如果为空，则初始化。

## JDK1.7及以前 ##

*  插入方式：头插

为什么头插？考虑一般使用不扩容的情况时，头插方便，不需要遍历链表。

隐患：并发出现循环链表

*  数据结构：数组+链表
 *  节点：Entry
 *  hash()
    
     **高低位扰动计算**，降低了了发生hash冲突的几率。
    
        h ^= (h >>> 20) ^ (h >>> 12);
            return h ^ (h >>> 7) ^ (h >>> 4);
 *  这是什么？index = hash&length-1，所有hash低位相同，高位不同导致hash冲突，性能保险，再次进行一种算法的hash运算。
 *  put（）过程：
    
    1.判断当前数组是否需要初始化。  
    2.如果 key 为空，则 put 一个空值进去。  
    3.根据 key 计算出 hashcode。  
    4.根据计算出的 hashcode 定位出所在桶。  
    5.如果桶是一个链表则需要遍历判断里面的 hashcode、key 是否和传入 key 相等，如果相等则进行覆盖，并返回原来的值。  
    6.如果桶是空的，说明当前位置没有数据存入；新增一个 Entry 对象写入当前位置。  
    7.当调用 addEntry 写入 Entry 时需要判断是否需要扩容。  
    如果需要就进行两倍扩充，并将当前的 key 重新 hash 并定位。  
    而在 createEntry 中会将当前位置的桶传入到新建的桶中，如果当前桶有值就会在位置形成链表。
 *  get（）过程：
    
        首先也是根据 key 计算出 hashcode，然后定位到具体的桶中。
        判断该位置是否为链表。
        不是链表就根据 key、key 的 hashcode 是否相等来返回值。
        为链表则需要遍历直到 key 及 hashcode 相等时候就返回值。
        啥都没取到就直接返回 null 。
 *  扩容时机：
    
     先判断扩容，后插入。
    
     为什么这个顺序？因为JDK7头插，如果先插入后扩容，而扩容时还要遍历元素，重新整顿，没必要先插入。
    
     (size>=threshold)&&(null !=table\[bucketIndex\])  
     1、 存放新值的时候当前已有元素的个数必须大于等于阈值  
     2、 存放新值的时候当前存放数据发生hash碰撞（当前key计算的hash值换算出来的数组下标位置已经存在值）
 *  rehash：这个定义指扩容时重新计算索引
    
    扩容导致时，将原有的对象重新计算hash值重新的分配并加入新的桶内。
    
    （再一次调用int i = indexFor(e.hash,newCapacity);
    
    目的：为了解决数量增多，导致一些链表太长，时间复杂度O(n)=n 的问题
    
    ## JDK1.8开始的情况 ##
    
     *  插入方式：尾插
    
     为什么尾插？因为在resize()的时候，头插方式，同一Entry链上的元素，重新计算索引位置时，顺序有变，导致出现并发问题，形成循环链表。尾插，扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。
    
     但put和get没有锁机制，依然无法保证多线程情况下的安全。
 *  数据结构：数组+链表+红黑树
    
     红黑树时间复杂度O(logn)
 *  节点：Node
 *  计算hash：
    
    首先，在高位扰动方面，只是简单的h = h ^ (h >>> 16)，没有再做那么多的扰动，就得到了hash值。其次，去掉了indexFor这个专门定位的函数，而是在put,get等操作中直接定位，可以看到这些函数中都有这两行  
    我自己的理解是，由于用红黑树优化了冲突很多，链很长的情况，所以没必要做那么多的高低位扰动了。有了冲突也可以处理。
 *  put（）过程：
    
    1.判断当前桶为空，为空初始化。
    
    2.计算key的hashcode，定位具体的桶，若痛为null，则没有hash冲突，直接创建一个新桶即可。
    
    3.若桶不为空（hash冲突），则比较当前桶中的 key、key 的 hashcode 与写入的 key 是否相等，相等就赋值给 e，
    
    4.若不相等，如果当前桶为红黑树，按照红黑树方式写入数据。
    
    5.如果当前桶为链表，就需要将当前的 key、value 封装成一个新节点写入到当前桶的后面
    
    6.接着判断当前链表的大小是否大于预设的阈值，大于时就要转换为红黑树。
    
    7.如果在遍历过程中找到 key 相同时直接退出遍历。  
    8.如果 e != null 就相当于存在相同的 key,那就需要将值覆盖。  
    9.最后判断是否需要进行扩容。（插入后的size>阈值）
 *  get（）过程:
    
        首先将 key hash 之后取得所定位的桶。
        如果桶为空则直接返回 null 。
        否则判断桶的第一个位置(有可能是链表、红黑树)的 key 是否为查询的 key，是就直接返回 value。
        如果第一个不匹配，则判断它的下一个是红黑树还是链表。
        红黑树就按照树的查找方式返回值。
        不然就按照链表的方式遍历匹配返回值。
 *  扩容时机：
    
    先插入，后判断扩容
    
     为什么这个顺序？因为JDK8尾插，如果先扩容后，而插入时还要遍历元素，扩容还要遍历一遍，没必要遍历两次啊。
    
    两种情况下扩容：1,初始化时。2,插入后的size>阈值。
 *  rehash：
    
    不需要重新计算hash，而是巧妙的使用了：原来的hash值&原数组长度 来判断：
    
    即e.hash&oldCap 如果结果等于0位置相同，如果不等于0，位置等于原来索引+原数组长度
 *  树化机制
    
    阈值：当前链表长度大于8
    
     为什么是8？源码上说，为了配合使用分布良好的hashCode，树节点很少使用。并且在理想状态下，受随机分布的hashCode影响，链表中的节点遵循泊松分布，而且根据统计，链表中节点数是8的概率已经接近千分之一，而且此时链表的性能已经很差了。所以在这种比较罕见和极端的情况下，才会把链表转变为红黑树。因为链表转换为红黑树也是需要消耗性能的，特殊情况特殊处理，为了挽回性能，权衡之下，才使用红黑树，提高性能。也就是大部分情况下，hashmap还是使用的链表，如果是理想的均匀分布，节点数不到8，hashmap就自动扩容了。
    
    条件：先判断table的长度是否大于64 && 链表长度超过阈值
 *  树退化机制
    
    阈值：当前树节点数小于6
    
     为什么是6？避免来回转化。
    
     因为树节点所占空间是普通节点的两倍，所以只有当节点足够多的时候，才会使用树节点。也就是说，节点少的时候，尽管时间复杂度上，红黑树比链表好一点，但是红黑树所占空间比较大，综合考虑，认为只能在节点太多的时候，红黑树占空间大这一劣势不太明显的时候，才会舍弃链表，使用红黑树。
    
    条件：
    
     1.remove():
    
     在红黑树的root节点为空 或者root的右节点、root的左节点、root左节点的左节点为空时 说明树都比较小了
    
     2.resize():
    
     当红黑树节点元素小于等于6时(只有resize()才用到了这个6)

## HashMap和HashTable区别 ##

*  父类不同
    
    HashTable：继承自Dictionary（已被废弃）
    
    HashMap：继承自AbstractMap类
    
    不过它们都实现了同时实现了map、Cloneable（可复制）、Serializable（可序列化）这三个接口。
    
    Hashtable比HashMap多提供了elments() 和contains() 两个方法。
    
        elments() 方法继承自Hashtable的父类Dictionnary。elements() 方法用于返回此Hashtable中的value的枚举。
    
    contains()方法判断该Hashtable是否包含传入的value。它的作用与containsValue()一致。事实上，contansValue() 就只是调用了一下contains() 方法。
 *  null值问题
    
    HashTable：不能有null值null键
    
    HashMap：可以有一个null值，支持null键。
    
    当get()方法返回null值时，可能是 HashMap中没有该键，也可能使该键所对应的值为null。因此，在HashMap中不能由get()方法来判断HashMap中是否存在某个键， 而应该用containsKey()方法来判断。
 *  线程安全性
    
    HashTable：线程安全，它的每个方法中都加入了Synchronize方法。
    
     但基本由于性能问题，已被弃用。ConcurrentHashMap因为ConcurrentHashMap使用了分段锁，并不对整个数据进行锁定。
    
    HashMap：单线程使用性能更好，多线程不安全，还可能造成死锁。
 *  遍历方式不同
 *  初始容量不同
    
    Hashtable的初始长度是11，之后每次扩充容量变为之前的2n+1（n为上一次的长度）
    
    而HashMap的初始长度为16，之后每次扩充变为原来的两倍
    
    创建时，如果给定了容量初始值，那么Hashtable会直接使用你给定的大小，而HashMap会将其扩充为2的幂次方大小。
 *  计算hash值方式不同
    
    为了得到元素的位置，首先需要根据元素的 KEY计算出一个hash值，然后再用这个hash值来计算得到最终的位置
    
    Hashtable直接使用对象的hashCode。hashCode是JDK根据对象的地址或者字符串或者数字算出来的int类型的数值。然后再使用除留余数发来获得最终的位置。 然而除法运算是非常耗费时间的。效率很低
    
    HashMap为了提高计算效率，将哈希表的大小固定为了2的幂，这样在取模预算时，不需要做除法，只需要做位运算。位运算比除法的效率要高很多。

## ConcurrentHashMap的原理 ##

*  jdk1.7
    
    是由 Segment 数组、HashEntry 组成，和 HashMap 一样，仍然是数组加链表。
    
    分段锁技术，其中 Segment 继承于 ReentrantLock。不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理，理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量)的线程并发。每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。
 *  jdk1.8
    
    抛弃了原有的 Segment 分段锁，节点改为Node，数组加链表+红黑树，而采用了 CAS + synchronized 来保证并发安全性。