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.

7 Years
Discussion Span
Last Post by 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
            if test_print:
                print("ix=%s  shift=%s  qix=%s" % (ix, shift, qix))
            if r_list[qix] == n:
                if test_print:
                return True
    if test_print:
    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

# 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.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.