哈希冲突python

### Python 中哈希冲突及其解决方案

在 Python 的哈希表实现中，哈希冲突是指不同的键通过哈希函数计算后得到了相同的索引位置。这种情况下，如果不加以处理，则会导致数据覆盖或丢失。

#### 拉链法（Separate Chaining）

拉链法是一种有效的解决哈希冲突的方法，在这种方法里，每一个哈希表的位置都指向一个容器（通常是列表），该容器用来保存所有被分配到此位置的元素。当新加入的项与已有的项发生碰撞时，就将其添加到对应的容器内[^1]。

class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]

    def hash_function(self, key):
        return abs(hash(key)) % self.size
    
    def insert(self, key, value):
        index = self.hash_function(key)
        bucket = self.table[index]
        found = False
        
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # 更新已有条目
                found = True
                break
                
        if not found:
            bucket.append((key, value))
    
    def get(self, key):
        index = self.hash_function(key)
        bucket = self.table[index]

        for k, v in bucket:
            if k == key:
                return v
            
        raise KeyError(f'Key {key} not found')

上述代码展示了如何利用拉链法构建简单的哈希表结构，并实现了基本的插入和获取操作。每当遇到新的键值对时，程序会先尝试找到合适的桶位；如果发现目标位置已经被占用，则将该项追加到现有链条后面。

对于较大的数据集来说，采用拉链法能够很好地应对高频率发生的哈希冲突现象，因为它允许任意数量的对象共享同一散列码而不必担心空间不足的问题[^3]。