Como as tabelas de hash O (1) levam em consideração a velocidade de hash?

Diz-se que as tabelas de hash são amortizadas usando, digamos, encadeamento simples e duplicação a uma determinada capacidade. $\Theta(1)$

No entanto, isso pressupõe que os comprimentos dos elementos sejam constantes. Computar o hash de um elemento requer passar pelo elemento, levando tempo em que é o comprimento. $\Theta(l)$ $l$

Mas, para discriminar entre elementos, precisamos que os elementos tenham comprimento pelo menos bits; caso contrário, pelo princípio do pigeonhole, eles não serão distintos. A função hash passando por bits do elemento levará tempo . $n$ $\lg n$ $\lg n$ $\Theta(\lg n)$

Então, podemos dizer que a velocidade de uma tabela de hash, levando em consideração uma função de hash razoável que usa todas as partes da entrada, é realmente ? Por que, então, as tabelas de hash na prática são eficientes para armazenar elementos de comprimento variável, como cadeias de caracteres e números inteiros grandes? $\Theta(\lg n)$

hash-tables dictionaries ithisa
fonte

Intimamente relacionado: (Quando) a pesquisa de tabela de hash O (1)? , Para que tipo de dados são as operações da tabela de hash O (1)?

Gilles 'SO- stop be evil'

A resposta é que eles não são . Esse tipo de análise de hash não leva em consideração a dimensão (ou número de bits) dos elementos, mas apenas sua multidão.

Nikos M.

Mas se uma pesquisa de mapa de hash que não considerasse ler e escrever os bits como descrito, é , então, sob os mesmos critérios, uma pesquisa binária ou qualquer outro processo que normalmente considere seria realmente não seria?

Θ (1)

$\Theta (1)$

\in Θ (l g

$\in \Theta (lg$

n)

$n)$

\in Θ l g

$\in \Theta lg$

n

$n$

\in Θ (l g^{2}

$\in \Theta( lg^2$

n)

$n )$

@tAllan cf uniforme vs modelo de custo logarítmico .

Raphael

@tAllan Uma pesquisa binária regular seria mas se você mantiver os itens classificados de acordo com a sequência de bits de suas chaves e fizer uma pesquisa binária comparando "um bit de cada vez" (detalhes complicados omitidos), você poderá conseguir atingir .

Θ (\log^{2} n)

$\Theta(\log^2 n)$

Θ (\log n)

$\Theta(\log n)$

Reintegrar Monica

Respostas:

O conto que tabelas de dispersão são amortizados é ~~uma mentira~~ uma simplificação. $\Theta(1)$

Isso só é verdade se:
- A quantidade de dados em hash por item é trivial em comparação com o número de K eys e a velocidade do hash de um K ey é rápida - . - O número de C ollisions é pequena - . - Nós não ter em conta o tempo necessário para R esize tabela hash - . $k$
$c$
$r$

Seqüências grandes de hash
Se a primeira suposição for falsa, o tempo de execução aumentará para . Definitivamente, isso é verdade para cadeias grandes, mas para cadeias grandes uma comparação simples também teria um tempo de execução de . Portanto, um hash não é assintoticamente mais lento, embora o hash sempre seja mais lento do que uma comparação simples, porque a comparação tem uma opção de exclusão inicial logo , e hash sempre tem que hash a cadeia completa , . $\Theta(k)$
$\Theta(k)$ $O(1)$ $\Omega(k)$ $O(k)$ $\Omega(k)$

Observe que números inteiros crescem muito lentamente. 8 bytes podem armazenar valores de até ; 8 bytes é uma quantidade trivial de hash. Se você deseja armazenar bigints, pense nelas como strings. $10^{18}$

Algoritmo de hash lento
Se o valor gasto em hash não é trivial em comparação com o armazenamento dos dados, obviamente a suposição se torna insustentável. A menos que um hash criptográfico seja usado, isso não deve ser um problema. $\Theta(1)$

O que importa é que . Enquanto isso acontecer, é uma afirmação justa. $n$ $>>$ $k$ $\Theta(1)$

Muitas colisões
Se a função de hash for ruim, ou a tabela de hash for pequena, ou se o tamanho da tabela de hash for desagradável, as colisões serão frequentes e o tempo de execução passará para . A função de hash deve ser escolhida de modo que as colisões sejam raras e, ao mesmo tempo, sejam o mais rápido possível, quando houver dúvida, opte por menos colisões às custas de hash mais lento. Uma regra prática é que a tabela de hash deve sempre ter menos de 75% de sua capacidade. E o tamanho da tabela de hash não deve ter nenhuma correlação com a função de hash. Frequentemente, o tamanho da tabela de hash é (relativamente) primo. $O(log(n))$

Redimensionando a tabela de hash
Como uma tabela de hash quase cheia causará muitas colisões e uma tabela de hash grande (vazia) é um desperdício de espaço, muitas implementações permitem que a tabela de hash cresça (e encolha!) Conforme necessário.
O crescimento de uma tabela pode envolver uma cópia completa de todos os itens (e possivelmente uma reorganização), porque o armazenamento precisa ser contínuo por razões de desempenho.
Somente em casos patológicos o redimensionamento da tabela de hash será um problema, para que os redimensionamentos (caros, mas raros) sejam amortizados em muitas chamadas.

Tempo de execução
Portanto, o tempo de execução real de uma tabela de hash é . Cada , , em média é assumido como uma (pequena) constante no tempo de execução amortizado e, portanto, dizemos que é uma demonstração justa. $\Theta(kcr)$
$k$ $c$ $r$ $\Theta(1)$

Para voltar às suas perguntas Por favor, desculpe-me por parafrasear, tentei extrair diferentes conjuntos de significados, fique à
vontade para comentar se perdi alguns

Você parece estar preocupado com o comprimento da saída da função hash. Vamos chamar isso de ( geralmente é considerado o número de itens a serem hash). será porque m precisa identificar exclusivamente uma entrada na tabela de hash. Isso significa que m cresce muito lentamente. Com 64 bits, o número de entradas da tabela de hash ocupará uma porção considerável da RAM disponível mundialmente. Com 128 bits, excederá em muito o armazenamento em disco disponível no planeta Terra. Produzindo um hash de 128 bits não é muito mais difícil do que um bit 32 de hash, de modo nenhum , o tempo para criar um hash não é (ou se preferir). $m$ $n$ $m$ $log(n)$

$O(m)$ $O(log(n))$

A função hash passando por bits do elemento vai levar de tempo. $log(n)$ $Θ(log(n))$

Mas a função hash não passa por bits de elementos. Por um item (!!), ele passa apenas pelos dados . Além disso, o comprimento da entrada (k) não tem relação com o número de elementos. Isso é importante, porque alguns algoritmos sem hash precisam examinar muitos elementos na coleção para encontrar um elemento (não) correspondente. A tabela de hash faz apenas 1 ou 2 comparações por item em consideração, em média, antes de chegar a uma conclusão. $log(n)$
$O(k)$

Por que as tabelas de hash são eficientes para armazenar elementos de comprimento variável?

Como, independentemente do comprimento da entrada ( ), o comprimento da saída ( ) é sempre o mesmo, as colisões são raras e o tempo de pesquisa é constante. No entanto, quando o comprimento da chave cresce em comparação com o número de itens na tabela de hash ( ), a história muda ... $k$ $m$
$k$ $n$

Por que as tabelas de hash são eficientes para armazenar grandes seqüências de caracteres?

As tabelas de hash não são muito eficientes para cadeias muito grandes.

Se for (ou seja, o tamanho da entrada é bastante grande comparado ao número de itens na tabela de hash), não podemos mais dizer que o hash tem um tempo de execução constante, mas devemos mudar para um tempo de execução de especialmente porque não há saída precoce. Você precisa fazer o hash da chave completa. Se você estiver armazenando apenas um número limitado de itens, pode ser muito melhor usar um armazenamento classificado, porque, ao comparar você pode optar por sair assim que houver uma diferença. $not$ $n >> k$ $\Theta(k)$ $k1$ $\ne$ $k2$

No entanto, se você conhece seus dados, pode optar por não hash da chave completa, mas apenas a parte volátil (conhecida ou assumida) dela, restaurando a propriedade enquanto mantém as colisões sob controle. $\Theta(1)$

Constantes ocultas
Como todos deveriam saber significa simplesmente que o tempo por elemento processado é uma constante. Essa constante é um pouco maior para hash do que para comparação simples. Para tabelas pequenas, uma pesquisa binária será mais rápida que uma pesquisa de hash, porque, por exemplo, 10 comparações binárias podem muito bem ser mais rápidas que um único hash. Para conjuntos de dados pequenos, alternativas para tabelas de hash devem ser consideradas. É em grandes conjuntos de dados que as tabelas de hash realmente brilham. $\Theta(1)$

Johan
fonte

Não entendo sua definição de . Não é verdade que o redimensionamento aumenta o tempo de execução amortizado. Desde que você redimensione adequadamente, o custo da cópia pode ser amortizado e não aumentar o tempo de execução amortizado. Eu não acho que a velocidade do hash seja um problema (mesmo os hashes criptográficos são muito rápidos; e, em qualquer caso, eles são executados em tempo constante, se o comprimento da entrada estiver no limite superior de uma constante). As declarações de tempo de execução sempre dependem do uso de uma boa função hash (portanto, as colisões serão poucas).

k, c, r

$k,c,r$

O (1)

$O(1)$

Portanto, dos problemas que você mencionou, acho que apenas o tamanho da entrada é realmente um problema sério. Além disso, isso realmente não responde à pergunta que foi feita. A pergunta fala sobre o comprimento das saídas e que o comprimento das saídas deve ser melhor considerado como bits vez de bits . Isso está correto, mas o que ele ignora é o modelo computacional usado para calcular o tempo de execução . Essa resposta não parece entrar em nada disso, então não tenho certeza se isso está chegando ao problema levantado na pergunta.

Ω (\lg n)

$\Omega(\lg n)$

O (1)

$O(1)$

O (1)

$O(1)$

Eu queria estar completo com todos os elementos do tempo de execução. Concordamos que apenas o comprimento da chave é realmente uma preocupação ao fazer o hash. Corrigi o problema do log (n) gerado pelo OP. Eu interpretei isso errado, porque não é um problema ao fazer hash na IMO.

317 Johan Johan

Espero que a resposta esteja mais em sintonia com a pergunta do OP agora.

Johan

Vamos começar com uma pergunta mais simples. Considere o que talvez seja a estrutura de dados mais simples existente, uma matriz . Para concretude, vamos imaginar uma matriz de números inteiros. Quanto tempo leva a operação ? A resposta depende do modelo de computação. Dois modelos são relevantes aqui: o modelo de RAM (que é mais comum) e o modelo de bit (que é mais simples de explicar). $A[i] = A[j]$

No modelo de bit , uma operação básica envolvendo pedaços custa . Portanto, se os inteiros tiverem bits de largura, a operação custará cerca de . $N$ $N$ $w$ $A[i] = A[j]$ $2w$

No modelo de RAM , a unidade básica de dados não é um pouco, mas uma palavra (às vezes conhecida como palavra-máquina ). Uma palavra é um número inteiro de largura , em que é o tamanho das entradas (em bits). A operação básica envolvendo palavras custa . Na maioria dos casos, se você tiver uma matriz inteira, os inteiros necessários terão largura e, portanto, a operação custa . $\log n$ $n$ $N$ $N$ $O(\log n)$ $A[i] = A[j]$ $O(1)$

Como eu disse acima, geralmente analisamos algoritmos usando o modelo de RAM. A única exceção comum é a aritmética inteira, especialmente a multiplicação inteira, que geralmente é analisada com relação ao número de operações de bits.

Por que usamos o modelo de RAM? Uma vez que tem mais poder preditivo (vis a vis realidade). A suposição de que o tamanho da entrada é no máximo exponencial do tamanho de uma palavra de máquina geralmente é justificada, especialmente para processadores modernos de 64 bits, e as operações com palavras de máquina levam tempo constante nas CPUs reais.

As tabelas de hash são estruturas de dados mais complicadas e realmente envolvem três tipos: o tipo de chave, o tipo de hash e o tipo de valor. Do ponto de vista do tipo de valor , uma tabela de hash é apenas uma matriz glorificada, então vamos ignorar esse aspecto. O tipo de hash sempre pode ser assumida para consistir de um pequeno número de palavras de máquina. O tipo de chave satisfaz uma propriedade especial: é lavável , o que significa que possui uma operação de hash que (no mínimo) é uma função determinística (uma função sempre retornando o mesmo valor).

Agora podemos responder à sua pergunta: quanto tempo leva para o hash de uma chave? A resposta depende do modelo de computação. Desta vez, temos três modelos comuns: os dois anteriores e o modelo oracle.

No modelo do oracle , assumimos que a função hash é dada a nós por um "oracle" que pode calcular o hash de uma chave arbitrária em tempo constante.

No modelo de RAM e no modelo de bit , a função hash é uma função real e a complexidade de tempo da tabela de hash depende da complexidade de tempo da função de hash. As funções de hash usadas para tabela de hash (em vez de para fins criptográficos) geralmente são muito rápidas e levam tempo linear na entrada. Isso significa que, se o tipo de chave tiver comprimento bits (no modelo de bits) ou palavras (no modelo de RAM), a função hash levará tempo . Quando é uma constante, a função hash leva tempo constante. $N$ $N$ $O(N)$ $N$

Quando analisamos o tempo de execução dos algoritmos da tabela de hash, geralmente usamos implicitamente o modelo oracle. Isso geralmente é expresso em um idioma diferente: simplesmente dizemos que contamos o número de invocações da função hash. Isso faz sentido, já que geralmente os aplicativos da função hash são o termo dominante no tempo de execução dos algoritmos da tabela de hash e, para analisar a complexidade real do tempo, tudo o que você precisa fazer é multiplicar o número de invocações de hash pelo tempo de execução. da função hash.

Ao analisar o tempo de execução de um algoritmo usando uma tabela de hash como estrutura de dados, geralmente estamos interessados no tempo de execução real, geralmente no modelo de RAM. Uma opção aqui é fazer o que foi sugerido no parágrafo anterior, ou seja, multiplicar o tempo de execução das operações da tabela de hash (fornecido em termos de número de chamadas de funções de hash) pelo tempo de execução da função de hash.

No entanto, isso não é bom o suficiente se as teclas tiverem comprimentos variados. Por exemplo, imagine que temos chaves de tamanho , e calculamos o hash de cada uma delas uma vez. A complexidade do tempo real é , mas o cálculo acima fornece apenas . Se esse for o caso em algum aplicativo, podemos levar isso em consideração ad hoc, usando uma análise refinada da complexidade da tabela de hash subjacente. $1,2,4,\ldots,2^m$ $O(2^m)$ $O(m2^m)$

Yuval Filmus
fonte