神速Hash

面试官: 聊聊HashMap的底层实现

理解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到不同的位置”,国王看天色渐晚,总结了一下,然后说道,今天就到这里,明天再议

未完待续

----------------------------------------------------

原文发布于微信公众号 - 趣谈编程(gh_51e791ad9174)

原文发表时间:2017-10-31

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-06.总结二维数组,面向对象

1:二维数组(理解) (1)元素是一维数组的数组。 (2)格式: A:数据类型[][] 数组名 = new 数据类型[m][n]; B:数据类型[][]...

2884
来自专栏JavaEdge

设计模式实战 - 解释器模式(Interpreter Pattern)

● 公式可以运行时编辑,并且符合正常算术书写方式,例如a+b-c ● 高扩展性,未来增加指数、开方、极限、求导等运算符号时较少改动 ● 效率可以不用考虑,晚...

1162
来自专栏小二的折腾日记

牛客网刷题总结-剑指offer(1)

这里一般的思路肯定是,从行或者列开始找,根据递增的顺序,找到行或者列之后再判断列或者行,知道找到为止。最好的方法是,从左下角或者右上角开始找。原因是:这样的一行...

1011
来自专栏算法channel

常用排序算法代码兑现

主要推送关于对算法的思考以及应用的消息。坚信学会如何思考一个算法比单纯地掌握100个知识点重要100倍。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎...

35911
来自专栏ACM算法日常

独角兽与数列(置换群循环)- HDU 4985

群论是法国数学家伽罗瓦(Galois)的发明。伽罗瓦是一个极具传奇性的人物,年仅21岁就英年早逝于一场近乎自杀的决斗中。他用该理论,具体来说是伽罗瓦群,解决了五...

863
来自专栏fangyangcoder

算法导论中的四种基本排序

                                                        by方阳

1232
来自专栏专知

关关的刷题日记12——Leetcode 189. Rotate Array 方法1、2、3

关小刷刷题12 – Leetcode 189. Rotate Array 方法1、2、3 题目 Rotate an array of n elements to...

3718
来自专栏落影的专栏

程序员进阶之算法练习(三十五)LeetCode专场

LeetCode上的题目是大公司面试常见的算法题,今天的目标是拿下5道算法题: 题目1是基于链表的大数加法,既考察基本数据结构的了解,又考察在处理加法过程中的边...

49216
来自专栏编程之旅

唠唠快速排序算法

每一个从事计算机相关方向工作的同学一定听说过快速排序算法,在面试的准备过程中,快排也一定是一个必须要牢牢掌握的算法。那么今天就来唠唠快速排序算法。

1132
来自专栏take time, save time

你所能用到的数据结构(五)

七、骚年,这就是你的终极速度了吗? 在介绍了前面的几个排序算法之后,这一次我准备写写快速排序,快速排序之所以叫快速排序是因为它很快,它是已知实践中最快的排序算...

2805

扫码关注云+社区

领取腾讯云代金券