Skip to main content
 首页 » 编程设计

python之用于二次探测的计数探针

2025年05月04日16qq78292959

当使用二次探测将键插入列表时,我正在尝试计算探测的数量(或必须传递的索引的数量)

我有

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 

我认为这只会在每次索引更改时计算在内,但不会计算它跨越的索引数。如何计算 key 通过的每个索引?

请您参考如下方法:

如果您想实现Quadratic probe在哈希表上,您需要的不仅仅是您编写的函数。以下类(class)可完成您正在寻找的工作:

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