Python Hash: метод ввода

Question

Я пытался написать метод insert(self, key): для моего класса MyHashTable:.

Предполагается использовать линейное зондирование для обработки разрешения столкновения. Если ключ уже находится в таблице, тогда метод возвращает -2. Если ключ еще не находится в таблице и существуют пустые слоты, то ключ вводится в пустой номер слота, возвращаемый hash_function, и этот номер слота возвращается. Если ключ не находится в хеш-таблице и нет пустых слотов, он возвращает -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) 
    if key in self.slots[slot]: 
     return -2 
    elif key in self.slots[slot] == False: 
     return -1 
    else: 
     self.slots[slot].append(key) 
     return slot 

Тест:

x = MyHashTable(2) 
print("Add 3, return:", x.insert(3)) 
print("Hashtable:", x) 
print("Add 3, return:", x.insert(3)) #duplicate 
print("Hashtable:", x) 

Результат должен быть:

Add 3, return: 1 
Hashtable: [None, 3] 
Add 3, return: -2 
Hashtable: [None, 3] 

Я попробовал несколько методов, но получаю ошибку. «Nonetype» не является итерируемым.

Answer 1

Хорошо, нам придется идти от первых принципов здесь. Вот что insert нужно будет сделать для вашего случая:

1. Получить начальный номер слота на основе ключа с помощью вызова hash_function. Сохраните эту позицию слота для более поздней, мы будем нуждаться в ней, чтобы определить, заполнена ли хэш-таблица.
2. Проверьте текущий слот, чтобы убедиться, что он пуст. Если это так, вставьте ключ в этот момент и верните успех.
3. Если ключ уже находится в этом слоте, возвращайте -2, это дубликат.
4. В противном случае в этом слоте есть другой ключ, поэтому перейдите в слот к следующему (оберните назад в нуль, если вы выйдете за пределы емкости). Если вы вернулись в исходный слот, сохраненный на шаге 1, верните -1, когда таблица заполнена.
5. В противном случае вернитесь к шагу 2 и продолжайте искать либо ключ, либо пустой слот.

Это как раз то, как работает работа с линейным зондированием.

Я призываю вас, чтобы попытаться осуществить это самостоятельно, вы станете лучше кодировщиком с некоторой кровью, потом и слез :-)

---

После того, как сделано, посмотреть, как он сравнивает с моим первоначальным разрезом:

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 

Я оставляю за собой право оставил некоторые тонкие ошибки там в случае, если это классная работа, что вы должны делать самостоятельно (на самом деле истина заключается в том, что я просто дал ему беглый испытательный пробег поэтому он не может быть полностью ошибка, но она соответствует алгоритму, который я предоставил так должно быть быть близко).

Answer 2

Ваша вставка() не будет возвращать итерируемый, если вы ничего не вернули.

Я предполагаю, что вы хотите напечатать, это MyHashTable x.В противном случае вам нужно добавить return self к определению insert(), хотя это выглядит действительно странно.