Visualizador de Tabela Hash

Hash tables employ deterministic mathematical algorithms to map arbitrary keys to finite index spaces, optimizing for O(1) temporal retrieval. Collisions, an inevitable consequence of the pigeonhole principle, necessitate strict resolution protocols. Chaining relies on linked list allocations, while linear and quadratic probing use mathematical step functions to navigate array indices. The load factor continuously dictates the statistical probability of these computationally expensive collisions.

Uma tabela hash é apenas um array combinado com uma regra — a função hash — que converte qualquer chave em um número de posição. Em vez de percorrer cada entrada uma a uma, você calcula onde um elemento deve ficar e vai direto até lá; é por isso que as buscas continuam rápidas mesmo com milhões de chaves. O detalhe: a velocidade depende de distribuir as chaves de forma uniforme. Insira algumas aqui e veja com que rapidez duas chaves disputam a mesma posição.

Como uma tabela hash degenera em uma busca linear lenta quando chaves demais caem na mesma posição — exatamente o pior caso que você pode provocar acima —, um atacante que conheça sua função hash pode forjar milhares de chaves que colidem de propósito. Em 2011, esse truque de 'hash-flooding' travou servidores web em PHP, Java, Python e Ruby com uma única requisição manipulada. A solução foram funções hash com semente aleatória como SipHash, hoje padrão em muitas linguagens.