你的位置:首页 > Java教程

[Java教程]【JAVA集合】HashSet、LinkedHashSet、TreeSet


以下内容基于jdk1.7.0_79源码;

关于HashSet、LinkedHashSet、TreeSet

Set接口的实现类,最大特点是不允许出现重复元素;

HashSet:基于HashMap实现,一个性能相对较好的Set;

LinkedHashSet:基于LinkedHashMap实现,一个保存了插入顺序的Set;

TreeSet;基于TreeSet实现,一个实现了排序的Set;

类图关系

源码分析

Set接口的实现类相对来说都比较简单,如果熟悉HashMap、LinkedHashMap、TreeMap源码的话,HashSet、LinkedHashSet、TreeSet的代码会很好理解,因为基本上都是调用对应Map的方法来实现的;

HashSet部分源码

package java.util;public class HashSet<E>  extends AbstractSet<E>  implements Set<E>, Cloneable, java.io.Serializable{  static final long serialVersionUID = -5024744406713321676L;  //存储元素的HashMap  private transient HashMap<E,Object> map;  // 一个冗余的空对象,用于在Map中存放key对应的value,Map中所有的键值对的value都是同一个空Object的引用  private static final Object PRESENT = new Object();  /**   * 构造方法,直接生成一个对应的HashMap   */  public HashSet() {    map = new HashMap<>();  }  //省略一部分代码.....      //返回HashMap的key迭代器,HashSet中的元素实际上就是HashMap中的key元素  public Iterator<E> iterator() {    return map.keySet().iterator();  }  //调用HashMap的put方法,将e-PRESENT键值对对象put到map中  public boolean add(E e) {    return map.put(e, PRESENT)==null;  }  //省略一部分代码.....}

LinkedHashMap源码,如下,代码很少,主要是构造方法,

根据传入的参数,调用父类HashSet的HashSet(int initialCapacity, float loadFactor, boolean dummy)方法,生成一个LinkedHashMap对象存储集合元素:

package java.util;public class LinkedHashSet<E>  extends HashSet<E>  implements Set<E>, Cloneable, java.io.Serializable {      private static final long serialVersionUID = -2851667679971038690L;  public LinkedHashSet(int initialCapacity, float loadFactor) {    super(initialCapacity, loadFactor, true);  }    public LinkedHashSet(int initialCapacity) {    super(initialCapacity, .75f, true);  }  public LinkedHashSet() {    super(16, .75f, true);  }  public LinkedHashSet(Collection<? extends E> c) {    super(Math.max(2*c.size(), 11), .75f, true);    addAll(c);  }}

HashSet中生成LinkedHashMap的构造方法HashSet(int initialCapacity, float loadFactor, boolean dummy)

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

TreeSet部分源码

有一个NavigableMap类型的Map和一个空对象,NavigableMap会在构造方法里被赋成一个TreeMap对象,PRESENT是所有键值对中value对象的同一个引用;

public class TreeSet<E> extends AbstractSet<E>  implements NavigableSet<E>, Cloneable, java.io.Serializable{  /**   * TreeMap对象   */  private transient NavigableMap<E,Object> m;  // 空对象,所有Map键值对中value对象的同一个引用  private static final Object PRESENT = new Object();

构造方法,可见TreeSet是基于TreeMap实现的:

  TreeSet(NavigableMap<E,Object> m) {    this.m = m;  }  public TreeSet() {    this(new TreeMap<E,Object>());  }

再看其它TreeSet中方法的源码,基本都是通过调用TreeMap的方法实现;

 //省略部分代码。。。 public NavigableSet<E> descendingSet() {    return new TreeSet<>(m.descendingMap());  }  public int size() {    return m.size();  }  public boolean isEmpty() {    return m.isEmpty();  }//省略部分代码。。。

补充一句

学好Set集合的关键是把Map学好。