Tabelas hash

Com 47 guardado numa tabela de 7 baldes, o computador vai direto ao balde 47 mod 7 = 5 em vez de procurar na tabela inteira.

Transformando uma chave numa posição

Até agora, achar um valor queria dizer buscar: até n passos num array desordenado ou numa lista encadeada. Os arrays, porém, chegam a qualquer posição em um passo. E se a própria chave dissesse a posição? Se as suas chaves fossem números inteiros pequenos, digamos números de matrícula de 0 a 99, você poderia ter um array de 100 células e guardar o aluno k na célula k. As notas do MIT chamam isso de array de acesso direto. Isso falha quando as chaves possíveis são enormes, como números de telefone ou palavras, porque não dá para ter uma célula para cada chave possível.

Uma função hash resolve isso espremendo qualquer chave numa faixa pequena de posições, de 0 a m − 1. Uma simples para números inteiros é h(k) = k mod m, o resto da divisão por m. O array de m células é a tabela hash, e as células dela costumam ser chamadas de baldes (buckets). Para guardar 47 com m = 7, calcule 47 mod 7 = 5 e ponha-o no balde 5. Para achar 47 depois, calcule a mesma coisa e olhe só no balde 5.

Colisões e encadeamento

Há um problema. Com 7 baldes e mais de 7 chaves possíveis, algumas chaves precisam dividir um balde: 12, 33 e 47 dão todos resto 5. Isso se chama colisão, e as notas do MIT observam que ela não pode ser evitada, pelo princípio da casa dos pombos. O remédio comum é o encadeamento: cada balde guarda uma pequena lista, uma cadeia, com todas as chaves que caíram nele. Achar 47 custa então 1 passo para o hash mais uma comparação para cada chave conferida na cadeia 5. Se 12 e 33 estiverem na frente, são 1 + 3 = 4 passos.

Qual é o comprimento das cadeias? Se as chaves se espalham por igual, cada cadeia tem cerca de n/m chaves, um número chamado fator de carga. Mantenha m mais ou menos tão grande quanto n e as cadeias ficam curtas, então achar, inserir e apagar levam um número constante de passos em média. O perigo é um espalhamento ruim. Se toda chave cair no mesmo balde, uma cadeia guarda todas as n chaves e a tabela não é melhor que uma lista encadeada. No laboratório, escolha 7 baldes e insira 14, 21 e 28: todos caem no balde 0.

Tabelas hash em JavaScript

Você quase nunca escreve uma tabela hash sozinho, porque o JavaScript tem Map e Set. A especificação ECMAScript diz que eles "precisam ser implementados usando tabelas hash ou outros mecanismos que, em média, ofereçam tempos de acesso sublineares em relação ao número de elementos". Em outras palavras, map.get(key) e set.has(x) precisam ser mais rápidos que buscar na coleção inteira. O MDN acrescenta que um Map mantém as chaves na ordem de inserção e, ao contrário de um objeto comum, não tem chaves padrão que possam colidir com as suas.

const price = new Map();
price.set("apple", 1.2);
price.set("bread", 2.5);
console.log(price.get("bread")); // 2.5, sem percorrer a lista
console.log(price.has("milk"));  // false
const seen = new Set([4, 8, 15]);
console.log(seen.has(8));        // true