[译文]5分钟系列-快速理解Hash Table(哈希表)

原文链接 : What is a Hash Table?

什么是哈希表?

哈希表是用来存储同种类型 键/值对 的数据结构,它使得存储在哈希表内的 键/值对 能被非常高效的查找到。最典型的哈希表就是衣柜内的抽屉 :假如 第一格存放袜子,第二格存放T恤,第三格存放内衣。那么要找某一双袜子,你只要去第一格就能快速找到。 key(键)就是抽屉索引,value (值) 就是抽屉内存放的衣物

了解哈希表有什么用处?

  • 你可以大概了解哈希映射(hash map)、关联数组( associative array )、字典 ( dictionary ) 等这些常用的数据结构如何实现
  • 可以明白哪些数据比较适合用哈希表来存储

5分钟带你走入哈希表

假如我们现在要存储用户信息,同时还可以根据名字查找到对应用户的信息

用户信息

我们大可以将这三个用户存在一个数组内,查找的时候遍历数组对比名字,就能找到。看起来没什么问题,假如有成千上万个用户呢?那最差情况是不是得遍历所有用户挨个对比名字才能找到我们想要的用户信息,这显然效率低下

创建哈希表

为了能使用哈希表,存储的对象必须要有一个 唯一 的东西当作key,我们称它为:ID,假设用户的名字作为 ID 。哈希表的工作原理是将对象存储在对应的桶(buckets)内

一个哈希表选择多少个桶,各种编程语言内的集合类存储结构对桶的数量都有着不同的考量,这是个很大的话题,本文暂且就用4个桶来阐述哈希表的基本原理

每个用户该存储在哪个桶内呢?这是很关键的一步。你当然可以随便放入一个桶内,但下次拿的时候,你能想起来你放在哪个桶内吗?所以,此时需要一种算法,能根据 ID 迅速找到对应的桶号( 这就是 Hash Function 哈希函数 )

假设 a= 0, b=1, c=2 依次类推(不区分大小写),Ada = 0+3+0 = 3 ,那么 用户ada 就放入3号桶

同理,当我们需要获取 Ada 的相关信息的时候,就可以根据相同的算法,快速定位到 3 号桶,从而拿到他/她的信息 。让我们来存放第二个用户:Grace

哦吼,29超过了我们最大的桶编号,咋个办 ? 一个比较通用的办法是将 29 与桶的数量进行求余运算

一群小朋友玩躲猫猫的游戏,但是一开始谁最先找呢?就用到 “点兵点将 骑马打仗 有钱喝酒 没钱滚蛋 ”这个顺口溜,小伙伴站一排,然后通过这个顺口溜,一个字一个人,从头到尾数,人数不够就又从头来,点到 谁是 “蛋” 字,谁就开始找,这就是最原始的”求余”

29 % 4 = 1(也可以表示为:29 mod 4 = 1),因此用户 Grace 放入1号桶内,结果如下:

冲突

一个好的哈希函数的终极目标就是让每一个桶内只存放一个用户信息,让我们来存放用户 Tim 试试

结果显示,用户 Tim 应该放入 3 号桶,但是 3 号桶已经存储了 Ada 的相关信息,这就是所谓冲突

针对冲突,常用的方法有如下方法:

  • 发现当前桶已经存储了信息,就存入下一号桶内,如果下一号桶也存储了信息,就继续下去直到有空的桶。上文 3 号桶已经存储了信息,那么我们就找下一号桶,因为没有4号桶,所以就跳到0号桶存入
  • 每个桶是一个数组/链表,可以存储多个对象,求余结果一样,放到同一个桶内
  • 增加桶的数量,这样就能大大降低冲突的概率

因此,哈希表最重要的是哈希函数,一个好的哈希函数能让信息均匀的存入每个桶内(但是冲突永远无法避免,只能减少概率)。最坏的哈希函数导致的结果可能是所有的对象都放在同一个桶内,这就跟直接放入数组内没有什么区别了

关于哈希表的更详细信息,可以参考我翻译的数据结构系列文章:数据结构

课外延申

发表评论

电子邮件地址不会被公开。 必填项已用*标注