--description--

In this lab, you will build a hash table from scratch. A hash table is a data structure that stores key-value pairs. A hash table works by taking the key as an input and then hashing this key according to a specific hashing function.

For the purpose of this lab, the hashing function will be simple: it will sum the Unicode values of each character in the key. The hash value will then be used as the actual key to store the associated value. The same hash value would also be used to retrieve and delete the value associated with the key.

Objective: Fulfill the user stories below and get all the tests to pass to complete the lab.

User Stories:

You should define a class named HashTable with a collection attribute initialized to an empty dictionary when a new instance of HashTable is created. The collection dictionary should store key-value pairs based on the hashed value of the key.
The HashTable class should have four instance methods: hash, add, remove, and lookup.
The hash method should:
- Take a string as a parameter.
- Return a hashed value computed as the sum of the Unicode (ASCII) values of each character in the string. You can use the ord function for this computation.
The add method should:
- Take two arguments representing a key-value pair, and compute the hash of the key.
- Use the computed hash value as a key to store a dictionary containing the key-value pair inside the collection dictionary.
- If multiple keys produce the same hash value, their key-value pairs should be stored in the existing nested dictionary under the same hash value.
The remove method should:
- Take a key as its argument and compute its hash.
- Confirm if the key exists in the collection.
- Remove the corresponding key-value pair from the hash table.
- If the key does not exist in the collection, it should not raise an error or remove anything.
The lookup method should:
- Take a key as its argument.
- Compute the hash of the key, and return the corresponding value stored inside the hash table.
- If the key does not exist in the collection, it should return None.

--hints--

You should define a HashTable class.

({ 
    test: () => assert(runPython(`
    _Node(_code).has_class("HashTable")
    `)) 
})

When a new instance of the HashTable class is created, its collection attribute should be initialized to an empty dictionary.

({ 
    test: () => runPython(`
        ht = HashTable()
        assert ht.collection == {}
    `) 
})

The HashTable class should have a hash method.

({test: () => {assert(runPython(`_Node(_code).find_class('HashTable').has_function('hash')`))}})

The hash method should take a string as a parameter.

({ test: () => assert(runPython(`
    import inspect 
    ht= HashTable()
    sig = inspect.signature(ht.hash)
    len(sig.parameters) == 1
  `))
})

The hash method should take a string as its argument and return the sum of the Unicode values of each character in the string.

({ 
    test: () => runPython(`
        ht = HashTable()
        hash_result = ht.hash("fcc")
        assert hash_result == 300

        # prevent hardcoding
        assert ht.hash("golf") == 424
        assert ht.hash("read") == 412
`) })

The HashTable class should have an add method.

({test: () => {assert(runPython(`_Node(_code).find_class('HashTable').has_function('add')`))}})

The add method should take a key and value as parameters.

({ test: () => assert(runPython(`
    import inspect 
    ht= HashTable()
    sig = inspect.signature(ht.add)
    len(sig.parameters) == 2
  `))
})

The HashTable class should have a remove method.

({test: () => {assert(runPython(`_Node(_code).find_class('HashTable').has_function('remove')`))}})

The remove method should take a key as a parameter.

({ test: () => assert(runPython(`
    import inspect 
    ht= HashTable()
    sig = inspect.signature(ht.remove)
    len(sig.parameters) == 1
  `))
})

When you try to remove a key that does not exist in the collection, it should not raise an error or remove anything.

({ 
    test: () => runPython(`
        ht = HashTable()
        ht.add("rose", "flower")
        index = ht.hash("rose")
        original = ht.collection.copy()

        ht.remove("tulip")
        ht.remove("sore")

        assert ht.collection == original
        assert "rose" in ht.collection[index]
        assert "tulip" not in ht.collection.get(index, {})
    `) 
})

If multiple keys hash to the same index, the remove method should only delete the specific key-value pair and not the entire dictionary at that index.

({
  test: () => runPython(`
    ht = HashTable()
    ht.add("rose", "flower")
    ht.add("sore", "pain")  # "rose" and "sore" both hash to the same index

    index = ht.hash("rose")
    ht.remove("rose")

    assert index in ht.collection
    assert "rose" not in ht.collection[index]
    assert "sore" in ht.collection[index]
    assert ht.collection[index]["sore"] == "pain"
  `)
})

The HashTable class should have a lookup method.

({test: () => {assert(runPython(`_Node(_code).find_class('HashTable').has_function('lookup')`))}})

The lookup method should take a key as the parameter.

({ test: () => assert(runPython(`
    import inspect 
    ht= HashTable()
    sig = inspect.signature(ht.lookup)
    len(sig.parameters) == 1
  `))
})

HashTable().hash('golf') should return 424.

({ 
    test: () => runPython(`
        ht = HashTable()
        hash_result = ht.hash("golf")
        assert hash_result == 424

        # prevent hardcoding
        assert ht.hash("dear") == 412
        assert ht.hash("cat") == 312
    `) 
})

HashTable().add('golf', 'sport') should add the key-value pair to the collection at key 424.


({ 
    test: () => runPython(`
    ht = HashTable()
    ht.add("golf", "sport")
    expected_value = {424: {'golf': 'sport'}}

    assert ht.collection == expected_value
    `) 
})

HashTable().add('dear', 'friend') and HashTable().add('read', 'book') should add both the key-value pairs to the collection at index 412 as a nested dictionary.

({ 
    test: () => runPython(`
 
    ht = HashTable()

    ht.add("dear", "friend")
    ht.add("read", "book")

    expected_value = {
        "dear": "friend",
        "read": "book"
    }

    assert ht.collection.get(412) == expected_value
    `) 
})

When a key exists in the hash table, the remove() method should remove the given key and its corresponding value from the collection.

({ 
    test: () => runPython(`
    ht = HashTable()
    ht.add("golf", "sport")

    expected_value_before_removal = {
        "golf": "sport"
    }

    index = ht.hash("golf")

    assert ht.collection.get(index) == expected_value_before_removal

    ht.remove("golf")

    assert "golf" not in ht.collection.get(index, {})
    `) 
})

When the 'golf', 'sport' key-value pair exists in the hash table, HashTable().lookup('golf') should return sport.

({ 
    test: () => runPython(`
    ht = HashTable()

    ht.add("golf", "sport")

    expected_value = "sport"
    assert ht.lookup("golf") == expected_value
    `) 
})

When the 'golf', 'sport' key-value pair does not exist in the collection, HashTable().lookup('golf') should return None.

({ 
    test: () => runPython(`
        ht = HashTable()
        assert ht.lookup("golf") is None
`) })

When the 'fcc' key exists in the collection, HashTable().lookup('cfc') should return None.

({ 
    test: () => runPython(`
        ht = HashTable()
        ht.add("fcc", "coding")
        assert ht.lookup("cfc") is None
`) })

When you add ('rose', 'flower') to the hash table, its collection attribute should look like this: { 441: { 'rose': 'flower' }}.

({ 
    test: () => runPython(`
 
    ht = HashTable()

    ht.add("rose", "flower")

    expected_value = {
        "rose": "flower"
    }

    assert ht.collection.get(441) == expected_value

    # prevent hardcoding

    ht2 = HashTable()

    ht2.add("kebab", "food")
    expected_value = {
        "kebab": "food"
    }

    assert ht2.collection.get(501) == expected_value
    `)
})

When you add a key that hashes to the same value as an existing key, like fcc and cfc, the collection should look like this: { 300: { 'fcc': 'coding', 'cfc': 'chemical' }}.

({ 
    test: () => runPython(`
 
    ht = HashTable()

    ht.add("fcc", "coding")
    ht.add("cfc", "chemical")

    expected_value = {
        "fcc": "coding",
        "cfc": "chemical"
    }

    assert ht.collection.get(300) == expected_value

    # prevent hardcoding

    ht2 = HashTable()
    ht2.add("cat", "animal")
    ht2.add("act", "verb")

    expected_value = {
        "cat": "animal",
        "act": "verb"
    }

    assert ht2.collection.get(312) == expected_value
    `)
})

--seed--

--seed-contents--

--solutions--

class HashTable:
    def __init__(self):
        self.collection = {}

    def hash(self, string):
        hashed = 0
        for char in string:
            hashed += ord(char)  
        return hashed

    def add(self, key, val):
        the_hash = self.hash(key)
        if the_hash not in self.collection:
            self.collection[the_hash] = {}
        self.collection[the_hash][key] = val

    def remove(self, key):
        the_hash = self.hash(key)
        if the_hash in self.collection and key in self.collection[the_hash]:
            del self.collection[the_hash][key]
            if not self.collection[the_hash]: 
                del self.collection[the_hash]

    def lookup(self, key):
        the_hash = self.hash(key)
        if the_hash in self.collection and key in self.collection[the_hash]:
            return self.collection[the_hash][key]
        return None

Build a Hash Table

--description--

--hints--

--seed--

--seed-contents--

--solutions--