如何在Python中实现哈希查找算法

2023-04-16 00:00:00 算法 查找 如何在

哈希查找算法也叫散列表,是一种基于数组的数据结构,通过把关键字映射到数组的特定位置来高效地访问数据。

在Python中实现哈希查找算法,需要先定义哈希函数将关键字转换为数组下标,然后在数组中查找目标数据。

下面是一个简单的哈希查找算法的示例代码:

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

    def __str__(self):
        return str(self.data)

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

    def add(self, key, value):
        index = self.hash(key)
        if self.data[index] is None:
            self.data[index] = [[key, value]]
        else:
            for pair in self.data[index]:
                if pair[0] == key:
                    pair[1] = value
                    return
            self.data[index].append([key, value])

    def get(self, key):
        index = self.hash(key)
        if self.data[index] is not None:
            for pair in self.data[index]:
                if pair[0] == key:
                    return pair[1]
        return None

以上代码定义了一个哈希表类 HashTable,其中支持添加 key-value 键值对以及根据 key 查找 value。哈希函数将 key 中每个字符的 ASCII 码值相加并对哈希表的大小取模得到数组下标。

可以使用以下代码测试这个哈希表类:

hash_table = HashTable()
hash_table.add("pidancode.com", "Welcome to pidancode.com")
hash_table.add("皮蛋编程", "欢迎来到皮蛋编程")
print(hash_table.get("pidancode.com"))
print(hash_table.get("皮蛋编程"))

输出结果为:

Welcome to pidancode.com
欢迎来到皮蛋编程

可以看到,使用哈希查找算法可以快速地根据 key 查找到对应的 value。

相关文章