Tabela Hash: busca O(1) medio

Uma tabela hash mapeia chaves pra valores usando uma funcao hash.

Big-O (medio): put/get/delete = O(1)
Pior caso (todas colisoes): O(n)
Python
class HashTable:
    def __init__(self, size=7):
        self.size = size
        self.table = [[] for _ in range(size)]
    def _hash(self, key):
        return sum(ord(c) for c in str(key)) % self.size
    def put(self, key, value):
i = self._hash(key)
Python
        for j, (k, v) in enumerate(self.table[i]):
            if k == key:
                self.table[i][j] = (key, value)
return
Python
        self.table[i].append((key, value))
    def get(self, key):
i = self._hash(key)
Python
        for k, v in self.table[i]:
            if k == key: return v
        return None