HashMap: do alto nível até os bytes

Toda vez que você escreve map.get("idade"), o computador precisa fazer um monte de coisa antes de te devolver 28. Hashing, manipulação de bits, gerenciamento de memória. Esse post vai abrir tudo isso.

O que você já sabe

Do lado de fora, é só isso:

const map = new Map<string, number>();
map.set("idade", 28);
map.get("idade"); // 28

Chave entra, valor sai. Você usa isso o tempo todo, mesmo que não perceba.

Contar quantas vezes cada palavra aparece num texto:

const count = new Map<string, number>();
for (const word of text.split(" ")) {
  count.set(word, (count.get(word) ?? 0) + 1);
}

Cache pra não ficar batendo na mesma API toda hora:

const cache = new Map<string, User>();

async function getUser(id: string) {
  if (cache.has(id)) return cache.get(id)!;
  const user = await fetch(`/api/users/${id}`).then((r) => r.json());
  cache.set(id, user);
  return user;
}

Rate limiting por IP:

const hits = new Map<string, number>();

function rateLimit(ip: string): boolean {
  const current = hits.get(ip) ?? 0;
  if (current >= 100) return false;
  hits.set(ip, current + 1);
  return true;
}

Nos três casos a lógica é a mesma: busca por chave em tempo constante. Mas pra isso funcionar rápido, o computador precisa resolver três coisas:

1. Transformar a chave em um número
2. Usar esse número pra achar uma posição num array
3. Decidir o que fazer quando duas chaves caem na mesma posição

Transformando texto em número

Imagina 16 gavetas numeradas de 0 a 15. Você precisa de uma regra fixa pra decidir em qual gaveta cada chave vai. Mesma chave, mesma gaveta, sempre, senão na hora de buscar você não sabe onde procurar.

Essa regra é a função hash. Pega qualquer texto, devolve um número.

Uma das mais conhecidas é a djb2. Em C:

unsigned long hash(const char *str) {
    unsigned long h = 5381;
    int c;
    while ((c = *str++))
        h = ((h << 5) + h) + c; // h * 33 + c
    return h;
}

Se C não faz parte do seu dia a dia, a mesma ideia em JavaScript:

function hash(str) {
  let h = 5381;
  for (let i = 0; i < str.length; i++) {
    h = ((h << 5) + h + str.charCodeAt(i)) >>> 0;
  }
  return h;
}

hash("idade"); // 262376668
hash("nome");  // 2090551252

A lógica: começa com 5381 (um primo que alguém testou bastante e viu que distribuía bem os resultados), percorre cada letra, multiplica o acumulador por 33 e soma o valor numérico da letra. No fim você tem um inteiro. Mesma string, sempre o mesmo inteiro.

O << 5 no C é um shift de bits, equivale a multiplicar por 32. Shift + soma original = multiplicação por 33 sem usar a instrução de multiplicação. Parece bobagem, mas quando você faz isso milhões de vezes, soma.

De número pra posição

O hash de "idade" pode dar um número gigante. Mas a tabela tem 16 posições. Preciso encaixar esse número entre 0 e 15.

O jeito óbvio: resto da divisão.

hash("idade") % 16 // = 7, vai na posição 7

Funciona, mas divisão é cara pro processador. Se o tamanho da tabela for potência de 2, dá pra trocar por um AND bitwise:

hash("idade") & (16 - 1) // = 7, mesmo resultado

Por quê? 16 em binário é 10000. 16 - 1 = 15 é 01111. O & (AND) zera todos os bits acima do quarto, mantendo só os que cabem no range de 0 a 15. É o mesmo que o resto da divisão, mas numa instrução só.

Pra ter uma ideia do impacto: no processador, uma divisão inteira leva 20-30 ciclos. Um AND leva 1. Num HashMap acessado milhões de vezes, isso se acumula rápido.

Se quiser ver a diferença no nível mais baixo, em assembly (as instruções que o processador de fato executa):

; divisão — 20-30 ciclos
mov  rax, rdi        ; coloca o hash num registrador
xor  rdx, rdx        ; zera rdx (exigência da instrução div)
div  rsi             ; divide pelo tamanho da tabela
; o resto fica em rdx

; AND — 1 ciclo
mov  rax, rdi        ; coloca o hash num registrador
dec  rsi             ; 16 vira 15
and  rax, rsi        ; mantém só os bits que cabem

Não precisa entender cada linha. O ponto é que % vira div (lento) e & vira and (rápido). É por isso que HashMaps quase sempre usam tamanhos que são potência de 2.

A tabela e as colisões

O hash sozinho não resolve nada. Precisa de uma estrutura pra guardar os pares chave-valor.

A abordagem clássica é separate chaining: o array tem N posições, cada posição guarda uma lista. Se duas chaves caem na mesma posição, as duas entram na lista daquela posição.

Em C a estrutura fica assim:

typedef struct Entry {
    char *key;           // a chave (texto)
    int value;           // o valor
    struct Entry *next;  // próximo item na lista, ou NULL
} Entry;

typedef struct {
    Entry **buckets;     // array de listas
    size_t capacity;     // quantas posições tem
    size_t size;         // quantos itens foram inseridos
} HashMap;

Se não lê C: cada Entry é uma caixinha com uma chave, um valor e uma seta apontando pra próxima caixinha (ou pra nada). O HashMap é um array de posições, cada posição apontando pro início de uma lista de caixinhas.

Capacidade inicial 16, potência de 2. Não é acidental.

Inserção

void hashmap_put(HashMap *map, const char *key, int value) {
    size_t idx = hash(key) & (map->capacity - 1);
    Entry *entry = map->buckets[idx];

    // percorre a lista procurando se a chave já existe
    while (entry) {
        if (strcmp(entry->key, key) == 0) {
            entry->value = value; // achou, atualiza
            return;
        }
        entry = entry->next;
    }

    // não achou, cria uma entry nova no início da lista
    Entry *new_entry = malloc(sizeof(Entry));
    new_entry->key = strdup(key);
    new_entry->value = value;
    new_entry->next = map->buckets[idx];
    map->buckets[idx] = new_entry;
    map->size++;

    // se tá ficando cheio, dobra o tamanho
    if ((double)map->size / map->capacity > 0.75)
        hashmap_resize(map);
}

Em palavras: calcula o hash, acha a posição, percorre a lista pra ver se a chave já existe. Se existe, atualiza. Se não, cria uma entry nova no começo da lista. E se a tabela tá passando de 75% da capacidade (o load factor), dobra de tamanho.

Busca

Mesmo caminho ao contrário:

int hashmap_get(HashMap *map, const char *key, int *out) {
    size_t idx = hash(key) & (map->capacity - 1);
    Entry *entry = map->buckets[idx];

    while (entry) {
        if (strcmp(entry->key, key) == 0) {
            *out = entry->value;
            return 1; // achou
        }
        entry = entry->next;
    }
    return 0; // não achou
}

Caso normal: a lista tem 0 ou 1 item. Busca instantânea, O(1). Pior caso: todas as chaves colidiram, a lista tem N itens, e a busca vira O(n). O load factor de 0.75 existe pra manter as listas curtas o bastante pra que o caso normal continue sendo o caso comum.

Resize

Quando o número de itens passa de 75% da capacidade, a tabela dobra de tamanho e redistribui tudo:

void hashmap_resize(HashMap *map) {
    size_t new_cap = map->capacity * 2;
    Entry **new_buckets = calloc(new_cap, sizeof(Entry *));

    for (size_t i = 0; i < map->capacity; i++) {
        Entry *entry = map->buckets[i];
        while (entry) {
            Entry *next = entry->next;
            size_t idx = hash(entry->key) & (new_cap - 1);
            entry->next = new_buckets[idx];
            new_buckets[idx] = entry;
            entry = next;
        }
    }

    free(map->buckets);
    map->buckets = new_buckets;
    map->capacity = new_cap;
}

Percorre cada item, recalcula o índice pra tabela nova (que agora tem o dobro de posições), e reinsere. O(n), percorre tudo. Dói.

Se você sabe mais ou menos quantos itens vai ter, pré-aloque:

// Rust
let mut map = HashMap::with_capacity(10_000);

// Go
m := make(map[string]int, 10_000)

O layout na memória

Uma tabela com 4 posições e 2 itens fica assim na RAM:

HashMap (na stack)
  .buckets   -> 0x7f00
  .capacity  =  4
  .size      =  2

Array de ponteiros em 0x7f00 (contíguo, 32 bytes):
  [0] NULL
  [1] -> 0xa200
  [2] NULL
  [3] -> 0xb100

Entry em 0xa200 (heap):          Entry em 0xb100 (heap):
  key:   "idade"                   key:   "nome"
  value: 28                        value: 1
  next:  NULL                      next:  NULL

Repara nos endereços: 0x7f00, 0xa200, 0xb100. O array de ponteiros é contíguo, mas as entries estão em regiões completamente diferentes.

O array de posições é contíguo na memória, mas cada entry foi alocada separadamente com malloc. Elas podem estar em qualquer lugar do heap.

Isso importa por causa de como o processador lê memória. Ele não lê um byte de cada vez. Ele puxa 64 bytes de uma vez (uma cache line) e guarda por perto, apostando que você vai precisar dos dados vizinhos logo em seguida. Se o próximo dado que você precisa tá em outro canto da memória, a aposta falhou. Isso é um cache miss, e é lento.

Com chaining, cada entry pode estar em qualquer lugar. Acessar entradas em sequência vira uma sequência de cache misses.

Isso é o problema.

Open addressing

Implementações modernas, como as do Rust, Go e Python, resolvem isso de outro jeito: guardam os itens direto no array, sem ponteiros apontando pra fora. O Google fez o mesmo com o Swiss Table no Abseil.

typedef struct {
    char *key;
    int value;
    uint8_t occupied; // 0 = vazio, 1 = ocupado, 2 = removido
} Slot;

typedef struct {
    Slot *slots;      // array contíguo de slots
    size_t capacity;
    size_t size;
} OpenHashMap;

Se tem colisão, em vez de criar uma lista, o algoritmo olha pro slot vizinho. E o próximo. Até achar um vazio. Isso se chama linear probing (tem variações como quadratic probing e Robin Hood hashing, mas a ideia base é a mesma).

Os dados ficam grudados na memória. Quando o processador puxa um slot pra cache, os vizinhos vêm junto de graça. Em benchmarks, open addressing costuma ser 2-3x mais rápido que chaining pra tabelas grandes, praticamente só por causa da localidade de cache.

Quando você escreve map["idade"] = 28, é isso que roda por baixo. Hashing, bit masking, probing. No dia a dia você não precisa pensar nisso. Mas quando um profiler mostrar 40% do tempo em rehash, ou quando precisar escolher entre HashMap e BTreeMap, saber o que acontece dentro ajuda. E quase sempre a resposta é chata: uma linha de pré-alocação.