1.散列表概念

     散列表（hash table ,hash map）是一种使用散列函数将“键”映射到“值”的数据结构，这样散列表实现了字典结构。示意图如下：

     散列函数(hash function)将“键”转为bucket的索引，正如在上一篇介绍散列函数是说的，一般情况下散列表不是理想散列，会发生“碰撞”（即不同的键映射到了相同的的值）。

    使用散列解决的一个核心问题就是查找（search）。散列的思想是是把键的某些内容打乱，使用这种部分的信息作为查找的开始。为了使用散列表，我们需要解决两个问题：寻找散列函数（hash function）和解决“碰撞”。

2.散列函数

一个良好的散列函数要满足两个条件：

1. 容易计算。
2. 最小化“碰撞”。概率的角度看，就是要求散列函数应该让散列值服从一个均匀分布，一个非均匀的分布，在概率大的地方，显然容易发生“碰撞”。设计一个散列函数，让散列值服从均匀分布是困难的。

设计良好的散列函数一直是一个有挑战性的工作。通常有两种：基于除法和基于乘法。

1. 取余法。h(k)=k%M 。M的取值对于散列函数影响较大，通常M取一个素数，使得r^k <> a ,其中r为键字符集合级数，k,a是较小的数。
2. 乘法方法。

其中：w是计算机字数目，A是一个w互素的常数。

3.解决“碰撞”

1.独立拉链。这种解决方法思路很简单，就是将发生“碰撞”的<键,值>对用链表连接起来。如下图：

2.开放寻址。这种方法是确定某种规则，通过它，某个键K来确定一个“探查序列”，即表中的某些位置，每当查找或是插入K时，这些位置就会被探查。最简单的方法是：线性开放寻址散列，即当发生“碰撞”时，把<键,值>对存到下一个可用的bucket中去。如下图：

两种方法比较：

评价准则：负载因子（loading factor）: a= n / b 其中：n为元素数目；b为bucket的数目。

更多的信息，大家可以参考wikipedia或是taop。

参考：wikipedia ,taop