As tabelas de hash podem ser O (1)?

Parece ser de conhecimento comum que as tabelas de hash podem alcançar O (1), mas isso nunca fez sentido para mim. Alguém pode por favor explicar isso? Aqui estão duas situações que vêm à mente:

A. O valor é um int menor que o tamanho da tabela de hash. Portanto, o valor é seu próprio hash, portanto, não há tabela de hash. Mas se houvesse, seria O (1) e ainda seria ineficiente.

B. Você tem que calcular um hash do valor. Nessa situação, a ordem é O (n) para o tamanho dos dados sendo pesquisados. A pesquisa pode ser O (1) depois que você faz O (n) funcionar, mas isso ainda aparece em O (n) em meus olhos.

E, a menos que você tenha um hash perfeito ou uma grande tabela de hash, provavelmente há vários itens por depósito. Então, ele se transforma em uma pequena pesquisa linear em algum momento.

Eu acho que as tabelas de hash são incríveis, mas eu não obtenho a designação O (1) a menos que seja apenas suposto ser teórico.

O artigo da Wikipedia para tabelas de hash referencia consistentemente o tempo de pesquisa constante e ignora totalmente o custo da function hash. Isso é realmente uma medida justa?


Edit: Para resumir o que aprendi:

  • Isso é tecnicamente verdadeiro porque a function hash não é necessária para usar todas as informações na chave e, portanto, pode ser um tempo constante e porque uma tabela grande o suficiente pode reduzir as colisões para um tempo quase constante.

  • É verdade, na prática, porque com o tempo isso apenas funciona desde que a function hash e o tamanho da tabela sejam escolhidos para minimizar as colisões, mesmo que isso muitas vezes signifique não usar uma function hash de tempo constante.

Você tem duas variables ​​aqui, m e n, onde m é o comprimento da input en é o número de itens no hash.

A declaração de desempenho de pesquisa O (1) faz pelo menos duas suposições:

  • Seus objects podem ser iguais comparados no tempo O (1).
  • Haverá poucas colisões de hash.

Se seus objects são de tamanho variável e uma verificação de igualdade requer a análise de todos os bits, o desempenho se tornará O (m). A function hash, no entanto, não precisa ser O (m) – pode ser O (1). Ao contrário de um hash criptográfico, uma function hash para uso em um dictionary não precisa examinar cada bit na input para calcular o hash. As implementações são livres para examinar apenas um número fixo de bits.

Para muitos itens, o número de itens se tornará maior que o número de hashes possíveis e, em seguida, você obterá colisões causando o aumento de desempenho acima de O (1), por exemplo, O (n) para uma simples passagem de linked list (ou O * m) se ambas as suposições forem falsas).

Na prática, embora a alegação O (1), embora tecnicamente falsa, seja aproximadamente verdadeira para muitas situações do mundo real, e em particular aquelas situações em que as suposições acima se mantêm.

Você tem que calcular o hash, então a ordem é O (n) para o tamanho dos dados sendo pesquisados. A pesquisa pode ser O (1) depois que você faz O (n) funcionar, mas isso ainda aparece em O (n) em meus olhos.

O que? Para hash um único elemento leva tempo constante. Por que isso seria outra coisa? Se você está inserindo n elementos, então sim, você tem que computar n hashes, e isso leva tempo linear … para olhar um elemento para cima, você calcula um único hash do que está procurando, então encontre o bucket apropriado com isso. Você não recalcula os hashes de tudo que já está na tabela de hash.

E, a menos que você tenha um hash perfeito ou uma grande tabela de hash, provavelmente há vários itens por depósito, de modo que, em algum ponto, ele se torna uma pequena pesquisa linear.

Não necessariamente. Os intervalos não precisam necessariamente ser listas ou matrizes, eles podem ser qualquer tipo de contêiner, como um BST balanceado. Isso significa que O(log n) pior caso O(log n) . Mas é por isso que é importante escolher uma boa function de hashing para evitar colocar muitos elementos em um único balde. Como Kenny apontou, em média, você ainda terá O(1) tempo, mesmo que ocasionalmente você tenha que cavar um balde.

O comércio de tabelas de hash é, naturalmente, a complexidade do espaço. Você está trocando espaço por tempo, o que parece ser o caso comum na ciência da computação.


Você menciona o uso de strings como chaves em um de seus outros comentários. Você está preocupado com a quantidade de tempo que leva para calcular o hash de uma string, porque ela consiste em vários caracteres? Como alguém apontou novamente, você não precisa necessariamente olhar todos os caracteres para calcular o hash, embora possa produzir um hash melhor se você o fizer. Nesse caso, se houver em média m caracteres em sua chave, e você usou todos eles para calcular seu hash, então eu suponho que você esteja certo, que as buscas levariam O(m) . Se m >> n , você pode ter um problema. Você provavelmente estaria melhor com um BST nesse caso. Ou escolha uma function de hash mais barata.

O hash é de tamanho fixo – procurar o bucket de hash apropriado é uma operação de custo fixo. Isso significa que é O (1).

Calcular o hash não precisa ser uma operação particularmente cara – não estamos falando de funções hash criptográficas aqui. Mas isso é a propósito. O cálculo da function hash em si não depende do número n de elementos; embora possa depender do tamanho dos dados em um elemento, isso não é o que n se refere. Portanto, o cálculo do hash não depende de n e também é O (1).

O hash é O (1) somente se houver apenas um número constante de chaves na tabela e algumas outras suposições forem feitas. Mas em tais casos tem vantagem.

Se sua chave tiver uma representação de n bits, sua function hash pode usar 1, 2, … n desses bits. Pensando em uma function hash que usa 1 bit. A avaliação é O (1) com certeza. Mas você está apenas particionando o espaço da chave em 2. Então, você está mapeando até 2 ^ (n-1) chaves na mesma posição. usando a pesquisa BST, isso leva até n-1 etapas para localizar uma chave específica se estiver quase cheia.

Você pode estender isto para ver que se sua function hash usa K bits, seu tamanho de bin é 2 ^ (nk).

function de hash do K-bit ==> não mais do que 2 ^ K checkboxs efetivas ==> até 2 ^ (nK) chaves de n bits por bin ==> (nK) etapas (BST) para resolver colisões. Na verdade, a maioria das funções hash é muito menos “efetiva” e precisa / usa mais do que K bits para produzir 2 ^ k bins. Então, mesmo isso é otimista.

Você pode visualizá-lo desta forma – você precisará de alguns passos para poder distinguir de maneira única um par de chaves de n bits no pior caso. Não há realmente nenhuma maneira de contornar este limite de teoria da informação, tabela de hash ou não.

No entanto, isso não é como / quando você usa a tabela de hash!

A análise de complexidade assume que, para chaves de n bits, você pode ter chaves O (2 ^ n) na tabela (por exemplo, 1/4 de todas as chaves possíveis). Mas a maioria, se não todo o tempo que usamos tabela de hash, só temos um número constante de chaves de n bits na tabela. Se você quer apenas um número constante de chaves na tabela, digamos C é o seu número máximo, então você poderia formar uma tabela de hash de checkboxs O (C), que garante colisão constante esperada (com uma boa function hash); e uma function hash usando ~ logC dos n bits na chave. Então toda consulta é O (logC) = O (1). É assim que as pessoas afirmam que “o access à tabela hash é O (1)” /

Há um par de capturas aqui – primeiro, dizendo que você não precisa de todos os bits só pode ser um truque de faturamento. Primeiro você não pode realmente passar o valor da chave para a function hash, porque isso seria mover n bits na memory que é O (n). Então você precisa fazer, por exemplo, uma passagem de referência. Mas você ainda precisa armazená-lo em algum lugar que já era uma operação O (n); você apenas não conta para o hashing; sua tarefa de computação geral não pode evitar isso. Segundo, você faz o hashing, encontra o bin e encontra mais de 1 chaves; seu custo depende do seu método de resolução – se você fizer uma comparação baseada em (BST ou List), você terá a operação O (n) (a chave de rechamada é n-bit); se você fizer o segundo hash, bem, você terá o mesmo problema se o segundo hash tiver colisão. Então O (1) não é 100% garantido, a menos que você não tenha colisão (você pode melhorar a chance tendo uma tabela com mais checkboxs do que chaves, mas ainda assim).

Considere a alternativa, por exemplo, BST, neste caso. existem chaves C, então um BST balanceado será O (logC) em profundidade, então uma busca leva os passos O (logC). No entanto, a comparação, neste caso, seria uma operação O (n) … por isso, parece que o hashing é uma escolha melhor neste caso.

Existem duas configurações sob as quais você pode obter O (1) pior momento.

  1. Se sua configuração for estática, o hashing do FKS fornecerá as garantias O (1) piores. Mas, como você indicou, sua configuração não é estática.
  2. Se você usar o hash Cuckoo, as consultas e exclusões serão O (1) no pior caso, mas a inserção é apenas O (1) esperada. O hash cuco funciona muito bem se você tiver um limite superior no número total de inserções e definir o tamanho da tabela como aproximadamente 25% maior.

Copiado daqui

Parece baseado na discussão aqui, que se X é o teto de (# de elementos em table / # de bins), então uma resposta melhor é O (log (X)) assumindo uma implementação eficiente de pesquisa de bin.