hash constante de tempo para cordas?

Question

Outra pergunta sobre SO trouxe as instalações em alguns idiomas para cadeias de hash para dar-lhes uma pesquisa rápida em uma tabela. Dois exemplos disso são dicionário <> em .NET e o {} estrutura de armazenamento em Python. Outros idiomas certamente apoiar tal mecanismo a. C ++ tem seu mapa, LISP tem um equivalente, como fazem a maioria outras línguas modernas.

Foi afirmado nas respostas para a pergunta que os algoritmos de hash em cordas podem ser realizados em timem constante com um membro do SO, que tem 25 anos de experiência em programação alegando que qualquer coisa pode ser hash em tempo constante. Meu argumento pessoal é que isso não é verdade, a menos que sua aplicação específica coloca um limite no comprimento da corda. Isto significa que alguma constante K que ditam o comprimento máximo de uma string.

Estou familiarizado com o algoritmo de Rabin-Karp, que usa uma função hash para o seu funcionamento, mas este algoritmo não dita uma função específica hash para uso, e os um dos autores sugeridos é O (m), onde m é o comprimento da corda hash.

Eu vejo algumas outras páginas como esta ( http: // www. cse.yorku.ca/~oz/hash.html ) que são apresentados alguns algoritmos de hash, mas parece que cada um deles repete ao longo de todo o comprimento da corda para chegar ao seu valor.

De minha leitura comparativamente limitada sobre o assunto, parece que as matrizes mais associativos para tipos string são realmente criadas usando uma função hash que opera com uma árvore de algum tipo sob o capô. Esta pode ser uma árvore árvore AVL ou vermelho / preto que aponta para a localização do elemento de valor no par chave / valor.

Mesmo com essa estrutura de árvore, se quisermos permanecer na ordem de theta (log (n)), sendo n o número de elementos na árvore, precisamos ter um algoritmo de hash de tempo constante. Caso contrário, temos a pena de aditivo de iteração sobre a corda. Mesmo que theta (m) seria eclipsado por teta (log (n)) para índices que contêm muitas cordas, não podemos ignorá-lo se estamos em tal domínio que os textos que buscam contra será muito grande.

Estou ciente de que árvores de sufixo / matrizes e Aho-Corasick pode trazer a pesquisa para baixo a teta (m) para uma despesa maior na memória, mas o que eu estou perguntando especificamente se existe um método em tempo constante hash para cordas de arbitrária comprimentos como foi reivindicada por outro membro do SO.

Graças.

Answer 1

Em geral, eu acredito que qualquer hash de cadeia completa deve usar todos os personagens da corda e, portanto, teria de crescer como O (n) para n caracteres. No entanto eu acho que para hashes de cordas práticas que você pode usar hashes aproximadas que podem ser facilmente O (1).

Considere um hash cadeia que usa sempre Min (n, 20) caracteres para calcular um hash padrão. Obviamente esta cresce como o (1) com tamanho de cadeia. Será que vai funcionar de forma confiável? Depende do seu domínio ...

Answer 2

A função hash não precisa (e não pode) retornar um valor único para cada string.

Você pode usar os primeiros 10 caracteres para inicializar um gerador de números aleatórios e, em seguida, usar isso para retirar 100 caracteres aleatórios a partir da cadeia, e hash que. Isso seria tempo constante.

Você também pode apenas retornar o valor constante 1. Estritamente falando, isso ainda é uma função hash, embora não seja uma forma muito útil.

Answer 3

Você não pode facilmente conseguir um algoritmo de hash geral constante de tempo para cordas sem arriscar casos graves de colisões de hash.

Para que seja constante de tempo, você não será capaz de acessar todos os caracteres na string. Como um exemplo simples, suponha que dar os primeiros 6 caracteres. Em seguida, vem alguém e tenta botar um conjunto de URLs. O tem a função vai ver "http: /". Para cada corda única

cenários semelhantes podem ocorrer para esquemas de outros personagens seleções. Você poderia escolher personagens pseudo-aleatoriamente com base no valor do caractere anterior, mas você ainda corre o risco de falhar espetacularmente se as cordas por alguma razão tem o padrão "errado" e muitos acabam com o mesmo valor hash.

Answer 4

Você pode esperança para assintoticamente inferior a tempo hashing linear se você usar cordas em vez de cordas e têm de partilha que permite ignorar alguns cálculos. Mas, obviamente, uma função hash pode entradas não separadas que não tenha lido, então eu não iria tomar a "tudo pode ser hash em tempo constante" muito a sério.

Tudo é possível no compromisso entre a qualidade da função hash e a quantidade de computação que é preciso, e uma função hash por longas cordas deve ter colisões de qualquer maneira.

Você tem que determinar se as cordas que são susceptíveis de ocorrer em seu algoritmo irá colidir com muita freqüência se a função hash só olha para um prefixo.

Answer 5

Embora eu não posso imaginar uma função hash em tempo fixo para cadeias de comprimento ilimitado, não há realmente nenhuma necessidade para isso.

A idéia por trás usando uma função hash é gerar uma distribuição dos valores de hash que o torna improvável que muitas cordas iria colidir - para o domínio em consideração. Esta chave permitiria acesso direto para um armazenamento de dados. Estes dois resultados combinados em um pesquisa constante de tempo - em média,

.

Se ocorrer alguma vez tal colisão, o algoritmo de pesquisa recai sobre uma sub-estratégia de pesquisa mais flexível.

Answer 6

Com certeza isso é factível, desde que você garantir que todas as suas cordas são 'internados', antes de passá-los para algo que requer hashing. Internar é o processo de inserir a cadeia para uma tabela de cadeia, de modo a que todas as cadeias internados com o mesmo valor é, de facto, o mesmo objecto. Em seguida, você pode simplesmente botar o ponteiro (comprimento fixo) para a cadeia internados, em vez de hash a corda em si.

Answer 7

Você pode estar interessado no seguinte resultado matemático eu vim com o ano passado.

Considere o problema de hash um número infinito de chaves, tais como o conjunto de todas as cadeias de qualquer comprimento para o conjunto de números em {1,2, ..., b}. Aleatória de hashing começa por colheita ao acaso uma função hash h de uma família de funções H.

Vou mostrar que há sempre um número infinito de chaves que estão determinados a colidir sobre todas as funções H, isto é, eles têm sempre o mesmo valor de hash para todas as funções de hash.

Escolha qualquer função hash h: há pelo menos um valor de hash y tal que o conjunto A = {s: h (s) = y} é infinito, ou seja, você tem um número infinito de seqüências de colisão. Escolher qualquer outra função de hash h 'e de hash as teclas no conjunto A. Existe, pelo menos, um valor hash de Y' de tal modo que o conjunto A '= {s é em A:' h (s) = y '} é infinito, isto é, há uma infinidade de cordas colidindo em duas funções hash. Você pode repetir esse argumento qualquer número de vezes. Repita-H vezes. Então você tem um conjunto infinito de cordas, onde todas as cordas colidem em todas as suas funções hash h. CQFD.

Leitura : hashing sensata de cadeias de comprimento variável é impossível http: // lemire.me/blog/archives/2009/10/02/sensible-hashing-of-variable-length-strings-is-impossible/