基于Python的哈希表算法实现

2023-04-11 00:00:00 python 算法哈希表

哈希表（hash table）是一种基于哈希函数（hash function）实现快速查找的数据结构。它将关键字 (key) 映射到哈希表的索引 (index) 上，使得查找时间复杂度为 O(1)。

下面是一个基于Python的哈希表算法实现，使用字符串“pidancode.com”作为范例：

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

    def hash(self, key):
        hash_value = 0
        for char in key:
            hash_value = (hash_value * 31 + ord(char)) % self.size
        return hash_value

    def insert(self, key, value):
        hash_value = self.hash(key)
        for i in range(len(self.table[hash_value])):
            if self.table[hash_value][i][0] == key:
                self.table[hash_value][i] = (key, value)
                return
        self.table[hash_value].append((key, value))

    def get(self, key):
        hash_value = self.hash(key)
        for i in range(len(self.table[hash_value])):
            if self.table[hash_value][i][0] == key:
                return self.table[hash_value][i][1]
        return None

# Example usage
table = HashTable(10)
table.insert("pidancode.com", 42)
print(table.get("pidancode.com")) # Output: 42

上述代码中，HashTable 类代表哈希表，它使用一个列表 table 来存储所有的键值对。在初始化时，将列表按照给定的大小 size 进行划分。

hash 方法根据给定的键 key 计算哈希值，采用的哈希函数是：$hash_value = (\sum_{i=0}^{len(key)-1}31^i \times ord(key[i])) \mod size$。其中，$ord(char)$ 返回字符 char 的 ASCII 码值。

insert 方法用于插入新的键值对，在插入前，先计算该键的哈希值，并遍历该哈希值对应的列表，查找是否已经存在该键，若存在，则更新其值，否则将其添加到列表中。

get 方法用于查找指定键的值，同样地，先计算其哈希值，并遍历其对应的列表，查找是否存在该键，若存在，则返回对应的值，否则返回 None。

上述代码只是一个基本实现，还有许多需要优化的地方，例如哈希函数的选择、冲突解决方法的实现等等。

相关文章