Python 数据结构基础（五）：哈希表

1. 哈希表的定义

哈希表（Hash Table）又称为散列表，是一种基于哈希函数的数据结构，用于存储键值对（key-value pairs）。哈希表通过将键通过哈希函数映射到一个固定大小的数组中，从而实现快速查找、插入和删除操作。

哈希表的关键思想是使用哈希函数，将键映射到一个固定大小的数组中。哈希函数将键转换为数组索引，从而实现快速查找、插入和删除操作。

2. 哈希函数

哈希函数是一种将任意长度的输入映射到固定长度的输出的函数。哈希函数的输出称为哈希值或哈希码。哈希函数应该满足以下特性：

一致性：对于相同的输入，哈希函数应该始终输出相同的哈希值。
均匀分布：哈希函数应该将输入均匀地映射到输出空间中，以减少哈希冲突。
不可逆性：哈希函数应该难以从输出反推输入，以保证数据的隐私和安全。
高效性：哈希函数的计算应该尽可能高效，以减少哈希表的操作时间。
碰撞最小化：哈希函数应该尽可能减少哈希冲突，以保持哈希表的性能。

常用的哈希函数有：直接定位法、除留余数法、平方取中法、折叠法、旋转法等。

2.1 直接定位法

直接定位法是最简单的哈希函数，直接将键的值作为哈希值。例如，对于整数键，可以直接使用键的值作为哈希值。对于字符串键，可以使用字符串的ASCII码值之和作为哈希值。

$Hash(k) = k$

这种方法简单易实现，且不容易发生冲突。但是容易造成存储空间的浪费。

2.2 除留余数法

除留余数法是最常用的哈希函数之一，它将键的值除以一个固定的数（通常是表的长度），然后取余数作为哈希值。例如，对于整数键，可以使用键的值除以数组的大小，然后取余数作为哈希值。

$Hash(k) = k\ \mathrm{mod}\ m$

3. 哈希冲突

哈希冲突（Hash Collision）指的是两个不同的键通过哈希函数映射到同一个哈希值的情况。当发生哈希冲突时，需要采取一定的策略来解决冲突，以保持哈希表的性能。

解决哈希冲突的方法主要分为 开放寻址法 和 链寻址法。

3.1 开放寻址法

开放寻址法是一种解决哈希冲突的方法，它通过在哈希表中查找下一个空闲位置来解决冲突。当发生哈希冲突时，哈希函数会返回一个初始位置，然后从该位置开始，按照一定的规则查找下一个空闲位置，直到找到一个空闲位置为止。

3.2 链寻址法

链寻址法是一种解决哈希冲突的方法，它将具有相同哈希值的键存储在一个链表中。当发生哈希冲突时，哈希函数会返回一个链表的头节点，然后将具有相同哈希值的键插入到链表中。

4. 哈希表的实现

在 Python 中，可以使用字典（dict）来实现哈希表。字典是一种基于哈希表的数据结构，用于存储键值对。字典的键和值可以是任意类型的对象，但键必须是可哈希的。

除了 dict 之外，Python 还提供了 collections 模块中的 defaultdict、Counter 和 OrderedDict 类，它们也是基于哈希表的数据结构，但具有一些额外的功能。

如果想不使用内置数据结构实现哈希表，可以参考：

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

    def _hash(self, key):
        """哈希函数"""
        return hash(key) % self.size
    
    def insert(self, key, value):
        """插入键值对"""
        index = self._hash(key)

        if self.table[index] is None:
            self.table[index] = [(key, value)]
        else:
            for i, (k, v) in enumerate(self.table[index]):
                if k == key:
                    self.table[index][i] = (key, value)
                    return
            self.table[index].append((key, value))
    
    def get(self, key):
        """获取键对应的值"""
        index = self._hash(key)
        if self.table[index] is not None:
            for k, v in self.table[index]:
                if k == key:
                    return v
        return None

    def delete(self, key):
        """删除键值对"""
        index = self._hash(key)
        if self.table[index] is not None:
            for i, (k, v) in enumerate(self.table[index]):
                if k == key:
                    del self.table[index][i]
                    return
        return None

5. 哈希表的应用场景

哈希表的应用非常广泛，以下是一些常见的应用场景：

缓存：哈希表可以用于实现缓存，将频繁访问的数据存储在哈希表中，以加快访问速度。
数据库索引：哈希表可以用于实现数据库索引，将数据按照键进行哈希，从而实现快速查找。
字符串查找：哈希表可以用于实现字符串查找，将字符串哈希后存储在哈希表中，从而实现快速查找。
集合操作：哈希表可以用于实现集合操作，如并集、交集、差集等。
负载均衡：哈希表可以用于实现负载均衡，将请求均匀地分配到多个服务器上。

6. 哈希表的练习

5.1 两数之和

描述： 给定一个整数数组 nums 和一个整数目标值 target

要求： 在该数组中找出和为 target 的两个整数，并输出这两个整数的下标。可以按任意顺序返回答案。

示例：

>>> nums = [2, 7, 11, 15]
>>> target = 9
>>> twoSum(nums, target)
[0, 1]

思路： 使用哈希表存储数组中的元素及其对应的索引，然后遍历数组，对于每个元素，计算目标值与该元素的差值，然后在哈希表中查找该差值，如果找到了，则返回两个元素的索引。

代码：

def twoSum(self, nums: List[int], target: int) -> List[int]:
    # 创建一个 hash map 用于存储
    # {'num': 'index'}
    mapping = defaultdict(int)

    # 遍历数组
    for i, num in enumerate(nums):
        # 计算差值
        diff = target - num
        # 如果差值在 hash map 中，则返回
        if diff in mapping:
            return [mapping[diff], i]
        # 否则将当前值和索引存入 hash map
        mapping[num] = i

    return []