由“两数之和”谈谈哈希表

胡啸宇 · · 79 次点击 · · 开始浏览    

为了响应陈皓老师的 ARTS 挑战,之后打算每周至少在 LetCode 上做一道算法题。那么就从最简单的开始做起吧。

LetCode 算法题 - 两数之和

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

LetCode 题解

解题思路有两种,一种是遍历两次去查找元素的暴力解法;另一种则要用到哈希表对时间复杂度进行优化:LetCode 官方题解

暴力解法在此就不过多叙述,这篇文章我想重点来讲讲 Hash Table 这种数据结构。

Hash Table - 哈希表

Hash Table 中文译名 散列表 ,又名 哈希表 或者 Hash 表。散列表利用了数组支持按照下标随机访问数据的特性,由数组扩展而来。

基本概念

首先在这里定义一下下文中有关 Hash Table 的基本概念:

  • 键(key):用于操作数据的标示,例如 PHP 数组中的索引,或者字符串键等等
  • 槽(slot/bucket):哈希表中用于保存数据的一个单元,也就是数据真正存放的容器
  • 哈希函数(hash function):将 key 映射 (map) 到数据应该存放的 slot 所在位置的函数
  • 哈希冲突(hash collision):哈希函数将两个不同的 key 映射到同一个索引的情况

散列思想

想要弄清散列表,就一定要先了解数组的实现:1.使用连续的内存空间储存 2.储存一组相同类型的数据

数组能够具有按照下标随机访问数据的特性,也是通过上面两条实现。首先获取数据类型的长度 type_size,然后根据数组下标 k 和数组的首地址 base_address,利用寻址公式 a[k]_address = base_address + k * type_size 即可实现时间复杂度 O(1) 的情况下随机访问数据。

而散列表的思想,便是通过散列函数将键转换为数组下标,然后根据数组下标存取数据,即 hash(key) => index。实际上,PHP 关联数组的设计便是利用了散列表这一思想。在 PHP 关联数组中,每个键关联一个值,即 key => value,通过合理的散列函数的设计,便可以将 key 从字符串转换为数组的数字下标 index,利用上文所述寻址公式到数组中存取 arr[index]

散列函数的设计

散列函数的基本要求有以下三点:

  • 散列函数计算得到的散列值是一个非负整数
  • 相同的 key 根据相同的散列函数得到的 value 相同
  • 不同的 key 根据相同的散列函数得到的 value 不同

第一条很好理解,由于数组下标都是非负整数,散列函数计算得到的值也应该为非负整数;第二条讲的是散列函数具有幂等性,使用同样的参数通过散列函数,都应该得到相同的返回值;而第三点,实际情况下想要完全实现并不是一件简单的事情。即使是一些知名的(例如 MD5)哈希算法,也无法避免这种散列冲突,再加上数组的存储空间有限,也会加大散列冲突的概率。

目前解决散列冲突常见的方法有 开放寻址法链表法,而 PHP 在处理散列冲突时则使用了链表法,这里简单介绍一下。

散列表中,每个槽 slot 对应一条链表,当出现散列冲突时,将值存放到对应槽中对链表中。

插入时,只需要通过散列函数 hash() 计算 key 对应的散列槽位 slot,将其插入对应链表中即可。所以插入的时间复杂度为O(1)。

查找或者删除时,时间复杂度与链表的长度 k 成正比,也就是 O(k)。对于散列比较均匀的散列函数,理论上 k = n/m。其中 n 表示散列中数据的个数,m 表示散列表中槽 slot 的个数。

值得注意的是,如果别有用心的人设计大量不同的 key 经过散列后都储存到同一个 slot 时,哈希表便会退化为一个链表,操作链表的时间复杂度为 O(n)。也就是说,如果原来散列表中有 10 万条数据,退化为链表之后,查询的效率就下降了 10 万倍。这样可能会导致大量 CPU 和线程资源用来处理查询操作,导致无法响应其他请求,使服务器遭受 DoS (服务拒绝攻击)。

因此,设计散列函数时,要保证以下两点:

  • 生成的值要尽可能的随机且均匀分布
  • 设计不能太复杂

其中设计太复杂是因为通过散列函数计算对应槽位时,也会有时间消耗。

小结

本篇文章主要是从 LetCode 的 “两数之和” 引发的思考,由于缺乏对数据结构的了解,看到这个题目时的思路只局限在暴力解法,很难想到利用哈希表查找时时间复杂度为 O(1) 的特性。希望之后能够对数据结构更深入了解,开拓自己的思路。

参考资料:

本文来自:Segmentfault

感谢作者:胡啸宇

查看原文:由“两数之和”谈谈哈希表

79 次点击  
加入收藏 微博
0 回复
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet