开放地址法的哈希表扩容

开放地址法是一种解决哈希冲突的方法，它通过在哈希表中寻找下一个可用的位置来存储冲突的元素。当哈希表的装载因子达到一定阈值时，需要进行扩容来保持哈希表的性能。下面是开放地址法的哈希表扩容的步骤：

1. 创建一个新的更大的哈希表，通常是原哈希表大小的两倍。
2. 将原哈希表中的所有元素重新哈希到新的哈希表中。
3. 将新的哈希表替换为原哈希表。

在重新哈希的过程中，需要使用新的哈希函数来计算元素在新哈希表中的位置。常见的重新哈希方法有线性探测、二次探测和双重哈希等。

下面是一个示例代码，演示了开放地址法的哈希表扩容过程：

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

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

    def rehash(self, key):
        return (key + 1) % self.size

    def put(self, key, value):
        index = self.hash_function(key)
        while self.keys[index] is not None:
            if self.keys[index] == key:
                self.values[index] = value
                return
            index = self.rehash(index)
        self.keys[index] = key
        self.values[index] = value

    def resize(self):
        new_size = self.size * 2
        new_keys = [None] * new_size
        new_values = [None] * new_size
        for i in range(self.size):
            if self.keys[i] is not None:
                index = self.hash_function(self.keys[i])
                while new_keys[index] is not None:
                    index = self.rehash(index)
                new_keys[index] = self.keys[i]
                new_values[index] = self.values[i]
        self.size = new_size
        self.keys = new_keys
        self.values = new_values

# 创建一个哈希表
hash_table = HashTable(5)

# 添加元素
hash_table.put(1, 'A')
hash_table.put(2, 'B')
hash_table.put(3, 'C')
hash_table.put(4, 'D')
hash_table.put(5, 'E')

# 扩容哈希表
hash_table.resize()

# 输出扩容后的哈希表
print(hash_table.keys)
print(hash_table.values)