HashMap Implementation (dictionary) in Python

Question

I attempted making a hashmap in python, and it was harder, due to some limitations but this is my version of dictionaries in python. Are there any way to simplify or do the same thing in less code along with tips and tricks?

class HashMap:
    def __init__(self, memory): # refers to the length of the bucket
            self.data = [None] * memory 
            self.memory = memory

    def _hash(self, key):
        hashed_value = 0
        bucket_length = self.memory
        string_length = len(key)
        i = 0
        while i < string_length:
            hashed_value += (ord(key[i]) * i) % bucket_length
            if hashed_value > bucket_length-1:
                hashed_value %= bucket_length-1

            i += 1
        return hashed_value

    def set(self, key, value):
        address = self._hash(key)
        bucket = self.data[address]
        if not bucket:
            self.data[address] = [key, value, None] # None refers to next pointer
        else:
            while bucket[2] != None:
                bucket = bucket[2]
            bucket[2] = [key, value, None]

    def get(self, key):
        address = self._hash(key)
        bucket = self.data[address]
        if bucket:
            while bucket[2] != None or key != bucket[0]:
                bucket = bucket[2]
            if bucket:
                return bucket[1]
        raise KeyError

    def keys(self):
        keys_list = []
        bucket_list = self.data
        for bucket in bucket_list:
            current_bucket = bucket
            if bucket:
                while current_bucket != None:
                    keys_list.append(current_bucket[0])
                    current_bucket = current_bucket[2]
        return keys_list

Answer 1

Your implementation of get is wrong. The code is:

def get(self, key):
        address = self._hash(key)
        bucket = self.data[address]
        if bucket:
            while bucket[2] != None or key != bucket[0]:
                bucket = bucket[2]
            if bucket:
                return bucket[1]
        raise KeyError

The line while bucket[2] != None or key != bucket[0] says "keep traversing the link list as long as it's possible to do so, and if it's impossible, try to do it anyway if the key is wrong". Because of the boolean or, the condition bucket[2] != None means the loop will always step forward in the linked list if it's possible to do so - even if the current key is correct. On top of that, once the loop gets to the last element, if the key at that position does not match the given key, the loop will attempt to iterate once more, giving us:

TypeError                                 Traceback (most recent call last)
<ipython-input-7-a5939dc0e83e> in <module>()
----> 1 h.get("apple")

<ipython-input-1-4777e6d3506b> in get(self, key)
     31         bucket = self.data[address]
     32         if bucket:
---> 33             while bucket[2] != None or key != bucket[0]:
     34                 bucket = bucket[2]
     35             if bucket:

TypeError: 'NoneType' object is not subscriptable

The result is get fails with this error in every case except when the requested key is the last one in its slot.

The correct condition is of course while bucket[2] != None and key != bucket[0]. We then need to check afterwards that we got out of the loop because we found the right key, not because we ran out of buckets, giving us the implementation:

def get(self, key):
        address = self._hash(key)
        bucket = self.data[address]
        if bucket:
            while bucket[2] != None and key != bucket[0]:
                bucket = bucket[2]
            if bucket[0] == key:
                return bucket[1]
        raise KeyError

Answer 2

Your implementation of set is also wrong. If you set the same key twice, the first value should be overwritten. Instead, the new key-value pair is added to the end of the bucket list, so memory usage will increase, the keys method will return multiple copies of the same key.