Better than linear probing, is using a second hash function for determining the perturbation value for a hash table. This is called “double hashing”. The advantage is that collisions whereby different keys end up at the same index, use different chains to seek for empty slots. The second hash function, which is only used to determine the perturbation value, can usually be simpler than the one that determines the hash number. A possible second hash number for strings is to take the ordinal values for the first and the last character of the string, and add them up. You just have to make sure that the perturbation value, when taken modulo the size of the table, is not zero, otherwise you will get into endless loops. Change the example implementation that I give below to encompass double hashing.
Note: The submission of this exercise is in markdown and therefore won’t be tested. Use your preferred code editor or Papyrus1 to test your code.
SIZE = 13 # should be prime
FACTOR = 0.7 # limit to how many slots may be filled
PERTURB = 1 # perturbation value
hash_table = SIZE * [None]
# Stores an element in the table
def hash_store( hash_table, element, key ):
hashnum = hash( key )
while hash_table[hashnum%SIZE] != None:
if hash_table[hashnum%SIZE][0] == key: # Key already exists and the element is thus overwritten
hash_table[hashnum%SIZE] = (key, element)
return
if hash_table[hashnum%SIZE][1] == None: # Slot had an element which is now deleted, and can be overwritten
hash_table[hashnum%SIZE] = (key, element)
return
hashnum += PERTURB
if hash_table.count( None ) < (1 - FACTOR) * SIZE:
print( "Table is considered full,", key, "cannot be stored" )
return
hash_table[hashnum%SIZE] = (key, element)
# Removes an element from the table
def hash_remove( hash_table, key ):
hashnum = hash( key )
while hash_table[hashnum%SIZE] != None:
if hash_table[hashnum%SIZE][0] == key:
hash_table[hashnum%SIZE] = (key, None) # This indicates that the spot is empty, but can be part of a chain
return
hashnum += PERTURB
# Returns element if key is in table, otherwise None
def hash_find( hash_table, key ):
hashnum = hash( key )
while hash_table[hashnum%SIZE] != None:
if hash_table[hashnum%SIZE][0] == key:
if hash_table[hashnum%SIZE][1] != None:
return hash_table[hashnum%SIZE][1]
hashnum += PERTURB
return None
fruitlist = ["apple", "banana", "cherry", "durian", "fig", "grape", "lychee", "mango", "orange", "pear", "tangerine"]
for i in range( len( fruitlist ) ): # store as much fruit as possible
hash_store( hash_table, i+1, fruitlist[i] )
hash_store( hash_table, 99, "pear" ) # overwrite "pear"
hash_remove( hash_table, "apple" ) # remove "apple"
for i in range( len( fruitlist ) ):
element = hash_find( hash_table, fruitlist[i] )
if element:
print( fruitlist[i], "-", element )
else:
print( fruitlist[i], "is not in the table" )