Python 数据结构：哈希查找（Hash Search）

# /*
# Python 数据结构：哈希查找（Hash Search）
# --------------------------------------------------------
# 概念：
# 哈希表（Hash Table）是一种通过“键 → 地址”的映射实现
# 高效查找的数据结构，平均查找时间复杂度 O(1)。
#
# 实现核心：
# 1) 哈希函数：将 key 映射到表的位置
# 2) 处理冲突：不同 key 可能映射到同一位置
#
# 冲突处理常见方法：
# 1) 开放定址法（Open Addressing）
#    - 线性探测（Linear Probing）
#    - 二次探测（Quadratic Probing）
#    - 双重哈希（Double Hashing）
#
# 2) 拉链法（Chaining）
#    - 每个桶是一个列表，冲突时放入同一个桶
#
# 本示例展示：
# A) 拉链法（Chaining）
# B) 线性探测法（Linear Probing）
# */

# ========================================================
# A) 拉链法（Chaining）实现
# ========================================================

class HashTableChaining:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]  # 每个桶是一个列表

    def hash_func(self, key):
        return key % self.size

    # 插入 key
    def insert(self, key):
        index = self.hash_func(key)
        if key not in self.table[index]:
            self.table[index].append(key)

    # 查找 key
    def search(self, key):
        index = self.hash_func(key)
        return key in self.table[index]

    # 显示表结构
    def display(self):
        print("\n【拉链法哈希表】")
        for i, bucket in enumerate(self.table):
            print(f"Bucket {i}: {bucket}")


# ========================================================
# B) 开放定址法：线性探测（Linear Probing）
# ========================================================

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

    def hash_func(self, key):
        return key % self.size

    # 插入 key（使用线性探测解决冲突）
    def insert(self, key):
        index = self.hash_func(key)
        original_index = index

        while self.table[index] is not None:
            index = (index + 1) % self.size
            if index == original_index:
                raise Exception("哈希表已满")

        self.table[index] = key

    # 查找 key
    def search(self, key):
        index = self.hash_func(key)
        original_index = index

        while self.table[index] is not None:
            if self.table[index] == key:
                return True
            index = (index + 1) % self.size
            if index == original_index:
                break
        return False

    # 显示结构
    def display(self):
        print("\n【线性探测哈希表】")
        for i, val in enumerate(self.table):
            print(f"Slot {i}: {val}")


# ========================================================
# 示例演示
# ========================================================

# ----------------------- 拉链法示例 ---------------------------------
ht_chain = HashTableChaining(size=7)

data = [10, 3, 17, 24, 31, 4, 11]
for x in data:
    ht_chain.insert(x)

ht_chain.display()

print("\n查找 17:", ht_chain.search(17))
print("查找 29:", ht_chain.search(29))

# --------------------- 线性探测示例 --------------------------------
ht_linear = HashTableLinearProbe(size=7)

for x in data:
    ht_linear.insert(x)

ht_linear.display()

print("\n查找 17:", ht_linear.search(17))
print("查找 29:", ht_linear.search(29))

# ========================================================
# 关键要点总结：
# --------------------------------------------------------
# 1) 哈希表平均查找时间复杂度 O(1)，非常高效；
# 2) 冲突不可避免，必须使用冲突解决策略；
# 3) 拉链法：结构简单，不易出现“表满”；
# 4) 线性探测：实现简单，但可能出现主聚集问题；
# 5) 根据应用场景选择不同的哈希方法；
# 6) 工程中 Python 的 dict 就是高效哈希表的实现；
# */

#
# 【拉链法哈希表】
# Bucket 0: []
# Bucket 1: []
# Bucket 2: []
# Bucket 3: [10, 3, 17, 24, 31]
# Bucket 4: [4, 11]
# Bucket 5: []
# Bucket 6: []
#
# 查找 17: True
# 查找 29: False
#
# 【线性探测哈希表】
# Slot 0: 31
# Slot 1: 4
# Slot 2: 11
# Slot 3: 10
# Slot 4: 3
# Slot 5: 17
# Slot 6: 24
#
# 查找 17: True
# 查找 29: False