数据结构篇——哈希表（以Python为例）

一、哈希表介绍

​散列表（英译）（Hash table， 也称哈希表（音译）），是根据关键码值（Key Value）而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

​给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash)表，函数f(key)为哈希(Hash)函数。

二、哈希表

给定一对关键字、值，关键字经过散列函数转换，得到存储位置，该存储位置存储关键字、值。

1. 哈希函数

一般使用较多的哈希函数为除留余数法：
$$h(k)=k\mathrm{m}\mathrm{o}\mathrm{d}m$$
​ 假设有一个长度为5的数组，哈希函数$h(k)=k\mathrm{m}\mathrm{o}\mathrm{d}5$，元素集合为{11, 17, 3, 9, 5}的存储方式如下图所示：

2. 哈希冲突

​ 当元素集合为{11, 17, 3, 9, 5, 7}时，$7\mathrm{m}\mathrm{o}\mathrm{d}5=2$，其应该被放置于$i=2$处，但是此处已经有值17了，所以7再放置于此处会产生冲突。

​ 受限于哈希表的大小，当要存储的值的数量超过一定值时，就会出现两个不同的元素映射到同一个位置的情况，此种现象称之为哈希冲突。

​ 为解决哈希冲突，本文一共介绍两种常用的方法：

• 开放寻址法

  如果哈希函数返回的位置处已经有值存在，则向后寻找新的位置来存储这个值

  • 线性探测：如果位置 $i$ 被占用，则探查 $i+1,i+2,...$
  • 二次探测：如果位置 $i$ 被占用，则探查 $i+1^2,i-1^2,i+2^2,i-2^2...$
  • 二度哈希：有 $n$ 个哈希函数，当使用第一个哈希函数$h1$发生冲突时，则尝试使用$h2,h3...$

• 拉链法

  • 哈希表的每一个位置都以链表的形式来对值进行存储，当冲突发生时，冲突的元素被存储到链表的末端。

3. 哈希表的实现

下面哈希表的实现当中，所采用的的哈希函数为除留余数法，解决哈希冲突的方法选择的是线性探测法，同时，为了减小哈希冲突发生的概率，我们需要设定一个载荷因子$\alpha$（一般设为0.75），当$\alpha =\frac{size}{capacity}$(其中size为已插入表中的元素的个数，capacity为表的容量)的值达到载荷因子时，需要对表进行扩容，一般选择扩大到已插入元素数量的2倍。即size的两倍（2*size），或者当前容量的1.5倍（1.5*capacity）。

有一个值得注意的是，在扩容的过程中，原数组中的数据必须重新计算其在新数组中的位置之后，再放入新数组中。

• 定义哈希表

class HashTable(object):
    """哈希表类"""
    def __init__(self, capacity):
        self.capacity = capacity
        """
        当哈希表内的元素增加时，产生冲突的可能性增加，因此，需要设定一个载荷因子（一般设定为0.75），
        当α(=元素个数/表长)达到载荷因子时，需要重新定义表的长度，一般选择扩大到已插入元素数量的2倍，
        即size的两倍(2*size)，或者当前容量的1.5倍(capacity*1.5)
        """
        self.load_factor = 0.75
        self.size = 0
        self.hash_table = [(None, None) for _ in range(self.capacity)]

    def hash(self, x):
        return x % self.capacity

    def resize(self):
        """
        当哈希表内的元素增加时，产生冲突的可能性增加，因此，需要设定一个载荷因子（一般设定为0.75），
        当α(=元素个数/表长)达到载荷因子时，需要对表进行扩容，一般选择扩大到已插入元素数量的2倍，
        即size的两倍(2*size)，或者当前容量的1.5倍(capacity*1.5)
        原数组中的数据必须重新计算其在新数组中的位置之后，再放入新数组中
        """
        capacity_new = int(self.capacity*1.5)
        self.capacity = capacity_new
        hash_table_new = [(None, None) for _ in range(capacity_new)]

        for (key, value) in self.hash_table:
            if key is not None:
                hash_k = self.hash(key)
                if hash_table_new[hash_k][0] is None:
                    hash_table_new[hash_k] = (key, value)
                else:
                    for i in range(self.capacity):
                        hash_k = self.hash(key+i)
                        if hash_table_new[hash_k][0] is None:
                            hash_table_new[hash_k] = (key, value)
                            break
        self.hash_table = hash_table_new
        print("扩容函数被调用了......")         # 用于检测扩容函数被调用的次数

    def put(self, key, value):
        # 放置元素
        hash_k = self.hash(key)
        # 当存储数据与哈希表容量比大于载荷因子时，进行扩容
        if self.size/self.capacity > self.load_factor:
            self.resize()
        # 冲突处理
        if self.hash_table[hash_k][0] is None:
            self.hash_table[hash_k] = (key, value)
        else:
            for i in range(self.capacity):
                hash_k = self.hash(key + i)             # 线性探测
                if self.hash_table[hash_k][0] is None:
                    self.hash_table[hash_k] = (key, value)
                    break
        self.size += 1

    def get(self, key):
        # 获取元素值
        hash_k = self.hash(key)
        # 判断是否冲突，若冲突，则通过线性探测法（只要和前面放置元素的方法一致即可）寻找。
        h_key, h_value = self.hash_table[hash_k]
        if h_key == key:
            return h_value
        else:
            for i in range(self.capacity):
                hash_k = self.hash(key+i)
                h_key, h_value = self.hash_table[hash_k]
                if h_key == key:
                    return h_value
        return -1

• 哈希表的使用

if __name__ == "__main__":
    Dic = HashTable(capacity = 10)
    for i in range(23):
        Dic.put(i, "number {}".format(i))
    print(Dic.capacity)
    print(Dic.size)
    print(Dic.get(2))