HashMap知识点

2024-01-03 00:47:55

1. Hashmap 的原理,内部数据结构?
底层使用哈希表(数组+链表),当链表过长会将链表转成红黑树以实现 o (ogn)时间复杂度内查找

2. 讲一下 Hashmap 中 put 方法过程?
对 Key求 Hash 值,然后再计算下标
如果没碰撞,直接放入桶中,
如果碰撞了,以链表的方式链接到后面,
如果链表长度超过阀值(TREEIFY THRESHOLD==8),就把链表转成红黑树
如果节点已经存在就替换旧值
如果桶满了(容量*加载因子),就需要 resize。

3. Hashmap 中 hash 函数怎么是是实现的?
高 16 bit 不变,低 16 bit 和高 16 bit 做了一个异或
(n-1) &hash->得到下标

  1. Hashmap 怎样解决沖突,讲一下扩容过程,假如个值在原数组中,现在移动了新数组,位置肯定改变了,那是什么定位到在这个值新数组中的位置,
    将新节点加到链表后,容量扩充为原来的两倍,然后对每个节点重新计算哈希值
    这个值只可能在两个地方,一个是原下标的位置,另一种是在下标为<原下标+原容量>的位置

5. 抛开 Hashmap, hash 冲突有那些解决法?
开放定址,链地址法

  1. 针对 Hashmap 中某个 Enty 链太长,查找的时间复杂度可能达到 O (n),怎么优化?
    将链表转为红黑树,JDK1.8 已经实现了

7. 为什么说Hash不安全
jdk7中多线程环境下容易造成死循环。 在hash map的扩容函数transfer时,对元素进行转移时使用头插法,链表的顺序会翻转,容易造成死循环

在jdk8中对HashMap进行了优化,在发生hash碰撞,不再采用头插法方式,而是直接插入链表尾部,因此不会出现环形链表的情况,但是在多线程的情况下仍然不安全,
jdk8中HashMap的put操作源码中,线程A和线程B同时进行put操作,刚好这两条不同的数据hash值一样,并且该位置数据为null,会发生覆盖现象

总结:
在jdk1.7中,在多线程环境下,扩容时会造成环形链或数据丢失。
在jdk1.8中,在多线程环境下,会发生数据覆盖的情况。

文章来源:https://blog.csdn.net/lijiaqiong/article/details/135351407
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。