* amortizado: a inserção é O(1) na média mesmo contando o rehash O(n) que acontece de vez em quando. O pior caso O(n) é quando todas as chaves caem no mesmo bucket e a tabela vira uma lista encadeada.
Na prática (map do Go)
m := make(map[string]int)
m["cat"] = 1 // insere/atualiza, O(1) médio
v, ok := m["cat"] // lookup, ok=false se não existe
delete(m, "cat") // remove
Hash table com chaining (esqueleto)
type entry struct { key string; val int }
type table struct { buckets [][]entry }
func (t *table) hash(k string) int {
h := 0
for _, c := range k {
h = h*31 + int(c) // hash polinomial simples
}
if h < 0 { h = -h }
return h % len(t.buckets)
}
func (t *table) insert(k string, v int) {
i := t.hash(k)
for j := range t.buckets[i] { // percorre a cadeia do bucket
if t.buckets[i][j].key == k {
t.buckets[i][j].val = v; return
}
}
t.buckets[i] = append(t.buckets[i], entry{k, v})
// se load factor > 0.75: dobra buckets e reinsere tudo (rehash)
}
func (t *table) get(k string) (int, bool) {
i := t.hash(k)
for _, e := range t.buckets[i] { // O(tamanho da cadeia)
if e.key == k { return e.val, true }
}
return 0, false
}