【Java入门提高篇】Day26 Java容器类详解(八)HashSet源码分析

  1. 云栖社区>
  2. 博客>
  3. 正文

【Java入门提高篇】Day26 Java容器类详解(八)HashSet源码分析

弗兰克的猫 2018-07-27 08:32:00 浏览638
展开阅读全文

  前面花了好几篇的篇幅把HashMap里里外外说了个遍,大家可能对于源码分析篇已经讳莫如深了。别慌别慌,这一篇来说说集合框架里最偷懒的一个家伙——HashSet,为什么说它是最偷懒的呢,先留个悬念,看完本文之后,你就会知道所言不假了。

  本篇将从以下几点来进行介绍:

  1.HashSet的特点和使用场景

  2.HashSet的示例

  3.HashSet的继承结构图

  4.HashSet的源码解析

HashSet的特点和使用场景

  HashSet是Set家族的一员,所以也具有着Set的全部性质,比如元素无序,元素不可重复,但HashSet也有它自己的一些特性,比如它的查找效率很高,跟HashMap的查找效率一样高(滑稽,看完源码分析你就知道为什么了),它的基本操作如,add/remove/contains/size等都只需要常量时间的开销,并且允许存在null值。

  所以HashSet的一个很重要的应用就是去重,把一堆存在重复的数据往HashSet里一丢,里面的元素因为是不会存在重复的,所以再取出来的时候就已经是去重过的数据了,这样HashSet就像一个筛子,把数据筛选了一次。另外HashSet由于其查找效率很高,所以也用于数据的查找,比如将处理过的数据往里面一丢,处理下一个数据的时候先到HashSet中查找一次,如果存在则说明已经处理过,不存在则继续处理。

HashSet的示例

  接下来,看一个HashSet的小栗子吧。

 1 public class Test {
 2 
 3     public static void main(String[] args){
 4         //nameList中可以存在重复元素,且顺序跟插入的顺序相同
 5         List<String> nameList = new ArrayList<>();
 6         nameList.add("Alice");
 7         nameList.add("Frank");
 8         nameList.add("Charles");
 9         nameList.add("Emma");
10         nameList.add("Jessie");
11         nameList.add("Frank");
12         System.out.println(nameList);
13 
14         //将列表里的元素插入到Set后,可以去除重复元素,但是没有顺序
15         System.out.println("====add====");
16         Set<String> nameSet = new HashSet<>();
17         for (String name : nameList){
18             nameSet.add(name);
19         }
20         System.out.println(nameSet);
21 
22         System.out.println("====contains====");
23         System.out.println(nameSet.contains("Frank"));
24         System.out.println(nameSet.contains("Bob"));
25 
26         System.out.println(nameSet.containsAll(nameList));
27 
28         System.out.println("====remove====");
29         nameSet.remove("Frank");
30         System.out.println(nameSet);
31 
32         nameSet.forEach(System.out::println);
33 
34         System.out.println("====Iterator====");
35         Iterator iterator = nameSet.iterator();
36         while (iterator.hasNext()){
37             System.out.println(iterator.next());
38         }
39 
40     }
41 }

  输出如下:

[Alice, Frank, Charles, Emma, Jessie, Frank]
====add====
[Charles, Alice, Jessie, Frank, Emma]
====contains====
true
false
true
====remove====
[Charles, Alice, Jessie, Emma]
Charles
Alice
Jessie
Emma
====Iterator====
Charles
Alice
Jessie
Emma

HashSet的继承结构图

 

  HashSet是继承自AbstractSet类的,同时实现了Set接口,Serializable接口,Cloneable接口,AbstractSet是Set的便利类,实现了Set接口的部分方法框架,AbstractSet里的方法其实很少,它继承自AbstractCollection类,同时实现了Set接口。

 1 public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E> {
 2     
 3     protected AbstractSet() {
 4     }
 5 
 6     // 比较和哈希
 7 
 8     /**
 9      * 比较两个HashSet是否相等
10      * 先比较是否是同一个引用,然后判断o是否实现了Set接口
11      * 再比较它们的大小是否一致,最后判断是否包含了o中所有元素
12      */
13     public boolean equals(Object o) {
14         if (o == this)
15             return true;
16 
17         if (!(o instanceof Set))
18             return false;
19         Collection<?> c = (Collection<?>) o;
20         if (c.size() != size())
21             return false;
22         try {
23             return containsAll(c);
24         } catch (ClassCastException unused)   {
25             return false;
26         } catch (NullPointerException unused) {
27             return false;
28         }
29     }
30 
31     /**
32      * hashCode方法,计算所有元素的hashCode之和
33      */
34     public int hashCode() {
35         int h = 0;
36         Iterator<E> i = iterator();
37         while (i.hasNext()) {
38             E obj = i.next();
39             if (obj != null)
40                 h += obj.hashCode();
41         }
42         return h;
43     }
44 
45     /**
46      * 移除所有在集合c中的元素
47      * 如果c中元素个数小于该Set中的元素个数,则遍历c中的元素,使用Set中的remove方法进行移除。
48      * 相反,如果c中的元素个数大于Set中的元素个数,则遍历该Set中的元素,如果存在于c中,则调用迭代器的remove方法进行移除。
49      */
50     public boolean removeAll(Collection<?> c) {
51         Objects.requireNonNull(c);
52         boolean modified = false;
53 
54         if (size() > c.size()) {
55             for (Iterator<?> i = c.iterator(); i.hasNext(); )
56                 //这里其实用了一个很巧妙的位操作,只要remove有一次成功,则返回true,modified就会变成true,之后不管remove返回true还是false,与modified进行或操作的时候结果都是true,所以只要remove中有一次是成功的,modified变量就是true
57                 modified |= remove(i.next());
58         } else {
59             for (Iterator<?> i = iterator(); i.hasNext(); ) {
60                 if (c.contains(i.next())) {
61                     i.remove();
62                     modified = true;
63                 }
64             }
65         }
66         return modified;
67     }
68 
69 }

HashSet的源码解析

  先来看看源码的结构:

  

  相比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);
    }

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

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

    public void clear() {
        map.clear();
    }

    @SuppressWarnings("unchecked")
    public Object clone() {
        try {
            HashSet<E> newSet = (HashSet<E>) super.clone();
            newSet.map = (HashMap<E, Object>) map.clone();
            return newSet;
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }
    }

  看完你也许会觉得,WTF???主要方法全部是一行代码解决??来看看这个map到底是何方神圣:

    private transient HashMap<E,Object> map;

  惊不惊喜,意不意外,HashSet其实就是里面放了一个HashMap实例,所有操作都是通过HashMap去完成的,至于它的元素不可重复特性,也是借助于HashMap的键值不可重复实现的。嗯,说它是最懒的容器类不过分吧。

  再来看看它的几个构造函数:

 1     /**
 2      * 构造一个空的HashSet,其中的HashMap实例使用默认的初始容量(16)和默认的装载因子(0.75)
 3      */
 4     public HashSet() {
 5         map = new HashMap<>();
 6     }
 7 
 8     /**
 9      * 构建一个包含指定集合所有元素的HashSet,其中的HashMap实例使用默认的装载因子(0.75)和能够容纳下集合中所有元素的初始容量(别忘了,必须是2的幂次方)
10      */
11     public HashSet(Collection<? extends E> c) {
12         map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
13         addAll(c);
14     }
15 
16     /**
17      * 构建一个空的HashSet,其中的HashMap实例使用指定的加载因子和初始容量
18      */
19     public HashSet(int initialCapacity, float loadFactor) {
20         map = new HashMap<>(initialCapacity, loadFactor);
21     }
22 
23     /**
24      * 构建一个空的HashSet,其中的HashMap使用默认的加载因子和指定的容量大小
25      */
26     public HashSet(int initialCapacity) {
27         map = new HashMap<>(initialCapacity);
28     }
29 
30     /**
31      * 构建一个空的LinkedHashSet,这是一个包私有的构造器,仅仅被LinkedHashSet使用,里面的HashMap是一个LinkedHashMap实例,使用指定的容量和装载因子
32      * dummy是一个没有意义的参数,目的是为了跟上面的构造函数区分开来,如果没有这个参数,将不能进行有效重载
33      */
34     HashSet(int initialCapacity, float loadFactor, boolean dummy) {
35         map = new LinkedHashMap<>(initialCapacity, loadFactor);
36     }
37 
38  

  所以,其实可以灵活定制HashSet的大小和装载因子,只是一般情况下,使用默认的即可,除非知道里面要放的元素个数,并且数量比较大时,才需要进行指定容量,这样可以减少扩容次数。

  再来看看剩下的几个函数:

    /**
     * 序列化
     */
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        // Write out any hidden serialization magic
        s.defaultWriteObject();

        // Write out HashMap capacity and load factor
        s.writeInt(map.capacity());
        s.writeFloat(map.loadFactor());

        // Write out size
        s.writeInt(map.size());

        // Write out all elements in the proper order.
        for (E e : map.keySet())
            s.writeObject(e);
    }

    /**
     * 反序列化
     */
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // Read in any hidden serialization magic
        s.defaultReadObject();

        // Read capacity and verify non-negative.
        int capacity = s.readInt();
        if (capacity < 0) {
            throw new InvalidObjectException("Illegal capacity: " +
                                             capacity);
        }

        // Read load factor and verify positive and non NaN.
        float loadFactor = s.readFloat();
        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
            throw new InvalidObjectException("Illegal load factor: " +
                                             loadFactor);
        }

        // Read size and verify non-negative.
        int size = s.readInt();
        if (size < 0) {
            throw new InvalidObjectException("Illegal size: " +
                                             size);
        }
        // Set the capacity according to the size and load factor ensuring that
        // the HashMap is at least 25% full but clamping to maximum capacity.
        capacity = (int) Math.min(size * Math.min(1 / loadFactor, 4.0f),
                HashMap.MAXIMUM_CAPACITY);

        // Constructing the backing map will lazily create an array when the first element is
        // added, so check it before construction. Call HashMap.tableSizeFor to compute the
        // actual allocation size. Check Map.Entry[].class since it's the nearest public type to
        // what is actually created.

        SharedSecrets.getJavaOISAccess()
                     .checkArray(s, Map.Entry[].class, HashMap.tableSizeFor(capacity));

        // Create backing HashMap
        map = (((HashSet<?>)this) instanceof LinkedHashSet ?
               new LinkedHashMap<E,Object>(capacity, loadFactor) :
               new HashMap<E,Object>(capacity, loadFactor));

        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            @SuppressWarnings("unchecked")
                E e = (E) s.readObject();
            map.put(e, PRESENT);
        }
    }

    /**
     * 可分割式迭代器
     */
    public Spliterator<E> spliterator() {
        return new HashMap.KeySpliterator<E,Object>(map, 0, -1, 0, 0);
    }

  嗯,HashSet的介绍就这么多了,很简单吧。

  之后还会继续将容器家族中常见的容器类进行源码解析,如LinkedList,LinkedHashMap,LinkedHashSet,TreeMap,TreeSet。嗯,所以预计关于容器类还有至少五篇文章,希望大家能耐心看下去,当然,如果对于源码解析实在没什么兴趣,也可以先跳过这一部分,先知道怎么用就好了。

  之后还会努力更新,欢迎大家继续关注。

真正重要的东西,用眼睛是看不见的。

网友评论

登录后评论
0/500
评论
弗兰克的猫
+ 关注