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.

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.20 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.