2015-02-11 86 views
0

我一直在嘗試爲我的MyHashTable:類寫一個insert(self, key):方法。Python哈希值:插入方法

它應該使用線性探測來處理衝突解決。如果密鑰已在表格中,則該方法返回-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」不可迭代。

+0

代碼中沒有插入方法。這使得診斷您遇到的問題變得有點困難:-) – paxdiablo 2015-02-11 03:32:56

+0

是的。我需要寫一個..... – Newbie 2015-02-11 03:35:04

+0

你不會從那個添加的代碼中獲得「NoneType不可迭代」,'pass'不是習慣於迭代隨機集合:-)我建議你添加一個你的嘗試。 – paxdiablo 2015-02-11 03:38:26

回答

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 

我保留權利,給我們留下某些微妙的錯誤在那裏的情況下,這是課堂作業,你應該做你自己(其實事實是,我只是給它一個粗略的測試運行,因此它可能不是完全無bug,但它匹配我提供的算法,如應該接近)。

+0

我不明白你爲什麼做'slot =(slot + 1)%self.capacity'。你知道有什麼好的資源來學習使用類似類的哈希? – Newbie 2015-02-11 04:08:32

+0

@Newbie,這是模運算符,相當於'slot = slot + 1',後面跟'if slot == self.capacity:slot = 0'。當你超越結尾時,它只是簡單的回到數組的開頭。 – paxdiablo 2015-02-11 04:18:06

0

只要你沒有返回任何東西,你的insert()將不會返回一個迭代。

我猜你想要打印的是MyHashTable x本身。否則,您需要在insert()的定義中附加return self,雖然它看起來很奇怪。