Java|风雨java路之【基础篇】——看看Set集合那点儿猫腻

一提java中的集合容器,第一时间会反应出Set、List、Map,下面这张图是学习马士兵J2SE时截的图,很直观反应出了这几种集合的关系。但不经意间发现,这张图其实是一张精简版的,还有一些,只不过是不常用罢了,而且没怎么细化。
Java|风雨java路之【基础篇】——看看Set集合那点儿猫腻
文章图片

这次只谈Set集合,看一下,Set有什么猫腻!
Java|风雨java路之【基础篇】——看看Set集合那点儿猫腻
文章图片

- HashSet:哈希表是通过使用称为散列法的机制来存储信息的,元素并没有以某种特定顺序来存放; - LinkedHashSet:以元素插入的顺序来维护集合的链接表,允许以插入的顺序在集合中迭代; - TreeSet:提供一个使用树结构存储Set接口的实现,对象以升序顺序存储,访问和遍历的时间很快。

HashSet
对于 HashSet 而言,它是基于 HashMap 实现的,HashSet 底层采用 HashMap 来保存所有元素,因此 HashSet 的实现比较简单,查看 HashSet 的源代码,可以看到如下代码:
public class HashSet extends AbstractSet implements Set, Cloneable, java.io.Serializable { // 使用 HashMap 的 key 保存 HashSet 中所有元素 private transient HashMap map; // 定义一个虚拟的 Object 对象作为 HashMap 的 value private static final Object PRESENT = new Object(); ... // 初始化 HashSet,底层会初始化一个 HashMap public HashSet() { map = new HashMap(); } // 以指定的 initialCapacity、loadFactor 创建 HashSet // 其实就是以相应的参数创建 HashMap public HashSet(int initialCapacity, float loadFactor) { map = new HashMap(initialCapacity, loadFactor); } public HashSet(int initialCapacity) { map = new HashMap(initialCapacity); } HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap(initialCapacity , loadFactor); } // 调用 map 的 keySet 来返回所有的 key public Iterator iterator() { return map.keySet().iterator(); } // 调用 HashMap 的 size() 方法返回 Entry 的数量,就得到该 Set 里元素的个数 public int size() { return map.size(); } // 调用 HashMap 的 isEmpty() 判断该 HashSet 是否为空, // 当 HashMap 为空时,对应的 HashSet 也为空 public boolean isEmpty() { return map.isEmpty(); } // 调用 HashMap 的 containsKey 判断是否包含指定 key //HashSet 的所有元素就是通过 HashMap 的 key 来保存的 public boolean contains(Object o) { return map.containsKey(o); } // 将指定元素放入 HashSet 中,也就是将该元素作为 key 放入 HashMap public boolean add(E e) { return map.put(e, PRESENT) == null; } // 调用 HashMap 的 remove 方法删除指定 Entry,也就删除了 HashSet 中对应的元素 public boolean remove(Object o) { return map.remove(o)==PRESENT; } // 调用 Map 的 clear 方法清空所有 Entry,也就清空了 HashSet 中所有元素 public void clear() { map.clear(); } ... }

由上面源程序可以看出,HashSet 的实现其实非常简单,它只是封装了一个 HashMap 对象来存储所有的集合元素,所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存,而 HashMap 的 value 则存储了一个 PRESENT,它是一个静态的 Object 对象。
HashSet 的绝大部分方法都是通过调用 HashMap 的方法来实现的,因此 HashSet 和 HashMap 两个集合在实现本质上是相同的。
LinkedHashSet
LinkedHashSet 是 HashSet 的子类,使用链表维护元素的次序,这使得元素看起来是以插入顺序保存的。看一下源码
public class LinkedHashSet extends HashSet implements Set, Cloneable, java.io.Serializable {public LinkedHashSet(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor, true); }public LinkedHashSet(int initialCapacity) { super(initialCapacity, .75f, true); }public LinkedHashSet() { super(16, .75f, true); }public LinkedHashSet(Collection c) { super(Math.max(2 * c.size(), 11), .75f, true); addAll(c); } }

LinkedHashSet继承自HashSet,HashSet基于HashMap实现,看LinkedHashSet类只是定义了四个构造方法,也没看到和链表相关的内容,为什么说LinkedHashSet内部使用链表维护元素的插入顺序(插入的顺序)呢?
【注意】这里的构造方法,都调用了父类HashSet的第五个构造方法:HashSet(int initialCapacity, float loadFactor, boolean dummy)。下面再给出这个构造方法的内容,看一下就应该明白为什么是基于链表。
HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap(initialCapacity, loadFactor); }

区别于其他的HashSet的构造方法,这个方法创建的是一个LinkedHashMap。LinkedHashMap继承自HashMap,同时自身有一个链表结构用于维护元素顺序,默认情况使用的是插入元素,所以LinkedHashSet既有HashSet的访问速度(因为访问的时候都是通过HashSet的方法访问的),同时可以维护顺序。
TreeSet
TreeSet 是一个有序的集合,它的作用是提供有序的Set集合。
public class TreeSet extends AbstractSetimplements NavigableSet, Cloneable, java.io.Serializable { // 使用 NavigableMap 的 key 来保存 Set 集合的元素 private transient NavigableMap m; // 使用一个 PRESENT 作为 Map 集合的所有 value。 private static final Object PRESENT = new Object(); // 包访问权限的构造器,以指定的 NavigableMap 对象创建 Set 集合 TreeSet(NavigableMap m) { this.m = m; } public TreeSet()// ① { // 以自然排序方式创建一个新的 TreeMap, // 根据该 TreeSet 创建一个 TreeSet, // 使用该 TreeMap 的 key 来保存 Set 集合的元素 this(new TreeMap()); } public TreeSet(Comparator comparator)// ② { // 以定制排序方式创建一个新的 TreeMap, // 根据该 TreeSet 创建一个 TreeSet, // 使用该 TreeMap 的 key 来保存 Set 集合的元素 this(new TreeMap(comparator)); } public TreeSet(Collection c) { // 调用①号构造器创建一个 TreeSet,底层以 TreeMap 保存集合元素 this(); // 向 TreeSet 中添加 Collection 集合 c 里的所有元素 addAll(c); } public TreeSet(SortedSet s) { // 调用②号构造器创建一个 TreeSet,底层以 TreeMap 保存集合元素 this(s.comparator()); // 向 TreeSet 中添加 SortedSet 集合 s 里的所有元素 addAll(s); } //TreeSet 的其他方法都只是直接调用 TreeMap 的方法来提供实现 ... public boolean addAll(Collection c) { if (m.size() == 0 && c.size() > 0 && c instanceof SortedSet && m instanceof TreeMap) { // 把 c 集合强制转换为 SortedSet 集合 SortedSet set = (SortedSet) c; // 把 m 集合强制转换为 TreeMap 集合 TreeMap map = (TreeMap) m; Comparator cc = (Comparator) set.comparator(); Comparator mc = map.comparator(); // 如果 cc 和 mc 两个 Comparator 相等 if (cc == mc || (cc != null && cc.equals(mc))) { // 把 Collection 中所有元素添加成 TreeMap 集合的 key map.addAllForTreeSet(set, PRESENT); return true; } } // 直接调用父类的 addAll() 方法来实现 return super.addAll(c); } ... }

从上面代码可以看出,TreeSet 的 ① 号、② 号构造器的都是新建一个 TreeMap 作为实际存储 Set 元素的容器,而另外 2 个构造器则分别依赖于 ① 号和 ② 号构造器,由此可见,TreeSet 底层实际使用的存储容器就是 TreeMap。
对于 TreeMap 而言,它采用一种被称为“红黑树”的自平衡二叉查找树来保存 Map 中每个 Entry —— 每个 Entry 都被当成“红黑树”的一个节点对待。(关于红黑树,后绪博客中将会有介绍)
总之:
似乎有Map和Set的地方,Set几乎都成了Map的一个马甲。此话怎讲呢?不管是HashSet,还是LinkedHashSet,亦或是TreeSet,我们发现他们的详细实现都是通过其相应的Map的来实现的。
最后来一个小demo,看一下直观效果:
/** * @description 几个set的比较 HashSet:哈希表是通过使用称为散列法的机制来存储信息的,元素并没有以某种特定顺序来存放; *LinkedHashSet:以元素插入的顺序来维护集合的链接表,允许以插入的顺序在集合中迭代; *TreeSet:提供一个使用树结构存储Set接口的实现,对象以升序顺序存储,访问和遍历的时间很快。 * @author 张连海 * */ public class SetDemo { public static void main(String[] args) { HashSet hs = new HashSet(); hs.add("B"); hs.add("A"); hs.add("D"); hs.add("E"); hs.add("C"); hs.add("F"); System.out.println("HashSet 顺序:\n" + hs + "\n"); LinkedHashSet lhs = new LinkedHashSet(); lhs.add("B"); lhs.add("A"); lhs.add("D"); lhs.add("E"); lhs.add("C"); lhs.add("F"); System.out.println("LinkedHashSet 顺序:\n" + lhs + "\n"); TreeSet ts = new TreeSet(); ts.add("B"); ts.add("A"); ts.add("D"); ts.add("E"); ts.add("C"); ts.add("F"); System.out.println("TreeSet 顺序:\n" + ts + "\n"); } }

【Java|风雨java路之【基础篇】——看看Set集合那点儿猫腻】输出效果:
Java|风雨java路之【基础篇】——看看Set集合那点儿猫腻
文章图片

    推荐阅读