转载

Java集合框架分析(五)-HashSet分析

本篇文章主要分析一下Java集合框架中的Set部分，HashSet，该源码分析基于JDK1.8，分析工具，AndroidStudio，文章分析不足之处，还请指正！

HashSet简介

类结构

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
复制代码

HashSet是一个没有重复元素的集合。它是由HashMap实现的，不保证元素的顺序，而且 HashSet允许使用 null 元素。HashSet是非同步的。和List接口一样，HashSet也是先继承了AbstractSet同时实现了Set接口，实现了Cloneable接口，即覆盖了函数clone()，能克隆。实现java.io.Serializable接口，这意味着HashSet支持序列化，能通过序列化去传输。

属性

接下来我们详细分析一下HashSet相关源码。首先我们来看下它的属性。

static final long serialVersionUID = -5024744406713321676L;
// 底层使用HashMap来保存HashSet的元素
   private transient HashMap<E,Object> map;
   // 由于Set只使用到了HashMap的key，所以此处定义一个静态的常量Object类，来充当HashMap的value
   private static final Object PRESENT = new Object();
复制代码

是不是很奇怪？HashSet的内部竟然使用了HashMap的数据的数据结构，这就有点意思了，我们都知道Set这种数据结构是不允许有重复的存在的，接下来我们就一探究竟，看看到底如何实现不重复操作的。

构造器

public HashSet() {
       map = new HashMap<>();
   }
    
   public HashSet(Collection<? extends E> c) {
       map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
       addAll(c);
   }
    
   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);
   }
复制代码

上面便是HashSet的构造器，非常简单，由于底层是使用了HashMap的数据结构，所以它的构造器就是初始化HashMap的代码，只有最后一个构造方法有写区别，这里构造的是LinkedHashMap，该方法不对外公开，实际上是提供给LinkedHashSet使用的，而第三个参数dummy是无意义的，只是为了区分其他构造方法。

其他方法

我们分下一下HashSet的添加add方法。

public boolean add(E e) {
       return map.put(e, PRESENT)==null;
   }
复制代码

看到了什么？非常简单，就是HashMap的put方法，但是发现没有，它的value是PRESENT，是我们一开始申明的Object对象。

private static final Object PRESENT = new Object();
复制代码

在这里我们就需要着重说明一下了，为什么要这样搞？

看到private static final Object PRESENT = new Object();不知道你有没有一点疑问呢。这里使用一个静态的常量Object类来充当HashMap的value，既然这里map的value是没有意义的，为什么不直接使用null值来充当value呢？比如写成这样子private final Object PRESENT = null;我们都知道的是，Java首先将变量PRESENT分配在栈空间，而将new出来的Object分配到堆空间，这里的new Object()是占用堆内存的（一个空的Object对象占用8byte），而null值我们知道，是不会在堆空间分配内存的。那么想一想这里为什么不使用null值。想到什么吗，看一个异常类java.lang.NullPointerException，这绝对是Java程序员的一个噩梦，这是所有Java程序猿都会遇到的一个异常，你看到这个异常你以为很好解决，但是有些时候也不是那么容易解决，Java号称没有指针，但是处处碰到NullPointerException。所以啊，为了从根源上避免NullPointerException的出现，浪费8个byte又怎么样，在下面的代码中我再也不会写这样的代码啦if (xxx == null) { … } else {….}，好爽。

我们接着分析一下其他的方法。

public boolean remove(Object o) {
       return map.remove(o)==PRESENT;
   }
复制代码

移除功能也就是调用HashMap的移除功能，没什么好说的，对于熟悉HashMap源码的伙伴可以参考文章开头列出来的一系列的文章。

由于HashSet的源码实在是比较简单，所以一次性都把剩余的方法都简单注释一下吧。

迭代器

//迭代器
  public Iterator<E> iterator() {
      return map.keySet().iterator();
  }
复制代码

容量

public int size() {
      return map.size();
  }
复制代码

**是否为空集合 **

//是否为空集合 
  public boolean isEmpty() {
      return map.isEmpty();
  }
复制代码

是否包含一个元素

//是否包含一个元素
  public boolean contains(Object o) {
      return map.containsKey(o);
  }
复制代码

以上便是HashSet的大概源码，HashSet的源码比较简单，主要是依靠HashMap来实现的，接下来我们总结一下关于HashSet的一些内容。

总结

由于HashMap基于hash表实现，hash表实现的容器最重要的一点就是可以快速存取，那么HashSet对于contains方法，利用HashMap的containsKey方法，效率是非常之快的。 HashSet 是一个没有重复元素的集合。它是由HashMap实现的，不保证元素的顺序，而且HashSet允许使用 null 元素，HashSet是非同步的。

原文 https://juejin.im/post/5dc1652ff265da4d1e26d783

正文到此结束