計數探針探測二次

Question

我試圖計算探頭的使用鑰匙插入到一個列表時（必須經過索引或數字）的數量二次探測

我

def hash_quadratic(key, values): 
    tablesize=len(values) 
    index=key%tablesize 
    probes=0 
    if values[index] is None: 
     values[index]=key 
     probes+=1 
     return probes 
    else: 
     while values[index] is not None: 
      index = (index+1**2)% tablesize 
      probes+=1 
     values[index]=key 
    return probes 

我認爲這只是每次索引更改時計數，但不計算索引數量。我如何計算密鑰傳遞的每個索引？

Answer 1

如果你想在散列表上實現Quadratic probe，你需要的不僅僅是你寫的函數。以下課程是你正在尋找的工作：

class HashTable(object): 
    def __init__(self, size=200): 
     self.size = size 
     self.slots = [None] * self.size 

    def hash_function(self, key): 
     s = str(key)  
     n_hash = 0 
     for obj in s: 
      if obj.isdigit(): 
       n_hash = (n_hash << 5) + n_hash + ord(obj) 
     return n_hash % self.size  

    def quad_prob(self, oldhash, iter): 
     n_hash = 0 
     n_hash = (oldhash + iter**2) % self.size 
     return n_hash  

    def put(self, key): 
     collis_count = 0 
     hashval = self.hash_function(key)    
     if self.slots[hashval] == None: 
      self.slots[hashval] = key 
     else: 
      if self.slots[hashval] == key: 
       pass 
      else: 
       iter_count = 1 
       first_hash = hashval 
       nextslot = self.quad_prob(first_hash, iter_count) 
       # looking for a key or any empty slot 
       while self.slots[nextslot] != None and self.slots[nextslot] != key and iter_count <= self.size: 
        iter_count += 1 
        nextslot = self.quad_prob(first_hash, iter_count) 
       collis_count = iter_count 
       if self.slots[nextslot] == None: 
       self.slots[nextslot] = key 
     return collis_count