浅析HashMap底层原理

迈不过友情╰ 2024-05-23 22:23 75阅读 0赞

## 浅析HashMap底层原理 ##

### HashMap底层原理 ###

*  HashMap底层是基于数组+链表+红黑树。
 *  默认初始容量为（数组长度为\*\*16），默认负载系数为0.75（这个表示的意思是扩容机制当容量达到75%的时候自动进行扩容（扩大一倍，扩容也是采用位运算【因为用乘法会影响CPU的性能，计算机不支持乘法运算，最终都会转化为加法运算\[01的方式\]。】），当扩容的时候，会创建新的数组，以前存放在数组中的数据将会重新通过hashCode进行排序，类似于hashCode/16取模【其实使用的是位运算，位运算效率更高】得到下标存放在对应的数组中，扩容后hashCode/32.）。
 *  **底层原理**：
    
     *  先通过hash算法计算出当前键值的hashCode值，然后对数组长度进行取余【其实是位运算】，从而获得余数（即为下标）存储到对应的数组中【存储的是当前hash值（key计算的hash值），key，value和next】（所以HashMap存取数据元素是无序的）。\[底层是位运算，性能更好，且可以更好的避免哈希碰撞\]
     *  通过下标存储键值时，如果当前下标没有存放其他键值时会直接存入，如果该下标处，已经存在其他键值时，则会发生哈希碰撞。
     *  发生哈希碰撞后，会继续比较下标处所有key的equals（内容）是否为true（来判断是不是同一个元素。）
     *  如果是true，表示是相同的key，执行覆盖操作。
     *  如果是false，表示是不同的key，执行在最后一个键值对后面追加操作，从而形成单向链表（链表的产生）。
     *  如果链表长度>=8个且当前Map集合中数组长度>=64个，则会形成红黑树；如果当前数组长度<64个，则会扩容键值对数组（16\*2），而且会重新进行排序。（并且会重新将所有键值对对32进行取余重新排序进行存储从而导致效率低）
     *  当调用remove方法的时候，会删除元素，当红黑树中剩余的键值对个数<=6个的时候，会重新还原成单向链表。（性能更好）
     *  ![在这里插入图片描述][f1a0390916154814a3607a3431738f9c.png]

### 如何解决hash冲突？ ###

*  拉链法，将产生hash碰撞的元素都链接到同一个链表中【形成链表结构】
 *  再Hash法，将产生hash碰撞的元素再采用不同的哈希算法进行处理，直至没有哈希冲突。
 *  建立公共溢出区，把哈希表分为基本表和溢出表，将产生哈希冲突的元素存储到公共溢出表
 *  开放寻址法：将产生hash碰撞的元素，去寻找一个新的空闲的哈希地址
    
     *  **线性探测法**：就是将在得到的**hash值进行加1**然后对数组长度取模，直到直到新的位置。
     *  \*\*公式：\*\*h(x)=(Hash(x)+i)mod (Hashtable.length);（i会逐渐递增加1）
     *  **平方探测法（二次探测）**：就是将在得到的**hash值进行**依次为+(i2)和-(i2)然后对数组长度取模，直到直到新的位置。
     *  **公式：h(x)=(Hash(x) +i)mod (Hashtable.length);（i依次**为+(i2)和-(i2)）

### HashMap为什么要用到链表结构？ ###

*  当我们向HashMap中添加元素时，会先根据key进行哈希运算，把hash值对数组长度进去取模（实际是位运算）得到一个下标，然后通过下标将元素进行存储。如果当前下标位置有数据就产生了哈希碰撞，进行equals比较内容是否相等，如果相等进行覆盖，如果不等，就会在用拉链法然后将这个数据追加到最后一个键值后面，最终形成单向链表。

### HashMap为什么选择红黑树？ ###

*  当HashMap中同一个索引位置出现哈希碰撞的元素多了，链表会变得越来越长，查询效率会变得越来越慢。因此在JDK1.8之后，当链表长度超过8个，且数组长度>=64个的时候会将链表转坏为红黑树来提高查询

### HashMap链表和红黑树在什么情况下转换的？ ###

*  当链表的长度大于等于8，同时数组的长度大于等于64，链表会自动转化为红黑树,当树中的节点数小于64，红黑树会自动转化为链表

### HashMap在什么情况下扩容？ ###

*  默认初始容量为（数组长度为**16），默认负载系数为0.75（这个表示的意思是扩容机制当容量达到75%的时候自动进行扩容（扩大一倍），当扩容的时候，会创建新的数组（数组中村的entry对象，key是对象通过hash算法运算后取模后的值，value是真正的对象），以前存放在数组中的数据将会重新通过hashCode进行排序 ，类似于hashCode/16取余得到下标存放在对应的数组中**，扩容后hashCode/32.）。
 *  HashMap的扩容公式：initailCapacity \* loadFactor 【负载因子】= HashMap
 *  其中initailCapacity是初始容量：默认值为16（懒加载机制，只有当第一次put的时候才创建）
 *  采用位运算的方式1\*2的4次方
 *  其中loadFactor是负载因子：默认值为0.75
 *  默认扩大一倍。

### HashMap是如何Put一个元素的 ？ ###

*  首先，将key进行hash运算，然后对数组长度进行取模（底层是位运算），计算出索引（下标）。此时判断该索引位置是否已经有元素了，如果没有，就直接放到这个位置。如果这个位置已经有元素了，也就是产生了哈希碰撞，那么判断旧元素的key和新元素的key的hash值是否相同，并且将他们进行equals比较，如果相同证明是同一个key，就覆盖旧数据，并将旧数据返回，如果不相同的话再判断当前桶是链表还是红黑树，如果是红黑树，就按红黑树的方式，写入该数据，如果是链表，就依次遍历并比较当前节点的key和新元素的key是否相同，如果相同就覆盖，如果不同就接着往下找，直到找到空节点并把数据封装成新节点挂到链表尾部。然后需要判断，当前链表的长度是否大于转化红黑树的阈值，如果大于就转化红黑树，最后判断数组长度是否需要扩容。

### HashMap是如何Get一个元素的？ ###

*  首先将key进行哈希运算，计算出数组中的索引位置，判断该索引位置是否有元素，如果没有，就返回null,如果有值，判断该数据的key是否为查询的key，如果是就返回当前值的value
 *  如果第一个元素的key不匹配，判断是红黑树还是链表,如果是红黑树，就就按照红黑树的查询方式查找元素并返回,如果是链表，就遍历并匹配key，让后返回value值

### 你知道HahsMap死循环问题吗 ？ ###

*  HashMap在扩容数组的时候，会将旧数据迁徙到新数组中，这个操作会将原来链表中的数据颠倒，比如a->b->null，转换成b->a->null这个过程单线程是没有问题的，但是在多线程环境，就可，能会出现a->b->a->b…，这就是死循环
 *  在JDK1.8后，做了改进保证了转换后链表顺序一致，死循环问题得到了解决。但还是会出现高并发时数据丢失的问题，因此在多线程情况下还是建议使用ConcurrentHashMap来保证线程安全问题

[f1a0390916154814a3607a3431738f9c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/23/a7cfa0c8e8404fa7b91d63cb03e20d93.png