How might this look like in code?


#1

Question

In the context of this exercise, explaining separate chaining, how might this look like in code?

Answer

When implementing separate chaining, each index of the array will contain a linked list or other data structure as each ‘chain’.

Here is a general overview of how this might look in Python. This will be different from how you actually implement it.

# First, we would set the array
array = [
  None,
  None,
  ...
]

# Each index will be set to a linked list, initially empty.
# This LinkedList class must be created separately.
bucket1 = LinkedList(None)
bucket2 = LinkedList(None)
...

array = [
  bucket1,
  bucket2,
  ...
]

# When we insert a new key-value to the hash map,
# first we get the index, using some hash function.
hash_index = hash_function(key, hashmap_size)

# Then, we insert it at the correct index, using 
# the linked list's function for adding a value.
array[hash_index].insert(value)