Java容器学习笔记(二)Set接口及其实现类相关知识总结

　Java 容器学习笔记（二）

　Set 接口及其实现类的相关知识总结 分类：

　Java 学习 实习笔记 2011-10-21 00:54 652 人阅读 评论(4) 收藏 举报 在 Java 容器学习笔记（一）中概述了 Collection 的基本概念及接口实现，并且总结了它的一个重要子接口 List 及其子类的实现和用法。

　本篇主要总结 Set 接口及其实现类的用法，包括 HashSet（无序不重复），LinkedHashSet（按放入顺序有序不重复），TreeSet （按红黑树方式有序不重复），EnumSet，ConcurrentSkipListSet（来自于 java.util.concurrent 包），CopyOnWriteArraySet（来自于 java.util.concurrent 包）等。

　2.

　 Set 接口及其实现类 Set 接口中方法清单：

　 Set 集合和 List 集合都存放的是单个元素的序列，但是 Set 集合不允许集合中有重复元素（主要依赖于 equals 方法）。

　Set 接口的父接口为 Collection 和 Iterable，直接实现该接口的子接口有 SortedSet 和NavigableSet。

　实现 Set 接口的重要类有 HashSet（无序不重复），LinkedHashSet（按放入顺序有序不重复），TreeSet（按红黑树方式有序不重复），EnumSet，ConcurrentSkipListSet（来自于java.util.concurrent 包），CopyOnWriteArraySet（来自于 java.util.concurrent 包）。

　在 Set 接口中没有新增任何方法，所有方法均来自其父接口。它无法提供像 List 中按位存取的方法。在数学上一个集合有三个性质：确定性，互异性，无序性。

　Ø

　HashSet 的特点、实现机制及使用方法 a)

　HashSet 的特点：

　HashSet 中存放的元素是无序的，底层是用 HashMap 实现的，其中 key 是要放入的元素，value是一个 Object 类型的名为 PRESENT 的常量，由于用到了散列函数，因此其存取速度是非常快的，在地址空间很大的情况下它的存取速度可以达到 O(1)级。如果首先了解了 HashMap 的实现方法，那么 HashSet 的实现是非常简单的。

　b）HashSet 的实现机制：

　首先需要了解一下散列或者哈希的用法。我们知道，当数据量很大时 hash 函数计算的结果将会重复，按照下图所示的形式进行存贮。

　 在 HashSet 中有个 loadFactor（负载因子），对于上图所示总共有 11 个位置，目前有 4 个位置已经存放，即 40%的空间已被使用。

　在 HashSet 的默认实现中，初始容量为 16，负载因子为 0.75，也就是说当有 75%的空间已被使用，将会进行一次再散列（再哈希），之前的散列表（数组）将被删除，新增加的散列表是之前散列表长度的 2 倍，最大值为 Integer.MAX_VALUE。

　负载因子越高，内存使用率越大，元素的寻找时间越长。

　负载因子越低，内存使用率越小，元素的寻找时间越短。

　从上图可以看出，当哈希值相同时，将存放在同一个位置，使用链表方式依次链接下去。

　（面试官问到这个问题，当时我的回答是再哈希，其实我并不知道 HashSet 真正是怎么实现的，我只知道在学习数据结构时学习过再哈希，就是这个哈希表很满时需要重新建立哈希表，以便于存取，因为大量的值放在一个位置上就变成了链表的查询了，几乎是 O(n/2)级别的，但是我没有说出来再哈希的过程，以及哈希值相同时到底如何存放，所以……~~o(>_<)o ~~）。

　为了说明 HashSet 在 Java 中确实如上实现，下面附上 JDK 中两个重要方法的源码：（下面源码来自于 HashMap，原因是 HashSet 是基于 HashMap 实现的）

　view plainprint? 1. /**

　2.

　* Rehashes the contents of this map into a new array with a

　3.

　* larger capacity.

　This method is called automatically when the

　4.

　* number of keys in this map reaches its threshold.

　5.

　*

　6.

　* If current capacity is MAXIMUM_CAPACITY, this method does not

　7.

　* resize the map, but sets threshold to Integer.MAX_VALUE.

　8.

　* This has the effect of preventing future calls.

　9.

　*

　10.

　* @param newCapacity the new capacity, MUST be a power of two;

　11.

　*

　must be greater than current capacity unless current

　12.

　*

　capacity is MAXIMUM_CAPACITY (in which case value

　13.

　*

　is irrelevant).

　14.

　*/

　 15.

　 void resize(int newCapacity) {

　 16.

　 Entry[] oldTable = table;

　 17.

　 int oldCapacity = oldTable.length;

　 18.

　 if (oldCapacity == MAXIMUM_CAPACITY) {

　 19.

　 threshold = Integer.MAX_VALUE;

　 20.

　 return;

　 21.

　 }

　 22.

　23.

　 Entry[] newTable = new Entry[newCapacity];

　 24.

　 transfer(newTable);

　 25.

　 table = newTable;

　 26.

　 threshold = (int)(newCapacity * loadFactor);

　 27.

　 }

　 28.

　29.

　 /**

　30.

　* Transfers all entries from current table to newTable.

　31.

　*/

　 32.

　 void transfer(Entry[] newTable) {

　 33.

　 Entry[] src = table;

　 34.

　 int newCapacity = newTable.length;

　 35.

　 for (int j = 0; j < src.length; j++) {

　 36.

　 Entry<K,V> e = src[j];

　 37.

　 if (e != null) {

　 38.

　 src[j] = null;

　 39.

　 do {

　 40.

　 Entry<K,V> next = e.next;

　 41.

　 int i = indexFor(e.hash, newCapacity);

　 42.

　 e.next = newTable[i];

　 43.

　 newTable[i] = e;

　 44.

　 e = next;

　 45.

　 } while (e != null);

　46.

　 }

　 47.

　 }

　 48.

　 }

　 HashSet 共实现了 5 个构造方法，对外提供了 4 个构造方法。这些方法在 api 中均可看到详细使用说明。由于 HashSet 基于 HashMap 实现，我们只关心我们放入的 key，value 是个 Object类型的常量，所以在 iterator 方法中使用的是 HashMap 的 keySet 方法进行迭代的。

　c）HashSet 的使用方法：

　从 HashSet 的特点及实现上看，我们知道在不需要放入重复数据并且不关心放入顺序以及元素是否要求有序的情况下，我们没有任何理由不选择使用 HashSet。另外 HashSet 是允许放空值的。

　那么 HashSet 是如何保证不重复的？下面一个例子说明：

　view plainprint? 1. import java.util.HashSet;

　 2. import java.util.Iterator;

　 3. public class ExampleForHashSet {

　 4.

　 public static void main(String[] args) {

　 5.

　 HashSet<Name> hs = new HashSet<Name>();

　 6.

　 hs.add(new Name("Wang", "wu"));

　 7.

　 hs.add(new Name("Zhang", "san"));

　 8.

　 hs.add(new Name("Wang", "san"));

　 9.

　 hs.add(new Name("Zhang", "wu"));

　 10.

　 //本句输出为 2

　 11.

　 System.out.println(hs.size());

　 12.

　 Iterator<Name> it = hs.iterator();

　 13.

　 //下面输出两行，分别为 Zhang:san 和 Wang:wu

　 14.

　 while(it.hasNext()) {

　 15.

　 System.out.println(it.next());

　 16.

　 }

　 17.

　 }

　 18. }

　 19. class Name {

　 20.

　 String first;

　 21.

　 String last;

　 22.

　 public Name(String first, String last) {

　 23.

　 this.first = first;

　 24.

　 this.last = last;

　 25.

　 }

　 26.

　 @Override

　 27.

　 public boolean equals(Object o) {

　 28.

　 if(null == o) {

　 29.

　 return false;

　30.

　 }

　 31.

　 if(this == o) {

　 32.

　 return true;

　 33.

　 }

　 34.

　 if(o instanceof Name) {

　 35.

　 Name name = (Name)o;

　 36.

　 //本例认为只要 first 相同即相等

　 37.

　 if(this.first.equals(name.first)) {

　 38.

　 return true;

　 39.

　 }

　 40.

　 }

　 41.

　 return false;

　 42.

　 }

　 43.

　 @Override

　 44.

　 public int hashCode() {

　 45.

　 int prime = 31;

　 46.

　 int result = 1;

　 47.

　 //hashcode 的实现一定要和 equals 方法的实现对应

　 48.

　 return prime*result + first.hashCode();

　 49.

　 }

　 50.

　 @Override

　 51.

　 public String toString() {

　 52.

　 return first + ":" + last;

　 53.

　 }

　 54. }

　 简单说明一下上面的例子：

　上面已经提到 HashSet 里面放的元素是不允许重复的，那么什么样的元素是重复呢，重复的定义是什么？

　上面例子中实现了一个简单的类 Name 类，并且重写了 equals 方法与 hashCode 方法，那么重复指的是 equals 方法吗？equals 相同就算是重复吗？当然不是这样的。如果我们改写一下hashCode 方法，将返回值改为

　 return prime*result + first.hashCode() + last.hashCode()

　那么 HashSet 中的 size 会变为 4，但是 Name(“Wang”, “wu”)和 Name(“Wang”, “san”)其实用equals 方法来比较的话其实是相同的。

　 Name n1 = new Name("W", "x");

　Name n2 = new Name("W", "y");

　System.out.println(n1.equals(n2));

　也就是说上面代码会输出 true。

　这样我们是不是可以这样认为：如果 hashCode 相同的话再判断 equals 的返回值是否为 true，如果为 true 则相同，即上面说的重复。如果 hashCode 不同那么一定是不重复的？

　由此看来 equals 相同，hashCode 不一定相同，equals 和 hashCode 的返回值不是绝对关联的？当然我们实现 equals 方法时是要根据 hashCode 方法实现的，必须建立关联关系，也就是说正常情况下 equals 相同，则 hashCode 的返回值应该是相同的。

　Ø

　LinkedHashSet 的特点、实现机制及使用方法 a)

　LinkedHashSet 的特点：

　LinkedHashSet 保证了按照插入顺序有序，继承自 HashSet，没有实现新的可以使用的方法。

　b)

　LinkedHashSet 实现机制：

　LinkedHashSet 继承自 HashSet，构造时使用了在 HashSet 中被忽略的构造方法：

　view plainprint? 1. /**

　2.

　 * Constructs a new, empty linked hash set.

　(This package private

　3.

　 * constructor is only used by LinkedHashSet.) The backing

　4.

　 * HashMap instance is a LinkedHashMap with the specified initial

　5.

　 * capacity and the specified load factor.

　6.

　 *

　7.

　 * @param

　initialCapacity

　 the initial capacity of the hash map

　8.

　 * @param

　loadFactor

　the load factor of the hash map

　9.

　 * @param

　dummy

　 ignored (distinguishes this

　10.

　 *

　 constructor from other int, float constructor.)

　11.

　 * @throws

　 IllegalArgumentException if the initial capacity is less

　12.

　 *

　 than zero, or if the load factor is nonpositive

　13.

　 */

　 14. HashSet(int initialCapacity, float loadFactor, boolean dummy) {

　 15.

　 map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);

　 16. }

　 由上面 JDK 代码可以看出 LinkedHashSet 底层是使用 LinkedHashMap 实现的。

　所以在实现上是比较简单的，是根据 dummy 这个参数，我们不需要传入，选择构造的是 HashSet还是 LinkedHashSet。

　c)

　LinkedHashSet 的使用方法：

　由于 LinkedHashSet 继承自 HashSet，并且没有提供额外的供使用的方法，所以在使用时与HashSet 基本相同，只是面临的是选择的问题。我们根据需要选择不同的数据结构来实现我们的需求。

　Ø

　CopyOnWriteArraySet 的特点、实现机制及使用方法 a)

　CopyOnWriteArraySet 的特点：

　CopyOnWriteArraySet 是 java.util.concurrent 包中的一个类，继承自 AbstractSet，底层使用CopyOnWriteArrayList 实现，拥有 Set 的特点，也具有 ArrayList 的特点，并且是线程安全的类。

　b)

　CopyOnWriteArraySet 的实现机制：

　在实现时使用了写时拷贝的方法以及使用重入锁实现了线程的同步，底层使用CopyOnWriteArrayList 来构造出一个实例对象，在添加元素时调用 CopyOnWriteArrayList 的addIfAbsent 方法保证数据不重复，其它实现与 CopyOnWriteArrayList 类似。

　c)

　CopyOnWriteArraySet 的使用方法：

　这仍然面临的是一个选择的问题，HashSet 底层也是使用数组实现的，它的优点是存取效率很高，当负载因子很小时，几乎可以达到 O(1)级的存取速度，但是它不是线程安全的。当我们需要在多线程并发环境下使用时可以考虑使用这个类，当然为了实现线程安全，这不是一个唯一的方法。

　Ø

　TreeSet 的特点、实现机制及使用方法 a)

　TreeSet 的特点：

　TreeSet 中所放的元素是有序的，并且元素是不能重复的。

　b)

　TreeSet 的实现机制：

　TreeSet 是如何保持元素的有序不重复的？

　首先 TreeSet 底层使用 TreeMap 实现，和 HashSet 一样，将每个要放入的元素放到 ...