As tabelas de hash podem realmente ser O (1)?

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

A. O valor é um int menor do que o tamanho da tabela 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ê deve calcular um hash do valor. Nessa situação, a ordem é O (n) para o tamanho dos dados que estão sendo pesquisados. A pesquisa pode ser O (1) depois que você faz o trabalho O (n), mas ainda assim resulta em O (n) aos meus olhos.

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

Acho que as tabelas hash são fantásticas, mas não recebo a designação O (1), a menos que seja apenas teórica.

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

Edit: Para resumir o que aprendi:

• É tecnicamente verdade porque a função 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 a um tempo quase constante.

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

Você tem duas variáveis ​​aqui, m e n, onde m é o comprimento da entrada en é o número de itens no hash.

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

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

Se seus objetos tiverem tamanho variável e uma verificação de igualdade exigir a observação de todos os bits, o desempenho será O (m). A função hash, entretanto, não precisa ser O (m) - pode ser O (1). Ao contrário de um hash criptográfico, uma função hash para uso em um dicionário não precisa examinar cada bit na entrada para calcular o hash. As implementações são livres para examinar apenas um número fixo de bits.

Para um número suficiente de itens, o número de itens se tornará maior do que o número de hashes possíveis e você obterá colisões causando o aumento de desempenho acima de O (1), por exemplo O (n) para uma simples travessia de lista vinculada (ou O (n * m) se ambas as suposições forem falsas).

Na prática, embora a afirmação O (1), embora tecnicamente falsa, é aproximadamente verdadeira para muitas situações do mundo real e, em particular, aquelas situações em que as suposições acima são válidas.

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

O que? O hash de um único elemento leva um tempo constante. Por que seria qualquer outra coisa? Se você está inserindo nelementos, então sim, você tem que calcular nhashes, e isso leva tempo linear ... para procurar um elemento, você calcula um único hash do que está procurando e, em seguida, encontra o intervalo 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 balde, portanto, ele se transforma em uma pequena pesquisa linear em algum ponto.

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

A desvantagem das tabelas hash é, obviamente, a complexidade do espaço. Você está trocando espaço por tempo, o que parece ser o caso usual na ciência da computação.

Você mencionou 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 outra pessoa apontou novamente, você não precisa necessariamente olhar todos os chars para calcular o hash, embora possa produzir um hash melhor se você fizer isso. Nesse caso, se houver em média mchars em sua chave, e você usou todos eles para calcular seu hash, então suponho que você esteja certo, as pesquisas demorariam O(m). Se m >> nentão você pode ter um problema. Você provavelmente estaria melhor com um BST nesse caso. Ou escolha uma função de hash mais barata.

O hash tem tamanho fixo - procurar o hash bucket 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 criptográficas de hash aqui. Mas isso é por aí. O cálculo da função hash em si não depende do número n de elementos; embora possa depender do tamanho dos dados em um elemento, não é a isso que n se refere. Portanto, o cálculo do hash não depende de n e também é O (1).

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

Se sua chave tiver uma representação de n bits, sua função hash pode usar 1, 2, ... n desses bits. Pensando em uma função hash que usa 1 bit. A avaliação é O (1) com certeza. Mas você está apenas particionando o espaço da chave em 2. Portanto, você está mapeando até 2 ^ (n-1) chaves no mesmo compartimento. usando a pesquisa BST, são necessárias até n-1 etapas para localizar uma chave específica, se ela estiver quase cheia.

Você pode estender isso para ver que se sua função hash usa K bits, o tamanho do compartimento é 2 ^ (nk).

então função hash de K-bit ==> não mais que 2 ^ K bins efetivos ==> até 2 ^ (nK) chaves de n bits por bin ==> (nK) etapas (BST) para resolver colisões. Na verdade, a maioria das funções hash são muito menos "eficazes" e precisam / usam mais do que K bits para produzir 2 ^ k caixas. Portanto, mesmo isso é otimista.

Você pode ver dessa forma - você precisará de ~ n etapas para poder distinguir de forma exclusiva um par de chaves de n bits no pior caso. Não há realmente nenhuma maneira de contornar esse limite da teoria da informação, com tabela hash ou não.

No entanto, NÃO é assim / quando você usa a tabela de hash!

A análise de complexidade assume que, para chaves de n bits, você poderia ter chaves O (2 ^ n) na tabela (por exemplo, 1/4 de todas as chaves possíveis). Porém, na maioria das vezes, senão sempre, usamos a tabela hash, temos apenas um número constante de chaves de n bits na tabela. Se você quiser apenas um número constante de chaves na tabela, digamos que C é seu número máximo, então você pode formar uma tabela hash de caixas O (C), que garante a colisão constante esperada (com uma boa função hash); e uma função hash usando ~ logC dos n bits na chave. Então, toda consulta é O (logC) = O (1). É assim que as pessoas afirmam "o acesso à tabela de hash é O (1)" /

Existem alguns pontos aqui - primeiro, dizer que você não precisa de todos os bits pode ser apenas um truque de cobrança. Primeiro, você não pode realmente passar o valor da chave para a função hash, porque isso estaria movendo n bits na memória, que é O (n). Portanto, você precisa fazer, por exemplo, uma passagem de referência. Mas você ainda precisa armazená-lo em algum lugar que já foi uma operação O (n); você simplesmente não cobra do hashing; sua tarefa de computação geral não pode evitar isso. Em segundo lugar, você faz o hash, encontra o bin e encontra mais de 1 chave; seu custo depende do seu método de resolução - se você fizer comparação com base (BST ou Lista), você terá a operação O (n) (a chave de rechamada é de n bits); se você fizer o segundo hash, bem, você terá o mesmo problema se o segundo hash tiver colisão.

Considere a alternativa, por exemplo, BST, neste caso. há chaves C, portanto, um BST balanceado será O (logC) em profundidade, portanto, uma pesquisa leva etapas O (logC). No entanto, a comparação neste caso seria uma operação O (n) ... então parece que o hash é uma escolha melhor neste caso.

TL; DR: As tabelas de hash garantem o tempo O(1)esperado para o pior caso, se você escolher sua função de hash uniformemente ao acaso em uma família universal de funções de hash. O pior caso esperado não é igual ao caso médio.

Isenção de responsabilidade: Eu não provo formalmente que as tabelas de hash são O(1), para isso, dê uma olhada neste vídeo do coursera [ 1 ]. Eu também não discuto o amortizado aspectos das tabelas hash. Isso é ortogonal à discussão sobre hashing e colisões.

Vejo uma confusão surpreendentemente grande em torno desse tópico em outras respostas e comentários, e tentarei retificar algumas delas nesta longa resposta.

Raciocinando sobre o pior caso

Existem diferentes tipos de análise de pior caso. A análise que a maioria das respostas fez aqui até agora não é o pior caso, mas sim o caso médio [ 2 ]. A análise de caso médio tende a ser mais prática. Talvez seu algoritmo tenha uma entrada de pior caso ruim, mas na verdade funciona bem para todas as outras entradas possíveis. O ponto principal é que seu tempo de execução depende do conjunto de dados você está executando.

Considere o seguinte pseudocódigo do getmétodo de uma tabela hash. Aqui, estou assumindo que lidamos com a colisão por encadeamento, portanto, cada entrada da tabela é uma lista vinculada de (key,value)pares. Também assumimos que o número de intervalos mé fixo, mas é O(n), onde nestá o número de elementos na entrada.

function get(a: Table with m buckets, k: Key being looked up)
  bucket <- compute hash(k) modulo m
  for each (key,value) in a[bucket]
    return value if k == key
  return not_found

Como outras respostas indicaram, isso O(1)ocorre na média e no pior caso O(n). Podemos fazer um pequeno esboço de uma prova por desafio aqui. O desafio é o seguinte:

(1) Você fornece seu algoritmo de tabela hash a um adversário.

(2) O adversário pode estudá-lo e preparar-se o quanto quiser.

(3) Finalmente, o adversário lhe dá uma entrada de tamanho npara você inserir na sua mesa.

A questão é: quão rápido é a sua tabela de hash na entrada do adversário?

No passo (1), o adversário conhece sua função hash; durante a etapa (2), o adversário pode criar uma lista de nelementos com o mesmo hash modulo m, por exemplo, computando aleatoriamente o hash de um grupo de elementos; e então em (3) eles podem lhe dar essa lista. Mas, vejam só, uma vez que todos os nelementos são hash para o mesmo intervalo, seu algoritmo levará O(n)tempo para percorrer a lista vinculada nesse intervalo. Não importa quantas vezes tentemos novamente o desafio, o adversário sempre vence, e esse é o quão ruim é o seu algoritmo, no pior caso O(n).

Por que o hashing é O (1)?

O que nos confundiu no desafio anterior foi que o adversário conhecia nossa função hash muito bem e poderia usar esse conhecimento para criar a pior entrada possível. E se, em vez de sempre usar uma função hash fixa, tivéssemos um conjunto de funções hash H, que o algoritmo pode escolher aleatoriamente em tempo de execução? Caso você esteja curioso, Hé chamada de família universal de funções hash [ 3 ]. Tudo bem, vamos tentar adicionar alguma aleatoriedade a isso.

Primeiro, suponha que nossa tabela hash também inclua uma semente re rseja atribuída a um número aleatório no momento da construção. Nós o atribuímos uma vez e então ele é corrigido para aquela instância da tabela hash. Agora vamos revisitar nosso pseudocódigo.

function get(a: Table with m buckets and seed r, k: Key being looked up)
  rHash <- H[r]
  bucket <- compute rHash(k) modulo m
  for each (key,value) in a[bucket]
    return value if k == key
  return not_found

Se tentarmos o desafio mais uma vez: a partir da etapa (1), o adversário pode saber todas as funções hash que temos H, mas agora depende da função hash específica que usamos r. O valor de ré privado de nossa estrutura, o adversário não pode inspecioná-lo em tempo de execução, nem prever com antecedência, então ele não pode inventar uma lista que sempre é ruim para nós. Vamos supor que no passo (2) o adversário escolhe uma função hashem Haleatoriamente, então ele artesanato uma lista de ncolisões menores hash modulo me envia isso para o passo (3), cruzando os dedos que em tempo de execução H[r]será o mesmo hashque escolheram.

Esta é uma aposta séria para o adversário, a lista que ele elaborou colide hash, mas será apenas uma entrada aleatória em qualquer outra função hash em H. Se ele ganhar esta aposta, nosso tempo de execução será o pior caso O(n)como antes, mas se ele perder, então, estamos apenas recebendo uma entrada aleatória que leva o O(1)tempo médio . E de fato na maioria das vezes o adversário vai perder, ele vence apenas uma vez a cada |H|desafio, e podemos torná- |H|lo muito grande.

Compare esse resultado com o algoritmo anterior em que o adversário sempre venceu o desafio. Acenando um pouco aqui, mas como na maioria das vezes o adversário falhará, e isso é verdade para todas as estratégias possíveis que o adversário pode tentar, segue-se que, embora o pior caso seja O(n), o pior caso esperado é de fato O(1).

Novamente, esta não é uma prova formal. A garantia que obtemos dessa análise de pior caso esperada é que nosso tempo de execução agora é independente de qualquer entrada específica . Esta é uma garantia verdadeiramente aleatória, ao contrário da análise de caso médio, onde mostramos que um adversário motivado poderia facilmente criar entradas ruins.

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

1. Se sua configuração for estática, então o hashing FKS lhe dará garantias O (1) de pior caso . Mas, como você indicou, sua configuração não é estática.
2. Se você usar o hashing Cuckoo, as consultas e exclusões serão O (1) o pior caso, mas a inserção será 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 mesa para ser aproximadamente 25% maior.

Copiado daqui

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

A. O valor é um int menor do que o tamanho da tabela 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.

Este é um caso em que você poderia mapear trivialmente as chaves para depósitos distintos, portanto, uma matriz parece uma escolha melhor de estrutura de dados do que uma tabela hash. Ainda assim, as ineficiências não aumentam com o tamanho da mesa.

(Você ainda pode usar uma tabela hash porque não confia que os ints permaneçam menores do que o tamanho da tabela à medida que o programa evolui, você deseja tornar o código potencialmente reutilizável quando essa relação não se mantém, ou simplesmente não quer que as pessoas que leiam / mantenham o código tenham que desperdiçar esforço mental para entender e manter o relacionamento).

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

Precisamos distinguir entre o tamanho da chave (por exemplo, em bytes) e o tamanho do número de chaves armazenadas na tabela hash. Afirma que as tabelas de hash fornecem operações O (1) significam que as operações (inserir / apagar / localizar) não tendem a ficar mais lentas conforme o número de chaves aumenta de centenas para milhares para milhões e bilhões (pelo menos não se todos os dados é acessado / atualizado em armazenamento igualmente rápido, seja na RAM ou no disco - os efeitos do cache podem entrar em ação, mas mesmo o custo de uma falha de cache no pior caso tende a ser algum múltiplo constante do acerto no melhor caso).

Considere uma lista telefônica: você pode ter nomes bem longos, mas se o livro tiver 100 nomes, ou 10 milhões, o tamanho médio do nome será bastante consistente, e o pior caso da história ...

O recorde mundial do Guinness para o nome mais longo usado por alguém já foi estabelecido por Adolph Blaine Charles David Conde Frederick Gerald Hubert Irvin John Kenneth Lloyd Martin Nero Oliver Paul Quincy Randolph Sherman Thomas Uncas Victor William Xerxes Yancy Wolfeschlegelsteinhausenbergerdorff, Sênior

... wcme diz que são 215 caracteres - não é um limite superior rígido para o comprimento da chave, mas não precisamos nos preocupar com a existência de muito mais.

Isso vale para a maioria das tabelas de hash do mundo real: o comprimento médio da chave não tende a aumentar com o número de chaves em uso. Existem exceções, por exemplo, uma rotina de criação de chave pode retornar strings incorporando inteiros incrementais, mas mesmo assim, toda vez que você aumenta o número de chaves em uma ordem de magnitude, você apenas aumenta o comprimento da chave em 1 caractere: não é significativo.

Também é possível criar um hash a partir de uma quantidade de dados-chave de tamanho fixo. Por exemplo, o Visual C ++ da Microsoft vem com uma implementação de biblioteca padrão std::hash<std::string>que cria um hash incorporando apenas dez bytes uniformemente espaçados ao longo da string, portanto, se as strings variam apenas em outros índices, você obtém colisões (e, portanto, na prática, comportamentos não O (1) no lado da pesquisa pós-colisão), mas o tempo para criar o hash tem um limite superior rígido.

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

Geralmente é verdade, mas a coisa mais incrível sobre as tabelas de hash é que o número de chaves visitadas durante essas "pequenas pesquisas lineares" é - para a abordagem de encadeamento separado para colisões - uma função do fator de carga da tabela de hash (proporção de chaves para baldes).

Por exemplo, com um fator de carga de 1,0, há uma média de ~ 1,58 para o comprimento dessas pesquisas lineares, independentemente do número de chaves (veja minha resposta aqui ). Para hashing fechado é um pouco mais complicado, mas não muito pior quando o fator de carga não é muito alto.

É tecnicamente verdade porque a função 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 a um tempo quase constante.

Isso meio que perde o ponto. Em última análise, qualquer tipo de estrutura de dados associativa tem que fazer operações em todas as partes da chave às vezes (a desigualdade às vezes pode ser determinada a partir de apenas uma parte da chave, mas a igualdade geralmente requer que cada bit seja considerado). No mínimo, ele pode fazer o hash da chave uma vez e armazenar o valor do hash, e se usar uma função de hash forte o suficiente - por exemplo, MD5 de 64 bits - ele pode praticamente ignorar até mesmo a possibilidade de hash de duas chaves para o mesmo valor (uma empresa Trabalhei para fazer exatamente isso para o banco de dados distribuído: o tempo de geração de hash ainda era insignificante em comparação com as transmissões de rede em toda a WAN). Portanto, não há muito sentido ficar obcecado com o custo para processar a chave: isso é inerente ao armazenamento de chaves, independentemente da estrutura de dados e, como dito acima - não

Quanto às tabelas hash grandes o suficiente para reduzir as colisões, isso também está perdendo o ponto. Para encadeamento separado, você ainda tem um comprimento de cadeia de colisão médio constante em qualquer fator de carga - é apenas mais alto quando o fator de carga é mais alto e essa relação não é linear. O usuário do SO, Hans, comenta minha resposta também no link acima :

o comprimento médio do balde condicionado a baldes não vazios é uma medida melhor de eficiência. É a / (1-e ^ {- a}) [onde a é o fator de carga, e é 2,71828 ...]

Portanto, o fator de carga sozinho determina o número médio de chaves em colisão que você deve pesquisar durante as operações de inserir / apagar / localizar. Para encadeamento separado, não se trata apenas de ser constante quando o fator de carga é baixo - é sempre constante. Para endereçamento aberto, embora sua afirmação tenha alguma validade: alguns elementos em colisão são redirecionados para depósitos alternativos e podem, então, interferir nas operações em outras chaves, portanto, em fatores de carga mais altos (especialmente> 0,8 ou 0,9), o comprimento da cadeia de colisão fica mais dramaticamente pior.

É verdade na prática porque, com o tempo, funciona, desde que a função hash e o tamanho da tabela sejam escolhidos para minimizar as colisões, embora isso geralmente signifique não usar uma função hash de tempo constante.

Bem, o tamanho da tabela deve resultar em um fator de carga lógico, dada a escolha de hash próximo ou encadeamento separado, mas também se a função hash for um pouco fraca e as chaves não forem muito aleatórias, ter um número primo de baldes geralmente ajuda a reduzir colisões também ( hash-value % table-sizeentão envolve de forma que as alterações apenas para um ou dois bits de ordem superior no valor de hash ainda resolvem em intervalos espalhados pseudo-aleatoriamente por diferentes partes da tabela de hash).