Java Hashmap基础知识。学习笔记

朴灿烈づ我的快乐病毒、 2023-05-21 11:48 30阅读 0赞

## 一.Hashmap基础知识 ##

### **1.Hashmap的底层数据结构是什么？** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyZWFtX3h1bg_size_16_color_FFFFFF_t_70][]

数组+链表+红黑树(jdk>1.7，产生hash冲突时，链表长度>=8时候，链表转换为红黑树)

### **2.为啥使用hash值计算索引？** ###

Put一个key，value的时候：根据key计算出一个hash散列值作为map中的元素下标，Index=hash%length 得到下标，这样查找非常快

### **3.什么是hash冲突，为啥会出现hash冲突，hashmap是怎么解决hash冲突的？** ###

简单说hash冲突就是两个不同的值或者相同的值根据hash算法算出了一样的hash值。也叫hash碰撞。根据上面的下标计算公式：Index=hash%length，可以得知，当index很可能算出来是一样的。假如length是16，那么当hash值是15或者31时计算出来的index时一样的，都是15，所以就会出现下标冲突。hashmap产生冲突后，就会产生链表来解决hash冲突。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyZWFtX3h1bg_size_16_color_FFFFFF_t_70 1][]

### **4.为啥jdk1.8以后，链表超过一定长度会转换为红黑树？** ###

因为都知道，链表查找元素的方式是从头查到尾，当链表长度过长，就会影响查询效率，所以就转化为了查找效率更快的红黑树（红黑树算法请大家自行了解）。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyZWFtX3h1bg_size_16_color_FFFFFF_t_70 2][]

### **5.为啥hashmap的的初始长度和扩容后的长度是2的指数幂？** ###

**先认清一点，当我们传入的初始化长度不是2的指数幂时，hashmap会自动将传入的数强制转换为最靠近且大于传入数的2的指数幂，举个例子：当传入的长度是13时，因为13大于2的3次幂，小于2的4次幂，所以按照最靠近且大于传入数的2的指数幂原理，会强制转换为16。**

### **测试：** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyZWFtX3h1bg_size_16_color_FFFFFF_t_70 3][]

### 结果： ###

![20200418213455742.png][]

**可以看出，当我们对这个容器初始化算法分别传入1，5，25，125测试时，自动转换成了大于传入数的2的指数幂1，8，32，128**

回到问题，那么为什么会强制这样转换呢，**原因有两点**：

**1.公式：Index=hash%length 用到了取模运算。取模的效率很低，用位计算远远高于取模运算，转换为2的指数幂以后用位运算能达到同样的效果，计算机运算速度是：加法>乘法>除法>取模**

![20200418214208472.png][]

**2.因为hashmap扩容的时候还要进行大量rehash（重新计算hash），所以用位运算能大大提高效率，注意，jdk<1.8才会进行rehash计算，jdk大于1.8优化扩容算法，没有进行rehash计算**

### 看一下index的位运算及快的原理： ###

//数组元素的下标算法
    public static final int index(int hash, int n) {
        return (n - 1) & hash;
    }

**当length是2的指数幂时，以下公式成立**

//当length是2的指数幂时
    hash%length = hash & (length-1)
    //当length不是2的指数幂时
    hash%length != hash & (length-1)

与运算原理：永远保证下标index在length以内，不会出现下标越界,如下图，&运算以后得到的结果是1010，转换为10进制数就是

![20200418222702694.png][]

**扩容大小为原来的两倍：2的指数幂数左移一位，数字翻倍！**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyZWFtX3h1bg_size_16_color_FFFFFF_t_70 4][]

### 6.扩容加载因子为什么是0.75？ ###

**假如是1，达到最大利用率，但是不可能均匀的分配完数组，就会造成hash碰撞严重，查询效率低**

**假如是0.5，hash碰撞少，查询效率高，但是浪费空间**

**时间和空间综合考虑，加载因子定0.75！！！！！！**

### **而且，根据泊松分布（自行了解）原理** ###

**放入同一个链表中的概率符合一个概率统计：泊松分布**

**大致贴一下泊松概率论：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyZWFtX3h1bg_size_16_color_FFFFFF_t_70 5][]

**根据泊松分布概率统计，加载因子定0.75的时候，放入同一个链表中的概率会随着长度越来越低，hash碰撞使链表长度达到8的时候概率几乎为0，所以链表长度达到8转红黑树也是有原因的，并且根据这概率链表转红黑树概率比较小，所以Jdk1.8比1.7性能提高也不是很大，大概是8%-10%**

### **7.jdk1.7中hashmap扩容存在什么问题，怎么解决的？** ###

jdk1.7中，hashmap在多线程环境中扩容会发生链表环的问题：

两个线程t1,t2都对hashmap扩容时，t2阻塞，t1完成扩容后，t2从阻塞中回过来继续去执行扩容操作，这时候就可能造成一个环。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyZWFtX3h1bg_size_16_color_FFFFFF_t_70 6][]

这个问题在1.8中得到了解决，解决方案是：

定义两 组指针：高位指针，低位指针

使用高低位指针进行扩容，没有进行rehash计算，而且还可以均匀拆分，避免链表环的产生

**链表环产生与解决方案详细请参考：[点我][Link 1]**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyZWFtX3h1bg_size_16_color_FFFFFF_t_70]: /images/20230521/ecef717268aa404db46715d0f3219a99.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyZWFtX3h1bg_size_16_color_FFFFFF_t_70 1]: /images/20230521/4142287bcfab43f395deb5663b8f2d39.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyZWFtX3h1bg_size_16_color_FFFFFF_t_70 2]: /images/20230521/93627623e6a0497081f9401acf6a6663.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyZWFtX3h1bg_size_16_color_FFFFFF_t_70 3]: /images/20230521/2ad215e51bb94605a9a51bf2b536af45.png
[20200418213455742.png]: /images/20230521/181a0abb01ca440a85c793b35a50f075.png
[20200418214208472.png]: /images/20230521/fdb5e2ffabcd4303925e3eb76440ac53.png
[20200418222702694.png]: /images/20230521/f2d6bb8e256849b383e9de2a72b6200d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyZWFtX3h1bg_size_16_color_FFFFFF_t_70 4]: /images/20230521/818dd2b5c5cc49239f0293ae522f2e76.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyZWFtX3h1bg_size_16_color_FFFFFF_t_70 5]: /images/20230521/73f16968d091430385d4be91beaa414e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyZWFtX3h1bg_size_16_color_FFFFFF_t_70 6]: /images/20230521/aef73dbcd1e94ca68e33be1efd7505af.png
[Link 1]: https://www.cnblogs.com/wen-he/p/11496050.html