Python: Implementing a hash table that uses double hashing

Your hash table class will be called HashTable. You will need to modify the put() and delete() functions. You will also need to implement a number of your own functions. This should be done in steps as listed below:

Programme: Python

HashTable.py

class HashTable:

def __init__(self):

self.__size = 7

self.__slots = [None] * self.__size

self.__data = [None] * self.__size

self.__deleted = "\0"

self.__count = 0

def hash_function(self, key, size):

return key % size

def rehash(self, old_hash,size):

return (old_hash + 1) % size

def get(self, key):

start_slot = self.hash_function(key,len(self.__slots))

position = start_slot

while self.__slots[position] != None:

if self.__slots[position] == key:

return self.__data[position]

else:

position = self.rehash(position, len(self.__slots))

if position == start_slot:

return None

return None

def put(self,key,data):

hash_value = self.hash_function(key,len(self.__slots))

if self.__slots[hash_value] == None or \

self.__slots[hash_value] == self.__deleted:

self.__slots[hash_value] = key

self.__data[hash_value] = data

elif self.__slots[hash_value] == key:

self.__data[hash_value] = data

else:

next_slot = self.rehash(hash_value, len(self.__slots))

while self.__slots[next_slot] != None\

and self.__slots[next_slot] != self.__deleted \

and self.__slots[next_slot] != key:

next_slot = self.rehash(next_slot,len(self.__slots))

if next_slot == hash_value:

return

if self.__slots[next_slot] == None or \

self.__slots[next_slot] == self.__deleted:

self.__slots[next_slot] = key

self.__data[next_slot] = data

else:

self.__data[next_slot] = data

def delete(self, key):

start_slot = self.hash_function(key, len(self.__slots))

position = start_slot

key_in_slot = self.__slots[position]

while key_in_slot != None:

if key_in_slot == key:

self.__slots[position] = self.__deleted

self.__data[position] = self.__deleted

return None

else:

position = self.rehash(position, len(self.__slots))

key_in_slot = self.__slots[position]

if position == start_slot:

return None

return None

def __delitem__(self, key):

return self.delete(key)

def __setitem__(self,key,data):

self.put(key,data)

def __getitem__(self,key):

return self.get(key)

def __len__(self):

count = 0

for value in self.__slots:

if value != None and value != self.__deleted:

count += 1

return count

def __contains__(self, key):

return self.get(key) != None

def __repr__(self):

str_rep = "{"

for i in range(len(self.__slots)):

key = self.__slots[i]

data = self.__data[i]

info = ""

if key == None or key == self.__deleted:

info = ""

else:

if data == None:

info = str(key) + ":None"

else:

info = str(key) + ":" + str(data)

str_rep += info + ", "

return str_rep[:-2] + "}"

Generator.py

from HashTable import HashTable import random

animal_list = ["aardvark", "bull", "cat", "dog", "elephant", "frog",\ "goat", "horse"] print("Test 1") print("------") h_table = HashTable() print("Insertion:") for i in range(len(animal_list)): h_table[i] = animal_list[i] print("key:",i,"data:",animal_list[i]) print(h_table,"count:",len(h_table)) print() print("Deletion:") for i in range(len(animal_list)): del(h_table[i]) print(h_table,"count:",len(h_table)) print()

print("Test 2") print("------") h_table = HashTable() print("Insertion:") for i in range(len(animal_list)): key = random.randrange(0,1000) h_table[key] = animal_list[i] print("key:",key,"data:",animal_list[i]) print(h_table,"count:",len(h_table)) print()

Your hash table class will be called HashTable. The constructor for this class has no parameter. Five instance variables will be initialized: size -the size of the hash table count -the number of items in the hash table .slots - a python list with size number of elements. data -a python list with size number of elements. deleted- a string consisting of the null character "10" . You will need to modify the put ) and delete functions discussed in class. You will also need to implement a number of your own functions. This should be done in steps as listed below: 1. Modify the put ) and delete () functions so that the variable count is altered appropriated whenever a key-data pair is added to or deleted from the hash table. Change the len function so that it returns this count. 2. Your hash table will use the remainder method as discussed in lectures: key % size. For collision resolution you will need to implement a second hash function: size-(key 96 (size-1)+1). You will need to alter the implementation of the rehash function to use this second hash function. You will need to implement a function that calculates the load factor of the hash table. Remember that the load factor is calculated using the formula: = count / size 3. 4. To increase the size of the hash table you want to find a prime number that approximately doubles its current size. For example if your hash table has a size of 7, you will be looking at increasing the size of the table to 13. You will need to implement a function that finds the largest prime number in the range n+1 to 2n. 5. You will need to implement a resize) function that increases the size of the hash table appropriately and rehashes all existing key-data pairs into the appropriate slots in the larger hash table. You will need to modify the put function to use this resize () function appropriately