java - Explicação sobre o algoritmo de hash HashMap neste exemplo




collision hashcode (4)

Eu estava tentando resolver esta pergunta:

Dado um conjunto de números inteiros com apenas 3 números únicos, imprima os números em ordem crescente (com suas respectivas frequências) em O (n) tempo.

Eu queria resolvê-lo sem usar o algoritmo de counting sort . Então, o que eu pensei é que eu poderia fazer um for loop e inserir os números em um HashMap e, em seguida, percorrer o HashMap entrySet e imprimir as informações necessárias.

Aqui está a função: 

public static void printOut(int[] arr){
        Map<Integer,Integer> hm=new HashMap<Integer,Integer>();
        for(int num : arr){
            if(hm.containsKey(num)){
                hm.put(num,hm.get(num)+1);
            }else{hm.put(num,1);}
        }
        for(Map.Entry<Integer,Integer> entry : hm.entrySet()){
            System.out.println("Key= "+entry.getKey()+" Value= "+entry.getValue());
        }
}

que fez o truque quando eu minha matriz era: [3, 3, 2, 1, 3, 2, 1]

No entanto, a matriz acima não deve levar a nenhuma colisão; portanto, tentei usar uma matriz que deveria levar a colisões. Uma das matrizes com as quais testei minha função foi: [6,6,9,9,6,3,9] ainda minha função ainda imprimiu as Keys em ordem crescente, o que me deixou confuso, porque pensei que quando a Key do HashMap fosse um número inteiro, o código hash deveria ser hashIndex = key % noOfBuckets portanto, quando tenho os números 6, 9 and 3 como meu HashMap keys Eu pensei que haveria colisões e minha função deve ser impressa (com base na matriz usada acima): 

Key= 6 Value= 3
Key= 9 Value= 3
Key= 3 Value= 1

Mas, em vez disso, foi impresso: 

Key= 3 Value= 1
Key= 6 Value= 3
Key= 9 Value= 3

Alguém poderia me explicar por que encontrei a solução certa para a pergunta que estava tentando resolver, em vez da resposta que esperava?

Obrigado.

Alguém poderia me explicar por que encontrei a solução certa para a pergunta que estava tentando resolver, em vez da resposta que esperava?

É uma coincidência

ATUALIZAR

Como já mencionado por outros, um HashMap não garante nenhuma ordem ao iterar seu conteúdo, ao contrário do TreeMap que está classificado ou do LinkHashMap que conserva a ordem de entrada. Então, sim, se seus elementos são classificados, é apenas uma coincidência.

  1. O termo "colisão" no mapa de hash / tabela de hash é uma situação em que duas chaves diferentes têm o mesmo código de hash. A implementação do HashMap em Java usa a List / RB-tree para resolver colisões, mas quando você tem literalmente 3 chaves inteiras, esse definitivamente não é o seu caso.
  2. O HashMap não garante a ordem de inserção (ou qualquer outra) de elementos. Existem outras estruturas diferentes, como o LinkedHashMap ou o TreeMap, que podem garantir alguma ordem. Mas usar essas estruturas para o seu caso é um pouco sobrecarregado, pois você pode classificar sua coleção de 3 elementos no tempo constante. Você pode até usar a matriz do Map.Entry em vez do HashMap para sua tarefa.

Isso é mera coincidência e o pedido do EntrySet e do KeySet não é garantido. O hashmap de informação em si não garante o pedido de inserção e isso também pode mudar durante a refilmagem.

Agora você está tentando inserir int primitivo no hashmap como chave que internamente faz autobox e o objeto Inteiro será inserido como chave.

A função de código hash inteiro é 

public static int hashCode(int value) {
    return value;
}

Significa apenas retornar diretamente o valor, no seu caso 6,9 e 3

Esse código de hash é usado internamente pelo hashmap para que a computação obtenha a posição do índice 

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Como você pode ver, o operador bit a bit com os valores fornecidos retornará 0 e exponencial nesses valores levará ao mesmo índice de 3, o que leva à colisão. Portanto, o hashmap armazenará isso usando o LinkedList (java8 anterior) e na árvore (java8 e sua versão posterior).

Ao iterar via keySet ou entrySet, o pedido não será garantido e, portanto, o pedido que você está recebendo é mera coincidência.

Não sei ao certo o que você quer dizer com "colisões", mas como já foi mencionado, se você ler a documentação do HashMap ( https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html ) não há declaração sobre o pedido:

"Esta classe não garante a ordem do mapa; em particular, não garante que a ordem permaneça constante ao longo do tempo."

E mais tarde "Para melhorar o impacto, quando as chaves são Comparáveis, essa classe pode usar a ordem de comparação entre as chaves para ajudar a romper os laços".

Você usa, finalmente, Inteiros como chaves, que estão implementando a interface Comparável, o que significa que a implementação do HashMap pode ordenar suas chaves - o que realmente acontece.

Você também pode usar uma implementação Hash em que a ordem das chaves é predefinida e previsível, como um SortedMap.




java   hashmap   collision   hashcode  


hashcode