java 集合如何在内部避免重复？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15062322/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How sets avoid duplicates internally?
提问by Kosuri Naresh
I had a doubt about the set in Collections framework. How the set itself will identify duplicates and how it will come to know? Could anyone please explain how it is implemented? How hashcode and equals method will come into the picture? I need a brief explanation as it is really important for me.
我对集合框架中的集合有疑问。集合本身将如何识别重复项以及如何知道？谁能解释一下它是如何实施的？hashcode 和 equals 方法将如何出现？我需要一个简短的解释，因为这对我来说真的很重要。
回答by Karthik T
It roughly works like this
它大致是这样工作的
if (!collection.contains(element))
collection.add(element);
And the contains method, would use equals/hashcode.
和 contains 方法，将使用 equals/hashcode。
In TreeSet, the elements are stored in a Red-Black Tree, whereas HashSet, uses a HashMap.
在 TreeSet 中，元素存储在红黑树中，而 HashSet 使用 HashMap。
Infact, the way it is added to the container is specific to the element (the spot on the tree, bucket in the hashtable), thus the adding itself uses equals/hashcode.
事实上，它被添加到容器的方式是特定于元素的（树上的位置，哈希表中的桶），因此添加本身使用 equals/hashcode。
回答by Daniel Kaplan
This is explained in the javadoc for Set.
这在javadoc for中进行了解释。Set
A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element.
不包含重复元素的集合。更正式地说，集合不包含一对元素 e1 和 e2，使得 e1.equals(e2)，并且最多包含一个空元素。
回答by Javier
The actual implementation depends on the container. HashMaplookup the item bucked given its hashCodethen test the inserted object and the stored ones by using equals(this is one of the reasons for requiring that a.equals(b)iff b.equals(a)).
实际的实现取决于容器。HashMap查找 bucked 的项目，hashCode然后使用 using 测试插入的对象和存储的对象equals（这是需要a.equals(b)iff的原因之一b.equals(a)）。
TreeMap, on the other hand, relies on the result of the compareTomethod (if the element implements Comparableor the comparemethod implemented by a Comparator). If comparereturns 0, the elements are regarded as "equals". (Note that compareToshould be consistent with equals, i.e. a.compareTo(b)==0iff a.equals(b)).
TreeMap，另一方面，依赖于compareTo方法的结果（如果元素实现Comparable或compare由 a实现的方法Comparator）。如果compare返回 0，则元素被视为“等于”。（注意compareTo应与 equals 一致，即a.compareTo(b)==0iff a.equals(b)）。
回答by Jigar Joshi
HashSetuses hashcode()toresolve bucket where object should go and equals()method to check equality on objects lying on that bucket
HashSet使用hashcode()toresolve 对象应该去的桶和equals()方法来检查位于该桶上的对象的相等性
回答by Eswaran Venkatesan
"Can u please explain with these example. s.add("123");s.add("123");"
“请你用这些例子解释一下。s.add("123");s.add("123");"
For the above query explained in context with Set interface, Please refer to the below snippet and explanation.
对于在 Set 接口上下文中解释的上述查询，请参阅以下片段和解释。
public void setTest() {
Set<String> obj = new HashSet<>();
System.out.println(obj.add("123")); //Output : true
System.out.println(obj.add("123")); //Output : false
}
If you notice in the above snippet, we have added 123 two times. for the first time add SOP will return true. then for the second time of added "123", SOP will return false.
如果您在上面的代码段中注意到，我们已经两次添加了 123。第一次添加 SOP 将返回 true。然后第二次添加“123”，SOP将返回false。
With this we can understand that, if we add same value in the Set for the second time or more, then the duplicated value will be skipped.
由此我们可以理解，如果我们在 Set 中第二次或更多次添加相同的值，那么重复的值将被跳过。
回答by Samarth Narula
Basically set is an interface which has many different implementations, let's take HashSet implementation for now, to answer you question, I downloaded the source code and went inside the HashSet class, then I searched add method and saw that it uses HashMap to store unique values. It uses the value to be stored as key of a HashMap and the corresponding value of key (i.e PRESENT in below code snippet) as a constant value(this value is a dummy value), we all know that keys of map are unique. So that is how it works. Code below:
基本上 set 是一个有很多不同实现的接口，现在让我们以 HashSet 实现来回答你的问题，我下载了源代码并进入了 HashSet 类，然后我搜索了 add 方法，看到它使用 HashMap 来存储唯一值. 它使用要存储的值作为 HashMap 的键和键的对应值（即下面代码片段中的 PRESENT）作为常量值（该值是一个虚拟值），我们都知道映射的键是唯一的。这就是它的工作原理。代码如下：
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
