17.6 Set和存储顺序

在第11章中的Set示例对可以用基本的Set执行的操作，提供了很好的介绍。但是那些示例很方便地使用了诸如Integer和String这样的Java预定义的类型，这些类型被设计为可以在容器内部使用。当你创建自己的类型时，要意识到Set需要一种方式来维护存储顺序，而存储顺序如何维护，则是在Set的不同实现之间会有所变化。因此，不同的Set实现不仅具有不同的行为，而且它们对于可以在特定的Set中放置的元素的类型也有不同的要求：

在HashSet上打星号表示，如果没有其他的限制，这就应该是你默认的选择，因为它对速度进行了优化。

定义hashCode()的机制将在本章稍后进行介绍。你必须为散列存储和树型存储都创建一个equals()方法，但是hashCode()只有在这个类将会被置于HashSet（这是有可能的，因为它通常是你的Set实现的首选）或者LinkedHashSet中时才是必需的。但是，对于良好的编程风格而言，你应该在覆盖equals()方法时，总是同时覆盖hashCode()方法。

下面的示例演示了为了成功地使用特定的Set实现类型而必须定义的方法：

为了证明哪些方法对于某种特定的Set是必需的，并且同时还要避免代码重复，我们创建了三个类。基类SetType只存储一个int，并且通过toString()方法产生它的值。因为所有在Set中存储的类都必须具有equals()方法，因此在基类中也有该方法。其等价性是基于这个int类型的i的值来确定的。

HashType继承自SetType，并且添加了hashCode()方法，该方法对于放置到Set的散列实现中的对象来说是必需的。

TreeType实现了Comparable接口，如果一个对象被用于任何种类的排序容器中，例如SortedSet（TreeSet是其唯一实现），那么它必须实现这个接口。注意，在compareTo()中，我没有使用“简洁明了”的形式return i-i2，因为这是一个常见的编程错误，它只有在i和i2都是无符号的int（如果Java确实有unsigned关键字的话，但实际上并没有）时才能正确工作。对于Java的有符号int，它就会出错，因为int不够大，不足以表现两个有符号int的差。例如i是很大的正整数，而j是很大的负整数，i-j就会溢出并且返回负值，这就不正确了。

你通常会希望compareTo()方法可以产生与equals()方法一致的自然排序。如果equals()对于某个特定比较产生true，那么compareTo()对于该比较应该返回0，如果equals()对于某个比较产生false，那么compareTo()对于该比较应该返回非0值。

在TypesForSets中，fill()和test()方法都是用泛型定义的，这是为了避免代码重复。为了验证某个Set的行为，test()会在被测Set上调用fill()三次，尝试着在其中引入重复对象。fill()方法可以接受任何类型的Set，以及其相同类型Class对象，它使用Class对象来发现并接受int参数的构造器，然后调用该构造器将元素添加到Set中。

从输出中可以看到，HashSet以某种神秘的顺序保存所有的元素（这将在本章稍后进行解释），LinkedHashSet按照元素插入的顺序保存元素，而TreeSet按照排序顺序维护元素（按照compareTo()的实现方式，这里维护的是降序）。

如果我们尝试着将没有恰当地支持必需的操作的类型用于需要这些方法的Set，那么就会有大麻烦了。对于没有重新定义hashCode()方法的SetType或TreeType，如果将它们放置到任何散列实现中都会产生重复值，这样就违反了Set的基本契约。这相当烦人，因为这甚至不会有运行时错误。但是，默认的hashCode()是合法的，因此这是合法的行为，即便它不正确。确保这种程序的正确性的唯一可靠方法就是将单元测试合并到你的构建系统中（请查看http://MindView. net/Books/BetterJava处的补充材料以了结更多的信息）。

如果我们尝试着在TreeSet中使用没有实现Comparable的类型，那么你将会得到更确定的结果：在TreeSet试图将该对象当作Comparable使用时，将抛出一个异常。

17.6.1 SortedSet

SortedSet中的元素可以保证处于排序状态，这使得它可以通过在SortedSet接口中的下列方法提供附加的功能：Comparator comparator()返回当前Set使用的Comparator；或者返回null，表示以自然方式排序。

Object first() 返回容器中的第一个元素。

Object last() 返回容器中的最末一个元素。

SortedSet subSet(fromElement, toElement) 生成此Set的子集，范围从fromElement（包含）到toElement（不包含）。

SortedSet headSet(toElement) 生成此Set的子集，由小于toElement的元素组成。

SortedSet tailSet(fromElement) 生成此Set的子集，由大于或等于fromElement的元素组成。

下面是一个简单的示例：