Question
****python**** Consider the HashTable class given in the textbook: class HashTable: def __init__(self, s=13): self.size = s self.slots = [None] * self.size self.data = [None]
****python****
Consider the HashTable class given in the textbook:
class HashTable: def __init__(self, s=13): self.size = s self.slots = [None] * self.size self.data = [None] * self.size def put(self,key,data): hashvalue = self.hashfunction(key,len(self.slots)) if self.slots[hashvalue] == None: self.slots[hashvalue] = key self.data[hashvalue] = data else: if self.slots[hashvalue] == key: self.data[hashvalue] = data #replace else: nextslot = self.rehash(hashvalue,len(self.slots)) while self.slots[nextslot] != None and \ self.slots[nextslot] != key: nextslot = self.rehash(nextslot,len(self.slots)) if self.slots[nextslot] == None: self.slots[nextslot]=key self.data[nextslot]=data else: self.data[nextslot] = data #replace def hashfunction(self,key,size): return key%size def rehash(self,oldhash,size): return (oldhash+1)%size def __str__(self): return str(self.slots)
Rewrite/Simplify the above Hashtable class. We will take a key and insert it into a list representing the hashtable using the following hash function
index = key % (length of hashtable)
You may assume there will be space for the key. If a collision occurs, you should use linear probing to determine where the key should be placed.
The 'None' value will be used to represent empty positions in the hashtable.
For example:
Test | Result |
---|---|
my_hash_table=LinearHashTable() my_hash_table.put(26) my_hash_table.put(54) my_hash_table.put(94) my_hash_table.put(17) my_hash_table.put(31) my_hash_table.put(77) print(my_hash_table) | [26, None, 54, 94, 17, 31, None, None, None, None, None, None, 77] |
template for the answer is:
class LinearHashTable:
def __init__(self, s=13):
self.size = s
self.slots = [None] * self.size
def put(self,key):
def hashfunction(self,key,size):
def __str__(self):
return str(self.slots)
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started