Java集合---Set-CSDN博客

本文详细解析了HashSet和TreeSet的实现原理与使用方法。介绍了HashSet如何基于HashMap存储元素，以及TreeSet如何利用TreeMap进行排序。同时，还探讨了它们各自的构造方法、增删查操作及特点。

Set 接口

一个不包含重复元素的 collection。更确切地讲，set 不包含满足 e1.equals(e2) 的元素对 e1 和 e2，并且最多包含一个 null 元素。正如其名称所暗示的，此接口模仿了数学上的 set 抽象。

Set接口是一种不包括重复元素的Collection，它维持它自己的内部排序，所以随机访问没有任何意义。

AbstractSet 抽象类

AbstractSet提供 Set 接口的骨干实现，从而最大限度地减少了实现此接口所需的工作。

HashSet

类声明

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

成员属性

private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();

看到这里，是不是已经很清楚了，HashSet 底层是 HashMap 实现的。

构造方法

Constructor 1
public HashSet() {
    map = new HashMap<E,Object>();
}

Constructor 2
public HashSet(int initialCapacity) {
    map = new HashMap<E,Object>(initialCapacity);
}

Constructor 3
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<E,Object>(initialCapacity, loadFactor);
}

Constructor 4
public HashSet(Collection<? extends E> c) {
    map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

可以看到，所有的构造方法的作用之一就是初始化 map 成员属性。

接下来看一下 HashSet 的增加、删除、访问和迭代元素的操作

1 添加元素

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

实际上就是往 map 中添加元素，只不过 map 中的有效元素是 key,因为 map 中所有 value 都是一个值 PRESENT。

1 HashSet 底层由 HashMap 实现
2 HashMap 允许 key = null ,那么 HashSet 也允许加入 null 元素，不过只可以加入一个 null 元素，再次加入就会覆盖前者
3 HashSet 没有提供同步机制
4 HashSet 加入元素时没有进行排序
5 对 HashSet 进行随机访问是没有意义的，其拥有自己的插入规则，拉链法实现*

2 删除元素

public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}

3 访问元素
对 HashSet 进行随机访问是没有意义的，其拥有自己的插入规则，拉链法实现，所以 HashSet 没有提供相关方法。

4 迭代元素

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

直接返回 map 的键集的迭代器

HashSet 总结

HashSet 底层由 HashMap 实现
HashSet 没有提供同步机制
HashSet 允许加入 null 元素
Hashset 不允许重复的元素加入，因为 HashMap 不允许加入重复的键，此处重复意味着 e1.equals(e2) = true

TreeSet

与HashSet是基于HashMap实现一样，TreeSet同样是基于TreeMap实现的。

TreeSet 类声明

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable

成员属性

private transient NavigableMap<E,Object> m;
private static final Object PRESENT = new Object();

TreeMap 实现了 NavigableMap 接口，提供了一系列的导航方法。

构造方法

Constructor 1
public TreeSet() {
    this(new TreeMap<E,Object>());
}

Constructor 2
public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<E,Object>(comparator));
}

Constructor 3
public TreeSet(Collection<? extends E> c) {
    this();
    addAll(c);
}

Constructor 4
TreeSet(NavigableMap<E,Object> m) {
       this.m = m;
}

构造方法中初始化 TreeMap 类型的属性 m

接下看一下 TreeSet 的添加、删除、访问和迭代元素

1 添加元素

public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}

2 删除元素

public boolean remove(Object o) {
    return m.remove(o)==PRESENT;
}

3 访问元素

没有提供随机方法元素的方法

4 迭代元素

public Iterator<E> iterator() {
   return m.navigableKeySet().iterator();
}

返回 m 的键集迭代器

5 快速导航方法 (因为 TreeMap 是内部有序的)
因为 TreeMap 实现了 NavigableMap 接口，提供一些快速导航的方法，TreeSet 由 TreeMap 支持，多以 TreeSet 也提供了一些快速导航的方法

E lower(E e);
E floor(E e);
E ceiling(E e);
E pollFirst();
E pollLast();

TreeSet 总结

底层由 TreeMap 实现
TreeMap 是否允许 key = null，取决于使用的排序方式，具体可以看 TreeMap中的介绍，所以 TreeMap 是否允许加入 null 元素是不确定的
TreeSet 没有提供同步机制
TreeSet 加入元素时进行了排序
TreeSet 实现了 NavigableSet 接口，提供一系列的导航方法