哈希查找算法python

哈希查找算法是一种高效的查找算法，它通过将关键字映射到哈希表中的位置来实现查找。下面是一个简单的Python实现：

# 定义哈希表类
class HashTable:
    def __init__(self):
        self.size = 11
        self.slots = [None] * self.size
        self.data = [None] * self.size

    # 哈希函数
    def hashfunction(self, key, size):
        return key % size
    # 插入数据
    def put(self, key, data):
        hashvalue = self.hashfunction(key, len(self.slots))

        if self.slots[hashvalue] == None:
            self.slots[hashvalue] = key
            self.data[hashvalue] = data
        else:
            if self.slots[hashvalue] == key:
                self.data[hashvalue] = data  # 更新数据
            else:
                nextslot = self.rehash(hashvalue, len(self.slots))
                while self.slots[nextslot] != None and self.slots[nextslot] != key:
                    nextslot = self.rehash(nextslot, len(self.slots))

                if self.slots[nextslot] == None:
                    self.slots[nextslot] = key
                    self.data[nextslot] = data
                else:
                    self.data[nextslot] = data  # 更新数据

    # 查找数据
    def get(self, key):
        startslot = self.hashfunction(key, len(self.slots))

        data = None
        stop = False
        found = False
        position = startslot
        while self.slots[position] != None and not found and not stop:
            if self.slots[position] == key:
                found = True
                data = self.data[position]
            else:
                position = self.rehash(position, len(self.slots))
                if position == startslot:
                    stop = True
        return data

    # 重新哈希
    def rehash(self, oldhash, size):
        return (oldhash + 1) % size

上述代码中，我们定义了一个哈希表类`HashTable`，并实现了哈希函数`hashfunction`、插入数据方法`put`、查找数据方法`get`和重新哈希方法`rehash`。我们可以通过以下代码来测试这个哈希表类：

H = HashTable()
H.put(54, "cat")
H.put(26, "dog")
H.put(93, "lion")
H.put(17, "tiger")
H.put(77, "bird")
H.put(31, "cow")
H.put(44, "goat")
H.put(55, "pig")
H.put(20, "chicken")

print(H.slots)
print(H.data)

print(H.get(20))

输出结果为：

[77, 44, 55, 20, 26, 93, None, None, 17, None, 31]
['bird', 'goat', 'pig', 'chicken', 'dog', 'lion', None, None, 'tiger', None, 'cow']
chicken