Linear probing and Quadratic probing

[drfcool]

Hello everyone, this time i have a question about this 2 algorithms,they are suposed to solve colisions in hash tables!

Does anyone have Python Examples of Implementations ?

I was given homework with this, im doing research on them, but the only language i consider myself capable of doing advanced coding is Python and Information I've found in google until now isn't really helpful for someone who does not really know C and Java Well.

[sneekula]

I played with it a little, but I am not sure about the complete algorithm. This is as far as I came:

# use linear and quadratic probing to find collision in an integer list
# incomplete:
# function quadratic_probe() needs to get all index values!!!!

import random

def linear_probe(n, r_list):
    """
    a linear probe checks every element in r_list
    """
    for ix in range(len(r_list)):
        if n == r_list[ix]:
            if test_print:
                print("ix = %s" % ix)
            return True
    return False

def quadratic_probe(n, r_list):
    """
    a quadratic probe checks the r_list every n^2 element
    if not found it shifts the probing
    needs work to reach all index values!!!!
    """
    # for test
    qix_list = []
    r_len = len(r_list)
    q_len = int(len(r_list)**0.5)
    shift = 0
    for shift in range(0, r_len):
        for ix in range(shift, q_len):
            qix = ix**2 + shift
            qix_list.append(qix)
            if test_print:
                print("ix=%s  shift=%s  qix=%s" % (ix, shift, qix))
            if r_list[qix] == n:
                if test_print:
                    print(sorted(qix_list))
                return True
    if test_print:
        print(sorted(qix_list))
    return False
    
# for debugging set to True
test_print = True

# create a list of count random integers in the range low to high-1
low = 100  #1000
high = 120  #12000
count = 17  #9000
r_list = random.sample(range(low, high), count)

# test the first 10 elements
print(r_list[:10])
#print(len(r_list))

# now create a another randomm integer in the range low to high-1
n = random.randrange(low, high)
# testing ...
print("n = %s" % n)

# and probe the list for collision (does the value exist?)

if linear_probe(n, r_list):
    print("linear probe found collision")

if quadratic_probe(n, r_list):
    print("qudratic probe found collision")

Maybe someone can look into it, so that all index values are eventually reached. Right now it seems to skip a fair number of them.