Python MyHashTable class: 线性探测的搜索方法

Question

我需要帮助实现我的方法 "MyHashTable" class:

def search(self, search_key):

该方法应该使用线性探测来处理冲突解决。如果 search_key 在散列 table 中，则方法 returns 包含该 search_key 的槽的槽号。如果 search_key 不在散列 table 中，方法 returns -1

我的 class 看起来像这样：

class MyHashTable:

def __init__(self, capacity):
    self.capacity = capacity
    self.slots = [None] * self.capacity

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

def __len__(self):
    count = 0
    for i in self.slots:
        if i != None:
            count += 1
    return count

def hash_function(self, key):
    i = key % self.capacity
    return i

def insert(self, key):
    slot = self.hash_function(key)
    orig = slot
    while True:
        if self.slots[slot] is None:
            self.slots[slot] = key
            return slot

        if self.slots[slot] == key:
            return -2

        slot = (slot + 1) % self.capacity
        if slot == orig:
            return -1

def search(self, search_key):

任何帮助或教程链接都会很棒。谢谢

Answer 1

您只使用一个列表来存储所有值，如果您想要一个散列 table，您可以使用一个列表列表，其中每个列表都是一个桶，但如果您只是想检查是否元素在您的散列 table 中，使用您自己的代码：

def search(self, search_key):
    hsh = self.hash_function(search_key)
    if self.slots[hsh] is None:
        return -1
    while hsh < self.capacity:
        if self.slots[hsh] == search_key:
            return hsh
        hsh += 1
    return -1

您还必须处理发生多次冲突的情况，因此我们最多需要检查散列中的每个元素 table 以找到正确的值：

 def search(self, search_key):
    hsh = self.hash_function(search_key)
    if self.slots[hsh] is None:
        return -1
    for i in range(self.capacity):
        mod = (hsh + i) % self.capacity
        if self.slots[mod] == search_key:
            return mod
    return -1

第一个 while 循环将一次探测一个值，但如果我们从多个冲突中环绕列表，它会在开始时丢失元素，因此使用 range 和 mod = (hsh + i) % self.capacity 确保我们检查所有条目，如下例所示。

m = MyHashTable(5)

m.insert(13) # 13 % 5 = 3
m.insert(73) # 83 % 5 = 3
m.insert(93) # 93 & 5 = 3
print(m.search(13)) # 3
print(m.search(73)) # 4
print(m.search(93)) # 0
print(m.search(2)) # -1

您可以通过跟踪何时将唯一值添加到哈希 table 来创建您的 len 方法 O(1)，Open_addressing 部分也有一个不错的 wiki 页面您可以将其采用到您的代码中，它将帮助您创建键到值的正确映射，并在需要时调整哈希 table 的大小。如果你想存储的不仅仅是数字，你需要使用不同的散列函数，我只使用散列，但你可以使用任何你喜欢的。当您的散列 table 已满且密钥不存在时使用 in 也会导致无限循环，因此您需要处理这种情况：

class MyHashTable:
    def __init__(self, capacity):
        self.capacity = capacity
        self.slots = [None] * self.capacity
        self.count = 0

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

    def __contains__(self, item):
        return self.search(item) != -1

    def __len__(self):
        return self.count

    def hash_function(self, key):
        return hash(key) % self.capacity

    def find_slot(self, key):
        slot = self.hash_function(key)
        while self.slots[slot] is not None and self.slots[slot] != key:
            slot = (slot + 1) % self.capacity
        return slot

    def insert(self, key):
        slot = self.find_slot(key)
        if self.slots[slot] != key:
            self.slots[slot] = key
            self.count += 1

    def search(self, key):
        i = self.find_slot(key)
        if self.slots[i] is not None:  
            return i
        return -1

添加 __contains__ 也将允许您使用 in 来测试成员资格：

m = MyHashTable(5)

m.insert("foo")
m.insert(73)
m.insert(93)
m.insert(1)
print(m.search(73))
print(m.search(93))
print(m.search(1))
print(m.search("foo"))
m.insert(73)
print(m.slots)
print(len(m))
print("foo" in m)
print(5 in m)

输出：

3
4
1
0
['foo', 1, None, 73, 93]
4
True
False

Python MyHashTable class: 线性探测的搜索方法

Python MyHashTable class: search method with linear probing

python

class

hashtable

linear-probing