[Python] Hi, I wrote a program to record collisions for inserting into a quadrat

Question

[Python]

Hi,

I wrote a program to record collisions for inserting into a quadratic probing hash table in python. How would I change it for just linear probing and double hashing table? Here's what I have. This program runs and works.

f = open("in.txt","r")
lines = f.read().splitlines()
keys = []
totalcollisions= 0
ourfile = open('increaseRandom.txt','r')
for line in ourfile:
for i in line.split():
keys.append(int(i))
ourfile.close()
HashTable = dict()
size = 191#size that was specified
for i in range(0,size):
HashTable[i] = None
collisions = []#records collisions for each key
for key in keys:
temp = key
collision = 0
while(True):
if HashTable[temp % size] == None:
collisions.append(collision)
HashTable[temp % size] = key
break
else:
totalcollisions+=1
collision = collision + 1
temp = ( temp % size ) + collision * collision
print ("Collisions record table:")
print (collisions)
print ("Total Collisions recorded for quadratic probing: {}".format(totalcollisions))

Explanation / Answer

You have taken key value and stored in temp, if initially there is no value in hash table, we place key value in the temp position.

If there is another value in the temp (i.e collision), we use probing.

In your program, Quadratic probing used, next index to search is

temp=(temp%size)+collision*collision

But for Linear probing, use temp = (temp%size)+collision

For Double hashing, you can create your own hash2 function. Here I am using hash2 function. i.e hash2=temp%size

                temp=(temp+collision*(temp%size))%size

you just need to change that paticular line only.

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.