Java中HashMap详解

深碍√TFBOYSˉ_ 2022-10-07 04:59 165阅读 0赞

### HashMap详细解析 ###

*  HashMap的实现原理
 *   *  HashMap的数据结构
     *  HashMap构造函数
     *  HashMap重要方法
     *   *  hash(K)
         *  put(K, V)
         *  resize()
         *  treeifyBin()
         *  get(K)
     *  Hash冲突
 *  HashMap总结
 *   *  HashMap中MAXIMUM\_CAPACITY设置为1<<30
     *  HashMap中容量设置为2的整数幂次方
     *  HashMap中的负载因子设置为0.75

# HashMap的实现原理 #

## HashMap的数据结构 ##

*  HashMap使用数组+链表+红黑树的数据结构存储数据的
 *  **HashMap**的内部数据结构是一个桶数组
    
     *  每一个桶中存放着一个单链表的头节点
     *  每一个节点中存储着一个键值对**Entry**
 *  **HashMap**采用拉链法解决存在的**Hash**冲突问题  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pld2F2ZU94Zm9yZA_size_16_color_FFFFFF_t_70_pic_center]

## HashMap构造函数 ##

*  **HashMap**中有三个构造函数 : 通常情况下,使用默认的无参构造函数.在能够预估到数据的容量时推荐使用指定容量大小的构造函数

public HashMap();
    
    public HashMap(int initialCapacity);
    
    public HashMap(int initialCapacity, float loadFactor);

*  构造函数中只是设置了几个参数的值,没有对数组和链表进行初始化,在第一次**put**操作时才调用**resize()** 方法初始化数组**tab.** 这样可以很好的节省空间

## HashMap重要方法 ##

### hash(K) ###

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

*  **Java**的**HashMap**中,没有直接使用**hashcode()** 作为**HashMap**中的**hash**值
 *  **HashMap**中将**hashcode()** 的值无符号右移**16**位得到一个新值,然后将**hashcode()** 的值和这个新值进行异或运算得到最终的**hash**值保存在**HashMap**中. 这样可以避免哈希碰撞
    
     *  比如容量大小**n**为**16**时 **,n-1**为**15(0x1111),** 散列值真正生效的只是低**4**位,此时新增的键的**hashcode()** 的值如果是**2,18,34**这样以**16**的倍数为差的等差数列时,就会产生大量的哈希碰撞
     *  使用这样的方法,将高**16**位和低**16**位进行异或,因为大部分**hashcode()** 的值分布已经很均匀了,即使发生碰撞也用 O ( l o g n ) O(logn) O(logn)时间复杂度的红黑树进行了优化.这样通过使用异或的方法,不仅减少了系统开销,也不会因为**tab**长度较小时高位没有参与下标的运算引发哈希碰撞

### put(K, V) ###

*  使用**put(K, V)** 操作时 **,HashMap**计算键值K的哈希值,然后将这个键值对**Entry**放入到**HashMap**中对应的桶**bucket**上
 *  然后寻找以当前桶为头结点的一个单链表,顺序遍历单链表找到某个节点的**Entry**中的**key**等于给定的参数**K**
 *  如果找到则将旧的参数值**V**替换为参数指定的**V.** 否则直接在链表的尾部插入一个新的**Entry**节点

if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))

*  **HashMap**中重写**equals()** 方法必须也要重写**hashcode()** 方法:
    
     *  根据hash值,定位到数组某个位置后,向位置中后面的链表添加元素时,判断元素是否一样中,首先判断**hash**值是否相等,然后再判断**equals()**
     *  如果只对**equals()** 进行重写,不对**hashcode()** 进行重写时,依然会按照不同的两个对象处理,所以重写**equals()** 方法时必须也要重写**hashcode()** 方法
 *  **HashMap**中既要判断**hash**值,也要使用**equals()** 方法判断:
    
     *  **HashMap**中链表结构进行遍历判断时,重写的**equals()** 方法判断对象是否相等的业务逻辑比较复杂,这样下来的循环遍历判断影响性能
     *  **HashMap**中将**hash**值的判断放在前面,只要**hash**值不同,整个条件就是**false,** 不需要进行**equals()** 方法判断对象是否相等,提升了**HashMap**的性能
     *  **HashMap**中是根据**hashcode()** 的值定位到数组的位置的,同一个数组位置中后面的链表中元素的**hashcode()** 的值都相同.比较**hashcode()** 的值没有意义,因为必定相等 **.HashMap**中没有直接使用**hashcode()** 的值,用的是对**hashcode()** 的值进行移位和异或运算后的**hash**值,这里比较的是元素的**hash**值

### resize() ###

*  初始化**HashMap**时,按照阈值**threshold**分配内存
 *  如果**HashMap**中的数据记录超过**HashMap**的阈值就会进行扩容
 *  扩容时,数组会采用将数组容量大小的值左移一位的算法将将数组扩容至两倍
 *  扩容时,根据数据的**hash**值与数组长度进行逻辑与运算,根据运算结果是否为**0**来决定数据是不动还是将数组索引位置变更为当前索引位置和原数组长度之和
 *  扩容时不会重新计算**hash**值 **,key**的**hash**值会保存在数组位置的后面的**node**节点元素中

### treeifyBin() ###

*  数组中单个链表长度超过**8,** 数组的长度超过**64**时才会进行链表结构到红黑树结构的转换,否则只是进行扩容操作
 *  **HashMap**中,使用红黑树结构占用空间大,尽可能不使用红黑树结构

### get(K) ###

*  **HashMap**通过计算键的哈希值,寻找到对应的桶**bucket,** 然后顺序遍历桶**bucket**存放的单链表,通过比对**Entry**的键找到对应的哈希值
 *  如果对应位置后面是红黑树结构就在红黑树结构中查找,如果是链表结构就遍历链表,查询需要找的对象
    
     *  红黑树遍历的时间复杂度 :  O ( l o g n ) O(logn) O(logn)
     *  链表遍历的时间复杂度 :  O ( n ) O(n) O(n)

## Hash冲突 ##

*  **Hash冲突:**
    
     *  因为**Hash**是一种压缩映射,这样每一个**Entry**节点无法对应到一个只属于自身的桶**bucket**
     *  必然会存在多个**Entry**共用一个桶**bucket,** 拉成一个链条的情况.这种情况就是**Hash**冲突
 *  **Hash冲突存在的问题:**
    
     *  在**Hash**冲突的极端情况下,某一个桶**bucket**后面挂着的链表会特别长,导致遍历的效率很低
 *  **Hash**冲突无法完全避免,为了提高**HashMap**的性能,需要尽量缓解**Hash**冲突来缩短每个桶的外挂链表的长度
    
     *  当**HashMap**中存储的**Entry**较多时,需要对**HashMap**扩容来增加桶**bucket**的数量
     *  这样对后续要存储的**Entry**来讲,就会大大缓解**Hash**冲突

# HashMap总结 #

## HashMap中MAXIMUM\_CAPACITY设置为1<<30 ##

*  **MAXIUM\_CAPACITY:**
    
     *  **int**类型,表示**HashMap**的最大容量
     *  使用 **<<** 移位运算的结果不能超过**int**类型表示的最大值
     *  使用**1**左移 **<<** 运算时最大只能左移**30**位,否则就会溢出
 *  **Java**中的**int**类型占**4**个字节,每个字节占用**8**位,所以**int**类型占用**32**位
 *  **Java**中的**int**类型是有符号的,使用第**1**位作为符号位,此时还有**31**位,这时使用**1**左移只能左移**30**位

## HashMap中容量设置为2的整数幂次方 ##

*  通过限制一个数组长度**length**为**2**的整数幂次方的数,这样使得 **(length - 1) & h** 和 **h % length** 的结果是一致的

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

*  **tab\[(n - 1) & hash\] :** 根据**hash**值快速定位到数组的位置
    
     *  数组**tab**
     *  数组长度**n**
     *  需要查找的**key**对应的值**hash**
        
         *  因为数组长度**n**设置为**2**的整数幂次方,这样初始情况下**n-1**转换为**2**进制时各个位上都是**1**
         *  此时使用 **&** 与对应的值**hash**进行运算时的结果就和**hash**值一样,也就快速定位到了数组中的位置
         *  使得数组中的数据更加分散,减少碰撞
 *  如果数组长度不是设置为**2**的整数幂次方:
    
     *  数组长度在初始情况下使用**n-1**转换为**2**进制时,存在**0**位,导致很多位置无法放置元素,造成空间浪费
     *  数组的有效使用位置大量减少,增加了碰撞几率,减慢了查询速度

## HashMap中的负载因子设置为0.75 ##

*  **泊松分布:** **Poisson**分布.描述某段时间内,事件具体的发生概率  
     P ( X = k ) = λ k k ! e − λ , k = 0 , 1 , … ( λ 是 均 值 , k 为 发 生 次 数 ) P(X=k)=\\frac\{\\lambda^k\}\{k!\}e^\{-\\lambda\},k=0,1,…(\\lambda是均值,k为发生次数) P(X=k)=k!λke−λ,k=0,1,…(λ是均值,k为发生次数)  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pld2F2ZU94Zm9yZA_size_16_color_FFFFFF_t_70_pic_center 1]
 *  **TreeNode**占用的空间是常规节点的两倍,所以只有当箱子**bin**(数组中的一个桶)中元素的数量超过**TREEIFY\_THRESHOLD**时才会需要使用**TreeNode**
 *  **HashMap**中的**hash**值分布比较均匀时,很少使用到**TreeNode**
 *  在随机**hashcode**情况下 **,bin**中节点出现的频率遵循泊松**Poisson**分布,此时负载因子为 **0.75,** 均值  λ \{\\lambda\} λ 为 **0.5**
 *  如果调整负载因子的值,均值  λ \{\\lambda\} λ 会出现较大偏差
 *  **HashMap**扩容到**32**或者**64**时,一个箱子**bin**中存储**8**个数据量的概率为**0.00000006.** 所以当一个箱子中节点数目大于等于**8**个时,可以将**HashMap**中桶中的数据从链表结构转换为树结构存储,效果是最好的

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pld2F2ZU94Zm9yZA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221005/a9d02cfee02748fead41f40b97285f67.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pld2F2ZU94Zm9yZA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221005/f2d7f5e69677411db11aa22f195fa73f.png