HashSet vs TreeSet vs LinkedHashSet基于添加重复值
我正在学习核心java的核心，即Collections 。我想知道当我们在HashSet ， TreeSet ， LinkedHashSet添加重复元素时，内部会发生什么。
天气条目被替换，忽略或抛出exception并且程序终止 。 一个子问题是， 哪一个操作具有相同或平均时间复杂度
非常感谢您的回复。
Java中的TreeSet，LinkedHashSet和HashSet是集合框架中的三个Set实现，与许多其他实现一样，它们也用于存储对象。 TreeSet的主要特征是排序，LinkedHashSet是插入顺序，HashSet只是用于存储对象的通用集合。 HashSet是使用Java中的HashMap实现的，而TreeSet是使用TreeMap实现的。 TreeSet是一个SortedSet实现，它允许它按照Comparable或Comparator接口定义的排序顺序保留元素。 Comparable用于自然顺序排序和Comparator，用于对象的自定义顺序排序，可以在创建TreeSet实例时提供。 无论如何在看到TreeSet，LinkedHashSet和HashSet之间的区别之前，让我们看看它们之间有一些相似之处：
1）重复：所有三个实现Set接口意味着它们不允许存储重复项。
2）线程安全：HashSet，TreeSet和LinkedHashSet不是线程安全的，如果在multithreading环境中使用它们，其中至少有一个线程修改了Set，你需要在外部同步它们。
3）Fail-Fast Iterator：TreeSet，LinkedHashSet和HashSet返回的迭代器是故障快速迭代器。 即如果Iterator在创建之后通过除Iterators remove（）方法以外的任何方式进行修改，它将尽最大努力抛出ConcurrentModificationException。 在此处阅读有关故障快速与故障安全迭代器的更多信息
现在让我们看看Java中的HashSet，LinkedHashSet和TreeSet之间的区别：
性能和速度：它们之间的第一个区别在于速度。 HashSet是最快的，LinkedHashSet在性能上排名第二或几乎与HashSet类似，但TreeSet因为每次插入时需要执行的排序操作而有点慢。 TreeSet为诸如add，remove和contains之类的常见操作提供了保证的O（log（n））时间，而HashSet和LinkedHashSet提供了恒定的时间性能，例如O（1）用于add，包含和删除给定的散列函数，在bucket中均匀分布元素。
排序：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（）方法来维护排序。 这就是为什么compareTo（）应该与Java中的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
这张图片可以帮到你……
图片来源： http ： //javaconceptoftheday.com/hashset-vs-linkedhashset-vs-treeset-in-java/
我没有找到关于这些差异的大量硬数据，因此我针对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- 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
- comparator() { return Comparator.comparing(Item::getName, Comparator.naturalOrder()) .thenComparing(Item::getId, Comparator.naturalOrder()); } } }
tldr：这些集合忽略重复值。
我没有看到问题的粗体部分的完整答案，重复出现了什么？ 它会覆盖旧对象还是忽略新对象？ 考虑一个对象的示例，其中一个字段确定相等但有额外的数据可能会有所不同：
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); } }
此unit testing显示所有3个集合都忽略重复值：
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 testSet; public SetRepeatedItemTest(Set testSet) { this.testSet = testSet; } @Parameterized.Parameters public static Collection 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，你会看到相同的行为。