学弟说他面试时被问到了HashMap,差点就遭老罪了

举报
三婶儿 发表于 2023/04/29 17:53:28 2023/04/29
【摘要】 练习时长两年半,了解HashMap吗?待会答不上来,你可就遭老罪喽......

面试官:小伙子,了解HashMap吗?
学弟:哎呦,你干嘛~ 真的问这个呀…
面试官:练习时长两年半?待会答不上来,你可就遭老罪喽!

image.png

那行吧,那开始吧…唱跳rap篮球🏀…

一、HashMap的底层结构

说一下你理解的HashMap底层?

hashMap是由数值和链表组合而成的数据结构,存储为key Value形式。

在java7中叫entry,数据形式为数组+链表。java8中叫Node,数据形式为数组+链表+红黑树(当链表长度大于8时转为红黑树)。

每一个节点都会保存自身的hash、key、value、以及next属性指向下一个节点。

image.png

二、为什么使用数组+链表数据结构

你刚提到了使用数组+链表,可以讲讲为什么使用这个结构吗?

HashMap内部使用数组来存储键值对,这个数组就是 HashMap 的主体。

image.png

在数组中存储的每个位置上,可能会有多个键值对,这些键值对通过链表的形式链接在一起。

image.png

使用数组+链表的数据结构是为了解决散列表中的键冲突问题。在散列表中,每个键都会被映射到一个桶中,但是不同的键可能会被映射到同一个桶中,这种情况被称为键冲突。

为了解决键冲突问题,HashMap 采用了链表的形式将所有映射到同一个桶中的键值对链接在一起,这样就可以通过遍历链表来查找指定键的值当链表长度过长时,查找效率就会下降,因此在链表长度超过一定阈值(8)后,HashMap会将链表转换为红黑树,以提高查找效率

同时,数组的优势在于支持通过下标快速访问元素,因此HashMap可以将每个桶的位置映射到数组的一个元素上,通过下标访问该元素即可访问到对应的链表或红黑树

我们都知道:数组的查询效率很高,添加和删除的效率低。链表的查询效率很低,添加和删除的效率高。

因此:使用数组加链表形式,不仅可以解决散列表中的键冲突问题,且数组的查询效率高、链表的添加和删除效率高。结合在一起,增删查效率都很高

image.png

嗯,确实不错。不愧是练习时长两年半的程序员…

三、数组+链表+红黑树

你刚说数组+链表+红黑树,什么情况下会转化红黑树?什么情况下转数组呢?

链表中元素过多,会影响查找效率,当其个数达到8的时候转换为红黑树。红黑树是平衡二叉树,在查找性能方面比链表要高

当红黑树的节点数小于等于6时,红黑树转换为链表,是为了减少内存开销

需要注意的是:将链表转换为红黑树、红黑树转换为链表的操作会影响HashMap的性能,因此需要尽可能避免这种情况的发生。同时,当HashMap中的元素数量较小时,不会出现链表转换为红黑树的情况,因此使用HashMap时,可以考虑在元素数量较少的情况下使用HashMap,以提高性能。

image.png

四、头插法和尾插法

说一下什么是头插法,什么是尾插法?

哇,这不是为难我胖虎吗?啥是头插法?啥是尾插法?

image.png

4.1、头插法

顾名思义,头插法就是新增元素时,放在最前面嘛。

举个栗子🌰,楼主画了一个简单的框框。用来表示原有存储顺序依次为1、2、3的数组。
image.png

假设现在加入了一个4,如果使用头插法,就会变为4123。

image.png

4.2、尾插法

同样道理,尾插法就是新增元素时,放在最后面。

还是原有存储顺序依次为1、2、3的数组。
image.png

假设现在加入了一个4,如果使用尾插法,就会变为1234。

image.png

头插法为什么要调整为尾插法呢?

为什么头插法要调整为尾插法?这是个好问题!!!

image.png

java7中使用头插法,新来的值会取代原有的值,原有的值就顺推到链表中。在这种情况下,引用关系可能会乱掉,严重会造成死循环。java8使用尾插法,把元素放到最后,就不会出现这种情况

五、HashMap如何运算存储索引

向一个hashMap中存入数据时,如何知道数据放在哪个位置呢?

当向一个hashMap中存入数据时,会先根据key的哈希值决定放在数组中哪个索引位置。

Hash公式:index = HashCode(Key) & (Length - 1)

如果数组中该索引位置是空的,直接将元素放入,如果该索引位置已经存在元素了,就根据equals方法判断下已有的元素是否和我们新放入的元素是同一个,如果返回true是同一个,则覆盖掉。不是同一元素则在原有元素下面使用链表进行存储

每个元素都有一个next属性指向下一个节点(数组+链表)

    /**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        .........
    }

六、HashMap初始化、扩容

嗯,你知道HashMap默认初始化大小是多少吗?还有它的扩容?

HashMap默认初始化容量大小是16,最大容量为2的30次方,负载因子是0.75

image.png

扩容时,会把原有数组中的值取出再次hash到新的数组中(长度扩大以后,Hash的规则也随之改变),因此性能消耗也相对较大。

当HashMap中的元素数量超过负载因子(默认为 0.75)乘以数组长度时,就会触发扩容操作,将数组长度增加一倍,并重新计算每个元素在新数组中的位置。

七、hash碰撞是什么

你听说过hash碰撞吗?

hash碰撞就是不同的Key,经过同一散列算法之后得到的hashCode值相同。

hashCode不同,key一定不同。hashCode相同,key却不一定相同。

当两个key的hashCode()返回值不同时,它们对应哈希表索引也一定不同。不同的key对象,即使它们包含相同的属性、值或状态,它们的hashCode()返回值也是不相同的。

image.png

当两个key的hashCode()返回值相同时,它们可能对应同一个哈希表索引,但它们并不一定相等。在哈希表中,不同的key可能会产生相同的哈希值(哈希碰撞)。

因此,当 key的hashCode相同时,还需要比较key的相等性。需要调用key的equals() 方法来判断它们是否相等。只有当hashCode相等,且equals方法返回true时。才可以认为这两个key相等

八、如何解决hash碰撞

解决hash碰撞的方法有哪些呢?

在哈希表中,哈希碰撞可能会导致性能下降或者安全问题。

常见的解决方法有:

1、开放地址法:在发生哈希碰撞时,通过一定的算法在哈希表中寻找一个空闲的位置,并将元素插入该位置。

2、链式哈希表:在每个哈希表的元素位置上,存储一个链表,哈希碰撞时,将元素插入到相应的链表中。

3、再哈希法:如果一个哈希函数产生的哈希值发生了碰撞,就再次使用另一个哈希函数计算哈希值。

4、负载因子调整:通过调整哈希表的容量、负载因子等参数,可以减少哈希碰撞的发生。

九、HashMap为什么线程不安全

HashMap线程安全吗?为什么?

HashMap是非线程安全的。在多线程环境下,如果多个线程同时修改HashMap中的数据,就可能会导致数据的不一致性。

说白了就是没加锁。

image.png

当多个线程同时调用HashMap的put()方法,一旦他们计算出的hash值相同,就会发生冲突,导致数据被覆盖。

所以,对于多线程并发访问的情况,建议使用线程安全的Map实现

例如ConcurrentHashMap,或者使用Collections.synchronizedMap()方法将HashMap包装成一个线程安全的Map

十、HashMap、HashTable、ConcurrentHashMap的区别

最后一个问题:说一下HashMap、HashTable、ConcurrentHashMap的区别?

麻了! 真的麻了…救救孩子吧…

image.png

HashMap、HashTable、ConcurrentHashMap都是Java中常用的哈希表实现。

区别主要在以下几个方面:

1、线程安全性:HashTable是线程安全的,HashMap是非线程安全的,ConcurrentHashMap通过分段锁的方式保证了线程安全。

2、是否可为空:HashTable不允许null值作为key或value,而HashMap和ConcurrentHashMap则允许null作为key或value。

3、迭代器:HashTable的迭代器是通过Enumeration实现的,而HashMap和ConcurrentHashMap使用的是Iterator实现的。

4、扩容:HashTable在扩容时,将容量扩大一倍加一,而HashMap和ConcurrentHashMap的扩容机制是将容量扩大一倍。

5、初始容量:HashTable的初始容量为11,而HashMap和ConcurrentHashMap的初始容量为16。

6、性能:HashMap通常比HashTable性能更好,因为它没加锁。所以弊端就是线程不安全。但后者加了锁,是线程安全的,缺点就是消耗性能。ConcurrentHashMap在多线程并发访问时,比HashTable和HashMap性能更好,因为它使用了分段锁来保证线程安全

所以,不建议使用HashTable。至于选择HashMap还是ConcurrentHashMap取决于并发访问量的大小,若并发访问量不高,则选用HashMap。若并发访问量较大,则选用ConcurrentHashMap。

ok,那今天先到这里吧。练习时长两年半的程序员…唱跳rap篮球🏀…差点就遭老罪喽~

还有,别忘记给那个练习时长两年半的三婶儿也点个赞哈~她唱跳rap篮球也还行…

image.png

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。