2

我需要帮助实现我的“MyHashTable”类的方法：

def search(self, search_key):

该方法应该使用线性探测来处理冲突解决。如果 search_key 在哈希表中，则该方法返回包含该 search_key 的槽的槽号。如果 search_key 不在哈希表中，该方法返回 -1

我的课看起来像这样：

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):

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

4

1 回答 1

2

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

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

您还必须处理有多个冲突的情况，因此我们需要检查哈希表中的每个元素以找到正确的值：

 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

您可以O(1)通过跟踪何时向哈希表添加唯一值来创建 len 方法，在Open_addressing上还有一个不错的 wiki 页面，您可以将其中的部分应用到您的代码中，它将帮助您创建正确的键映射值并在需要时调整哈希表的大小。如果你想存储的不仅仅是数字，你需要使用不同的散列函数，我只使用散列，但你可以使用任何你喜欢的东西。同样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
于 2015-10-11T09:42:54.630 回答