0

今天面试官问我：Set如何保证不重复？

4

3 回答 3

2

答案在于add方法的源代码。例如在源代码中TreeSetadd 方法的实现如下：

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

其中，PRESENT是Object类的对象。并且m是 的对象NavigableMap。这NavigableMap m用于将元素存储e为给定的key key 。因此，每个键都有相同的对象。oracle doc中定义的方法是：PRESENTvalueemPRESENTputMap

将指定的值与此映射中的指定键相关联。如果映射先前包含键的映射，则替换旧值。
...
...
返回：与 key 关联的前一个值，如果没有 key 的映射，则返回 null。（返回 null 还可以指示映射先前将 null 与 key 关联。）

因此，当您将重复元素放入 set 时，此元素将放入NavigableMap带有 value 的 as 键中PRESENT。如果此键不存在，NavigableMap则put方法返回null并因此 m.put(e,PRESENT)==null返回 true 并且我们知道该元素已添加。如果该键已经存在于NavigableMapthen方法中，则使用 PRESENTput覆盖valuefor the inside 并返回旧值（即 PRESENT）并因此 返回，我们知道该元素未添加。key eNavigableMapm.put(e,PRESENT)==nullfalse

于 2013-07-02T18:22:10.633 回答
1

Set 是一种抽象数据类型，可以通过多种方式实现。就其本身而言，它是合同的规范；因此，它不保证任何事情。由接口的实现来保证合同的履行。

因此，看看这些实现如何以及为什么工作会更有趣。一些常见的实现是：

  • 哈希表，在 Java 中由HashSet
  • 平衡树，在 Java 中实现TreeSet
  • 位集（用于特殊类型），在 Java 中由EnumSetand实现BitSet
  • 跳过列表，由ConcurrentSkipListSet
  • 朴素数组：在添加元素之前扫描数组；不经常使用。在Java中实现为CopyOnWriteArraySet

在一次工作面试中，您会回答上述问题，并愿意解释任何一种实现的细节。面试官应该已经知道其中的一些，除非被问到，否则开始漫无边际地谈论它们对你没有好处。

于 2013-07-02T18:06:04.647 回答
1

从规范的角度来看，它是通过例如指定add如果您尝试添加重复项时该方法必须执行的操作来实现的。该add方法的文档说明了这一点，例如：

如果指定元素尚不存在，则将其添加到此集合中（可选操作）。更正式地说，如果集合不包含元素 e2，则将指定的元素 e 添加到此集合中，使得 (e==null ? e2==null : e.equals(e2))。如果该集合已包含该元素，则调用将保持该集合不变并返回 false。结合对构造函数的限制，这确保了集合永远不会包含重复的元素。

从同一页面（http://docs.oracle.com/javase/6/docs/api/java/util/Set.html）：

毫不奇怪，对构造函数的附加规定是，所有构造函数都必须创建一个不包含重复元素的集合（如上所述）。

（为了完整起见，还有关于equals并hashCode确保Set正确建模集合抽象的规定。）

于 2013-07-02T18:07:48.013 回答