哈希表

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

哈希表是除了数组之外，最常见的数据结构，几乎所有的语言都会有数组和哈希表这两种集合元素，有的语言将数组实现成列表，有的语言将哈希表称作结构体或者字典，但是它们其实就是两种设计集合元素的思路，数组用于表示一个元素的序列，而哈希表示的是键值对之间映射关系。当然，数组也可以看做是一个特殊的哈希表，数组中的“键”即为数组索引，值为相应的数组元素。也就是说，当哈希表中所有的键都是较小的整数时，我们可以使用数组来实现哈希表，将数组的索引作为键，而索引处的数组元素即为键对应的值，但是这一表示仅限于所有的键都是比较小的整数时，否则可能会使用一个非常大的数组。

对于基于哈希实现的哈希表，若我们要在其中查找一个键，需要进行以下步骤：

首先我们使用散列函数将给定键转化为一个“数组的索引”，理想情况下，不同的key会被转为不同的索引，但在实际应用中我们会遇到不同的键转为相同的索引的情况，这种情况叫做碰撞。
得到了索引后，我们就可以像访问数组一样，通过这个索引访问到相应的键值对。

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

- 哈希表查找步骤
- 哈希函数构建方法
  - 直接定址法
  - 数字分析法
  - 折叠法
  - 除法散列法
  - 乘法散列法
  - 平方取中法
  - 随机数法
- 处理哈希碰撞的方法
  - 线性探测法
  - 二次探测法
  - 随机探测法
  - 再哈希法
  - 链地址法
  - 公共溢出法
- 算法实现
- 哈希表性能分析
  - 哈希函数是否均匀
  - 处理冲突方法
  - 哈希表的装填因子

哈希表的缺陷

查找限制

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

哈希冲突

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

Links

最近更新于0001-01-01