神速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),作者:涛声依旧

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 选择排序

    面试官: 聊聊选择排序 选择排序是一种简单直观的算法,今天我们聊聊选择排序的思想,代码以及复杂度 排序思想 一天,小一尘和师傅下山去了,在集市中路经一个水果摊,...

    用户1260737
  • 神速Hash

    面试官: 聊聊HashMap的底层 理解HashMap底层,首先应该理解Hash函数,今天我们聊聊Hash函数出现冲突的解决办法(此故事为连载形式,若没看上篇...

    用户1260737
  • 快速排序(基础版)

    用户1260737
  • 2020年值得你去试试的10个React开发工具

    JavaScript每天都在出现大量的框架和工具,而React是除了上次我们提到的Vue和Ember之外另一款比较流行的框架。但因为新的工具每天都在不断的出现,...

    葡萄城控件
  • Web App Install Banners简介

    移动端,web和native app有一个比较大的区别:访问的过程。

    RP道貌不岸然
  • React教程:组件,Hooks和性能 [每日前端夜话0x36]

    正如 我们的React教程第一部分 【点击直达】中所指出的,开始使用 React 相对容易。首先使用 Create React App(CRA)初始化一个新项目...

    疯狂的技术宅
  • java 集合框架(List操作)

    /*list 基本操作 * * List a=new List(); * 增 * a.add(index,element);按指定位置添加,其余元素...

    用户3030674
  • Java自动化测试(webdriver常用API 24)

    缺点:设置是针对全局的,在WebDriver实例整个生命周期有效,但并不是所有的元素都需要等待

    zx钟
  • 追溯 React Hot Loader 的实现

    文:萝卜(沪江金融前端开发工程师) 本文原创,转载请注明作者及出处 如果你使用 React ,你可以在各个工程里面看到 Dan Abramov 的身影。他于...

    iKcamp
  • 机器学习day2

    为了能够使得组合特征避免出现参数过多,过拟合等问题,因此,我们需要找到有效的方法帮助我们进行特征的组合。 以预测问题举例。 输出特征有年龄,性别,购买物品类别,...

    Rare0716

扫码关注云+社区

领取腾讯云代金券