Hashset vs Treeset

496

Eu sempre amei árvores, que agradável O(n*log(n))e a arrumação delas. No entanto, todo engenheiro de software que eu já conheci me perguntou claramente por que eu usaria um TreeSet. Do fundo do CS, acho que não importa muito o que você usa, e não me importo de mexer com funções de hash e buckets (no caso de Java).

Em quais casos devo usar um HashSetover a TreeSet?

heymatthew
fonte

Respostas:

860

O HashSet é muito mais rápido que o TreeSet (tempo constante versus tempo de log para a maioria das operações, como adicionar, remover e conter), mas não oferece garantias de pedidos como o TreeSet.

HashSet

  • a classe oferece desempenho de tempo constante para as operações básicas (adicionar, remover, conter e tamanho).
  • não garante que a ordem dos elementos permaneça constante ao longo do tempo
  • O desempenho da iteração depende da capacidade inicial e do fator de carga do HashSet.
    • É bastante seguro aceitar o fator de carga padrão, mas convém especificar uma capacidade inicial com o dobro do tamanho em que você espera que o conjunto cresça.

TreeSet

  • garante o log (n) custo do tempo para as operações básicas (adicionar, remover e conter)
  • garante que os elementos do conjunto sejam classificados (ascendente, natural ou o especificado por você através de seu construtor) (implementa SortedSet)
  • não oferece nenhum parâmetro de ajuste para o desempenho da iteração
  • oferece alguns métodos úteis para lidar com o conjunto ordenado como first(), last(), headSet(), e tailSet()etc

Pontos importantes:

  • Ambos garantem uma coleção de elementos sem duplicação
  • Geralmente é mais rápido adicionar elementos ao HashSet e depois converter a coleção em um TreeSet para uma travessia classificada sem duplicação.
  • Nenhuma dessas implementações é sincronizada. Ou seja, se vários encadeamentos acessam um conjunto simultaneamente e pelo menos um dos encadeamentos modifica o conjunto, ele deve ser sincronizado externamente.
  • LinkedHashSet é, em certo sentido, intermediário entre HashSete TreeSet. Implementado como uma tabela de hash com uma lista vinculada em execução, no entanto, fornece iteração ordenada por inserção que não é igual à travessia classificada garantida pelo TreeSet .

Portanto, a escolha do uso depende inteiramente de suas necessidades, mas acho que, mesmo que você precise de uma coleção ordenada, ainda deve preferir o HashSet para criar o conjunto e depois convertê-lo em TreeSet.

  • por exemplo SortedSet<String> s = new TreeSet<String>(hashSet);
sactiw
fonte
38
Só eu sou que acha a afirmação "HashSet é muito mais rápida que o TreeSet (tempo constante versus tempo de log ...)" claramente errada? Primeiro, trata-se de complexidade de tempo, não de tempo absoluto, e O (1) pode ser em muitos casos mais lento que O (f (N)). Segundo, O (logN) é "quase" O (1). Eu não ficaria surpreso se, em muitos casos comuns, um TreeSet tivesse um desempenho superior ao HashSet.
precisa saber é
22
Eu só quero secundar o comentário de Ivella. complexidade do tempo NÃO é a mesma coisa que tempo de execução, e O (1) nem sempre é melhor que O (2 ^ n). Um exemplo perverso ilustra o ponto: considere um conjunto de hash usando um algoritmo de hash que levou 1 trilhão de instruções de máquina para executar (O (1)) versus qualquer implementação comum de classificação de bolhas (O (N ^ 2) avg / pior) para 10 elementos . O tipo de bolha ganha sempre. O ponto é que as classes de algoritmos ensinam a todos a pensar em aproximações usando a complexidade do tempo, mas no mundo real os fatores constantes importam com frequência.
Peter Oehlert
17
Talvez seja só eu, mas não é o conselho primeiro adicionar tudo a um hashset e depois torná-lo horrível? 1) A inserção em um hashset é rápida apenas se você souber o tamanho do seu conjunto de dados com antecedência, caso contrário, você paga um re-hash O (n), possivelmente várias vezes. e 2) Você paga pela inserção do TreeSet de qualquer maneira ao converter o conjunto. (com força, porque a iteração através de um hashset não é muito eficiente)
TinkerTank
5
Este conselho é baseado no fato de que, para um conjunto, você deve verificar se um item é uma duplicata antes de adicioná-lo; portanto, você economizará tempo eliminando as duplicatas se estiver usando um hashset em um conjunto de árvores. No entanto, considerando o preço a pagar pela criação de um segundo conjunto para as não duplicatas, a porcentagem de duplicatas deve ser realmente grande para superar esse preço e torná-lo uma economia de tempo. E, claro, isso é para conjuntos médios e grandes porque, para um conjunto pequeno, o conjunto de árvores é possivelmente mais rápido que um hashset.
SylvainL
5
@ PeterOehlert: forneça uma referência para isso. Entendo o seu argumento, mas a diferença entre os dois conjuntos quase não importa com tamanhos de coleção pequenos. E assim que o conjunto cresce a um ponto em que a implementação é importante, o log (n) está se tornando um problema. Em geral, as funções de hash (mesmo as complexas) são magnitudes de ordem mais rápidas do que várias falhas de cache (que você tem em árvores enormes para quase todos os níveis acessados) para encontrar / acessar / adicionar / modificar a folha. Pelo menos essa é a minha experiência com esses dois conjuntos em Java.
Bouncner
38

Uma vantagem ainda não mencionada de a TreeSeté que ela possui uma "localidade" maior, o que é uma abreviação para dizer (1) se duas entradas estão próximas na ordem, as TreeSetcoloca próximas umas das outras na estrutura de dados e, portanto, na memória; e (2) esse posicionamento tira proveito do princípio de localidade, que diz que dados semelhantes são frequentemente acessados ​​por um aplicativo com frequência semelhante.

Isso contrasta com a HashSet, que espalha as entradas por toda a memória, independentemente de quais sejam suas chaves.

Quando o custo de latência da leitura de um disco rígido é milhares de vezes o custo da leitura do cache ou da RAM e quando os dados são realmente acessados ​​com a localidade, TreeSetpode ser uma escolha muito melhor.

Carl Andersen
fonte
3
Você pode demonstrar que, se duas entradas estão próximas na ordem, um TreeSet as coloca próximas umas das outras na estrutura de dados e, portanto, na memória ?
David Soroko 10/10
6
Muito irrelevante para Java. Os elementos do conjunto são Objetos de qualquer maneira e apontam para outro lugar, para que você não economize muito.
Andrew Gallasch
Além dos outros comentários feitos sobre a falta de localidade em Java em geral, a implementação de TreeSet/ do OpenJDK TreeMapnão é otimizada para localidade. Embora seja possível usar uma árvore b da ordem 4 para representar uma árvore vermelho-preta e, assim, melhorar o desempenho da localidade e do cache, não é assim que a implementação funciona. Em vez disso, cada nó armazena um ponteiro para sua própria chave, seu próprio valor, seu pai e seus nós filhos esquerdo e direito, evidentes no código-fonte JDK 8 para TreeMap.Entry .
kbolino
25

HashSeté O (1) para acessar elementos, então isso certamente importa. Mas manter a ordem dos objetos no conjunto não é possível.

TreeSeté útil se a manutenção de um pedido (em termos de valores e não do pedido de inserção) for importante para você. Mas, como você observou, você está negociando uma ordem por um tempo mais lento para acessar um elemento: O (log n) para operações básicas.

Dos javadocs paraTreeSet :

Essa implementação fornece o tempo de log (n) garantido para as operações básicas ( add, removee contains).

duffymo
fonte
22

1.HashSet permite objeto nulo.

2.TreeSet não permitirá objeto nulo. Se você tentar adicionar valor nulo, ele lançará uma NullPointerException.

3.HashSet é muito mais rápido que TreeSet.

por exemplo

 TreeSet<String> ts = new TreeSet<String>();
 ts.add(null); // throws NullPointerException

 HashSet<String> hs = new HashSet<String>();
 hs.add(null); // runs fine
SuReN
fonte
3
ts.add (null) funcionará bem no caso de TreeSet se null for adicionado como primeiro objeto no TreeSet. E qualquer objeto adicionado depois disso fornecerá NullPointerException no método compareTo do Comparator.
precisa saber é o seguinte
2
Você realmente não deveria estar adicionando nullao seu conjunto de qualquer maneira.
fofo
TreeSet<String> badassTreeSet = new TreeSet<String>(new Comparator<String>() { public int compare(String string1, String string2) { if (string1 == null) { return (string2 == null) ? 0 : -1; } else if (string2 == null) { return 1; } else { return string1.compareTo(string2); } } }); badassTreeSet.add("tree"); badassTreeSet.add("asdf"); badassTreeSet.add(null); badassTreeSet.add(null); badassTreeSet.add("set"); badassTreeSet.add("tree"); System.out.println(badassTreeSet);
Dávid Horváth
21

Baseando-se na adorável resposta visual do Maps por @shevchyk, aqui está minha opinião:

╔══════════════╦═════════════════════╦═══════════════════╦═════════════════════╗
   Property          HashSet             TreeSet           LinkedHashSet   
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
                no guarantee order  sorted according                       
   Order       will remain constant to the natural        insertion-order  
                    over time          ordering                            
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
 Add/remove           O(1)              O(log(n))             O(1)         
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
                                      NavigableSet                         
  Interfaces           Set                Set                  Set         
                                       SortedSet                           
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
                                       not allowed                         
  Null values        allowed        1st element only        allowed        
                                        in Java 7                          
╠══════════════╬═════════════════════╩═══════════════════╩═════════════════════╣
                 Fail-fast behavior of an iterator cannot be guaranteed      
   Fail-fast   impossible to make any hard guarantees in the presence of     
   behavior              unsynchronized concurrent modification              
╠══════════════╬═══════════════════════════════════════════════════════════════╣
      Is                                                                     
 synchronized               implementation is not synchronized               
╚══════════════╩═══════════════════════════════════════════════════════════════╝
kiedysktos
fonte
13

A razão pela qual a maioria usa HashSeté que as operações são (em média) O (1) em vez de O (log n). Se o aparelho contiver itens padrão, você não estará "brincando com as funções de hash", como foi feito para você. Se o conjunto contiver classes personalizadas, você precisará implementar hashCodepara usá-lo HashSet(embora o Java Efetivo mostre como), mas se você usar um, TreeSetprecisará fazê-lo Comparableou fornecer um Comparator. Isso pode ser um problema se a classe não tiver uma ordem específica.

Às vezes, usei TreeSet(ou realmente TreeMap) para conjuntos / mapas muito pequenos (<10 itens), embora não tenha verificado se há algum ganho real ao fazê-lo. Para conjuntos grandes, a diferença pode ser considerável.

Agora, se você precisar da classificação, TreeSetserá apropriado, embora, mesmo assim, se as atualizações sejam frequentes e a necessidade de um resultado classificado seja pouco frequente, às vezes copiar o conteúdo para uma lista ou matriz e classificá-los pode ser mais rápido.

Kathy Van Stone
fonte
quaisquer pontos de dados para esses elementos grandes, como 10K ou mais #
kuhajeyan
11

Se você não estiver inserindo elementos suficientes para resultar em rehashings frequentes (ou colisões, se o seu HashSet não puder ser redimensionado), um HashSet certamente oferecerá o benefício do acesso em tempo constante. Mas em conjuntos com muito crescimento ou retração, você pode obter um desempenho melhor com o Treesets, dependendo da implementação.

O tempo amortizado pode estar próximo de O (1) com uma árvore vermelho-preta funcional, se a memória me servir. O livro de Okasaki teria uma explicação melhor do que eu consigo. (Ou veja sua lista de publicações )

JasonTrue
fonte
7

As implementações do HashSet são, obviamente, muito, muito mais rápidas - menos sobrecarga porque não há pedidos. Uma boa análise das várias implementações do Conjunto em Java é fornecida em http://java.sun.com/docs/books/tutorial/collections/implementations/set.html .

A discussão lá também aponta uma interessante abordagem de "meio termo" para a questão Tree vs Hash. O Java fornece um LinkedHashSet, que é um HashSet com uma lista vinculada "orientada a inserção" sendo executada, ou seja, o último elemento da lista vinculada também é o mais recentemente inserido no Hash. Isso permite evitar a irregularidade de um hash não ordenado sem incorrer no aumento do custo de um TreeSet.

Joseph Weissman
fonte
4

O TreeSet é uma das duas coleções classificadas (a outra é o TreeMap). Ele usa uma estrutura de árvore Vermelho-Preto (mas você sabia disso) e garante que os elementos estejam em ordem crescente, de acordo com a ordem natural. Opcionalmente, você pode construir um TreeSet com um construtor que permita fornecer à coleção suas próprias regras para o que o pedido deve ser (em vez de depender da ordem definida pela classe dos elementos) usando um Comparable ou Comparator

e Um LinkedHashSet é uma versão ordenada do HashSet que mantém uma lista duplamente vinculada em todos os elementos. Use esta classe em vez do HashSet quando se importar com a ordem da iteração. Quando você itera através de um HashSet, o pedido é imprevisível, enquanto um LinkedHashSet permite iterar pelos elementos na ordem em que foram inseridos.

subhash laghate
fonte
3

Muitas respostas foram dadas, com base em considerações técnicas, especialmente em relação ao desempenho. Segundo mim, escolha entre TreeSete HashSetimporta.

Mas prefiro dizer que a escolha deve ser conduzida primeiro por considerações conceituais .

Se, para os objetos que você precisa manipular, uma ordem natural não faz sentido, não use TreeSet.
É um conjunto classificado, pois é implementado SortedSet. Portanto, isso significa que você precisa substituir a função compareTo, que deve ser consistente com o que retorna a função equals. Por exemplo, se você tiver um conjunto de objetos de uma classe chamada Student, não creio que umTreeSetfaria sentido, uma vez que não há ordenação natural entre os alunos. Você pode encomendá-los pela nota média, ok, mas isso não é um "pedido natural". A função compareToretornaria 0 não apenas quando dois objetos representam o mesmo aluno, mas também quando dois alunos diferentes têm a mesma nota. No segundo caso, equalsretornaria falso (a menos que você decida fazer com que o último retorne verdadeiro quando dois alunos diferentes tiverem a mesma nota, o que tornaria a equalsfunção um significado enganoso, sem dizer um significado errado.)
Observe esta consistência entre equalse compareToé opcional, mas altamente recomendado. Caso contrário, o contrato da interface Setserá quebrado, tornando seu código enganoso para outras pessoas, resultando também em comportamento inesperado.

Esse link pode ser uma boa fonte de informações sobre esta questão.

Marek Stanley
fonte
3

Por que ter maçãs quando você pode comer laranjas?

Sério, garotos e garotas - se sua coleção é grande, lida e escrita em bilhões de vezes, e você está pagando por ciclos de CPU, então a escolha da coleção é relevante SOMENTE se você PRECISA ter um desempenho melhor. No entanto, na maioria dos casos, isso realmente não importa - alguns milissegundos aqui e ali passam despercebidos em termos humanos. Se realmente importava muito, por que você não está escrevendo código no assembler ou C? [indique outra discussão]. Portanto, o ponto é se você está feliz usando a coleção que escolheu e resolve o seu problema (mesmo que não seja especificamente o melhor tipo de coleção para a tarefa). O software é maleável. Otimize seu código sempre que necessário. Tio Bob diz que a otimização prematura é a raiz de todo mal. Tio Bob diz isso

user924272
fonte
1

Edição da mensagem ( reescrita completa ) Quando o pedido não importa, é quando. Ambos devem fornecer Log (n) - seria útil verificar se um é mais de cinco por cento mais rápido que o outro. O HashSet pode testar O (1) em um loop e deve revelar se é.

Nicholas Jordan
fonte
-3
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class HashTreeSetCompare {

    //It is generally faster to add elements to the HashSet and then
    //convert the collection to a TreeSet for a duplicate-free sorted
    //Traversal.

    //really? 
    O(Hash + tree set) > O(tree set) ??
    Really???? Why?



    public static void main(String args[]) {

        int size = 80000;
        useHashThenTreeSet(size);
        useTreeSetOnly(size);

    }

    private static void useTreeSetOnly(int size) {

        System.out.println("useTreeSetOnly: ");
        long start = System.currentTimeMillis();
        Set<String> sortedSet = new TreeSet<String>();

        for (int i = 0; i < size; i++) {
            sortedSet.add(i + "");
        }

        //System.out.println(sortedSet);
        long end = System.currentTimeMillis();

        System.out.println("useTreeSetOnly: " + (end - start));
    }

    private static void useHashThenTreeSet(int size) {

        System.out.println("useHashThenTreeSet: ");
        long start = System.currentTimeMillis();
        Set<String> set = new HashSet<String>();

        for (int i = 0; i < size; i++) {
            set.add(i + "");
        }

        Set<String> sortedSet = new TreeSet<String>(set);
        //System.out.println(sortedSet);
        long end = System.currentTimeMillis();

        System.out.println("useHashThenTreeSet: " + (end - start));
    }
}
gli00001
fonte
1
A publicação dizia que geralmente é mais rápido adicionar elementos ao HashSet e depois converter a coleção em um TreeSet para um percurso ordenado sem duplicação. Defina <> s = novo TreeSet <>> (hashSet); Eu estou querendo saber por que não definir <String> s = new TreeSet <String> () diretamente se sabemos que será usado para iteração classificada, então fiz essa comparação e o resultado mostrou que é mais rápido.
gli00001
"Em quais casos eu gostaria de usar um HashSet sobre um TreeSet?"
21139 Austin Henley
1
O que quero dizer é que, se você precisar pedir, usar o TreeSet sozinho é melhor do que colocar tudo no HashSet e criar um TreeSet com base nesse HashSet. Não vejo o valor do HashSet + TreeSet da postagem original.
gli00001
@ gli00001: você perdeu o ponto. Se você nem sempre precisa que seu conjunto de elementos seja classificado, mas vai manipulá-lo com bastante frequência, vale a pena usar um hashset para se beneficiar das operações mais rápidas na maioria das vezes. Nos momentos ocasionais em que você precisa processar os elementos em ordem, envolva-os com um conjunto de árvores. Depende do seu caso de uso, mas esse não é um caso de uso incomum (e provavelmente supõe um conjunto que não contém muitos elementos e com regras de pedido complexas).
haylem