起因

透过python的Dict冲突解决源码，其使用Open Addressing方式解决冲突，而二次再散列法是在搜索的时候出现的一个词。二次再散列法这个词组首先是这么理解，第二次，再稀疏，的方法，为什么这么理解？因为平时我们常说哈希函数，很清楚的知道是指这个hashing函数，但是它同样也叫散列函数，散列同样也可以理解为稀疏散开列，所以这里的散列并不是一个名词而是一个动词。为哈希冲突解决方法的统称的中文名称。

哈希函数 or 散列函数 (Hash function)

Source: Wikipedia

A hash function is any function that can be used to map data of arbitrary size to data of fixed size.

哈希函数是一个映射（mapping）函数，很多kv数据结构基础便基于此。

哈希表(Hash Table)

Source: Wikipedia

In computing, a hash table (hash map) is a data structure which implements an associative array abstract data type, a structure that can map keys to values.

本文所关心和所述皆是哈希表结构下的算法。数组通过下标直接寻址，可以在O(1)时间复杂度内访问任意元素，哈希表是普通数组O(1)时间复杂度的推广，为动态集合数据结构，在哈希表中查找一个元素的期望时间复杂度为O(1).

理想的哈希函数是希望将键值对分布在一系列的buckets中：

1
index = f(key, array_size)

实际上，通常是两部实现的：

1
2
hash = hashfunc(key)
index = hash % array_size

使用求模来减少存储空间，函数依赖于array_size长度，这种情况下array_size通常是2次方增长。

哈希冲突

潜在的数据通过哈希函数获得唯一index总是高于我们的期望，并且哈希冲突提高了操作的代价，哈希表的设计目标就是要尽可能的减少冲突发生。

通常有两种解决哈希冲突方法：避免和解决。

Collision Avoidance

哈希避免的方式简单来说就是选择更适合的哈希函数，所以要具体问题具体分析。

Collision Resolution

使用冲突解决方法就有很深的研究价值，目前有这些方法：

  • Separate chaining
    • Separate chaining with linked lists
    • Separate chaining with list head cells
    • Separate chaining with other structures
  • Open addressing
    • Coalesced hashing
    • Cuckoo hashing
    • Hopscotch hashing
  • Robin Hood hashing
  • 2-choice hashing

根据前文所提，那么这些解决冲突的方法就是标题中的二次再散列法的中文总称。

链接法（Separate Chaining）

非本文重点，简述。
链接技术（Chaining）将采用额外的数据结构来处理冲突，其将哈希表中每个位置（slot）都映射到了一个链表。当冲突发生时，冲突的元素将被添加到桶（bucket）列表中，而每个桶都包含了一个链表以存储相同哈希值的元素。

开放地址法（Open Addressing）

顾名思义，开放地址就是开放哈希表中的所有地址，不使用额外的空间。如果遇到冲突，寻找其他位置存储。

Linear Probing

线性探测，探测间隔总是固定的，通常为1.

$$H+1,H+2,H+3,H+4,…,H+k$$

也就是地址冲突，地址+1.

Quadratic probing

二次探查，这是线性探测的改进，每次的步长变为平方倍数。
$$ H+1^{2},H+2^{2},H+3^{2},H+4^{2},…,H+k^{2} $$
但同样也会有同类哈希聚集问题（Secondary Clustering）。

CPython 的 Dictionary冲突解决实现就是使用二次探寻散列，在c源码头注释可以看见：
Source: http://svn.python.org/projects/python/trunk/Objects/dictobject.c

1
2
3
j = (5*j) + 1 + perturb;
perturb >>= PERTURB_SHIFT;
use j % 2**i as the next table index;

Double hashing or Rehashing

另一种改进的开放寻址法称为重哈希(Double hashing)或者叫二度哈希（Rehashing）
随机第,一直地，独立地选定两个哈希函数$ h_1, h_2 $, 在哈希表$T$中$k$键的第$i$位为：
$$h(i,k) = (h_1(k)+i*h_2(k)) mod |T|$$

Reference