Uma das estruturas de dados mais adoradas na ciência da computação é a tabela de hash.
Uma tabela de hash é uma estrutura de dados que associa chaves a valores. A principal operação que ela suporta com eficiência é uma pesquisa: dada uma chave (por exemplo, o nome de uma pessoa), encontre o valor correspondente (por exemplo, o número de telefone dessa pessoa). Ele funciona transformando a chave usando uma função de hash em um hash, um número que é usado para indexar em uma matriz para localizar o local desejado (“bucket”) onde os valores devem estar.
Os pares chave-valor são bastante comuns nos dados do mundo real, e os hashtables são razoavelmente eficientes no armazenamento e bastante rápidos nas pesquisas, oferecendo desempenho O(1) na maioria dos casos. É por isso que os hashtables são a estrutura de dados preferida de muitos programadores. Pode não ser a escolha ideal, mas, ao contrário de muitas coisas na ciência da computação, raramente é uma ruim escolha.
Mas as tabelas de hash têm um ponto fraco crucial: elas são tão boas quanto a função de hash que as controla. À medida que adicionamos cada novo item à hashtable, calculamos um valor de hash a partir da chave desse item e colocamos o item no bucket representado por esse valor de hash. Então, de quantos compartimentos precisamos? Vamos considerar os extremos:
- Se tivéssemos um balde gigantetudo seria empilhado junto. Teríamos de examinar todos os itens do nosso único balde para encontrar o que queremos, o que nos reduz ao pior desempenho possível: uma pesquisa linear O(n).
- Se tivéssemos exatamente o mesmo número de baldes que os itensCada item é colocado em seu próprio balde individual e exclusivo. Sabemos que cada balde conterá um, e somente um, item. Essa é uma função hash perfeita, que oferece o melhor desempenho possível: uma pesquisa O(1).
A realidade, é claro, está em algum lugar entre esses dois extremos. A escolha da função hash é fundamental para que o senhor não fique com falta de baldes. À medida que o usuário coloca mais e mais itens em cada balde (ou seja, “colisões”), ele se aproxima da extremidade lenta O(n) do espectro de desempenho.
Há algo de mágico nessas funções de hash que impulsionam o hashtable. A ideia do hash como um impressão digital exclusiva para cada pedaço de dados em todo o mundo é fascinante. É uma impressão digital que, de forma inteligente, cabe em meros 32 bits de armazenamento, mas que, de alguma forma, é capaz de identificar exclusivamente qualquer conjunto de dados já criado.
É claro, isso é uma mentira, por vários motivos. Vamos começar com a mais óbvia. Considere todos os valores possíveis de uma função hash de 32 bits:
232 ~= 4,3 bilhões
A população atual da Terra é de cerca de 6,6 bilhões de pessoas. Se aplicássemos um perfeito de 32 bits ao DNA de cada homem, mulher e criança do planeta, não poderíamos garantir a exclusividade. simplesmente não temos valores de hash possíveis suficientes para representar todos eles!
Isso é conhecido como princípio do pigeonhole. Não é complicado. Se o senhor tentar colocar 6 pombos em 5 buracos, um deles será inevitavelmente deixado de fora.
O senhor certamente vai querer usar um valor de hash grande o suficiente para que o senhor possa evitar o princípio do “pigeonhole”. O grau de preocupação com isso depende de quantas coisas o senhor planeja armazenar na hashtable, naturalmente.
O outro motivo pelo qual os hashes podem falhar como impressões digitais é que as colisões são muito mais prováveis do que a maioria das pessoas imagina. O paradoxo do aniversário ilustra a rapidez com que o senhor pode se deparar com problemas de colisão para valores de hash pequenos. Lembro-me perfeitamente do paradoxo do aniversário do minha faculdade e vou fazer ao senhor a mesma pergunta que nosso professor nos fez:
Em uma sala de aula típica de 30 alunos, qual é a probabilidade de que dois dos alunos tenham a mesma data de aniversário?
Não continue lendo até que o senhor tenha dado um palpite. Qual é a resposta do senhor?
Cada pessoa tem um DNA completamente único, mas compartilha uma das 365* datas de nascimento possíveis com o restante de nós. Os aniversários são efetivamente uma pequena função hash de 365 valores. Usando um valor de hash tão pequeno, há 50% de chance de duas pessoas compartilharem a mesma data de aniversário após um mero 23 pessoas. Com os 30 alunos em nossa sala de aula hipotética, as chances de dois alunos terem a mesma data de aniversário aumentam para 70%. As estatísticas não mentem: quando a pergunta foi feita naquela sala de aula há tantos anos, havia de fato dois alunos que compartilhavam a mesma data de aniversário.
Uma regra prática para estimar o número de valores que o senhor precisa inserir em uma hashtable antes de ter 50% de chance de uma colisão existente é tirar a raiz quadrada de 1,4 vezes o número de valores de hash possíveis.
SQRT(1.4 * 365) = 23 SQRT(1.4 * 232) = 77,543
Quando usamos um valor de hash de 32 bits, temos 50% de chance de que haja uma colisão após cerca de 77 mil entradas, o que está muito longe dos 4 bilhões de valores possíveis que poderíamos armazenar nesse valor de 32 bits. Isso não é um grande problema para uma hashtable; e daí se alguns de nossos buckets tiverem mais de um item? Mas é um grande problema se o senhor estiver confiando no hash como uma impressão digital exclusiva.
As funções de hashing por trás de nossos preciosos hashtables podem ser uma mentira. Mas elas são uma conveniente lie. Elas funcionam. Basta ter em mente o princípio do buraco de pombo e o paradoxo do aniversário ao usá-los, e o senhor se sairá bem.
* Não, vamos esquecer os anos bissextos por enquanto. E outras variáveis, como padrões de nascimento. Sim, eu sei que é assim que os programadores pensam. Mas imagine o quanto seria ruim ter um aniversário a cada quatro anos. Ai.