Counting probes for quadratic probing

Question

I'm trying to count the number of probes (or number of indices that must be passed over) when inserting keys into a list using quadratic probing

I have

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

I think this just counts every time the index changes but doesn't count the number of indices that it crosses over. How do I count every index that the key passes?

I suspect that `(index+1**2)` doesn't do what you think it does. The `**` operator binds more closely than `+`. — Blckknght, Feb 05 '16 at 02:45
Also your top level `if` and `else` are probably not necessary, since the `while` loop tests the same condition. You should be able to let the loop run zero times instead of using the `if` block. — Blckknght, Feb 05 '16 at 02:48

score 1 · Answer 1 · answered Feb 05 '16 at 17:36

If you would like to implement Quadratic probe on a hash table, you need more than the function you have written. The following class does the job you are looking for:

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

Counting probes for quadratic probing

1 Answers1