HashMap源码浅析（一）

╰+哭是因爲堅強的太久メ 2021-11-30 00:46 306阅读 0赞

## HashMap<T> ##

`java.util.HashMap`

其内部的冲突解决方案采用的是拉链法，故HashMap的结构表现为**数组+链表**

插入时，先根据Key的hashCode，定位到待插入的地址，若待插入的地址为空，则直接插入；若待插入的地址不为空，说明发生冲突，则用拉链法，将元素插入到该地址的链表中。

拉链法会导致链表过深，而造成性能下降的问题，HashMap中，当链表长度过长时，会选择将结构转化成**红黑树**

*  **为什么不用二叉排序树呢**？：因为二叉排序树在某些较坏情况下会不平衡，甚至在最坏情况下会退化成链表，性能仍然很低下
 *  **为什么不用AVL树呢？**：AVL树是严格的平衡二叉树，当插入或删除节点时，只要一破坏了平衡条件，就要通过旋转来保持平衡，而**旋转操作是比较耗时的**，AVL更适合插入删除较少，查询较多的情况。**在实际情况中，AVL树用于保持平衡所付出的代价，比从中获取的收益还大，而我们更多是追求局部的而不是全局的严格平衡**，红黑树是一种弱平衡二叉树，相同节点的情况下，红黑树的高度可能会大于AVL树，相对AVL树来说，红黑树的旋转次数更少，为保持平衡而付出的性能开销更低，红黑树更适用于插入，删除，查找都较多的情况

当链表的长度超过**树化阈值**（`TREEIFY_THRESHOLD = 8`），则把链表转化为红黑树，若链表长度低于**非树化阈值**（`UNTREEIFY_THRESHOLD = 6`），则将红黑树重新转化为链表（链表过长时，效率会降低，故转化为红黑树关于红黑树）

Hash的冲突解决方案

*  开发定址法
    
    插入元素时，若发生冲突，则按照某种算法，向后探测，直到遇到空位为止
    
     *  线性探测法
        
        `fi = ( f(key) + i ) % m 0 ≤ i ≤ m-1`
        
        发生冲突时，依次向后探测。先探测`T[d]`，接着依次探测`T[d+1]`，`T[d+2]`，… 直到`T[m-1]`
        
        缺点：会产生聚集，导致性能下降
     *  二次探测法
        
        `fi = ( f(key) + di ) % m 0 ≤ i ≤ m-1`
        
        发生冲突时，依次向后探测。先探测`T[d]`，接着探测`T[d+di]`，`di`为增量序列12，22，…，q2，且`q ≤ 1/2(m-1)`
     *  伪随机探测法
        
        增量是个伪随机数序列
     *  再散列法
        
        `fi = ( f(key) + i * g(key) ) % m i = 1,2...,m-1`
        
        冲突时，采用另一个哈希函数`g()`，依次向后进行探测
    
    **注意**：通过开放定址法，可能会产生堆积，并且删除时，不能直接删除，只能添加一个删除标记，因为直接删除会导致该位置的值是null，若存在同义词且在该位置之后，则无法被查找到
 *  拉链法
    
    将冲突的值以链表的形式进行追加
    
    **注意**：当链表过长，甚至比数组长度还长时，会大大降低查找的效率，在HashMap的实现中，当链表的长度大于8时，就会进行树化，转化为红黑树。并且哈希表有一个**负载因子** α ，在HashMap中被设定为0.75，当哈希表的 元素数量 / 数组大小 超过这个负载因子时，就进行扩容，并且将元素rehash。采用拉链法解决冲突的哈希表中，α可以超过1（拉链法的哈希表，α其实就代表了链表的平均长度），而纯数组的哈希表，α必定小于1

**红黑树**

红黑树是具备以下特征的二叉树

*  节点是红色或黑色
 *  根节点是黑色
 *  每个叶子的节点都是黑色的空节点
 *  红色节点的2个子节点必须都是黑色
 *  从任意节点出发，到其的每个叶子节点的所有路径，都包含相同数目的黑色节点

红黑树可以保证最长路径不超过最短路径的2倍

红黑树插入节点时，保持平衡需要做**变色**和**旋转**等操作，具体的内容，待下次追加。

HashMap在多线程环境下，可能会出现死循环的问题，若2个线程同时调用HashMap的`resize()`方法，HashMap的`resize()`对哈希表中的链表， 采用的是头插法（这样避免了**尾部遍历**，即每次都需要遍历到尾部才进行插入，这样效率会很低，也正是因为头插法，导致了链表中元素顺序颠倒了，这也解释了HashMap为什么不保证有序），在某些条件（多线程产生条件竞争）下，可能会造成环形链表，若此时尝试通过一个不存在的key，去从HashMap中取值，则会造成无限循环（根据hash值去到了这个环形链表的桶中，会一直往下遍历，尝试获取到和key相等的那个Entry，而因为是环形链表，则会无限循环）。

在HashMap等一些线程不安全的集合类中，都会包含一个叫做`modCount`的变量，存储的是该HashMap实例被**修改**的次数，修改包括：1. 元素数量的改变（插入/删除） 2. HashMap结构的改变（树化）

该变量和线程安全相关。在使用`Iterator`迭代器对HashMap进行遍历时，初始化迭代器时会存储当时的`modCount`值，如果有其他线程对该map做了修改，会导致该map的`modCount`发生变化，迭代过程中会将存储下来的`modCount`和map当前的`modCount`做比较，若两者不一致，则会抛出`ConcurrentModificationException`，这就是HashMap的fail-fast策略。

故，一般建议对线程不安全的容器进行遍历时，用迭代器。