É um hashmap Java realmente O (1)?

StackOverflow https://stackoverflow.com/questions/1055243

Pergunta

Eu vi algumas afirmações interessantes sobre SO re HashMaps Java e seu tempo de pesquisa O(1). Alguém pode explicar por que isso acontece? A menos que estes HashMaps são muito diferentes de qualquer um dos algoritmos de hash que foi comprada em diante, não deve existir sempre um conjunto de dados que contém colisões.

Nesse caso, a pesquisa seria O(n) em vez de O(1).

Alguém pode explicar se eles são O (1) e, em caso afirmativo, como eles conseguir isso?

Foi útil?

Solução

Uma característica particular de um HashMap é que, digamos, árvores, ao contrário equilibrado, o seu comportamento é probabilística. Nestes casos, a sua geralmente mais úteis para falar sobre a complexidade em termos de probabilidade de um evento de pior caso ocorra seria. Para um mapa de hash, que, claro, é o caso de uma colisão com respeito a quão cheio o mapa passa a ser. Uma colisão é muito fácil de estimar.

p colisão = n / capacidade

Assim, um mapa de hash, mesmo com um número modesto de elementos é bastante provável que a experiência pelo menos uma colisão. Big O notação nos permite fazer algo mais atraente. Observe que para qualquer arbitrária, fixo constante k.

O (n) = O (k * n)

Podemos usar esse recurso para melhorar o desempenho do mapa hash. Poderíamos, em vez pensar sobre a probabilidade de no máximo 2 colisões.

p colisão x 2 = (n / capacidade) 2

Este é muito menor. Uma vez que o custo do tratamento de uma colisão extra é irrelevante para a Big O desempenho, nós encontramos uma maneira de melhorar o desempenho sem alterar o algoritmo! Podemos generalzie isso

p colisão x k = (n / capacidade) k

E agora podemos ignorar alguns número arbitrário de colisões e acabar com infimamente pequena probabilidade de mais colisões que estamos representando. Você poderá obter a probabilidade para um nível arbitrariamente pequena, escolhendo o k correto, tudo sem alterar a implementação real do algoritmo.

Nós falamos sobre isso dizendo que o hash-mapa tem O (1) o acesso com alta probabilidade

Outras dicas

Você parece misturar-se o comportamento de pior caso com caso média de tempo de execução (esperado). O primeiro é de fato O (n) para tabelas de hash em geral (ou seja, não usando um hash perfeito), mas isso raramente é relevante na prática.

Qualquer implementação tabela hash confiável, acoplado com um meio de hash decente, tem um desempenho de recuperação de O (1) com um pequeno factor de (2, de facto), no caso que o esperado, com uma margem muito estreita de variância.

Em Java, HashMap funciona usando hashCode para localizar um balde. Cada balde é uma lista de itens que residem nesse balde. Os itens são digitalizados, usando iguais para comparação. Ao adicionar itens, o HashMap é redimensionado uma vez uma certa percentagem de carga é alcançado.

Então, às vezes ele terá que comparar com alguns itens, mas geralmente é muito mais perto de O (1) do que O (n). Para fins práticos, isso é tudo que você deve precisam saber.

Lembre-se que o (1) não significa que cada pesquisa analisa apenas um único item - isso significa que o número médio de itens marcados restos w.r.t. constante o número de itens no recipiente. Então, se ele leva em média 4 comparações para encontrar um item em um recipiente com 100 itens, ele também deve ter uma média de 4 comparações para encontrar um item em um recipiente com 10.000 itens, e para qualquer outro número de itens (há sempre um bit de variância, especialmente em torno dos pontos em que os rehashes tabela de hash, e quando há um número muito pequeno de itens).

Assim colisões não impedem que o recipiente a partir de ter (1) O operações, desde que o número médio de chaves por restos de balde dentro de um fixo ligado.

Eu sei que isto é uma questão de idade, mas há realmente uma nova resposta para isso.

Você está certo de que um mapa de hash não é realmente O(1), estritamente falando, porque, como o número de elementos fica arbitrariamente grande, eventualmente, você não será capaz de pesquisar em tempo constante (e O-notação é definida em termos de números que pode obter arbitrariamente grande).

Mas isso não significa que a complexidade de tempo real é O(n) - porque não há nenhuma regra que diz que os baldes têm de ser implementadas como uma lista linear.

Na verdade, Java 8 implementos os baldes como TreeMaps uma vez que excederem o limiar, o que torna a O(log n) tempo real.

Se o número de baldes (chame-b) é constante em espera (o caso mais usual), seguida de pesquisa é, na verdade, O (n).
Como n se torna grande, o número de elementos em cada balde médias de n / b. Se a resolução de colisão é feito em uma das formas habituais (lista ligada, por exemplo), em seguida, pesquisa é O (n / b) = O (n).

A notação O é sobre o que acontece quando n se torna maior e maior. Ele pode ser enganosa quando aplicado a certos algoritmos e tabelas de hash são um caso no ponto. Nós escolher o número de baldes com base em quantos elementos que estamos esperando para lidar com eles. Quando n é aproximadamente o mesmo tamanho como b, em seguida, consulta é aproximadamente de tempo constante, mas não podemos chamá-lo de O (1), porque S é definido em termos de um limite como n ? 8.

O(1+n/k) onde k é o número de baldes.

Se os conjuntos de implementação k = n/alpha então é O(1+alpha) = O(1) desde alpha é uma constante.

Nós estabelecemos que a descrição padrão de tabela hash pesquisas sendo O (1) refere-se à média de casos de tempo de espera, não o estrito desempenho de pior caso. Para uma tabela hash resolver colisões com encadeamento (como hashmap de Java) este é tecnicamente O (1 + a) com um bom função hash, onde a é o fator de ocupação mesa. Ainda constante, desde que o número de objetos que você está armazenando não é mais do que um fator constante maior do que o tamanho da tabela.

Ele também tem sido explicou que, estritamente falando, é possível introduzir construção que requer O ( n ) pesquisas para qualquer função hash determinista. Mas também é interessante considerar o pior caso de esperado tempo, o que é diferente do tempo de busca médio. Usando encadeamento este é O (1 + o comprimento da cadeia mais longa), por exemplo T (log registo log n / n ) quando a = 1.

Se você está interessado em formas teóricas para alcançar constante de tempo esperado pesquisas de pior caso, você pode ler sobre dinâmica hashing perfeito que resolve colisões de forma recursiva com outra tabela de hash!

É O (1) somente se a função hash é muito bom. A implementação de tabela de hash Java não protege contra hash funções ruins.

Se você precisa para crescer a mesa ao adicionar itens ou não, não é relevante para a questão porque é sobre o tempo de pesquisa.

Elementos dentro do HashMap são armazenados como uma matriz de lista ligada (nó), cada lista encadeada da matriz representa um balde para o valor hash exclusivo de uma ou mais chaves.
Ao adicionar uma entrada no HashMap, o hashcode da chave é usada para determinar a localização do balde na matriz, algo como: 

location = (arraylength - 1) & keyhashcode

Aqui a & AND bit a bit operador representa.

Por exemplo: 100 & "ABC".hashCode() = 64 (location of the bucket for the key "ABC")

Durante a operação get ele usa mesma maneira para determinar a localização do balde para a chave. Sob o melhor caso, cada tecla tem hashcode única e resulta em um balde exclusivo para cada chave, neste caso, o método get gasta tempo apenas para determinar a localização balde e recuperando o valor que é O constante (1).

De acordo com o pior caso, todas as chaves têm o mesmo código de hash e armazenado no mesmo recipiente, isto resulta em que atravessa toda a lista que conduz para o (n).

No caso de java 8, o balde lista ligada é substituído por um TreeMap se o tamanho cresce para mais de 8, isso reduz o pior eficiência pesquisa caso a O (log n).

Isto vai, basicamente, para a maioria das implementações de tabela de hash na maioria das linguagens de programação, como o próprio algoritmo realmente não muda.

Se não há colisões presentes na tabela, você só tem que fazer um único look-up, portanto, o tempo de execução é O (1). Se houver colisões presente, você tem que fazer mais do que um look-up, que impulsiona para baixo o desempenho no sentido de O (n).

Isso depende do algoritmo que você escolher para evitar colisões. Se os seus usos implementação separar encadeamento, em seguida, o pior cenário acontece onde cada elemento de dados é hash para o mesmo valor (má escolha da função hash, por exemplo). Nesse caso, os dados de pesquisa não é diferente de uma pesquisa linear sobre uma lista ligada isto é O (n). No entanto, a probabilidade de isso acontecer é insignificante e pesquisas de melhor e casos médios permanecem constantes ou seja, O (1).

Academics lado, a partir de uma perspectiva prática, HashMaps deve ser aceito como tendo um impacto no desempenho inconseqüente (a menos que o profiler lhe diga o contrário.)

Apenas em caso teórico, quando hashcodes são sempre diferentes e um balde para cada código de hash também é diferente, o O (1) existirá. Caso contrário, é de ordem constante ou seja, com incremento de hashmap, a sua ordem de busca permanece constante.

Claro que o desempenho do hashmap dependerá com base na qualidade da função hashCode () para o objeto fornecido. No entanto, se a função é implementado de tal forma que a possibilidade de colisões é muito baixa, ele terá um desempenho muito bom (isto não é estritamente O (1) em todas caso possível, mas é no mais casos).

Por exemplo, a implementação padrão na versão Oracle JRE é usar um número aleatório (que é armazenado na instância do objeto para que ele não muda - mas também desativa bloqueio tendenciosa, mas isso é uma outra discussão) para a chance de colisões é muito baixo.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top