Java

深入理解Java集合框架-set家族

Java集合框架

Set集合的最大特点是能够保证内部的元素唯一性. 这种特性是建立在Map的基础上的. 换句话说: Set通过组合的模式, 在Map的基础上扩展了一些特性. 由于Set是建立在Map的基础上的. 如果理解了Map的话, Set会很好理解. 接下来我们来看看Set家族的UML

UML

Set接口对应Map接口, 定义了Set的一些方法. AbstractSet对应AbstractMap, 为Set家族提供了一些默认的实现. HashSet通过组合HashMap并且利用HashMap的Key值的唯一性, 来保证内部元素的唯一性. LinkedHashSet通过组合LinkedHashMap, 使得Set内部的元素是有序的. 同种道理, TreeSet也是基于TreeMap来实现的.

Set家族

  • HashSet
  • LinkedHashSet
  • TreeSet

HashSet

1
2
3
4
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

前面说过Set家族都是通过组合Map家族来实现的. 从上面的字段, 可以看出HashSet是基于HashMap来实现的. 而PRESENT则是一个虚假的值.

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

当向HashSet中添加元素时, 将元素作为map的key, 而value则是用一个虚假的值PRESENT. 由于HashMap中的Key是唯一的. 而HashSet中的元素是作为Key储存在HashMap中的.这样就保证了HashSet元素中没有重复的值.

LinkedHashSet

LinkedHashSet继承于HashSet, 它对应Map家族的LinkedHashMap. 但是当你查看LinkedHashSet的时候, 可能会发现并没有LinkedHashMap.

1
2
3
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

上面这个构造函数是HashSet为LinkedHashSet预留的.

1
2
3
public Iterator<E> iterator() {
    return map.keySet().iterator();
}

`LinkedHashSet中还提供了一个迭代器接口, 迭代器遍历时是有序的遍历. 因为该迭代器是LinkedHashMap的一个实现.

TreeSet

TreeSet对应于TreeMap, TreeSet的实现思路跟前面两个Set差不多.. 这里不分析.

最后

到这里…不知不觉已经分析完了集合框架. 但是并没有包含并发的集合工具. 接下来准备看完并发后再来梳理并发集合工具.

分享到