现在假设我们要使用员工的社保号作为唯一标识进行存储。社保号的格式为 DDD-DD-DDDD（D 的范围为数字 0-9）。

通常采用的冲突解决策略为 开放寻址法（Open Addressing） ，将所有的元素都存放在哈希表内的数组中，不使用额外的数据结构。

开放寻址法的最简单的一种实现就是 线性探查（Linear Probing） ，步骤如下：

现在如果我们要将五个员工的信息插入到哈希表中：

则插入后的哈希表可能如下：

元素的插入过程：

线性探查（Linear Probing）方式虽然简单，但并不是解决冲突的最好的策略，因为它会导致同类哈希的聚集（Primary Clustering）。这导致搜索哈希表时，冲突依然存在。例如上面例子中的哈希表，如果我们要访问 Edward 的信息，因为 Edward 的社保号 111-00-1235 哈希为 1235，然而我们在 1235 位置找到的是 Bob，所以再搜索 1236，找到的却是 Danny，以此类推直到找到 Edward。

一种改进的方式为 二次探查（Quadratic Probing） ，即每次检查位置空间的步长为平方倍数。也就是说，如果位置 s 被占用，则首先检查 s + 1 ² 处，然后检查s - 1 ² ，s + 2 ² ，s - 2 ² ，s + 3 ² 依此类推，而不是象线性探查那样以 s + 1，s + 2 ... 方式增长。尽管如此，二次探查同样也会导致同类哈希聚集问题（Secondary Clustering）。

另一种改进的开放寻址法称为 二度哈希（Rehashing） （或称为 双重哈希（Double Hashing） ）。

二度哈希的工作原理如下：

有一个包含一组哈希函数 H1...Hn 的集合。当需要从哈希表中添加或获取元素时，首先使用哈希函数 H1。如果导致冲突，则尝试使用 H2，以此类推，直到 Hn。所有的哈希函数都与 H1 十分相似，不同的是它们选用的乘法因子（multiplicative factor）。

在 .NET 中 Hashtable 类的哈希函数 Hk 的定义如下：

Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)))] % hashsize

当使用二度哈希时，重要的是在执行了 hashsize 次探查后，哈希表中的每一个位置都有且只有一次被访问到。也就是说，对于给定的 key，对哈希表中的同一位置不会同时使用 Hi 和 Hj。在 Hashtable 类中使用二度哈希公式，其始终保持 (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)) 与 hashsize 互为素数（两数互为素数表示两者没有共同的质因子）。

二度哈希使用了 Θ(m ² ) 种探查序列，而线性探查（Linear Probing）和二次探查（Quadratic Probing）使用了Θ(m) 种探查序列，故二度哈希提供了更好的避免冲突的策略。

向 Hashtable 中添加新元素时，需要检查以保证元素与空间大小的比例不会超过最大比例。如果超过了，哈希表空间将被扩充。步骤如下：

由此看出，对哈希表的扩充将是以性能损耗为代价。因此，我们应该预先估计哈希表中最有可能容纳的元素数量，在初始化哈希表时给予合适的值进行构造，以避免不必要的扩充。

链接技术（chaining） 是一种冲突解决策略（Collision Resolution Strategy）。在链接法中，把哈希到同一个槽中的所有元素都放到一个链表中。

使用探查技术（probing）时，如果发生冲突，则将尝试列表中的下一个位置。如果使用二度哈希（rehashing），则将导致所有的哈希被重新计算。而 链接技术（chaining） 将采用额外的数据结构来处理冲突，其将哈希表中每个位置（slot）都映射到了一个链表。当冲突发生时，冲突的元素将被添加到桶（bucket）列表中，而每个桶都包含了一个链表以存储相同哈希的元素。

上图中的哈希表包含了 8 个桶（bucket），也就是自顶向下的黄色背景的位置。如果一个新的元素要被添加至哈希表中，将会被添加至其 Key 的哈希所对应的桶中。如果在相同位置已经有一个元素存在了，则将会将新元素添加到列表的前面。

使用链接技术添加元素的操作涉及到哈希计算和链表操作，但其仍为常量，渐进时间为 O(1)。而进行查询和删除操作时，其平均时间取决于元素的数量和桶（bucket）的数量。具体的说就是运行时间为 O(n/m)，这里 n 为元素的总数量，m 是桶的数量。但通常对哈希表的实现几乎总是使 n = O(m)，也就是说，元素的总数绝不会超过桶的总数，所以 O(n/m) 也变成了常量 O(1)。

一个好的哈希函数应满足假设：每个关键字都等可能地被哈希到 m 个槽位的任何一个之中，并且与其他的关键字已被哈希到哪一个槽位中无关。不幸的是，通常情况下不太可能检查这一条件是否成立，因为人们很少能知道关键字所符合的概率分布，而各关键字可能并不是完全互相独立的。在实践中，常常运用启发式技术来构造好的哈希函数。比如在设计中，可以利用有关关键字分布的限制性信息等。

除法哈希法和乘法哈希法属于启发式的方法，而全域哈希法则采用了随机化技术来获取良好的性能。

一种好的哈希做法是以独立于数据中可能存在的任何模式的方式导出哈希值。例如，除法哈希法用一个特定的质数来除所给的关键字，所得的余数即为该关键字的哈希值。

除法哈希函数可表示为：

hash(key) = key mod m

其中 key 表示被哈希的关键字，m 表示哈希表的大小，mod 为取余操作。 假定所选择的质数与关键字分布中的任何模式都是无关的，这种方法常常可以给出很好的结果。

乘法哈希函数可表示为：

hash(key) = floor( m * ( A * key mod 1) )

其中 floor 表示对表达式进行下取整，常数 A 取值范围为（0<A<1），m 表示哈希表的大小，mod 为取余操作。 [A * key mod 1] 表示将 key 乘上某个在 0~1 之间的数并取乘积的小数部分，该表达式等价于 [A*key - floor(A * key)]。

乘法哈希法的一个优点是对 m 的选择没有什么特别的要求，一般选择它为 2 的某个幂次，这是因为我们可以在大多数计算机上更方便的实现该哈希函数。

虽然这个方法对任何的 A 值都适用，但对某些值效果更好，最佳的选择与待哈希的数据的特征有关。Don Knuth 认为 A ≈ (√5-1)/2 = 0.618 033 988... 比较好，可称为黄金分割点。

在向哈希表中插入元素时，如果所有的元素全部被哈希到同一个桶中，此时数据的存储实际上就是一个链表，那么平均的查找时间为 Θ(n) 。而实际上，任何一个特定的哈希函数都有可能出现这种最坏情况，唯一有效的改进方法就是随机地选择哈希函数，使之独立于要存储的元素。这种方法称作 全域哈希（Universal Hashing） 。

当关键字的集合是一个不变的静态集合（Static）时，哈希技术还可以用来获取出色的最坏情况性能。如果某一种哈希技术在进行查找时，其最坏情况的内存访问次数为 O(1) 时，则称其为 完美哈希（Perfect Hashing） 。

设计完美哈希的基本思想是利用两级的哈希策略，而每一级上都使用全域哈希（Univeral Hashing）。