Por que uma pesquisa de hashtable (sem colisão) é realmente O (1)?

Isenção de responsabilidade: Eu sei que já existem perguntas semelhantes aqui e no Stackoverflow. Mas eles são todos sobre colisões, o que não é o que estou pedindo.

Minha pergunta é: por que a pesquisa sem colisões O(1)em primeiro lugar?

Vamos supor que eu tenho essa hashtable:

Hash  Content
-------------
ghdjg Data1
hgdzs Data2
eruit Data3
xcnvb Data4
mkwer Data5
rtzww Data6

Agora estou procurando a chave konde a função hash h(k)fornece h(k) = mkwer. Mas como a pesquisa "sabe" que o hash mkwerestá na posição 5? Por que ele não precisa rolar por todas as teclas O(n)para encontrá-lo? Os hashes não podem ser algum tipo de endereço de hardware real, porque eu perderia a capacidade de mover os dados. E até onde eu sei, a hashtable não está classificada nos hashes (mesmo que fosse, a pesquisa também levaria O(log n))?

Como o conhecimento de um hash ajuda a encontrar o local correto na tabela?

A função hash não retorna uma string, como mkwer. Retorna diretamente a posição do item na matriz. Se, por exemplo, sua tabela de hash tiver dez entradas, a função hash retornará um número inteiro no intervalo de 0 a 9.

A função hash calcula a posição da matriz de uma determinada string . Se esse hash for perfeito, significa que certamente não há colisões, a matriz provavelmente é pelo menos duas vezes maior que o número de elementos.

Por exemplo, darei hash muito ruim para letras, apenas para ilustrar o mecanismo:
0) 1) para cada caractere na cadeia, pegue o valor ascii, subtraia 'a' se estiver em minúscula, subtraia 'A' se estiver em maiúscula, adicione valor a x. 2) o número resultante, por exemplo, 15 é o índice da matriz. x = x m o d $x = 0;$
$x = x mod 52$

Esse hash muito simples (limitado e propenso a colisões) difere de outros hashes no mecanismo de hash, não considera a entrada fornecida. No esquema mais avançado, o hash é um número maior, ajustado ao número de elementos. O hash perfeito é gerado para todas as entradas para garantir nenhuma colisão.

Isso é porque o cálculo do hash da string depende de quão sofisticada é a função computada, mas não depende do número de elementos.$O(1)$

No caso de um hash perfeito, quando os elementos são adicionados é recalculado, o caso mais simples com colisões quando a carga do array é grande, o tamanho do array aumenta, a função assume um módulo de saída maior e os elementos são deslocados para os novos locais.$h(k)$

Matriz é um fragmento de memória contínua; para obter o elemento, você pega o endereço do primeiro elemento (início da matriz) e adiciona a esse endereço para ter uma célula de memória explícita.n * ( s i z e o f e l e m e n t $n-th$$n * (size of element)$

Para expandir a resposta de David Richerby, o termo " função hash " está um pouco sobrecarregado. Freqüentemente, quando falamos de uma função hash, pensamos em MD5, SHA-1 ou algo como o .hashCode()método Java , que transforma algumas entradas em um único número. No entanto, é muito improvável que o domínio desse número (ou seja, o valor máximo) seja do mesmo tamanho da hashtable em que você está tentando armazenar dados. (MD5 é 16 bytes, SHA-1 é 20 bytes e .hashCode()é int- 4 bytes).

Portanto, sua pergunta é sobre o próximo passo - uma vez que temos uma função hash que pode mapear entradas arbitrárias para números, como as colocamos em uma estrutura de dados de um tamanho específico? Com outra função, também chamada de "função hash"!

Um exemplo trivial dessa função é módulo ; você pode mapear facilmente um número arbitrário de tamanho para um índice específico em uma matriz com módulo. Isso é introduzido no CLRS como "o método de divisão":

No método de divisão para criar funções de hash, mapeamos uma chave em um dos slots, pegando o restante de dividido por . Ou seja, a função hash é$k$$m$$k$$m$

$h(k) = k$ mod .$m$

...

Ao usar o método de divisão, geralmente evitamos certos valores de . Por exemplo, não deve ser uma potência de 2, pois se então é apenas os bits de de ordem mais baixa de .$m$$m$$m = 2^p$$h(k)$$p$$k$

~ Introdução aos Algoritmos, §11.3.1 - CLRS

Portanto, o módulo não é uma excelente função de hash, pois restringe os tamanhos que podemos usar com segurança para nossa estrutura de dados subjacente. A próxima seção apresenta um "método de multiplicação" um pouco mais complexo, que também usa módulo, mas é vantajoso porque "o valor de não é crítico". No entanto, funciona melhor com algum conhecimento prévio de "características dos dados que estão sendo hashados" - algo que geralmente não sabemos.$m$

O Java HashMapusa uma versão modificada do método de divisão que executa uma etapa de pré-processamento para levar em conta .hashCode()implementações fracas, para que ele possa usar matrizes de tamanho de dois poder. Você pode ver exatamente o que está acontecendo no .getEntry()método (os comentários são meus):

 // hash() transforms key.hashCode() to protect against bad hash functions
 int hash = (key == null) ? 0 : hash(key.hashCode());
 // indexOf() converts the resulting hash to a value between 0 and table.length-1
 for (Entry<K,V> e = table[indexFor(hash, table.length)];
     ...

_{O Java 8 trouxe uma reescrita HashMapainda mais rápida, mas um pouco mais difícil de ler. Ele usa o mesmo princípio geral para pesquisa de índice, no entanto.}