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

10

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?

Foo Bar
fonte

Respostas:

24

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.

David Richerby
fonte
11
Obrigado. :) Meu erro foi pensar em uma função de hash de hashtable como MD5 ou SHA. Mas um hash pode, é claro, ser uma posição inteira, na qual eu não pensei. Agora que sei o que procurar, encontrei rapidamente um bom exemplo: a função hash do PHP: github.com/php/php-src/blob/PHP-5.6.10/Zend/zend_hash.h#L237
Foo Bar
13
@FooBar: MD5 e SHA também calculam números únicos da entrada, é tão comum falar sobre os hashes na forma hexadecimal. Assim como os endereços de memória raramente são considerados em decimal.
precisa saber é o seguinte
4
Além disso, o MD5 etc. é muito longo para ser usado como um índice de matriz diretamente. Seria possível usar alguma parte do hash, como os n bits inferiores .
Chirlu
6

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 52x=0;
x=xmod52

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 )nthn(sizeofelement)

Mal
fonte
11
E como a pesquisa sabe onde está o hash na tabela? Não são pedidos nem endereços de hardware.
Foo Bar
Você fornece uma string, por exemplo, "xcnvb", para que o hash calculado forneça o índice da matriz, "xcnvb" é o seu elemento a ser pesquisado, 8 é o índice na tabela. É ordenado por aceno, hash retorna o local para recuperar o elemento. Este elemento foi colocado lá pela mesma função. O hardware não tem nada a ver aqui. Você fornece matriz, função de hash e calcula o hash para obter o índice na matriz, o mesmo na recuperação. A matriz não é classificada, também nunca está cheia. h("xcnvb")=8
mal
Mas nem todos os índices serão preenchidos. Se eu tenho os hash 1, 4, 8, 90 e 223 preenchidos com dados, como uma pesquisa encontra o local correto? Nesse caso, o índice "90" está na posição 4 porque a maioria dos outros índices não existe. E uma hashtable vazia não é de tamanho infinito, com todas as posições possíveis !?
Foo Bar
Sim, a matriz permite assumir 512 elementos, 9 bits usados ​​para a função hash e você possui apenas 4 elementos. O índice 90 tem a posição 90 na matriz, como no exemplo - quase todas as células estão vazias. Se a sua matriz é você posicioná-lo = seus dados para "xcnvb"HaHa(h("xcnvb"))=Ha[90]
Mal
A função hash não retorna um índice na matriz. Em vez disso, ele retorna um número previsível que pode ser mapeado na matriz. Isso geralmente é feito usando o operador de módulo com o número de buckets da tabela de hash como o outro operando.
Christopher Schultz
3

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 ékmkm

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 .mmm=2ph(k)pk

~ 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.

dimo414
fonte