集合-Set解析

2017-09-19  本文已影响0人  史云龙

一、概述

  1. Set集合与Collection集合基本相同，没有提供额外的方法。实际上Set就是Collection，只是行为略有不同(Set不允许包含重复元素)。
  2. Set不允许包含重复元素，如果视图把两个相同的元素加入到同一个Set集合中，则会添加失败，add()方法返回false，且新元素不会被加入。
  3. 加入Set的元素必须定义equals()方法以确保对象的唯一性。Set接口不保证维护元素的次序。

二、HashSet

2.1 概述

  1. HashSet是Set的典型接口实现，实现了Set接口中所有方法，并没有额外添加方法
  2. HashSet是针对了HashMap进行封装，其中Set中存储的元素是存储在HashMap的Key，但是Value值在Java和Android中实现有不同的表现，JDK1.8中使用的是一个固定的Object来当值，而在Android中则是使用HashMap本来来作为值。
  3. 既然是对HashMap的封装，那么必然也需要Set中存储的元素需要实现equals()和hashCode()方法。
  4. 为快速查找而设计的Set

2.2 代码

Java

private transient HashMap<E,Object> map;//封装的HashMap
private static final Object PRESENT = new Object();//Map需要的Values值
//几个构造函数，都调用了相对应的HashMap的构造函数来确保对HashMap的封装
public HashSet() {
        map = new HashMap<>();
}
public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
}
//主要针对LinkedHashSet来封装LinkedHashMap
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
//常用操作
 public boolean add(E e) {//增
        return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {//删
        return map.remove(o)==PRESENT;
}
public boolean contains(Object o) {//查
        return map.containsKey(o);
}
public Iterator<E> iterator() {//遍历
        return map.keySet().iterator();
}

Android

transient HashMap<E, HashSet<E>> backingMap;//值的泛型时HashSet
//构造函数，调用的全是一个没有修饰符的构造函数，子类调的也是这个
public HashSet() {
        this(new HashMap<E, HashSet<E>>());
}
public HashSet(int capacity) {
        this(new HashMap<E, HashSet<E>>(capacity));
}
public HashSet(int capacity, float loadFactor) {
        this(new HashMap<E, HashSet<E>>(capacity, loadFactor));
}
public HashSet(Collection<? extends E> collection) {
        this(new HashMap<E, HashSet<E>>(collection.size() < 6 ? 11 : collection
                .size() * 2));
        for (E e : collection) {
            add(e);
        }
}
HashSet(HashMap<E, HashSet<E>> backingMap) {
        this.backingMap = backingMap;
}
//常用操作
@Override
public boolean add(E object) {//增
        return backingMap.put(object, this) == null;
}
@Override
public boolean remove(Object object) {//删
        return backingMap.remove(object) != null;
}
@Override
public boolean contains(Object object) {//查询，包含
        return backingMap.containsKey(object);
}
@Override
public Iterator<E> iterator() {//遍历
        return backingMap.keySet().iterator();
}

三、LinkedTreeSet

3.1 概述

  1. 继承自HashSet，是对LinkedHashMap的封装
  2. 数据的遍历顺序是采用LinkedHashMap相关的遍历顺序
  3. 具有HashSet的查询数据，且内部使用链表维护元素的顺序，于是在使用迭代器遍历Set是，结果会按元素插入的次序显示。

3.2 代码

构造函数都是调用父类的默认构造函数

Java

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

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);
}

}

Android

public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable,
        Serializable {
public LinkedHashSet() {
        super(new LinkedHashMap<E, HashSet<E>>());
}
public LinkedHashSet(int capacity) {
        super(new LinkedHashMap<E, HashSet<E>>(capacity));
}
public LinkedHashSet(int capacity, float loadFactor) {
        super(new LinkedHashMap<E, HashSet<E>>(capacity, loadFactor));
}
public LinkedHashSet(Collection<? extends E> collection) {
        super(new LinkedHashMap<E, HashSet<E>>(collection.size() < 6 ? 11
                : collection.size() * 2));
        for (E e : collection) {
            add(e);
        }
}
}

四、TreeSet

4.1 概述

  1. TreeSet是NavigableSet 的实现类，NavigableSet是继承SortedSet的接口，TreeSet默认是排序的。
  2. TreeSet为了保证是有序的序列，那么它的元素必须是可比较的，或者使用比较器来比较它的元素。
  3. TreeSet是对TreeMap进行封装，那么TreeSet的底层数据结构也和TreeMap相同

4.2 代码

Java

private transient NavigableMap<E,Object> m;//可排序的Map
private static final Object PRESENT = new Object();//Map的值
TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
}
public TreeSet() {
        this(new TreeMap<E,Object>());//初始化一个TreeMap
}
public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));//初始化一个TreeMap
}
public TreeSet(Collection<? extends E> c) {
        this();
        addAll(c);
}
public TreeSet(SortedSet<E> s) {
        this(s.comparator());
        addAll(s);
}
//常用方法
public boolean add(E e) {
        return m.put(e, PRESENT)==null;
}
public  boolean addAll(Collection<? extends E> c) {
        // Use linear-time version if applicable
        if (m.size()==0 && c.size() > 0 &&
            c instanceof SortedSet &&
            m instanceof TreeMap) {
            SortedSet<? extends E> set = (SortedSet<? extends E>) c;
            TreeMap<E,Object> map = (TreeMap<E, Object>) m;
            Comparator<?> cc = set.comparator();
            Comparator<? super E> mc = map.comparator();
            if (cc==mc || (cc != null && cc.equals(mc))) {
                map.addAllForTreeSet(set, PRESENT);
                return true;
            }
        }
        return super.addAll(c);
}
public boolean remove(Object o) {
        return m.remove(o)==PRESENT;
}
public boolean contains(Object o) {
        return m.containsKey(o);
}
//还有一些NavigableSet或者SortedMap方法，比如获取第一个元素，最后一个元素，前一个元素，后一个元素等
//遍历
public Iterator<E> iterator() {//正序遍历
        return m.navigableKeySet().iterator();
}
public Iterator<E> descendingIterator() {//倒序遍历
        return m.descendingKeySet().iterator();
}

Android

private transient NavigableMap<E, Object> backingMap;//需要封装的对象
private transient NavigableSet<E> descendingSet;//倒序Set
TreeSet(NavigableMap<E, Object> map) {
        backingMap = map;
}
public TreeSet() {
        backingMap = new TreeMap<E, Object>();
}
public TreeSet(Collection<? extends E> collection) {
        this();
        addAll(collection);
}
public TreeSet(Comparator<? super E> comparator) {
        backingMap = new TreeMap<E, Object>(comparator);
}
public TreeSet(SortedSet<E> set) {
        this(set.comparator());
        Iterator<E> it = set.iterator();
        while (it.hasNext()) {
            add(it.next());
        }
}
//常用方法
@Override
public boolean add(E object) {
        return backingMap.put(object, Boolean.TRUE) == null;
}
@Override
public boolean addAll(Collection<? extends E> collection) {
        return super.addAll(collection);
}
@Override
public boolean contains(Object object) {
        return backingMap.containsKey(object);
}
@Override
public boolean remove(Object object) {
        return backingMap.remove(object) != null;
}
//遍历
@Override
public Iterator<E> iterator() {
        return backingMap.keySet().iterator();
}
public Iterator<E> descendingIterator() {
        return descendingSet().iterator();
}

五、EnumSet

5.1 概述

  1. 专为枚举设置的集合，后续会补充

六、总结

  1. 这几种Set可以根据需要进行旋转。
    1.1 查询操作较多时，并且忽略顺序时，使用HashSet
    1.2 查询、遍历操作较多时，并且需要顺序是，可以使用LinkedHashSet
    1.3 当只需要一个特定排序的集合时，这个排序如果需要自定义时，可以考虑使用TreeSet
    1.4 插入、删除等操作，在数据量比较小时考虑使用HashSet，不用特意去考虑
    hashCode的算法，也能有较高的效率，如果数据量比较大时，可以考虑使用TreeSet毕竟TreeSet操作时间效率在O(logn)
    1.5 具体选择哪种集合，还需要写测试代码进行测试。
  2. Java中Set就是对相应的Map进行一层封装，具体可以参考下方关于Map的文章
  3. 没有3了......

其他文章

容器解析
ArrayList解析
LinkedList解析
TreeMap解析(上)
TreeMap解析(下)
HashMap解析
LinkedHasMap解析(下)
Set解析

上一篇 下一篇

猜你喜欢

热点阅读