Modify the class BasicHashTable with double hashing (hash2(key)=5-key%5) such th

Question

Modify the class BasicHashTable with double hashing (hash2(key)=5-key%5) such that it stores a list of probe sequences for inserted keys.

The class should have the following attributes:

class BasicHashTable:

def __init__(self,size=7):

self.size = size

self.slots = [None] * self.size

self.probeSequences = [[]] * self.size

The list probeSequences contains initially an empty list for each slot. If a key is inserted into slots[k] then probeSequences[k] should contain the entire probe sequence produced when inserting that key

Please write the code in python

Test:

hash_t = BasicHashTable() #default table size is 7
hash_t.put(3)
hash_t.put(20)
hash_t.put(10)
print(hash_t.slots)
print(hash_t.probeSequences)

Result:

[None, 10, None, 3, None, None, 20]
[[], [3, 1], [], [3], [], [], [6]]

Explanation / Answer

I have designed and developed the Python Program for Hash table using Double Hashing. I have added the comments for each part of sections and attached the final output of it.

Let me explain you in brief and in step-by-step manner:-

Step-1:

The initial part is import the sys class which needs to be defined in the header files and mainly helps in combining both the print, get, and inserting into the hash table.

Example:-

class hashItems:
key = ""
value = 0

def __init__(hashSelf,key,value):
hashSelf.key = key
hashSelf.value = value

Step-2:

The next part is to bind the values to the key and values using the HashTable class by defining the hashtable size and its entries.

Example:-

class BasicHashTable :
hastTableSize = 0
hastTableEntries = 0
hastTableArray = []

Step-3:

The final step is to call the hashtable with the hash items which are neccessary using the insert method

Example:-

   hashObj = BasicHashTable (11)

item = hashItems("hashOne",1)
hashObj.insert(item)
hashObj.print()

Python HashTable Program:-

# It is the import method used to embedd methods and classes

import sys

class hashItems:
key = ""
value = 0

def __init__(hashSelf,key,value):
hashSelf.key = key
hashSelf.value = value

def print(hashSelf):
print(" '" + hashSelf.key + "' / " + str(hashSelf.value) )

# The basicHashTable is used to carry table size and table entries

class BasicHashTable :
hastTableSize = 0
hastTableEntries = 0
hastTableArray = []


def __init__(hashSelf, hashSize):
hashSelf.hastTableSize = hashSize
hashSelf.hastTableArray = [[] for i in range(hashSize)]

def insert(hashSelf,item):
hash = hashSelf.hashing(item.key)
# print(hash)
for i,it in enumerate(hashSelf.hastTableArray[hash]):
if it.key == item.key:
del hashSelf.hastTableArray[hash][i]
hashSelf.hastTableEntries -= 1
hashSelf.hastTableArray[hash].append(item)
hashSelf.hastTableEntries += 1   

def print(hashSelf):
print ( "The hash Table current scenario:" )
print ( str(hashSelf.getNumEntries()) + " list items in table" )
for i in range(hashSelf.hastTableSize):
print ( " [" + str(i) + "]: " )
for j in range(len(hashSelf.hastTableArray[i])):
hashSelf.hastTableArray[i][j].print()
print ( "The hash table ends" )

def getNumEntries(hashSelf):
return hashSelf.hastTableEntries


main:
hashObj = BasicHashTable (11)

item = hashItems("hashOne",1)
hashObj.insert(item)
hashObj.print()
hashObj.insert(item)
hashObj.print()

item = hashItems("hashTwo",2)
hashObj.insert(item)

item = hashItems("hashThree",3)
hashObj.insert(item)
hashObj.print()

item = hashItems("hashOne",4);
hashObj.insert(item);

items = hashObj.get("hashOne");
if items != None:
for j in range(len(items)):
items[j].print()

item = hashItems("The list of items are long enuf",123456789)
hashObj.insert(item)
hashObj.print()

items = hashObj.get("The list of items are long enuf")
if items != None:
for j in range(len(items)):
items[j].print()

items = hashObj.get("You have selected one item")
if items != None:
for j in range(len(items)):
items[j].print()

hashObj.delete("The list of items are long enuf")
hashObj.print()

hashObj.delete("You have selected one item")
hashObj.print()

hashObj.delete("Hash One selected")
hashObj.print()

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

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