HashMap底层实现
HashMap
hashmap几乎是Java面试必问题,相关的知识点其实有很多,更为详细的hashmap知识点,我也有写,全部讲一遍,差不多要一个小时以上,有时间的同学可以去看看,这里提供地址:https://blog.csdn.net/java_wxid/article/details/124788118,面试官想问的可能就那么几个,另外还需要控制hashmap讲解的时长,挑几个比较重要的,进行讲解即可,下面由浅到深讲解,专门针对面试题,归总的知识点列举出来。
HashMap底层实现
向HashMap中添加一个元素时,当前元素的key会调用hashCode方法来决定它在数组中存放的位置。如果这个位置没有其他元素,会把这个键值对直接放到一个node类型的数组中,这个数组就是hashmap底层基础的数据结构。如果这个位置有其他元素,会继续拿着这个key调用equals方法和这个位置已存在的元素key进行对比,对比二个元素的key。key一样,返回true,原来的value值会被替换成新的value。key不一样,返回flase,这个位置就用链表的形式把多个元素串起来存放。
jdk1.7版本的HashMap数据结构就是数组加链表的形式存储元素的,但是会有弊端,当链表中的数据较多时,查询的效率会下降。所以JDK1.8版本做了一个升级,当链表长度大于8,并且数组长度大于64时,会转换为红黑树。因为红黑树需要进行左旋,右旋,变色操作来保持平衡,如果当数组长度小于64,使用数组加链表比使用红黑树查询速度要更快、效率更高。
在HashMap源码有这样一段描述,大致意思是说在理想状态下受随机分布的hashCode影响,链表中的节点遵循泊松分布,节点数是8的概率接近千分之一,这个时候链表的性能很差,所以在这种比较罕见和极端的情况下才会把链表转变为红黑树,大部分情况下HashMap还是使用链表,如果理想情况下,均匀分布,节点数不到8就已经自动扩容了。
1.7版本和1.8版本的差异
jdk1.7的hashmap有二个无法忽略的问题。
第一个是扩容的时候需要rehash操作,将所有的数据重新计算HashCode,然后赋给新的HashMap,rehash的过程是非常耗费时间和空间的。
第二个是当并发执行扩容操作时会造成环形链和数据丢失的情况,开多个线程不断进行put操作,当旧链表迁移新链表的时候,如果在新表的数组索引位置相同,则链表元素会倒置,就是因为头插法,所以最后的结果打乱了插入的顺序,就有可能发生环形链和数据丢失的问题,引起死循环,导致CPU利用率接近100%。
在JDK1.8中,对HashMap这二点进行了优化。
第一点是经过rehash之后元素的位置,要么是在原位置,要么是原位置+原数组长度。不需要像JDK1.7的实现那样重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了。在数组的长度扩大到原来的2倍, 4倍,8倍时,在resize(也就是length - 1)这部分,相当于在高位新增一个或多个1bit。
举个例子,hashmap默认的初始长度是16,负载因子是0.75,当元素被使用75%以上时,触发扩容操作,并且每次扩容一倍。扩容时:将旧数组中的元素转换后,填充到新数组中。通过底层获取索引indexfor方法里面有个(length -1)公式,取它的二进制,它的二进制位后八位是0000 1111,扩容二倍到32,通过公式(length -1)取31的二进制,它的后八位0001 1111,可以发现它的高位进的是1,然后和原来的hash码进行与操作,这样元素在数组中映射的位置要么不变,要不就是在原位置再移动2次幂的位置。
高位上新增的是1的话索引变成原位置+原数组长度,是0的话索引没变。这样既省去了重新计算hash值的时间,而且由于高位上新增的1bit是0还是1,可以认为是随机的,复杂度更高,从而让分布性更高些。
第二点,发生hash碰撞,不再采用头插法方式,而是直接插入链表尾部,因此不会出现环形链表的情况,但是在多线程环境下,会发生数据覆盖的情况。
举个例子,如果没有hash碰撞的时候,它会直接插入元素。如果线程A和线程B同时进行put操作,刚好这两条不同的数据hash值一样,并且该位置数据为null,线程A进入后还未进行数据插入时挂起,而线程B正常执行,从而正常插入数据,然后线程A获取CPU时间片,此时线程A不用再进行hash判断了,线程A会把线程B插入的数据给覆盖,导致数据发生覆盖的情况,发生线程不安全。
并发修改异常解决方案
HashMap在高并发场景下会出现并发修改异常,导致原因:并发争取修改导致,一个线程正在写,一个线程过来争抢,导致线程写的过程被其他线程打断,导致数据不一致。
第一种解决方案:使用HashTable:HashTable是线程安全的,只不过实现代价却太大了,简单粗暴,get/put所有相关操作都是synchronized的,这相当于给整个哈希表加了一把大锁。多线程访问时候,只要有一个线程访问或操作该对象,那其他线程只能阻塞,相当于将所有的操作串行化,在竞争激烈的并发场景中性能就会非常差。
第二种解决方案:使用工具类Collections.synchronizedMap(new HashMap<>());和Hashtable一样,实现上在操作HashMap时自动添加了synchronized来实现线程同步,都对整个map进行同步,在性能以及安全性方面不如ConcurrentHashMap。
第三种解决方案:使用写时复制(CopyOnWrite):往一个容器里面加元素的时候,不直接往当前容器添加,而是先将当前容器的元素复制出来放到一个新的容器中,然后新的元素添加元素,添加完之后,再将原来容器的引用指向新的容器,这样就可以对它进行并发的读,不需要加锁,因为当前容器不添加任何元素。利用了读写分离的思想,读和写是不同的容器。缺点也很明显,会有内存占用问题,在复制的时候只是复制容器里的引用,只是在写的时候会创建新对象添加到新容器里,而旧容器的对象还在使用,所以有两份对象内存。会有数据一致性问题,CopyOnWrite容器只能保证数据的最终一致性,不能保证数据的实时一致性。
第四种解决方案:使用ConcurrentHashMap:ConcurrentHashMap大量的利用了volatile,CAS等技术来减少锁竞争对于性能的影响。在JDK1.7版本中ConcurrentHashMap避免了对全局加锁,改成了局部加锁(分段锁),分段锁技术,将数据分成一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问,能够实现真正的并发访问。不过这种结构的带来的副作用是Hash的过程要比普通的HashMap要长。所以在JDK1.8版本中CurrentHashMap内部中的value使用volatile修饰,保证并发的可见性以及禁止指令重排,只不过volatile不保证原子性,使用为了确保原子性,采用CAS(比较交换)这种乐观锁来解决。
- 点赞
- 收藏
- 关注作者
评论(0)