Java HashSet 源代码学习

 

 

注：这里使用Java 1.6版本

Set集合，是collection容器的一种；特点是保证里面的元素只出现一次。

 

1.HashSet继承AbstractSet类，实现Set、Cloneable、Serializable接口；

 

2.HashSet的内部实现。

    HashSet内部采用HashMap的方式进行实现。

 

    private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

 

 

    HashSet内部采用HashMap进行实现，HashMap中的Key即是Set中的元素；value都是一样的，即上面定义的PRESENT，这是一个Object对象。

 

3.HashSet的初始化

    HashSet定义了5种初始化方法：

1)Public HashSet()

    使用不带参数的HashMap的初始化方法，初始化内部的map对象；

 

2)Public HashSet(Collection<? Extends E> c)

    使用collection c进行初始化；先是使用c的元素数量初始化map，（这里使用了HashMap中的扩展因子loadFactor以及阈值的概念，同时默认最小的map大小为16，这也是和HashMap有很深的关系）；然后将c中的所有元素加入map中。

 

    /**
     * Constructs a new set containing the elements in the specified
     * collection.  The <tt>HashMap</tt> is created with default load factor
     * (0.75) and an initial capacity sufficient to contain the elements in
     * the specified collection.
     *
     * @param c the collection whose elements are to be placed into this set
     * @throws NullPointerException if the specified collection is null
     */
    public HashSet(Collection<? extends E> c) {
	map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));
	addAll(c);
    }

 

 

    addAll方法的实现如下：

 

    public boolean addAll(Collection<? extends E> c) {
	boolean modified = false;
	Iterator<? extends E> e = c.iterator();
	while (e.hasNext()) {
	    if (add(e.next()))
		modified = true;
	}
	return modified;
    }

 

 

    这里使用c的迭代器，将每个c中的元素加入到HashSet中；只要有一个加入成功，整个方法就算成功了。这里的addAll方法，属于AbstractCollection中定义的。

 

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

 

 

    这里调用的add方法，是HashSet中定义的；加入的时候，设置key为元素e，value为定义好的Object对象PRESENT。当加入成功之后，返回true；加入失败的时候，返回false。这里的加入失败，不是因为操作真正失败了，而是因为元素e已经存在在了HashSet中。

 

    这里的实现，通过HashMap实现。在HashMap中，当put一个元素的时候，返回的结果是原始的旧的结果；所以在这里，put的时候，如果元素返回结果是null，表示HashMap中不存在以e为key的元素，即元素e不在HashSet中；如果返回结果不是null，那肯定是PRESENT，表示元素e已经存在了。

 

    同时，向HashMap中put元素，为了返回旧的值；将会先查询HashMap中的结果，这里如果碰撞比较严重（大多数元素的hash结果都相同），也会有性能的问题。一般情况下，不会太严重，使用的时候注意下即可。

 

3)Public HashSet(int initialCapacity, float loadFactor)

    使用指定的参数，初始化内部map；具体见map的初始化方法。

 

4)Public HashSet(int initialCapacity)

    使用指定的参数，初始化内部map；具体见map的初始化方法。

 

5)Public HashSet(int initialCapacity, float loadFactor, Boolean dummy)

    使用指定的参数，初始化一个LinkedHashMap；

    这里的参数dummy，只是一个标识参数，没有具体的意义。

 

    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
	map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
    }

 

 

4.迭代器（Iterator）

    HashMap中为了方便地进行元素的遍历，提供了key的迭代器、value的迭代器、Entry的迭代器；在HashSet中，因为只有key有意义，所以仅通过HashMap的key的迭代器实现了整个HashSet的迭代器。如下：

 

    /**
     * Returns an iterator over the elements in this set.  The elements
     * are returned in no particular order.
     *
     * @return an Iterator over the elements in this set
     * @see ConcurrentModificationException
     */
    public Iterator<E> iterator() {
	return map.keySet().iterator();
    }

 

 

    见注释，迭代器中的元素的顺序不是特定的。

 

5.其他基本操作

    HashSet的基本操作，包括添加add、删除remove、元素包含检查contains、清除clear、判空isEmpty等等。

    其中add方法已经在初始化的时候介绍过了；

    其他的基本操作，也都是通过HashMap实现的；基本上，都是HashMap中原方法的直接调用。

 

    public boolean isEmpty() {
	return map.isEmpty();
    }

 

 

    这里实际上就是判断，map中的size是否为0；

 

    public boolean contains(Object o) {
	return map.containsKey(o);
    }

 

 

    使用参数o，到map中进行查询，查到表示包含；否则不包含。

 

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

 

 

    Remove和add是一对逆操作；HashMap的remove操作，返回的结果是旧的value。在这里，如果旧的结果是PRESENT，表示元素o，在HashSet中，此时返回true；否则，元素o不在HashSet中，返回false。经过这个方法之后，无论返回结果是false还是true；HashSet中都不包含元素o。

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

 

    将map的元素情况，modCount清零；其他参数，loadFactor和数组长度等不变。

    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();
	}
    }

 

    返回结果的浅拷贝（shallow copy）。

 

6.最后，为了序列化，HashSet也实现了序列化和反序列化方法readObject和writeObject