HashSet源码分析 jdk1.6

Set的特点：Set元素无顺序，且元素不可以重复。

1、定义

public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable

Set接口定义：

public interface Set<E> extends Collection<E> {
// Query Operations
int size();
boolean isEmpty();
boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray();
<T> T[] toArray(T[] a);
// Modification Operations
boolean add(E e);
boolean remove(Object o);
// Bulk Operations
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean retainAll(Collection<?> c);
boolean removeAll(Collection<?> c);
void clear();
// Comparison and hashing
boolean equals(Object o);
int hashCode();
}

2、底层存储

// 底层使用HashMap来保存HashSet的元素
private transient HashMap<E,Object> map;

// Dummy value to associate with an Object in the backing Map
// 由于Set只使用到了HashMap的key，所以此处定义一个静态的常量Object类，来充当HashMap的value
    //用于避免java.lang.NullPointerException异常
private static final Object PRESENT = new Object();

3、构造方法

/**
     * 使用HashMap的默认容量大小16和默认加载因子0.75初始化map，构造一个HashSet
*/
public HashSet() {
        map = new HashMap<E,Object>();
    }

/**
     * 构造一个指定Collection参数的HashSet，这里不仅仅是Set，只要实现Collection接口的容器都可以
*/
public HashSet(Collection<? extends E> c) {
        map = new HashMap<E,Object>(Math. max((int) (c.size()/.75f) + 1, 16));
// 使用Collection实现的Iterator迭代器，将集合c的元素一个个加入HashSet中
       addAll(c);
    }

/**
     * 使用指定的初始容量大小和加载因子初始化map，构造一个HashSet
*/
public HashSet( int initialCapacity, float loadFactor) {
        map = new HashMap<E,Object>(initialCapacity, loadFactor);
    }

/**
     * 使用指定的初始容量大小和默认的加载因子0.75初始化map，构造一个HashSet
*/
public HashSet( int initialCapacity) {
        map = new HashMap<E,Object>(initialCapacity);
    }

/**
     * 不对外公开的一个构造方法（默认default修饰），底层构造的是LinkedHashMap，dummy只是一个标示参数，无具体意义
*/
    HashSet( int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}

4、增加和删除

/**
     * 利用HashMap的put方法实现add方法
*/
public boolean add(E e) {
return map .put(e, PRESENT)== null;
    }

/**
     * 利用HashMap的remove方法实现remove方法
*/
public boolean remove(Object o) {
return map .remove(o)==PRESENT;
    }

/**
     * 添加一个集合到HashSet中，该方法在AbstractCollection中
*/
public boolean addAll(Collection<? extends E> c) {
boolean modified = false;
// 取得集合c迭代器Iterator
       Iterator<? extends E> e = c.iterator();
// 遍历迭代器
while (e.hasNext()) {
// 将集合c的每个元素加入到HashSet中
if (add(e.next()))
              modified = true;
       }
return modified;
    }

/**
     * 删除指定集合c中的所有元素，该方法在AbstractSet中
*/
public boolean removeAll(Collection<?> c) {
boolean modified = false;

// 判断当前HashSet元素个数和指定集合c的元素个数，目的是减少遍历次数
if (size() > c.size()) {
// 如果当前HashSet元素多，则遍历集合c，将集合c中的元素一个个删除
for (Iterator<?> i = c.iterator(); i.hasNext(); )
                modified |= remove(i.next());
        } else {
// 如果集合c元素多，则遍历当前HashSet，将集合c中包含的元素一个个删除
for (Iterator<?> i = iterator(); i.hasNext(); ) {
if (c.contains(i.next())) {
                    i.remove();
                    modified = true;
                }
            }
        }
return modified;
}

Hashset的很多地方就是利用 hashmap的key实现的

秒客网

HashSet源码分析 jdk1.6

相关文章