java 以自然顺序在集合中存储唯一元素

To store unique element in a collection with natural order

提问by St.Antario

While I was solving a Java test I came up with the following question:

在解决 Java 测试时，我提出了以下问题：

You need to store elements in a collection that guarantees that no duplicates are stored and all elements can be accessed in natural order. Which interface provides that capability?

您需要将元素存储在一个集合中，以保证不会存储重复项，并且可以按自然顺序访问所有元素。哪个接口提供了这种能力？

A. java.util.Map
B. java.util.Set
C. java.util.List
D. java.util.Collection

I have no idea what is the right case here? We can store the same element in any of these collections unless in a Set, but the Setdoesn't provide the natural order. What's wrong?

我不知道这里的正确情况是什么？我们可以在这些集合中的任何一个中存储相同的元素，除非在 a 中Set，但Set不提供自然顺序。怎么了？

回答by Eran

TreeSet would give you ordering (either natural ordering by default of custom ordering via a Comparator).

TreeSet 将为您提供排序（默认情况下通过比较器进行自定义排序的自然排序）。

To be more general, SortedSetis the more general interface that offers uniqueness and ordering.

更通用地说，SortedSet是提供唯一性和排序的更通用的接口。

A Set that further provides a total ordering on its elements. The elements are ordered using their natural ordering, or by a Comparator typically provided at sorted set creation time. The set's iterator will traverse the set in ascending element order. Several additional operations are provided to take advantage of the ordering.

进一步提供其元素的总排序的 Set。元素使用它们的自然顺序进行排序，或者通过通常在排序集创建时提供的 Comparator 进行排序。集合的迭代器将按元素升序遍历集合。提供了几个额外的操作来利用排序。

回答by Makoto

The correct answer for that test is SetLet's remember that it's asking for an interface that could provide that; given the right implementation, the Setinterface could provide it.

该测试的正确答案是Set让我们记住它要求提供一个接口；给定正确的实现，Set接口可以提供它。

• The Mapinterface doesn't make any guarantees around what order things are stored, as that's implementation specific. However, if you use the rightimplementation (that is, TreeMapas spelled out by the docs), then you're guaranteed a natural ordering and no duplicate entries.

  However, there's no requirement about key-value pairs.

• The Setinterface also doesn't make any guarantees around what order things are stored in, as that's implementation specific. But, like TreeMap, TreeSetis a set that can be used to store things in a natural order with no duplicates.

  Here's how it'd look.

  Set<String> values = new TreeSet<>();
  

• The Listinterface will definitely allow duplicates, which instantly rules it out.

• The Collectioninterface doesn't have anything directlyimplementing it, but it is the patriarch of the entire collections hierarchy. So, in theory, code like this is legal:

  Collection<String> values = new TreeSet<>();
  

  ...but you'd lose information about what kind of collection it actually was, so I'd discourage its usage.

• 该Map接口不对事物的存储顺序做出任何保证，因为这是特定于实现的。但是，如果您使用正确的实现（即，TreeMap如文档所述），那么您可以保证自然排序并且没有重复条目。

  但是，没有关于键值对的要求。

• 该Set接口也不对事物的存储顺序做出任何保证，因为这是特定于实现的。但是，就像TreeMap，TreeSet是一个可以用来以自然顺序存储事物而没有重复的集合。

  这是它的外观。

  Set<String> values = new TreeSet<>();
  

• 该List界面肯定会允许重复，这会立即排除它。

• 该Collection接口没有任何直接实现它的东西，但它是整个集合层次结构的元老。所以，理论上，这样的代码是合法的：

  Collection<String> values = new TreeSet<>();
  

  ...但是你会丢失关于它实际上是什么类型的集合的信息，所以我不鼓励它的使用。

回答by mavarazy

If by natural order, you mean order of insertion, then LinkedHashSetis your go to Set implementation.

如果按自然顺序，您的意思是插入顺序，那么LinkedHashSet是您的 Set 实现。

The correct answers are: SortedSetgives guarantees, regarding natural order of elements. TreeSetis typical implementation

正确答案是： SortedSet提供关于元素自然顺序的保证。 TreeSet是典型的实现

回答by amit

Strictly speaking, when choosing from the above Listis the only of the interfaces that has a defined order of iteration, however it does allow duplicates.

严格来说，当从上面选择时，List是唯一具有定义迭代顺序的接口，但它确实允许重复。

Setand Mapon the other hands, does not allow duplicates (of keys for Map), but they also do not define the order of iteration, they are unordered by default, with HashSet/HashMapbeing the counter example.

Set而Map在其他的手，不允许重复（键的Map），但他们也没有定义迭代的顺序，它们是无序的默认情况下，用HashSet/HashMap作为反例。

Collectionallows none.

Collection不允许。

So, strictly speaking - none of the suggested interfaces provide the desired capability, However, as others suggested, there are specific implementations of the interfaces that do allow natural order of elements and no duplicates, mainly the SortedSetinterface and its TreeSetimplementation

因此，严格来说 - 建议的接口都没有提供所需的功能，但是，正如其他人所建议的那样，接口的特定实现确实允许元素的自然顺序并且没有重复，主要是SortedSet接口及其TreeSet实现

---

---

To further elaborate why Setis not a good option, if you have a variable, let it be mySet, and you want it to be ordered, users are going to be surprised when you use the Setinterface, imaigine the following code:

为了进一步阐述为什么Set不是一个好的选择，如果你有一个变量，让它成为mySet，并且你希望它被排序，当你使用Set界面时，用户会感到惊讶，想象一下以下代码：

public int processMyDataStructure(Set set) {
   //some calculation that assumes set is ordered
   return result;
}

and users provide you a HashSetas argument - you are going to get a wrong behavior from your method, because Setdoes not guarantee ordering. To avoid it you should have asked for an SortedSetrather than Set.

并且用户为您提供一个HashSet作为参数 - 您将从您的方法中得到错误的行为，因为Set不保证排序。为了避免它，你应该要求一个SortedSet而不是Set。

回答by Marcin Szawurski

I've come over this question yesterday on my interview test and need to comment on that: the question (assuming one of the listed A, B, C or D answers has to be correct) is plainly wrong. There is no correct answer listed.

我昨天在面试中遇到了这个问题，需要对此发表评论：这个问题（假设列出的 A、B、C 或 D 答案之一必须是正确的）显然是错误的。没有列出正确答案。

Nothing in Setinterface guarantees the order in which the elements are to be returned. And there is no such thing, as Makotowould like it in his accepted answer, as right implementationthat could theoretically do the job, because we are not asked for any implementation here, but whether interfaceprovides the requested capability.

Set接口中的任何内容都不能保证元素返回的顺序。并且没有这样的事情，正如Makoto在他接受的答案中所希望的那样，作为理论上可以完成这项工作的正确实现，因为这里没有要求我们提供任何实现，但是接口是否提供了请求的功能。

So, the test question with the answers provided is misguided.

因此，提供答案的测试问题是错误的。

Referring a bit more to accepted answer, there is one more reason for it to be wrong. Specifically, Makotoargues, that The List interface will definitely allow duplicates, which instantly rules it out.This argument may be defied by citation from Listspecification saying:

多参考已接受的答案，还有一个原因是错误的。具体来说，Makoto认为，List 接口肯定会允许重复，这会立即排除它。这个论点可能会被List规范中的引用所推翻：

It is not inconceivable that someone might wish to implement a list that prohibits duplicates, by throwing runtime exceptions when the user attempts to insert them, but we expect this usage to be rare

有人可能希望通过在用户尝试插入它们时抛出运行时异常来实现一个禁止重复的列表，这并非不可想象，但我们希望这种用法很少见

so in my opinion, any of the answers given is equally wrong, or, as accepted answerwants it, equally correct, as we are free to write implementation of List (or Map, or Collection) behaving in any way we wish (in boundaries set by an interface specification), but interfaces and their specifications are here to guaranteesome contract, and this question is really about them, not about possible implementations.

所以在我看来，给出的任何答案都同样是错误的，或者，正如公认的答案所希望的那样，同样正确，因为我们可以自由地编写 List（或 Map 或 Collection）的实现，以我们希望的任何方式（在边界内）表现由接口规范设置），但是接口及其规范在这里是为了保证某种契约，这个问题实际上是关于它们的，而不是关于可能的实现。