Java容器总结(四)

Java 容器总结(四) —— HashSet

1、HashSet 由两个单词组成，Hash 和 Set，Set 表示接口，实现 Set 接口有多种方式，HashSet 实现的方式利用了 Hash。Set 表示的是没有重复元素、且不保证顺序的容器接口，它扩展了 Collection，但没有定义任何新的方法，不过，对于其中的一些方法，它有自己的规范。

2、Set 接口定义

public interface Set<E> extends Collection<E> {
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    // 迭代遍历时，不要求元素之间有特别的顺序
    // HashSet 的实现就是没有顺序，但有的 Set 实现可能会有特定的顺序，比如 TreeSet
    Iterator<E> iterator();
    Object[] toArray();
    <T> T[] toArray(T[] a);
    // 如果集合中已经存在相同元素了，则不会改变集合，直接返回 false，只有不存在时，才会添加，并返回 true
    boolean add(E e);
    boolean remove(Object o);
    boolean containsAll(Collection<?> c);
    // 重复的元素不添加，不重复的添加，如果集合有变化，返回 true，没变化返回 false
    boolean addAll(Collection<? extends E> c);
    boolean retainAll(Collection<?> c);
    boolean removeAll(Collection<?> c);
    void clear();
    boolean equals(Object o);
    int hashCode();
}

3、注意：HashSet 要求元素重写 hashCode 和 equals 方法，且对两个对象，equals 相同，则 hashCode 也必须相同，如果元素是自定义的类，需要注意这一点。因为 HashSet 就是依靠 hashCode 和 equals 方法来判断对象是否相等的，所以使用 HashSet 的时候一定要注意重写这两个方法。

4、HashSet 内部组成

public class HashSet<E> extends AbstractSet<E> implements Set<E>,
        Cloneable, java.io.Serializable {
      // HashSet 内部是用 HashMap 实现的，它内部有一个 HashMap 实例变量    
      private transient HashMap<E,Object> map;
      // HashSet 相当于只有键，值都是相同的固定值 PRESENT
      private static final Object PRESENT = new Object();
}

5、HashSet 的构造方法，主要就是调用了对应的 HashMap 的构造方法。

6、add() 方法源码解析

public boolean add(E e) {
    // 返回值为 boolean 类型
    return map.put(e, PRESENT)==null;
}

就是调用 map 的 put 方法，元素 e 用于键，值就是那个固定值 PRESENT，put 返回 null 表示原来没有对应的键，添加成功了。HashMap 中一个键只会保存一份，所以重复添加 HashMap 不会变化。

7、remove() 方法源码解析

// 调用 map 的 remove 方法，返回值为 PRESENT 表示原来有对应的键且删除成功了
public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}

8、迭代器

// 返回 map 的 keySet 的迭代器
public Iterator<E> iterator() {
    return map.keySet().iterator();
}

9、HashSet 特点分析
HashSet 实现了 Set 接口，内部是通过 HashMap 实现的，这决定了它有如下特点：

没有重复元素。

可以高效的添加、删除元素、判断元素是否存在，效率都为 O(1)。

没有顺序。

10、HashSet 实现了 Set 接口，不含重复元素，内部实现利用了 HashMap，可以方便高效地实现如去重、集合运算等功能。HashSet 没有顺序，如果要保持添加的顺序，可以使用 HashSet 的一个子类 LinkedHashSet。

参考博客

Java编程的逻辑 - 剖析 HashSet