综述

本文主要介绍散列表的概念、hash函数以及散列表的冲突解决方法等。本文的完整代码可以在我的github找到。

概念

散列表(Hash Table)是一种存储一对键值对(key, value)的数据结构，它可以直接根据键值key寻找元素的存储位置。散列表可以看作数组的一种推广，数组直接使用下标访问数组元素，散列表将key值映射到存储位置进而访问元素。我们定义装载因子$\alpha$如下：

$$\alpha=n/m$$
其中，m为散列表的槽位，n为要存储的元素数。

hash函数

将key值映射到槽h(key)的函数称为hash函数。hash函数将关键字的全域U映射到散列表T[0..m-1]的槽位上：

$$h: U \rightarrow \lbrace 0, 1, 2, 3, …, m - 1\rbrace $$
散列表的大小m一般远小于|U|。
一个好的散列函数应近似地满足简单均匀散列假设：

每个关键字都被等可能的散列到m个槽位中的任何一个，并与其他关键字已散列到那个槽位无关。

常见的散列函数有除法散列和乘法散列等。下面我们将以key为整数为例，介绍hash函数。对于key为字符串等类型时，通常根据一定的规则计算出一个整数值。

除法散列法

除法散列法使用模除将key映射到{0, 1, 2, 3, …, m - 1}，其python代码如下:

1 2	def div_hash(key, m): return key % m

散列表的大小m一般选择不太接近2的整数幂的素数，当$m=2^p$时， key对m取模时，相当于取key的二进制的后p位。当key的后p位的各种排列形式不是等可能的，将会增大冲突的概率。不过当后p位足够均匀时，m也可直接采用2的整数幂，而对hash值进行一系列的位变换，使得其足够均匀。例如python、java语言的源码对于hash表的实现都采用的是$m=2^p$。

乘法散列法

乘法散列法使用下面的变换将key映射到{0, 1, 2, 3, …, m - 1}

$$h(k)=\lfloor{m(kA mod 1)}\rfloor$$
其python代码如下：

1 2	def mul_hash(key, m, A): return int(m * (A * k - int(A * k))

其中m一般取2的整数幂，设计算机的字长位w位，A一般取形如$s/2^w$的分数，其值接近$(\sqrt{5}-1)/2$。其中kA mod 1为取kA的小数部分，即$kA - \lfloor{kA}\rfloor$。

冲突解决方法

当不同的k值映射到相同的槽时，即$h(k_1)=h(k_2)$我们说发生了冲突。解决冲突的方法通常有两种：链接法和开放寻址法。

链接法

链接法即使用链表来解决冲突，当发生冲突时，将映射到同一个槽的元素放在一个链表中。即对于散列表T[0, 1, 2, …, m- 1]，每一个槽i指向一个链表，该链表存放$h(k)=i$的元素。采用链接法解决冲突的python代码示例如下：

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.pre = None
        self.next =None

class HashTable:
    def __init__(self, m):
        self.m = m
        self.table = m * [None]

    def insert(self, key, value):
        h = self.div_hash(key)
        if self.table[h] is None:
            self.table[h] = Node(key, value)
        else:
            n1 = self.table[h]
            n2 = Node(key, value)
            self.table[h] = n2
            n2.next = n1
            n1.pre = n2

    def delete(self, key):
        h = self.div_hash(key)
        n = self.table[h]
        while n and n.key != key:
            n = n.next

        if n is None:
            print('no such data with key: %s' % key)
            return -1
        else:
            if n.pre is None:
                self.table[h] = n.next
            else:
                n.pre.next = n.next

            if n.next:
                n.next.pre = n.pre

            return 0

    def search(self, key):
        h = self.div_hash(key)
        n = self.table[h]
        while n and n.key != key:
            n = n.next

        if n is None:
            print('no such data with key: %s' % key)
            return -1
        else:
            return n.value

    def div_hash(self, key):
        h = 0
        for c in key:
            h = ord(c) + h * 127

        return h % self.m

对于散列表的每一个槽，其所指向的链表的期望长度为装载因子$\alpha$。对于链接法解决冲突的散列表，其装载因子一般大于1。在简单均匀散列的假设下，对于链接法解决冲突的散列表，一次不成功查找和一次不成功查找的平均时间均为O($1+\alpha$)。

开放寻址法

开放寻址法将所有的元素存放在散列表中，每个表项包含一个元素或者为NIL。因此一般使用开放寻址法解决冲突的散列表，其装载因子$\alpha$小于1，且一般为0.75左右。开放寻址法有一次探查和二次探查等方式。

一次探查

一次探查法采用的散列函数如下所示：

$$h(k, i)=(h_{1}(k)+i)modm, i=0,1, 2, …, m-1$$

$h_{1}(k)$即上述的散列函数，一次探查首先在$h_{1}(k)$计算的位置进行探查，如果探查不到，则依次往后探查，直至探查到为止。

二次探查

二次探查次采用的散列函数如下所示：

$$h(k, i)=(h_{1}(k)+c_1i+c_{2}i^2)modm, i=0, 1, 2, 3, …, m-1$$
其中$c_1$和$c_2$为正的辅助常数，一个可能的取值为1/2， 1/2，即算法导论11-3给出的方法。
以一次探查为例，其python代码示例如下：

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value

class HashTable:
    def __init__(self, m):
        self.m = m
        self.table = m * [None]
        self.state = m * ['idle']

    def div_hash(self, key):
        return hash(key) % self.m

    def linear_hash(self, key, i):
        return (hash(key) + i) % self.m

    def search(self, key):
        for i in range(self.m):
            h = self.linear_hash(key, i)
            if self.state[h] == 'idle':
                return None

            if self.state[h] == 'busy' and self.table[h].key == key:
                return self.table[h].value

        return None

    def insert(self, key, value):
        i = 0
        while i < self.m:
            h = self.linear_hash(key, i)
            if self.state[h] != 'busy':
                self.state[h] = 'busy'
                self.table[h] = Node(key, value)
                break
            
            i += 1

        if i >= self.m:
            print('hash map overflow')
        else:
            print('insert success')

    def delete(self, key):
        i = 0
        while i < self.m:
            h = self.linear_hash(key, i)
            if self.state[h] == 'busy' and self.table[h].key == key:
                self.state[h] = 'dirty'
                break

            i += 1

        if i < self.m:
            print('delete success')
        else:
            print('no such data with key %s' % key)

需要指出的是，在开放寻址法解决冲突的时，如果要删除某一个元素，不能直接将其删除，不然在进行查找的时候将查找不到与该元素冲突但在该元素后插入的元素。解决的办法为每一个元素加入一个状态变量，这样，当状态变量为’idle’时，表示这个位置为空；当状态变量为’dirty’时，表示这个位置的元素已经被删除；当状态变量为’busy’时，表示这个位置有元素。这样在查找时，遇到dirty的元素，并不退出循环；而在插入时，遇到dirty的元素，可以覆盖。

定义均匀散列如下：如果每个关键字的探查序列等可能地为(0, 1, …, m-1)的$m!$种排列中的任一种。在均匀散列的条件下，装载因子为$\alpha$的开放寻址散列表，一次不成功的查找，其期望的探查次数至多为$1/(1-\alpha)$，插入一个元素至多需要做$1/(1-\alpha)$次探查，一次成功查找中的期望探查次数至多为$\frac{1}{\alpha}ln(\frac{1}{1-\alpha})$。

Reference

本文主要参考《算法导论》。