Hi, does anyone can help me figure out what is happen with my code for HashTable
ID: 3844209 • Letter: H
Question
Hi, does anyone can help me figure out what is happen with my code for HashTable?
class BasicHashTable:
def __init__(self,size=7):
self.size = size
self.slots = [None]*self.size
def hash_function(self, key):
return key % self.size
def rehash(self, old_hash):
return (old_hash + 1) % self.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
def put(self, key):
ind = self.hash_function(key)
if self.slots[ind] == None:
self.slots[ind] = key
elif self.slots[ind] == key:
pass
else:
iter_count = 1
first_hash = ind
ind = self.rehash(first_hash)
while self.slots[ind] != None and self.slots[ind] != key and iter_count <= self.size:
iter_count += 1
ind = self.rehash(first_hash)
if self.slots[ind] == None:
self.slots[ind] = key
There is my whole code and I wanna to write a code which is put() in quadratic probing.
Test:
hash_t = BasicHashTable() #default table size is 7
hash_t.put(3)
hash_t.put(17)
hash_t.put(10)
print(hash_t.slots)
--------------------------
hash_t = BasicHashTable(11)
hash_t.put(14)
hash_t.put(6)
hash_t.put(17)
hash_t.put(27)
hash_t.put(7)
hash_t.put(16)
print(hash_t.slots)
Result:
[10, None, None, 3, 17, None, None]
-------------------------------------------------
[None, None, None, 14, None, 27, 6, 17, 7, 16, None]
But for my code, I always get the result just shown below:
[None, None, None, 3, 17, None, None]
------------------------------------------------------
[None, None, None, 14, None, 27, 6, 17, 7, None, None]
Can anyone help? Thank you
Explanation / Answer
The modified code is given below. While hashing it has to be done by linear probing and while rehashing it has to be done by quadratic probing.
class BasicHashTable:
def __init__(self, size = 7):
self.size = size
self.slots = [None] * self.size
def put(self, key):
ind = self.hash(key)
if self.slots[ind] == None:
self.slots[ind] = key
elif self.slots[ind] == key:
pass
else:
iter_count = 1
first_hash = ind;
ind = self.rehash(first_hash, iter_count)
while self.slots[ind] != None and self.slots[ind] != key and iter_count <= self.size:
iter_count += 1
ind = self.rehash(first_hash, iter_count)
if self.slots[ind] == None:
self.slots[ind] = key
def hash(self, key):
return key % self.size
def rehash(self, oldhash, iter):
n_hash = 0
n_hash = (oldhash + iter**2) % self.size
return n_hash
hash_t = BasicHashTable()
hash_t.put(3)
hash_t.put(17)
hash_t.put(10)
print(hash_t.slots)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.