In this week\'s lab, you are given a hash table that has entries for \"all time

Question

In this week's lab, you are given a hash table that has entries for "all time favorite" movies according to IMDB. The hashing function for the keys is quite simple for this lab. The table has a fixed size of 10 and it is 70% full. Your first task is to come up with entries with your ownn favorite movies that will cause collisions in the hash table. You'll need to change the program so that it outputs the number of collisions. Then, come up with your own hash function that results in a lower collision rate with the same entries

Python file:

class StringHash:
def __init__(self, table_size):
self.table_size = table_size
self.keys = [''] * table_size
self.values = [''] * table_size
self.count = 0

def hash(self, elem):
return sum(map(lambda x: ord(x), elem))

def add(self, key, value):
try:
assert type(key) == str and type(value) == str
if self.count < self.table_size:
slot = self.hash(key) % self.table_size
if self.keys[slot] == '':
self.keys[slot] = key
self.values[slot] = value
self.count += 1
return True
else:
print('Collision b/w ' + self.keys[slot] + ' and ' + key)
return False
else:
print('Hash table is full!!!')
return False
except AssertionError:
print('Element should be string')

def __str__(self):
return str(dict(zip(self.keys, self.values)))

def main():
hash_table = StringHash(6)
hash_table.add('ECyGu', 'The Shawshank Redemption')
hash_table.add('cnHeg', 'The Godfather')
hash_table.add('UdXEA', 'The Dark Night')
hash_table.add('cgnON', 'Shutter Island')
hash_table.add('PFSwE', 'Schindler's List')
hash_table.add('biFYv', 'Pulp Fiction')
hash_table.add('XCTEa', 'Star Wars')
print(hash_table)
if __name__ == '__main__':
main()

Explanation / Answer

class StringHash:
def __init__(self, table_size):
self.table_size = table_size
self.keys = [''] * table_size
self.values = [''] * table_size
self.count = 0
self.collision = 0

def hash(self, elem):
return sum(map(lambda x: ord(x), elem))

## own hash function to reduce number of collision
# This function takes a string as input. It processes the string four bytes at a time,
# and interprets each of the four-byte chunks as a single long integer value
# The integer values for the four-byte chunks are added together.

def hash2(self, elem):
k = int(len(elem) / 4)
s = 0
for j in range(k):
c = elem[j*4:(j*4)+4]
m = 1
for k in range(len(c)):
s += ord(c[k]) * m
m *= 256
c = elem[k*4:]
m = 1
for r in range(len(c)):
s += ord(c[r]) * m
m *= 256
return abs(s)

def add(self, key, value):
try:
assert type(key) == str and type(value) == str
if self.count < self.table_size:
## change the hash function here to see the output difference
slot = self.hash2(key) % self.table_size
if self.keys[slot] == '':
self.keys[slot] = key
self.values[slot] = value
self.count += 1
return True
else:
self.collision += 1
print('Collision b/w ' + self.keys[slot] + ' and ' + key)
return False
else:
print('Hash table is full!!!')
return False
except AssertionError:
print('Element should be string')

def __str__(self):
## the return statement is modified so that it also return number of collision
return str(dict(zip(self.keys, self.values))) + " {'Collision' : " + str(self.collision) + "}"

def main():
hash_table = StringHash(6)
hash_table.add('ECyGu', 'The Shawshank Redemption')
hash_table.add('cnHeg', 'The Godfather')
hash_table.add('UdXEA', 'The Dark Night')
hash_table.add('cgnON', 'Shutter Island')
hash_table.add('PFSwE', 'Schindler's List')
hash_table.add('biFYv', 'Pulp Fiction')
hash_table.add('XCTEa', 'Star Wars')
## own fav movies that will cause collision
hash_table.add('Hngec', 'The Godfather - II')
hash_table.add('aTCEX', 'Star Wars - II')
print(hash_table)
if __name__ == '__main__':
main()

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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