2 stone yw stone_yw 于 2017.09.19 09:45 提问

HashMap插入时存在避免尾部遍历之说? 2C

HashMap插入元素的过程:
1 首先计算key的hash值,然后根据table的长度进行取模,找到自己的index位置。
2 如果table[index]位置上没有其他元素,则直接插入,否则就发生了hash冲突。
hashmap解决hash冲突是采用链地址法,也就是说,当发生hash冲突后,会
遍历链表中每个元素,调用equals方法进行比较,如果相等则将旧的value替换为新的 value,如果遍历结束后,都没有相等的,则在链表头部插入。

问题来了,为什么要在链表头部插入呢?网上说是避免尾部遍历。。但是真的存在避免尾部遍历么?因为在插入元素时,会调用equals方法和每个元素进行比较,少不了遍历的过程,完全可以在遍历结束后在尾部进行插入,并不会多出额外的时间复杂度。

求大神解答啊。。谢谢啦

2个回答

u011315960
u011315960   2017.09.19 10:37

首先HashMap在解决hashcode相同的时候,选择了头部插入的链式结构,我觉得主要是为了提高效率:

1、你后插入的相同hashcode的对象,从理论上说,应该是最近要使用的概率最高,所以插入头部位置。就好像某些软件的最近使用列表,一定是按照你最近打开的顺序排序的,那么你一定会去打开最近使用的吗?不一定,只是从感性上推断最近使用的那个打开的效率最高,例如从我工作的情况来看,重复打开同一个Work文档的概率非常高。

2、我记得源码里,并没有提供尾部遍历的方法,都是通过next指向下一个对象,并且你也说了头部和尾部的遍历效率几乎是一样的,所以我觉得避免尾部遍历的说法有点说不过去。

stone_yw
stone_yw 但是在网上查相关的时候,出来的都是避免尾部遍历//
2 个月之前 回复
stone_yw
stone_yw 可是觉得hashmap设计头部插入肯定不仅仅是使用概率的原因,而且如果仅从使用概率上考虑感觉没有绝对说服力。
2 个月之前 回复
stone_yw
stone_yw   2017.09.19 13:40

我在想的是,是不是因为其他什么原因?如果放在尾部,会不会需要一个额外的变量来保存上一个非空的元素。。

Csdn user default icon
上传中...
上传图片
插入图片