vlambda博客
学习文章列表

哈希表概念

哈希表（散列表），是基于关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数（哈希函数），存放记录的数组叫做散列表。

上面所提到的哈希函数是指：有一个对应关系 f ，使得每个关键字和结构中一个唯一的存储位置相对应，这样在查找时，我们不需要像传统的查找算法那样进行比较，而是根据这个对应关系 f 找到给定值K的像f（K）。

哈希函数与哈希表

• 这个hash函数并没有什么统一标准，它的核心思想就是就是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。

• 这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数，这个消息可能是字符、数组、字符串等等。

• 再使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位。

• 拥有这样的hash存储结构的数据结构称为散列表，或者叫哈希表。

• 哈希表一般基于数组实现，特定情况下结合链表，但是数组是哈希表基础数据结构。

为什么要有哈希表呢？
数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法。

哈希算法

一个hash函数需要满足

1. 接受一个单一的参数，这个参数可以是任何类型，但是只能是一个。

2. 返回一个整型值(一般情况下)。

4. 对于两个相同的输入，输出必须相同。

5. 对于两个不同的输入，输出相同的概率需要做到非常小。

6. hash的计算不能过于复杂，时间复杂度尽可能地低。

既然自己想不到比较好的hash算法，我们就来看看别人是怎么做的吧，下面是一些常用的hash算法：

• 直接定址法
  取key的线性函数值作为hash值，value = a * key + b,a,b为常数。这一类散列码的特点是：对输入为整型数据而言，不会产生下标冲突。不产生冲突当然是最完美的状态，但是这种方式要求输入的key遵循一定的线性规律。

例如：有一个01到07的部门人数统计表，其中，部门编号作为关键字，哈希函数取关键字自身。如下表所示：

• 除留余数法
  除留余数法：假设数组的长度为l，value = key % l,这一种散列码实现简单，运用比较多，但是如果输入的元素集合不具有一定的规律，比较容易产生冲突。数组的长度最好是质数，被除数为质数在一定程度上可以缓解数据堆积的问题。

除留余数法此方法为最常用的构造散列函数方法。对于散列表长为m的散列函数公式为：

f( key ) = key mod p ( p ≤ m )

mod是取模（求余数）的意思。事实上，这方法不仅可以对关键字直接取模，也可在折叠、平方取中后再取模。

显然在这里选取p的值至为关键，那么选取p值多少为合适呢？下面我们来举个例子看看：有一个关键字，它有7个记录。如果采用除留余数法，那么可以先尝试将散列函数设计为f(key) = key mod 7的方法。比如12 mod 7= 5，所以它存储在下标为5的位置。

不过这也是存在冲突的可能的，像7、14、21、28、35…..这些获得的下标都为零。

如何合理选取p值?
使用除留余数法的一个经验是，若散列表表长为m，通常p为小于或等于表长（最好接近m)的最小质数或不包含小于20质因子的合数。
举个例子： 某散列表的长度为100，散列函数H(k)=k%P,则P通常情况下最好选择哪个作为p呢？答案是97。

• 数字分析法
  数字分析法即对关键字进行分析，取关键字的若干位进行或者组合进行hash计算，这一类散列码的特点是比较灵活，通常是结合其他hash函数来计算，可根据实际情况来做出调整，具有相当的灵活性。

有学生的生日数据如下：

经分析，第一位，第二位，第三位、第四位重复的可能性大，取这四位造成冲突的机会增加，所以尽量不取前四位，取后四位比较好。

例如：每一种西文图书都有一个国际标准图书编号，它是一个10位的十进制数字，若要以它作关键字建立一个哈希表，当馆藏书种类不到10,000时，可采用此法构造一个四位数的哈希函数。

处理哈希冲突的方法

基本原则： 从hash函数的要求可以看到，事实上我们只能定义对于两个不同的输入，输出相同的概率尽可能小。

    （1）-di值可能为1,2,3,…m-1，称线性探测再散列。如果di取1，则每次冲突之后，向后移动1个位置.
    （2）-di取值可能为1,-1,4,-4,9,-9,16,-16,…kk,-kk(k<=m/2）称二次探测再散列。
    （3）-di取值可能为伪随机数列。称伪随机探测再散列。

线性探测再散列

二次探测再散列

• 多哈希法
  设计多种哈希函数，可以避免冲突，但是冲突几率还是有的，函数设计的越好或越多都可以将几率降到最低。

• 拉链法
  拉出一个动态链表代替静态顺序存储结构，可以避免哈希函数的冲突，不过缺点就是链表的设计过于麻烦，增加了编程复杂度。此法可以完全避免哈希函数的冲突。

左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。

总结

优点：

• 不论哈希表中有多少数据，查找、插入、删除（有时包括删除）只需要接近常量的时间即0(1）的时间级。实际上，这只需要几条机器指令。

• 哈希表运算得非常快，在计算机程序中，如果需要在一秒种内查找上千条记录通常使用哈希表（例如拼写检查器)哈希表的速度明显比树快，树的操作通常需要O(N)的时间级。哈希表不仅速度快，编程实现也相对容易。

• 如果不需要有序遍历数据，并且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

缺点：

• 它是基于数组的，数组创建后难于扩展，某些哈希表被基本填满时，性能下降得非常严重，所以程序员必须要清楚表中将要存储多少数据（或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程）。