Java 集合框架分析 - HashSet

阅读 632
收藏 0
2017-03-20
原文链接: www.jianshu.com

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

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

一、HashSet简介

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


1.1 类结构

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

1.2 构造器

    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方法。

    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的一些内容。

二、总结

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

关于我

github: github.com/crazyandcod…
博客 crazyandcoder.github.io/


参考链接

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