Java集合框架分析-HashSet

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

相关文章
1、Java 集合框架分析-概述
2、Java集合框架分析-HashMap
3、Java集合框架分析-LinkedHashMap
4、Java集合框架分析-ArrayList
5、Java集合框架分析-LinkedList
6、Java集合框架分析-Iterator

一、HashSet简介

首先来看下java集合框架的总图,在网上找了两张关于集合框架的架构图:

1.1 类结构

首先,我们来看下HashSet的类继承结构。

1
2
3
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相关源码。首先我们来看下它的属性。

1
2
3
4
5
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这种数据结构是不允许有重复的存在的,接下来我们就一探究竟,看看到底如何实现不重复操作的。

1.2 构造器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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是无意义的,只是为了区分其他构造方法。

1.3 其他方法

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

1
2
3
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}

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

1
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 {….},好爽。

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

1
2
3
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//迭代器
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的一些内容。

二、总结

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

关于我

github: https://github.com/crazyandcoder
博客 http://crazyandcoder.github.io/
掘金:https://juejin.im/user/56b96af96240b8005865df59/share


参考链接

1、http://www.cnblogs.com/skywang12345/p/3311252.html
2、http://www.tuicool.com/articles/U736ryy