基于添加重复值的比较：HashSet vs TreeSet vs LinkedHashSet

Question

基于添加重复值的比较：HashSet vs TreeSet vs LinkedHashSet

javacollectionsset

38

我正在学习Java核心的精华——Collections。我想知道在HashSet、TreeSet和LinkedHashSet中添加重复元素时内部会发生什么。

是否替换条目，忽略还是抛出异常并终止程序。还有一个子问题是，其中哪一个对于所有操作具有相同或平均时间复杂度

非常感谢您的回复。

- Prashant Shilimkar

如果添加重复内容，它将覆盖简单内容。 - shreyansh jogi

4个回答

13

这张图片可能有助于您理解......

图片来源：http://javaconceptoftheday.com/hashset-vs-linkedhashset-vs-treeset-in-java/

- user2485429

关于TreeSet不允许空值的部分是错误的。TreeSet支持添加空值。如果使用默认的“自然顺序”比较器，确实会出现NPE。但是，如果您提供支持空值的比较器，例如new TreeSet<>(Comparator.nullFirst(Comparator.naturalOrder))，它可以正常工作。 - kapex

2

我没有找到太多关于它们之间差异的硬数据，所以我对这3种情况进行了基准测试。

看起来，在添加时 HashSet 比 TreeSet 快约4倍（在某些情况下，这可能会根据您的数据的确切特征而有所不同）。

# Run complete. Total time: 00:22:47

Benchmark                                                     Mode  Cnt  Score   Error  Units
DeduplicationWithSetsBenchmark.deduplicateWithHashSet        thrpt  200  7.734 ▒ 0.133  ops/s
DeduplicationWithSetsBenchmark.deduplicateWithLinkedHashSet  thrpt  200  7.100 ▒ 0.171  ops/s
DeduplicationWithSetsBenchmark.deduplicateWithTreeSet        thrpt  200  1.983 ▒ 0.032  ops/s

以下是基准测试代码：

package my.app;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;

import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;

public class DeduplicationWithSetsBenchmark {

    static Item[] inputData = makeInputData();

    @Benchmark
    public int deduplicateWithHashSet() {
        return deduplicate(new HashSet<>());
    }

    @Benchmark
    public int deduplicateWithLinkedHashSet() {
        return deduplicate(new LinkedHashSet<>());
    }

    @Benchmark
    public int deduplicateWithTreeSet() {
        return deduplicate(new TreeSet<>(Item.comparator()));
    }

    private int deduplicate(Set<Item> set) {
        for (Item i : inputData) {
            set.add(i);
        }
        return set.size();
    }

    public static void main(String[] args) throws RunnerException {

        // Verify that all 3 methods give the same answers:
        DeduplicationWithSetsBenchmark x = new DeduplicationWithSetsBenchmark();
        int count = x.deduplicateWithHashSet();
        assert(count < inputData.length);
        assert(count == x.deduplicateWithLinkedHashSet());
        assert(count == x.deduplicateWithTreeSet());


        Options opt = new OptionsBuilder()
            .include(DeduplicationWithSetsBenchmark.class.getSimpleName())
            .forks(1)
            .build();

        new Runner(opt).run();
    }

    private static Item[] makeInputData() {
        int count = 1000000;
        Item[] acc = new Item[count];
        Random rnd = new Random();

        for (int i=0; i<count; i++) {
            Item item = new Item();
            // We are looking to include a few collisions, so restrict the space of the values
            item.name = "the item name " + rnd.nextInt(100);
            item.id = rnd.nextInt(100);
            acc[i] = item;
        }
        return acc;
    }

    private static class Item {
        public String name;
        public int id;

        public String getName() {
            return name;
        }

        public int getId() {
            return id;
        }

        @Override
        public boolean equals(Object obj) {
            Item other = (Item) obj;

            return name.equals(other.name) && id == other.id;
        }

        @Override
        public int hashCode() {
            return name.hashCode() * 13 + id;
        }

        static Comparator<Item> comparator() {
            return Comparator.comparing(Item::getName, Comparator.naturalOrder())
                .thenComparing(Item::getId, Comparator.naturalOrder());
        }
    }
}

- Rich

0

简而言之：这些集合会忽略重复的值。

我还没有看到对于问题中加粗部分的完整回答，重复的值到底会发生什么？它会覆盖旧对象还是忽略新对象？考虑一个对象的例子，其中一个字段确定相等性，但有可能存在额外的数据变化：

public class MyData implements Comparable {
    public final Integer valueDeterminingEquality;
    public final String extraData;

    public MyData(Integer valueDeterminingEquality, String extraData) {
        this.valueDeterminingEquality = valueDeterminingEquality;
        this.extraData = extraData;
    }

    @Override
    public boolean equals(Object o) {
        return valueDeterminingEquality.equals(((MyData) o).valueDeterminingEquality);
    }

    @Override
    public int hashCode() {
        return valueDeterminingEquality.hashCode();
    }

    @Override
    public int compareTo(Object o) {
        return valueDeterminingEquality.compareTo(((MyData)o).valueDeterminingEquality);
    }
}

这个单元测试表明所有三个集合都会忽略重复的值：

import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;

import java.util.*;

import static org.hamcrest.CoreMatchers.is;
import static org.hamcrest.MatcherAssert.assertThat;

@RunWith(Parameterized.class)
public class SetRepeatedItemTest {
    private final Set<MyData> testSet;

    public SetRepeatedItemTest(Set<MyData> testSet) {
        this.testSet = testSet;
    }

    @Parameterized.Parameters
    public static Collection<Object[]> data() {
        return Arrays.asList(new Object[][] {
                { new TreeSet() }, { new HashSet() }, { new LinkedHashSet()}
        });
    }

    @Test
    public void testTreeSet() throws Exception {
        testSet.add(new MyData(1, "object1"));
        testSet.add(new MyData(1, "object2"));
        assertThat(testSet.size(), is(1));
        assertThat(testSet.iterator().next().extraData, is("object1"));
    }
}

我也研究了TreeSet的实现，我们知道它使用了TreeMap... 在TreeSet.java文件中：

public boolean add(E var1) {
    return this.m.put(var1, PRESENT) == null;
}

不要展示TreeMap的整个put方法，这里是相关的搜索循环：

parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
        t = t.left;
else if (cmp > 0)
        t = t.right;
else
    return t.setValue(value);
} while (t != null);

所以如果cmp == 0，也就是说我们找到了一个重复的条目，则提前返回而不是在循环结束时添加一个子节点。调用setValue实际上并没有做任何事情，因为TreeSet在这里使用虚拟数据作为值，重要的是键不会改变。如果你研究HashMap，你会发现它也有相同的行为。

- Ben B

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- constantlearner · Accepted Answer

Java中的TreeSet、LinkedHashSet和HashSet是集合框架中的三种Set实现，与许多其他集合一样也用于存储对象。TreeSet的主要特点是排序，LinkedHashSet是插入顺序，而HashSet则是通用目的用于存储对象的集合。在Java中，HashSet使用HashMap进行实现，而TreeSet使用TreeMap进行实现。TreeSet是SortedSet的实现，在Comparable或Comparator接口定义的排序顺序下保持元素的排序顺序。Comparable用于自然排序，而Comparator用于自定义对象排序，这可以在创建TreeSet实例时提供。在看到TreeSet、LinkedHashSet和HashSet之间的区别之前，我们先来看看它们之间的一些相似之处：

1）重复项：所有三个实现Set接口，这意味着它们不允许存储重复项。

2）线程安全性：HashSet、TreeSet和LinkedHashSet不是线程安全的，如果您在多线程环境中使用它们，并且至少有一个线程修改了Set，则需要对它们进行外部同步。

3）Fail-Fast Iterator：TreeSet、LinkedHashSet和HashSet返回的迭代器都是快速失败迭代器。即，如果在迭代器创建后以任何方式修改迭代器，而不是通过Iterators remove()方法，则它将尽力抛出ConcurrentModificationException异常。在此处阅读有关fail-fast vs fail-safe Iterator的更多信息。

现在让我们看看Java中HashSet、LinkedHashSet和TreeSet之间的区别：

性能和速度：它们之间的第一个差异是速度。HashSet最快，LinkedHashSet在性能方面排名第二或几乎类似于HashSet，但TreeSet由于需要对每次插入执行排序操作而稍微慢一些。TreeSet为常见操作如添加、删除和包含提供了保证的O(log(n))时间，而HashSet和LinkedHashSet提供了恒定的时间性能，例如添加、包含和删除，只要哈希函数均匀地分布元素在桶中。

排序：HashSet不维护任何顺序，而LinkedHashSet维护元素的插入顺序，类似于List接口，而TreeSet维护元素的排序顺序。

内部实现：HashSet由HashMap实例支持，LinkedHashSet使用HashSet和LinkedList进行实现，而TreeSet由Java中的NavigableMap支持，并且默认情况下使用TreeMap。

null：HashSet和LinkedHashSet都允许null，但TreeSet不允许null，并且当您将null插入到TreeSet时会抛出java.lang.NullPointerException异常。由于TreeSet使用各自元素的compareTo()方法进行比较，当与null进行比较时会抛出NullPointerException异常，以下是示例：

TreeSet cities
Exception in thread "main" java.lang.NullPointerException
        at java.lang.String.compareTo(String.java:1167)
        at java.lang.String.compareTo(String.java:92)
        at java.util.TreeMap.put(TreeMap.java:545)
        at java.util.TreeSet.add(TreeSet.java:238)

HashSet和LinkedHashSet在Java中使用equals()方法进行比较，而TreeSet使用compareTo()方法来维护排序。因此，在Java中，compareTo()应该与equals保持一致。如果没有这样做，就会破坏Set接口的普遍约定，即它可能允许重复项。

您可以使用以下链接查看内部实现：http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashSet.java#HashSet.add%28java.lang.Object%29

From the source code 
Hashset hases Hashmap to store the data and LinkedHashSet extends Hashset and hence uses same add method of Hashset But TreeSet uses NavigableMap to store the data

来源：http://javarevisited.blogspot.com/2012/11/difference-between-treeset-hashset-vs-linkedhashset-java.html#ixzz2lGo6Y9mm