java架构师培训:hash函数复杂度的保障

2021年01月03日 15:01

46

    get和put都实现了,整个hashmap是不是就实现完了?很显然没有,因为还有一件很重要的事情我们没有做,就是保证hashmap的复杂度。


    一个简单的分析将显示以这种方式实现的hashmap存在一个主要问题。这是因为hashmap开头的链表的数组是固定长度的,无论数组有多长,只要我们存储足够的元素,每个链表中都会分配很多元素。我们都知道链表的遍历速度为O(1),那么如何确保查询速度恒定呢?

java架构师培训:hash函数get、put实现

    另外,还有另一个问题,即哈希值倾斜的问题。例如,我们显然有100个链接列表,但是在哈希值取模100之后,我们的大多数数据恰好为0。结果,大量数据将存储在0存储桶中,从而导致其他数据都没有桶,而这个桶已满。我们如何避免这种情况?


    实际上,无论是过多的数据还是分布不均,实际上都是相同的情况。即,在至少一个存储桶中存储了太多数据,导致效率降低。针对这种情况,在哈希图中设计了一种检查机制。存储桶中的元素一旦超过某个阈值,便会触发重置。那就是使哈希图中的链表数量增加一倍,所有数据都将被重新整理。此阈值由称为load_factor的参数设置。当存储桶中的元素大于load_factor*容量时,将触发重置机制。


    我们把reset的逻辑加进去,那么put函数就变成了这样:


    defput(self,key,val):hash_key=self.get_hash_key(key)linked_list=self.headers[hash_key]#如果超过阈值iflinked_list.size>=self.load_factor*self.capacity:#进行所有数据resetself.reset#对当前要加入的元素重新hash分桶hash_key=self.get_hash_key(key)linked_list=self.headers[hash_key]node=linked_list.get_by_key(key)ifnodeisnotNone:node.val=valelse:node=Node(key,val)linked_list.append(node)


    reset的逻辑也很简单,我们把数组的长度扩大一倍,然后把原本的数据一一读取出来,重新hash分配到新的桶当中即可。


    defreset(self):#数组扩大一倍headers=[LinkedListfor_inrange(self.capacity*2)]cap=self.capacity#capacity也扩大一倍self.capacity=self.capacity*2foriinrange(cap):linked_list=self.headers[i]nodes=linked_list.get_list#将原本的node一个一个填入新的链表当中foruinnodes:hash_key=self.get_hash_key(u.key)head=headers[hash_key]head.append(u)self.headers=headers


    其实这里的阈值就是我们的最大查询时间,我们可以把它近似看成是一个比较大的常量,那么put和get的效率就有保障了。因为插入了大量数据或者是刚好遇到了hash不平均的情况我们就算是都解决了。


   推荐阅读:jvm培训:如何判断哪些对象需要回收?


更多鲁班学院java高级培训免费课程试听地址https://www.lubanjava.com/course.html

鲁班学院java高级培训课程https://www.lubanjava.com/course/detail/519.html

加群即可领取鲁班学院最新Java高级培训课程资料学习包 群号:700541970



咨询(2)
免费试听
领取优惠
加群交流

扫一扫
加群领取架构师资料

售后反馈
返回顶部