你的位置:首页 > Java教程

[Java教程]Java集合源码分析(五)HashSetE


HashSet简介

  HashSet实现Set接口,由哈希表(实际上是一个HashMap实例)支持。它不保证set 的迭代顺序;特别是它不保证该顺序恒久不变。此类允许使用null元素。

HashSet源码分析

  对于HashSet而言,它是基于HashMap实现的,HashSet底层使用HashMap来保存所有元素,因此HashSet 的实现比较简单,相关HashSet的操作,基本上都是直接调用底层HashMap的相关方法来完成,
  HashSet的源代码如下:

/* * @(#)HashSet.java	1.37 06/04/21 * * Copyright 2006 Sun Microsystems, Inc. All rights reserved. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. */package java.util;/** * @param <E> the type of elements maintained by this set * * @author Josh Bloch * @author Neal Gafter * @version 1.37, 04/21/06 * @see	  Collection * @see	  Set * @see	  TreeSet * @see	  HashMap * @since  1.2 */public class HashSet<E>  extends AbstractSet<E>  implements Set<E>, Cloneable, java.io.Serializable{  static final long serialVersionUID = -5024744406713321676L;	// 使用HashMap来保存HashSet中所有元素。  private transient HashMap<E,Object> map;  // 定义一个虚拟的Object对象作为HashMap的value,将此对象定义为static final。  private static final Object PRESENT = new Object();  // 默认的无参构造器,构造一个空的HashSet。实际底层会初始化一个空的HashMap。  public HashSet() {	map = new HashMap<E,Object>();  }  // 构造一个包含指定collection中的元素的新set。  // 实际底层使用传入Collection除以0.75再加1大小的HashMap或者大小为16的HashMap,这两个值之间取最大  public HashSet(Collection<? extends E> c) {	map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));	addAll(c);  }  /**   * 以指定的initialCapacity和loadFactor构造一个空的HashSet。   * 实际底层以相应的参数构造一个空的HashMap。   *   * @param initialCapacity   * 				初始容量   * @param loadFactor   * 				加载因子   */  public HashSet(int initialCapacity, float loadFactor) {	map = new HashMap<E,Object>(initialCapacity, loadFactor);  }  /**   * 以指定的initialCapacity构造一个空的HashSet。   * 实际底层以相应的参数构造一个空的HashMap。   * @param initialCapacity   * 				初始容量   */  public HashSet(int initialCapacity) {	map = new HashMap<E,Object>(initialCapacity);  }  /**   * 以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。   * 此构造函数为包访问权限,不对外公开,实际只是是对LinkedHashSet的支持。   *   * 实际底层会以指定的参数构造一个空LinkedHashMap实例来实现。   * @param initialCapacity   * 				初始容量   * @param loadFactor   * 				加载因子   * @param dummy   * 				标记   */  HashSet(int initialCapacity, float loadFactor, boolean dummy) {	map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);  }  /**   * 返回对此set中元素进行迭代的迭代器。返回元素的顺序并不是特定的。   *   * 底层实际调用底层HashMap的keySet来返回所有的key。   * 可见HashSet中的元素,只是存放在了底层HashMap的key上,   * value使用一个static final的Object对象标识。   * @return 对此set中元素进行迭代的Iterator。   */  public Iterator<E> iterator() {	return map.keySet().iterator();  }  // 返回此set中的元素的数量(set的容量)。  // 底层实际调用HashMap的size()方法返回Entry的数量,就得到该Set中元素的个数。  public int size() {	return map.size();  }  // 如果此set不包含任何元素,则返回true。  // 底层实际调用HashMap的isEmpty()判断该HashSet是否为空。  public boolean isEmpty() {	return map.isEmpty();  }  // 如果此set包含指定元素,则返回true。  // 更确切地讲,当且仅当此set包含一个满足(o==null ? e==null : o.equals(e))的e元素时,返回true。  public boolean contains(Object o) {	return map.containsKey(o);  }  // 如果此set中尚未包含指定元素,则添加指定元素。  // 更确切地讲,如果此 set 没有包含满足(e==null ? e2==null : e.equals(e2))的元素e2,则向此set 添加指定的元素e。  // 如果此set已包含该元素,则该调用不更改set并返回false。  // 底层实际将将该元素作为key放入HashMap。  // 由于HashMap的put()方法添加key-value对时,当新放入HashMap的Entry中key与集合中原有Entry的key相同(hashCode()返回值相等,通过equals比较也返回true),  // 新添加的Entry的value会将覆盖原来Entry的value,但key不会有任何改变,  // 因此如果向HashSet中添加一个已经存在的元素时,新添加的集合元素将不会被放入HashMap中,原来的元素也不会有任何改变,这也就满足了Set中元素不重复的特性。  public boolean add(E e) {	return map.put(e, PRESENT)==null;  }  // 如果指定元素存在于此set中,则将其移除。  // 更确切地讲,如果此set包含一个满足(o==null ? e==null : o.equals(e))的元素e,  // 则将其移除。如果此set已包含该元素,则返回true   // (或者:如果此set因调用而发生更改,则返回true)。(一旦调用返回,则此set不再包含该元素)。  public boolean remove(Object o) {	return map.remove(o)==PRESENT;  }  // 从此set中移除所有元素。此调用返回后,该set将为空。  public void clear() {	map.clear();  }  // 返回此HashSet实例的浅表副本:并没有复制这些元素本身。  // 底层实际调用HashMap的clone()方法,获取HashMap的浅表副本,并设置到 HashSet中。  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();	}  }  // java.io.Serializable的写入函数  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 (Iterator i=map.keySet().iterator(); i.hasNext(); )      s.writeObject(i.next());  }  // java.io.Serializable的读取函数  private void readObject(java.io.ObjectInputStream s)    throws java.io.IOException, ClassNotFoundException {	// Read in any hidden serialization magic	s.defaultReadObject();    // Read in HashMap capacity and load factor and create backing HashMap    int capacity = s.readInt();    float loadFactor = s.readFloat();    map = (((HashSet)this) instanceof LinkedHashSet ?        new LinkedHashMap<E,Object>(capacity, loadFactor) :        new HashMap<E,Object>(capacity, loadFactor));    // Read in size    int size = s.readInt();	// Read in all elements in the proper order.	for (int i=0; i<size; i++) {      E e = (E) s.readObject();      map.put(e, PRESENT);    }  }}