---
id: 67ed03ac474c48692f41749e
title: Build a Hash Table
challengeType: 27
dashedName: build-a-hash-table
saveSubmissionToDB: true
---

# --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:**

1. 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.

2. The `HashTable` class should have four instance methods: `hash`, `add`, `remove`, and `lookup`.

3. 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.

4. 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.

5. 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.

6. 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.

```js
({ 
    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.

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

The `HashTable` class should have a `hash` method.

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

The `hash` method should take a string as a parameter.

```js
({ 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.

```js
({ 
    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.

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

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

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

The `HashTable` class should have a `remove` method.

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

The `remove` method should take a key as a parameter.

```js
({ 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.

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

        ht.remove("tulip")

        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.

```js
({
  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.

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

The `lookup` method should take a key as the parameter.

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

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

```js
({ 
    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`.

```js

({ 
    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.

```js
({ 
    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.

```js
({ 
    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`.

```js
({ 
    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`.

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

```

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

```js
({ 
    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' }}`.

```js
({ 
    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--

```py

```

# --solutions--

```py
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
```
