转载

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
正文到此结束
Loading...