神速Hash(上)

理解HashMap底层,首先应该理解Hash函数,今天我们聊聊什么是Hash函数以及Hash函数的设计、

查找速度的困扰

算法国自建立起,就以快速为至高的荣誉,O(n^2) 时间复杂度的设计常常被人嫌弃,一般都想着弄个O(logn)

算法国最近遇到了一个问题,就是随着处理数据的逐步增大,查找的时间越来越大了

之前用的数组和链表,最后改成二叉查找树,可是这些都需要和其中的元素进行比较,比较的次数越多,查询的速度就越慢

国王想着能不能有一种办法,查找某个元素的时候,不需要比较,直接就得到这个元素,时间复杂度直接就为O(1),和集合中的元素个数就没有关系了

初次的方案

国王召集各大臣讨论此事

“如果不需要比较,我们可以借鉴数组下标访问的思路来做”,经验老道的王大臣发话了

“哦,怎么个设计?”何大臣问道

“你看,我们要访问数组中某个元素怎么访问?”

“只需要知道起始位置和下标值就可以了,不管数组中有多少个元素,都可以一次访问到,这正是因为起始位置和下标值组成了元素的存储位置,从这个存储位置就可以直接找到元素”,王大臣自问自答起来

左丞相接着道,“所以说,给定一个元素,我们只要得到该元素的位置,也就是说将元素和元素位置建立一种一一对应的关系,就可以迅速定位要查的元素了”,说着说着,王大臣在纸上画起了图

图片

“现在问题的关键就是输入55,我们如何知道元素55的存储位置”,何大臣说道

“对”,王大臣答到

“如果输入的数为正整数的话,我们完全可以用数组存储,用这个输入的正整数作为数组的下标来存取元素”,王大臣说道

“比如说55,我们就存到下标为55的位置,这样是不是很简单”,王大臣举了一个例子,顺便画了一个图

图片

Hash函数的出现

“这也太理想了吧,现实生活中要存储的元素(key)的取值范围一般很大,比如说正整数,不可能为无穷多个正整数分配无穷大的数组吧,这不现实

就算有无穷大的数组,但实际存储的元素的范围可能很小,比如输入大多数在1-100之间,只有极少数的是其他数,那预先分配的那些空间不是浪费了吗?”,何大臣立马驳回了王大臣的想法

“那依你看,如何是好?”王大臣问道

“我看,既然输入的元素的范围可能很大甚至无穷,而我们的内存有限,所以说我们需要一种函数映射关系,将这些无限的元素映射到我们有限的内存地址上”,说着说着画了一个图

图片

“很显然,多个数据有可能被映射到同一个地址上,我们暂且称为冲突吧”,何大臣说道

“我们给这个函数映射起一个名字,就叫Hash函数吧,这个Hash函数代表着一类函数,即把任意范围的元素可以通过映射关系压缩成固定范围的元素”何大臣说道,大家一致同意

Hash函数的选择

“那现在的问题就很清晰了,一个是这个Hash函数该选择什么样具体的函数,另一个就是出现冲突该怎么办?”王大臣说道

“如果是正整数,我们可以用这个正整数数除以某个数,取其余数,即我们常用的 k % m,k为正整数,m 为除数

这样一来,范围就缩小了很多,比如说 15%10=5,26%10=6,…,所有的正整数经过运算,都变成了 0-9 范围之间的数了,这样范围就缩小了很多”何大臣发挥了他数学的才能

大家一致称赞

m 的选择

“如果是这种做法,m 的选择就非常重要了,如果 k 值分布均匀还无所谓,如果 k 值具有某些特征

比如说 k 的个位基本上不变,而高位分布均匀,如 15,25,45,65,85,95,155,这么一组数据,经过你刚才的 k%10不就全部落在5这个位置上了吗?”一直没有说话的另一个李大臣发话了

这个李大臣虽少言寡语,但非常有才能

“对对对”,何大臣连声说道

“我们必须要使得经过Hash函数后关键字的分布均匀,尽量减少冲突,所以针对不同类型的关键字要有自己特定的Hash函数,整数应该有整数的Hash函数,字符串应该有字符串的Hash函数

就算针对同一类型的关键字,如果它具有某种规律,我们也要具体情况具体设计,刚才李大臣说的那种情况,我们就得选取其他分布均匀的高位来进行Hash”右丞相补充道

“那为何不优化一下我们的Hash函数来使得关键字分布均匀,比如说 m 取一个素数,这样就不会出现刚才的情况了,比如说m取11,15,25,45,65,85,95,155,这些数Hash后就会变成这个”,李大臣说着说着画了一个表

图片

“这样就分布均匀,冲突很少,所以我们只需要用一个长度为11的数组来存储就行,只比你原先的10多了一个长度”李大臣补充道

“如果事先知道元素的分布情况,那我们可以针对特定的元素来设计Hash函数,如果不知道的话,那我们就提前想一个比较好的Hash函数,来应对各种可能出现的情况

不管怎样,我们最终的目的就是让各个关键字均匀的Hash到不同的位置”,国王看天色渐晚,总结了一下,然后说道,今天就到这里,明天再议

发表回复

后才能评论