hash_table.py

CaptainLupa commented on Oct 19, 2021 •

Tried to make line by line breakdown of this for people who aren't getting it still(took me like 15 minutes to get it as well lol):

# This simply lets us add a type hint of Any to function arguments to let python
# know that it can be literally anything.
from typing import Any


class HashMap:
    def __init__(self, size):
        # Create list of size size
        # i.e., size = 5, self.map = [None, None, None, None, None]
        self.map = [None] * size
        # store initial length of list
        self.size = len(self.map)

    def checkForKey(self, key: str):
        h1 = hash(key)  # create hash of key
        firstIndex = h1 % self.size  # Make hashed key fit inside self.map

        if not self.map[firstIndex]:  # if self.map[firstIndex] is None
            return (False, firstIndex)
            # Key does not exist and there is nothing there, so return False and firstIndex to insert()
        elif self.map[firstIndex][0] == key:
            return (True, firstIndex)
            # Both the key and the value are stored in self.map as [key, value],
            # so self.map[firstIndex][0] would grab index 0 of the [key, value] which is the key.
            # If the existing key is equal to the key we are checking for, we tell the insert function to
            # simply replace the value of that [key, value] pair.

        # Think of this next part as a big else statement

        # Since both of the above conditions were skipped, there must be a collision where we wanted to
        # place our [key, value] pair.
        # To deal with this, we use double hashing.
        h2 = hash(key + 'd')
        # We create a new hash that is slightly different than our first one

        # We create our 'c' variable as Dojo calls it, I will call it stride here because it will represent
        # our stride across the list as we search for a new home for our [key, value] pair.
        stride = h2 % (self.size - 1) + 1
        # Going through this with order of operations we get a stride between 1 and self.size - 1, Dojo
        # explained this well enough in his video

        # Our second index variable
        secondIndex = (firstIndex + stride) % self.size

        while secondIndex != firstIndex:  # Go through the entire table
            # Same conditions as the first if and elif statements
            if not self.map[secondIndex]:
                return (False, secondIndex)
            elif self.map[secondIndex][0] == key:
                return (True, secondIndex)
            else:
                secondIndex = (secondIndex + stride) % self.size

        return (False, -1)  # Table is full

    def insert(self, key: str, value: Any):
        # Run the search function we just wrote
        searchResult = self.checkForKey(key)

        # A Result of -1 means the table is full, so end the function here
        if searchResult[1] == -1:
            return

        # A result of True means that the key already exists and we should simply update the value
        # associated with it
        if searchResult[0]:
            index = searchResult[1]
            self.map[index][1] = value
            return

        # There is now only one option left, and that is to put the new [key, value] pair where the hashing
        # we did in the checkForKey() function tells us to
        index = searchResult[1]
        self.map[index] = [key, value]

    def get(self, key: str):
        # Basically the same process as the insert() function, except here we just return the value of the
        # [key, value] pair
        searchResult = self.checkForKey(key)

        # Table is full
        if searchResult[1] == -1:
            return

        # Key does not exist
        if not searchResult[0]:
            return False

        # Return value of [key, value]
        index = searchResult[1]
        return self.map[index][1]


map = HashMap(10)

map.insert('key1', 12)
print(map.get('key1'))
map.insert('key2', 66)
map.insert('key3', 5)
# Because we used Any when building the insert function, the value can vary from key to key.
map.insert('key4', 'elephant')

# Prints False because key5 does not exist in our map yet.
print(map.get('key5'))
map.insert('key5', 11)
# Prints 11 now
print(map.get('key5'))
print(map.get('key4'))
# Update key4
map.insert('key4', 'Yolo')
print(map.get('key4'))