前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Hash表(一)——Hash函数

Hash表(一)——Hash函数

作者头像
用户3470542
发布2019-07-10 15:39:58
1.7K0
发布2019-07-10 15:39:58
举报
文章被收录于专栏:算法半岛

↑点击上面"算法半岛"

关注"算法半岛"第一时间接收最新文章

Hash表的理解

Hash表也叫 散列表,具有像数组那样根据随机访问的特性,可以根据 key来获得 value

我们通过一个具体实例来理解散列表。当学校举办校运动会,每个运动员都有一个号码牌,这个号码牌的是根据“年级+班级+需序号”组成,比如初一三班的小岛的号码牌为 070311,其中 07表示七年级即初一, 03表示三班, 11表示班上第11个班上参加运动会的序号。这个时候我们如何存储运动员的信息,来实现通过号码牌来查找运动员的信息?

按照以往的经验,我们可以通过使用数组来存储,其中号码牌即为数组的下标,数组的值为运动员的信息。但是这里有一个问题,运动员的号码牌不是连续的,而申请数组的时候内存空间是连续的,因此会有很多内存空间浪费。

这个时候就可以使用散列表,处理过程如下所示:

从上图可以观察到,我们在存储运动员信息的时候,不是将整个号码牌作为数组的下标,而是将号码牌先进行 hash函数(对100取余)处理后得到的数作为数组的下标,这样就可以数组的大小大大减小,并且在查找到时候也可以通过号码牌来查找对应的运动员的信息。

细心的小伙伴观察到,如果 hash函数处理后的余数一样该怎么办?比如,号码牌为 080211的运动员就会和 070311运动员在 hash函数处理后得到的数是一样,因此会发生冲突,这个就是散列冲突的问题,在后续的讲解中会有相应的解决方案。这里先讲解 Hash函数。

Hash函数

从上面的图可以观察到,中间的部分的部分为 Hash函数,也称为散列函数。它在散列表中起着关键作用。

Hash函数一般使用 hash(key)表示,其中 key表示元素的键值部分, hash(key)的表示经过 Hash函数计算得到的 Hash值(散列值)。

对于上面运动会的问题,我们的 Hash函数是将号码牌转为整型后对 100取余。不同的应用实例 Hash函数不同,该怎么去构造 Hash函数,一般遵循一下三条:

  • Hash函数计算得到的散列值是一个非负整数
  • 如果 key1==key2,那么 hash(key1)==hash(key2);
  • 如果 key1!=key2,那么 hash(key1)!=hash(key2).

对于第一条很好理解,因为数组的下标是从0开始,所以 Hash函数生成的 Hash值也需要是非负整数。

对于第二条,相同的 key经过 Hash函数处理后得到的 Hash值应该也是相同的。

对于第三条,逻辑上应该是这样的,不同的 key经过 Hash函数处理后得到的 Hash值应该是不相同的,但是想要找到一条不同的 key对应的 Hash值都不一样几乎为不可能的,数组的存储空间是有限的,会加大散列冲突的概率。对于散列冲突,我们需要通过其他的方式来解决。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-07-02,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 算法半岛 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Hash表的理解
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档