HashMap的底层原理

梦里梦外; 2024-03-26 17:45 67阅读 0赞

HashMap是我们在开发中用到非常多的，在面试中用的也是非常多，接下来就简单的分享一下HashMap的底层原理。

首先HashMap是懒加载，只有往里面存储元素的时候才会创建。那么创建数组的默认长度是16，

在存储元素的时候，先会计算元素的hash值，然后用它的高16位与低16位进行异或运算，然后模数组的长度取余数，就是此元素下标的位置。如果再次存储元素得到的下标位置是一毛一样的，也就是产生了哈希冲突。

常见的哈希冲突解决办法： 拉链发（在当前位置创建一个单向链表），再散列法（换一种哈希算法计算 ）， 开放寻址法（用哈希值再次进行哈希计算），建立公共溢出区（将哈希冲突的元素放到移除表里面）

那么在hashMap中，解决哈希冲突的算法就是拉链法，在产生哈希冲突的时候，先比较key的值，如果相同直接覆盖，不相同就用equlas方法比较，相同直接覆盖，不相同的话就在当前下标出建立一个单向链表，并且用尾插法的方式插入到列表当中（在jdk1.7中采用了头插法，头插法虽然效率比尾插法高，但是头插法会将链表颠倒，容易造成环形锁，导致取数据取不出来），那么如果单向链表中的元素个数超过了8个，那么就会变成为红黑树提高效率（注意： 此时会先判定一下数组的长度有没有超过64，如果超过了64，那么就会变为红黑树，如果没有超过64，会优先进行一个数组的扩容，数组的扩容机制在后面会说到），在删除元素的时候，如果红黑树中元素的个数小于6个，那么就又变为单向链表进行提高效率。

可能有的小伙伴会问，为什么是8的时候变为红黑树，为啥又是6变为单向链表呢。因为大佬在设计的时候，经过计算，8个是产生哈希碰撞最小的数量，那么为什么又是6的时候变为单向链表呢，如果也设定为8的话，那么就会经常变换数据类型，也是会消耗性能滴，所以就设置了6哒。

那么上面说到了数组的扩容，数组的扩容机制是左位移一位，其实也就相当有长度扩大了2倍，那么除了在产生哈希冲突的时候会有一个扩容，当负载因子达到0.75的时候也会扩容，比如说数组长度为16，当元素的数量达到12个的时候，注意不是长度，就会进行一个扩容。

那么在多线程环境下，HashMap它是安全的吗，肯定不是！在多线程环境下，它容易造成循环添加数据，所以会有脏数据，一般在多线程环境下，我们会使用ConcurrentHashMap，CouncurrentHashMap它在jdk1.7之前使用了分段锁，这也是它比HashTable效率高的原因，它不会把整个数据都上锁，在jdk1.8之后，用了cas机制和Synchronized锁，并且它的value值和next都被volatitle修饰，保证了数据的可见性。

刚才又提到了HashTable，那么就简单的说一下它和CouncurrentHashMap的区别吧，HashTable的初始容量是11，它的key和value值都不能为null,而CouncurrentHashMap的key可以有一个null,value值可以有多个null.

第一次发布文章，请大家多多指教，欢迎讨论哦