Complexidade de tempo de execução da tabela de hash (inserir, pesquisar e excluir)

Por que continuo vendo diferentes complexidades de tempo de execução para essas funções em uma tabela de hash?

No wiki, search e delete são O (n) (eu achei que o ponto das tabelas hash era ter uma busca constante, então qual é o ponto se a busca é O (n)).

Em algumas notas do curso de um tempo atrás, vejo uma grande variedade de complexidades, dependendo de certos detalhes, incluindo um com todos os O (1). Por que qualquer outra implementação seria usada se eu conseguisse todos os O (1)?

Se eu estiver usando tabelas hash padrão em uma linguagem como C ++ ou Java, o que posso esperar da complexidade de tempo?

Tabelas de hash são O(1) complexidade de casos média e amortizada , no entanto, sofre de O(n) complexidade do tempo do pior caso . [E eu acho que é aqui que está sua confusão]

Tabelas de hash sofrem de O(n) pior complexidade de tempo devido a dois motivos:

  1. Se muitos elementos foram colocados na mesma chave: olhar dentro desta chave pode levar O(n) tempo.
  2. Uma vez que uma tabela hash passou pelo seu balanceamento de carga – ela precisa ser repetida [crie uma nova tabela maior e reinsira cada elemento na tabela].

No entanto, diz-se que é O(1) caso médio e amortizado porque:

  1. É muito raro que muitos itens sejam colocados em hash na mesma chave [se você escolheu uma boa function hash e não tem um saldo de carga muito grande.
  2. A operação rehash, que é O(n) , pode no máximo acontecer depois de n/2 ops, que são todos assumidos O(1) : Assim quando você sum o tempo médio por op, você obtém: (n*O(1) + O(n)) / n) = O(1)

Observe que, devido ao problema recorrente – aplicativos em tempo real e aplicativos que precisam de baixa latência – não deve usar uma tabela de hash como estrutura de dados.

EDIT: outro problema com tabelas de hash: cache
Outro problema em que você pode ver uma perda de desempenho em grandes tabelas de hash é devido ao desempenho do cache. As Tabelas de hash sofrem com o mau desempenho do cache e, portanto, com uma grande coleção – o tempo de access pode levar mais tempo, já que é necessário recarregar a parte relevante da tabela da memory de volta para o cache.

Idealmente, um hashtable é O(1) . O problema é se duas chaves não são iguais, no entanto, elas resultam no mesmo hash.

Por exemplo, imagine as cordas “foi a melhor das épocas em que foi o pior dos tempos” e “Green Eggs and Ham” ambos resultaram em um valor hash de 123 .

Quando a primeira string é inserida, ela é colocada no bucket 123. Quando a segunda string é inserida, ela verá que já existe um valor para o bucket 123 . Compararia então o novo valor ao valor existente e veria que eles não são iguais. Nesse caso, uma matriz ou linked list é criada para essa chave. Neste ponto, recuperar esse valor se torna O(n) pois o hashtable precisa iterar por meio de cada valor desse intervalo para localizar o valor desejado.

Por esse motivo, ao usar uma tabela de hash, é importante usar uma chave com uma function de hash realmente boa que seja rápida e não resulte em valores duplicados para objects diferentes.

Faz sentido?

Algumas tabelas de hash (hash de cuco) têm garantia de consulta de O (1)

Depende de como você implementa hashing, no pior dos casos pode ir para O (n), no melhor dos casos é 0 (1) (geralmente você pode conseguir se o seu DS não for tão grande assim)

Talvez você estivesse olhando para a complexidade do espaço? Isso é O (n). As outras complexidades são as esperadas na input da tabela de hash . A complexidade de pesquisa se aproxima de O (1) à medida que o número de depósitos aumenta. Se, no pior caso, você tiver apenas um bloco na tabela de hash, a complexidade da pesquisa será O (n).

Editar em resposta ao comentário Não acho correto dizer que O (1) é o caso médio. É realmente (como diz a página da wikipedia) O (1 + n / k) onde K é o tamanho da tabela de hash. Se K é grande o suficiente, então o resultado é efetivamente O (1). Mas suponha que K seja 10 e N seja 100. Nesse caso, cada bucket terá em média 10 inputs, então o tempo de busca definitivamente não é O (1); é uma busca linear em até 10 inputs.