散列又称为哈希（hash）它本身就是一个整数值，在不同的数制系统下有不同的表示，例如在16进制下的表示。但散列的整数值具有特殊的意义，它对应于一段字符串。一段字符串在给定的散列函数下生成确定的散列值，我们可以用以下的方式表示：

1
address = Hash(string)

我们认为address和string有对应关系，根据address我们可以快速确认string的值。

根据上述原理，可是实现符号表数据结构，这种实现不同于树类的实现。它可以在O(1)的时间复杂度下找到给定key下的value。而是类实现的字典，由于有一个查找过程，需要O(lgN)的时间复杂度。当然，这两种实现的性能比较是相对的。使用散列实现的符号表的性能和散列函数的质量关系很大，这个质量包括计算复杂度、随机程度。

接下来先讲散列函数的实现然后是符号表实现及其遇到的种种问题，然后对比散列实现的符号表和树类结构实现的符号表的差异。

散列函数

散列函数有很好的通用性，根据不同的输入都能输出散列后的值，例如输入字符串、数值、或者字符串和数值的混合。通常来说，高效的散列满足一下三个性质：

  • 一致性 相同的键必然会产生相等的散列值
  • 高效性 根据输入，快速计算出散列值
  • 均匀性 计算结果应该在一定范围内均匀分布

一致性并不能保证，不同的键会有不同的散列结果。不同的键生产相同的结果我们称为冲突。在有限的空间内均匀容纳无限组合可能的key必然或产生冲突，这时我们需要解决冲突的方式，后面会详细。

整数值散列函数

  1. 直接定址
1
Hash(key) = a*key + b

该方法计算简单、不会产生冲突，适用于key很小的情况，如果key很大，那么hash空间就非常大了，这并不实际。

  1. 除留余数

在大小为m的Hash空间中

1
Hash(key) = key%k  k<= m

k最后取接近m的质数，使用质数是确保key不能被整除，从而产生随机的余数。

结合方法1，我们可以设计如下的散列函数

1
Hash(key) = (a*key + b) % k  k<=m
  1. 折叠法

对于这个整数，我们可以把它均匀分为两部分或多部分，然后对它们求和。例如：

1
2
key = 123456
Hash(key) = 123 + 456 = 579

为了避免过大的散列空间，我们可以把产生进位的最高位除掉。

  1. 乘余取整数法

浮点数散列函数

对于浮点数，我们可以对其乘与一个大数M取下限，然后转化为整数值散列函数。

例如

1
Hash(key) = (M*key + b) % k  k<=m