哈希

哈希表

Hash Table 是一种用于存储键值对(key-value pair)的数据结构,可翻译做散列,也可直接音译做哈希。哈希算法就是把任意长度的输入,通过散列算法,变换成固定长度的输出,该输出就是哈希值。这种转换是一种压缩映射,也就是,哈希值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从哈希值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

哈希表是除了数组之外,最常见的数据结构,几乎所有的语言都会有数组和哈希表这两种集合元素,有的语言将数组实现成列表,有的语言将哈希表称作结构体或者字典,但是它们其实就是两种设计集合元素的思路,数组用于表示一个元素的序列,而哈希表示的是键值对之间映射关系。

我们平常经常使用的数组也可以看做是一个特殊的哈希表,数组中的“键”即为数组索引,值为相应的数组元素。也就是说,当哈希表中所有的键都是较小的整数时,我们可以使用数组来实现哈希表,将数组的索引作为键,而索引处的数组元素即为键对应的值,但是这一表示仅限于所有的键都是比较小的整数时,否则可能会使用一个非常大的数组。哈希表是对以上策略的一种“升级”,但是它可以支持任意的键而并没有对它们做过多的限定。对于基于哈希表实现的哈希表,若我们要在其中查找一个键,需要进行以下步骤:

  • 首先我们使用散列函数将给定键转化为一个“数组的索引”,理想情况下,不同的 key 会被转为不同的索引,但在实际应用中我们会遇到不同的键转为相同的索引的情况,这种情况叫做碰撞,在下文我们会讨论常见的碰撞解决方案,而在自然语言处理系列中我们会讨论文本哈希的相关算法。

  • 得到了索引后,我们就可以像访问数组一样,通过这个索引访问到相应的键值对。

以上就是哈希表的核心思想,哈希表是时空权衡的经典例子。当我们的空间无限大时,我们可以直接使用一个很大的数组来保存键值对,并用 key 作为数组索引,因为空间不受限,所以我们的键的取值可以无穷大,因此查找任何键都只需进行一次普通的数组访问。反过来,若对查找操作没有任何时间限制,我们就可以直接使用链表来保存所有键值对,这样把空间的使用降到了最低,但查找时只能顺序查找。在实际的应用中,我们的时间和空间都是有限的,所以我们必须在两者之间做出权衡,哈希表就在时间和空间的使用上找到了一个很好的平衡点。哈希表的一个优势在于我们只需调整散列算法的相应参数而无需对其他部分的代码做任何修改就能够在时间和空间的权衡上做出策略调整。散列技术既是一种存储方法,也是一种查找方法。然而它与线性表、 树、图等结构不同的是,前面几种结构,数据元素之间都存在某种逻辑关系,可以用连线图示表示出来,而散列技术的记录之间不存在什么逻辑关系,它只与关键字有关联。因此,散列主要是面向査找的存储结构。

Hash CheatSheet

Hash 就是把任意长度的输入(又叫做预映射, pre-image),通过哈希算法,变换成固定长度的输出(通常是整型),该输出就是哈希值。这种转换是一种 压缩映射 ,也就是说,哈希值的空间通常远小于输入的空间。不同的输入可能会散列成相同的输出,从而不可能从哈希值来唯一的确定输入值。简单的说,就是一种将任意长度的消息压缩到某一固定长度的息摘要函数。

数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。

我们可以从上图看到,左边很明显是个数组,数组的每个成员是一个链表。该数据结构所容纳的所有元素均包含一个指针,用于元素间的链接。我们根据元素的自身特征把元素分配到不同的链表中去,反过来我们也正是通过这些特征找到正确的链表,再从链表中找出正确的元素。其中,根据元素特征计算元素数组下标的方法就是 哈希算法。

总的来说,哈希表适合用作快速查找、删除的基本数据结构,通常需要总数据量可以放入内存。在使用哈希表时,有以下几个关键点:

hash 函数(哈希算法)的选择:针对不同的对象(字符串、整数等)具体的哈希方法;

碰撞处理:常用的有两种方式,一种是 open hashing,即 >拉链法;另一种就是 closed hashing,即开地址法(opened addressing)。

SuRF

SuRF 是一种查询效率高、压缩比高的字典树(Trie)数据结构,其功能十分简单,提供过滤器的功能。众所周知,BloomFilter 被广泛用于单点过滤——用于判断单个 key 是否存在于集合中。而 SuRF 的不仅拥有单点过滤功能,还能支持范围查询这个大杀器,即其能根据给出的 key 范围来判断其是否在集合中。SuRF 是一种 Trie 树结构,Trie 树的结构使其能支持范围查询,但传统 Trie 树所占空间太大,效率低,在数据库里实际运用很少。SuRF 的突破创新点是其拥有极限小的空间,其 trie 树的每个节点平均只需要占 10bit 空间,而且同时保持了很高的查询性能,构造性能。SuRF 团队将 SuRF 运用到了目前十分受欢迎的 NoSQL 系统 RocksDB 之中,在范围查询之中提升了 1.5 倍~5 倍的效率。

哈希表的缺陷

查找限制

比如那种同样的关键字,它能对应很多记录的情况,却不适合用散列技术。一个班级几十个学生,他们的性别有男有女,你用关键字“男”去査找,对应的有 许多学生的记录,这显然是不合适的。这个时候可以用班级学生的学号或者身份证号来散列存储,此时一个号码唯一对应一个学生才比较合适。同样哈希表也不适合范围查找,比如査找一个班级 18-22 岁的同学,在哈希表中没法进行。想获得表中记录的排序也不可能,像最大值、最小值等结果也都无法从哈希表中计算出来。

哈希冲突

另一个问题是冲突。在理想的情况下,每一个关键字,通过散列函数计算出来的地址都是不一样的,可现实中,这只是一个理想。我们时常会碰到两个关键字 key1 ≠ key2,但是却有 f (key1) = f (key2),这种现象我们称为冲突(collision),并把 key1 和 key2 称为这个散列函数的同义词(synonym)。出现了冲突当然非常糟糕,那将造成数据査找错误。尽管我们可以通过精心设计的散列函数让冲突尽可能 的少,但是不能完全避免。于是如何处理冲突就成了一个很重要的课题,这在我们后面也需要详细讲解。

链接