7

hash_table.py

 2 years ago
source link: https://gist.github.com/ykdojo/4f9741398c3653d3dc8b95ef52bb3fcf
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Copy link

CaptainLupa commented on Oct 19, 2021 •

edited

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'))

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK