Por que a implementação HashSet em HashMap uso Sun Java como o seu apoio?

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

  •  19-09-2019
  •  | 
  •  

Pergunta

Olhando para o fonte de Java 6, HashSet<E> é realmente implementado usando HashMap<E,Object>, usando instância do objeto fictício em cada entrada do Conjunto.

Eu acho que os resíduos de 4 bytes (em máquinas de 32 bits) para o tamanho da própria entrada.

Mas, por que é ainda usado? Existe alguma razão para usá-lo, além de torná-lo mais fácil de manter os códigos?

Foi útil?

Solução

Na verdade, não é apenas HashSet. Todos implementações da interface Set em Java 6 são baseadas em uma Map subjacente. Isso não é um requerimento; é apenas a forma como a implementação é. Você pode ver por si mesmo, verificando a documentação para as várias implementações de Set .

As suas principais perguntas são

Mas, por que é ainda usado? Existe qualquer razão para usá-lo, além de torná-lo mais fácil de manter os códigos?

Eu assumo que a manutenção do código é um fator motivador grande. Então está impedindo a duplicação e inchaço.

Set e Map são interfaces semelhantes, em que os elementos duplicados não são permitidos. (Acho que a única Set não apoiado por uma Map é CopyOnWriteArraySet, que é uma coleção incomum, porque é imutável.)

Especificamente:

A partir da documentação de Set :

Uma coleção que não contém elementos duplicados. Mais formalmente, conjuntos contêm nenhum par de elementos e1 e e2 de modo que e1.equals (e2), e em mais um elemento nulo. Como implícito seu nome, esta interface de modelos os matemática set abstração.

A interface Set coloca adicional estipulações, além daquelas herdadas a partir da interface da recolha, no contratos de todos os construtores e sobre os contratos dos add, iguais e hashCode. declarações para outros métodos herdados são igualmente incluído aqui por conveniência. (O especificações que acompanham estes declarações foram adaptados para o interface do conjunto, mas eles não contêm qualquer estipulações adicionais.)

A estipulação adicional sobre construtores é, não surpreendentemente, que todos os construtores devem criar um conjunto que não contém duplicado Elementos (como definido acima).

E a partir Map :

Um objeto que mapeia chaves para valores. Um mapa não pode conter chaves duplicadas; cada tecla pode mapear para, no máximo, valor um.

Se você pode implementar suas Sets usando o código existente, qualquer benefício (velocidade, por exemplo), você pode perceber a partir acumula código existente para o seu Set também.

Se você optar por implementar um Set sem um suporte Map, você tem que código duplicado projetado para impedir que elementos duplicados. Ah, a deliciosa ironia.

Dito isto, não há nada impedindo-o de implementar suas Sets diferente.

Outras dicas

Eu estou supondo que nunca transformou-se como um problema significativo para aplicações reais ou benchmarks importantes. Por que complicar o código para nenhum benefício real?

Além disso, observe que os tamanhos de objetos são arredondados para cima em muitos implementação JVM, portanto, pode não ser realmente um aumento no tamanho (não sei para este exemplo). Além disso, o código para HashMap é susceptível de ser compilado e em cache. Outras coisas sendo iguais, mais code => mais erros de cache => menor desempenho.

Meu palpite é que HashSet foi originalmente implementado em termos de HashMap, a fim de fazê-lo rapidamente e facilmente. Em termos de linhas de código, HashSet é uma fracção de HashMap.

Eu acho que a razão é ainda não foi otimizado medo da mudança.

No entanto, o desperdício é muito pior do que você pensa. Em ambos os 32 bits e 64 bits, HashSet é 4x maior do que o necessário, e HashMap é 2x maior do que o necessário. HashMap poderia ser implementado com uma matriz com as teclas e os valores em que (mais cadeias de colisões). Isso significa que dois ponteiros por entrada, ou 16 bytes de um 64 bits VM. Na verdade, HashMap contém um objecto de entrada por entrada, que adiciona 8 bytes para o ponteiro para a entrada e 8 bytes para o cabeçalho objecto de entrada. HashSet também usa 32 bytes por elemento, mas o lixo é 4x vez de 2x, uma vez que exige apenas 8 bytes por elemento.

Sim, você está certo, uma pequena quantidade de desperdício é definetley lá. Pequeno, porque, para cada entrada que usa o mesmo PRESENT objeto (que é declarada final). Daí o único desperdício é para o valor de cada entrada no HashMap.

Na maior parte eu acho, eles tomaram essa abordagem para a manutenção e reutilização. (Os desenvolvedores JCF teria pensado, testámos HashMap de qualquer maneira, por que não reutilizá-lo.)

Mas se você está tendo coleções enormes, e você é um freak de memória, então você pode optar por sair de melhores alternativas como trove ou Google Collections .

Eu olhei para a sua pergunta e ele me levou um tempo para pensar sobre o que você disse. Então aqui está a minha opinião sobre a implementação HashSet.

É necessário ter o exemplo fictício de saber se o valor é ou não está presente no conjunto.

Dê uma olhada no método add 

public boolean add(E e) {
return map.put(e, PRESENT)==null;
}

Abd agora vamos dar uma olhada no valor put retorno

@returns o valor anterior associado à chave, ou null se não havia nenhum mapeamento para a chave. (A return null também pode indicar que o mapa anteriormente associado nulo com chave.)

Assim, o objeto PRESENT é apenas usado para representar que o conjunto contém o valor e. Eu acho que você perguntou por que não usar null vez de PRESENT. Mas o, você não seria capaz de distinguir se a entrada foi previamente no mapa porque map.put(key,value) voltar sempre null e você não teria como saber se a chave existiu.

Dito você poderia argumentar que eles poderiam ter usado uma implementação como esta 

   public boolean add(E e) {

        if( map.containsKey(e) ) {
            return false;
        }

        map.put(e, null);

        return true;

}

Eu acho que eles perdem 4 bytes para evitar calcular o hashCode, como poderia ser caro, é a chave duas vezes (se a chave vai ser adicionado).

Se você questão de porque eles usaram um HashMap que iria perder 8 bytes (por causa da Map.Entry) em vez de alguma outra estrutura de dados usando uma entrada semelhante de apenas 4, então sim, eu diria que eles fizeram isso pelas razões você mencionou.

Depois de pesquisar através de páginas como esta se perguntando por que a implementação padrão ligeiramente ineficiente, encontrou com.carrotsearch.hppc.IntOpenHashSet

Sua pergunta: Eu acho que os resíduos de 4 bytes (em máquinas de 32 bits) para o tamanho da própria entrada.

Apenas uma variável objeto é criado para toda a estrutura de dados de hashset e fazer que iria salvar-se de re-escrever todo o tipo HashMap de código novamente.

private static final Object PRESENT = new Object();

Todas as chaves estão tendo um valor de objeto ou seja PRESENTE.

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