Python----数据结构（哈希表：哈希表组成，哈希冲突）

一、哈希表

哈希表(Hash table)是一种常用、重要、高效的数据结构。

哈希表通过哈希函数,可以快速地将键(Key)映射到值(Value)。从而允许在近常数时间内对键关联的值进行插入、删除和查找操作。

哈希表的主要思想是通过哈希函数将键转换为索引，将索引映射到数组中的存储位置

通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表，在首字母为L的表中查找“雷”姓的电话号码，显然比直接查找就要快得多。

二、代码展示

2.1、键值对

class Pair:  
    """键值对的类，包含一个键和一个值"""  

    def __init__(self, key: int, val: str):  
        """初始化键值对"""  
        self.key = key  # 键，整数类型  
        self.val = val  # 值，字符串类型  

    def __repr__(self):  
        """返回键值对的字符串表示"""  
        return f"{self.key} -> {self.val}"

2.2、初始化

    def __init__(self):  
        """构造方法，初始化哈希表"""  
        # 创建一个包含 100 个桶的数组  
        self.buckets: list[Pair | None] = [None] * 100

2.3、哈希函数

    def hash_func(self, key: int) -> int:  
        """哈希函数，将键映射到索引"""  
        index = hash(key) % 100  # 使用内置哈希函数计算键的哈希值，并对桶的数量取模  
        return index

2.4、添加键值对

    def put(self, key: int, val: str):  
        """添加键值对到哈希表"""  
        pair = Pair(key, val)  # 创建新的键值对  
        index: int = self.hash_func(key)  # 计算键的哈希索引  
        self.buckets[index] = pair  # 将键值对放入相应的桶中

2.5、查询值

    def get(self, key: int) -> str:  
        """根据给定的键查询值"""  
        index: int = self.hash_func(key)  # 计算键的哈希索引  
        pair: Pair = self.buckets[index]  # 获取对应的键值对  
        if pair is None:  
            return None  # 如果未找到，返回 None  
        return pair.val  # 返回找到的值

2.6、删除键值对

    def remove(self, key: int):  
        """根据给定的键删除键值对"""  
        index: int = self.hash_func(key)  # 计算键的哈希索引  
        self.buckets[index] = None  # 将桶置为 None，表示删除

2.7、返回所有键值对

    def entry_set(self) -> list[Pair]:  
        """返回哈希表中所有的键值对"""  
        result: list[Pair] = []  
        for pair in self.buckets:  
            if pair is not None:  
                result.append(pair)  # 将非空桶的键值对添加到结果列表中  
        return result

2.8、返回键

    def key_set(self) -> list[int]:  
        """返回哈希表中所有的键"""  
        result = []  
        for pair in self.buckets:  
            if pair is not None:  
                result.append(pair.key)  # 将非空桶的键添加到结果列表中  
        return result

2.9、返回值

    def value_set(self) -> list[str]:  
        """返回哈希表中所有的值"""  
        result = []  
        for pair in self.buckets:  
            if pair is not None:  
                result.append(pair.val)  # 将非空桶的值添加到结果列表中  
        return result

2.10、输出

    def print(self):  
        """打印哈希表中的所有键值对"""  
        for pair in self.buckets:  
            if pair is not None:  
                print(pair.key, "->", pair.val)  # 打印每个键值对

2.11、完整代码

class Pair:  
    """键值对的类，包含一个键和一个值"""  

    def __init__(self, key: int, val: str):  
        """初始化键值对"""  
        self.key = key  # 键，整数类型  
        self.val = val  # 值，字符串类型  

    def __repr__(self):  
        """返回键值对的字符串表示"""  
        return f"{self.key} -> {self.val}"  


class ArrayHashMap:  
    """基于数组实现的哈希表"""  

    def __init__(self):  
        """构造方法，初始化哈希表"""  
        # 创建一个包含 100 个桶的数组  
        self.buckets: list[Pair | None] = [None] * 100  

    def hash_func(self, key: int) -> int:  
        """哈希函数，将键映射到索引"""  
        index = hash(key) % 100  # 使用内置哈希函数计算键的哈希值，并对桶的数量取模  
        return index  

    def put(self, key: int, val: str):  
        """添加键值对到哈希表"""  
        pair = Pair(key, val)  # 创建新的键值对  
        index: int = self.hash_func(key)  # 计算键的哈希索引  
        self.buckets[index] = pair  # 将键值对放入相应的桶中  

    def get(self, key: int) -> str:  
        """根据给定的键查询值"""  
        index: int = self.hash_func(key)  # 计算键的哈希索引  
        pair: Pair = self.buckets[index]  # 获取对应的键值对  
        if pair is None:  
            return None  # 如果未找到，返回 None  
        return pair.val  # 返回找到的值  

    def remove(self, key: int):  
        """根据给定的键删除键值对"""  
        index: int = self.hash_func(key)  # 计算键的哈希索引  
        self.buckets[index] = None  # 将桶置为 None，表示删除  

    def entry_set(self) -> list[Pair]:  
        """返回哈希表中所有的键值对"""  
        result: list[Pair] = []  
        for pair in self.buckets:  
            if pair is not None:  
                result.append(pair)  # 将非空桶的键值对添加到结果列表中  
        return result  

    def key_set(self) -> list[int]:  
        """返回哈希表中所有的键"""  
        result = []  
        for pair in self.buckets:  
            if pair is not None:  
                result.append(pair.key)  # 将非空桶的键添加到结果列表中  
        return result  

    def value_set(self) -> list[str]:  
        """返回哈希表中所有的值"""  
        result = []  
        for pair in self.buckets:  
            if pair is not None:  
                result.append(pair.val)  # 将非空桶的值添加到结果列表中  
        return result  

    def print(self):  
        """打印哈希表中的所有键值对"""  
        for pair in self.buckets:  
            if pair is not None:  
                print(pair.key, "->", pair.val)  # 打印每个键值对  


if __name__ == '__main__':  
    map = ArrayHashMap()  # 创建一个新的哈希表实例  
    map.put('m', '蟒')  # 添加键值对  
    map.put('s', '蛇')  
    map.put('c', '程')  
    map.put('x', '序')  
    map.put('y', '员')  
    
    # 查询并打印值  
    print(map.get('m'))  # 输出：蟒  
    print(map.get('s'))  # 输出：蛇  
    print(map.get('c'))  # 输出：程  
    print(map.get('x'))  # 输出：序  
    print(map.get('y'))  # 输出：员  
    
    # 打印哈希表的内容  
    map.print()  
    print(map.entry_set())  # 输出所有的键值对