集合

1、概述

• List、Set、Queue都是接口，均实现Collection接口。
• List下有ArrayList、LinkedList、Vector。
• Set下有HashSet、LinkedHashSet、TreeSet。

• Collection接口下还有一个Queue接口，它的实现类是PriorityQueue类。

  
  集合架构.png

2、List和Set的区别

• List允许插入重复的元素，并且List中的元素是有序的。

• ArrayList：
  优点：底层使用的是动态数组实现的，所以查询快，增删慢。
  缺点：线程不安全
• Vector：
  优点：底层使用的是数组，所以查询快，增删慢。
  缺点：线程安全，但效率低
• LinkedList:
  优点：底层使用的是双向链表，所以查询慢，增删快。
  缺点：线程不安全

• Set不允许插入重复的元素，而且是无序的（LinkedHashSet除外）

• HashSet:底层数据结构是哈希表，无序、唯一。
  对于HashSet而言，它是基于HashMap实现的，HashSet底层使用HashMap来保存所有元素，更确切的说，HashSet中的元素，只是存放在了底层HashMap的key上， 而value使用一个static final的Object对象标识。因此HashSet 的实现比较简单，相关HashSet的操作，基本上都是直接调用底层HashMap的相关方法来完成。
• LinkedHashSet:底层数据结构是链表和哈希表。有序、唯一。
  对于LinkedHashSet而言，它是基于LinkedHashMap实现的，LinkedHashSet底层使用LinkedHashMap来保存元素，更确切的说，LinkedHashSet中的元素，只是存放在了LinkedHashMap的key上，而value使用一个static final的Object对象标识。
  1.链表保证元素有序
  2.哈希表保证元素唯一
• TreeSet：底层使用红黑树实现，无序、唯一。
  红黑树是平衡二叉搜索树，所以可以保证元素的有序，但不能保证元素顺序和插入顺序一致。
  在插入相同的元素会进行元素覆盖，这样能保证唯一。

注意:java集合中的有序无序是针对插入顺序的，是指在插入元素时，是否保持插入的顺序，在遍历集合时是否会按照插入的顺序展示。
前面我们已经学习了ArrayList的实现以及LinkedList的实现，下面看下如何使用我们学习的数据结构实现Set。

3、Set

前面已经提到，Set的特点的是不存放重复的元素。
前面我们已经学习的数据结构有：数组、链表、二叉搜索树（AVL树、红黑树），显然这些数据结构都是可以实现Set集合的。
下面我们就以链表和红黑树来实现Set。在实现之前，先设计一下Set的接口。

public interface Set<E> {

    int size();

    boolean isEmpty();

    void clear();

    boolean contains(E element);

    void add(E element);

    void remove(E element);

    void traversal(Vistor<E> vistor);

    public static abstract class Vistor<E> {
        boolean stop;
        public abstract boolean vistor(E element);
    }
}

可以看到上面我们提供了一个遍历的方法traversal(Vistor<E> vistor)，由于集合Set是无序的，不存在index的概念的，所以需要向外提供一个遍历方法。

3.1、使用链表实现Set集合

public class ListSet<E> implements Set<E> {
    private LinkedList<E> list = new LinkedList<>();

    @Override
    public int size() {
        return list.size();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public void clear() {
        list.clear();
    }

    @Override
    public boolean contains(E element) {
        return list.contains(element);
    }

    @Override
    public void add(E element) {
        // 由于Set中元素不能重复
        int index = list.indexOf(element);
        if (index == -1) {
            list.add(element);
        } else {
            list.set(index, element);
        }
    }

    @Override
    public void remove(E element) {
        int index = list.indexOf(element);
        if (index != -1)
            list.remove(index);

    }

    @Override
    public void traversal(Vistor<E> vistor) {
        if (vistor == null)
            return;
        int size = list.size();
        for (int i = 0; i < size; i++) {
            if (vistor.stop)
                break;
            vistor.stop=vistor.vistor(list.get(i));
        }
    }

}

3.2、使用红黑树实现Set

public class TreeSet<E> implements Set<E> {
    private RBTree<E> rbTree = new RBTree<>();

    @Override
    public int size() {
        return rbTree.size();
    }

    @Override
    public boolean isEmpty() {
        return rbTree.isEmpty();
    }

    @Override
    public void clear() {
        rbTree.clear();
    }

    @Override
    public boolean contains(E element) {
        return rbTree.contains(element);
    }

    @Override
    public void add(E element) {
        // 我们在写二叉搜索树时，内部已经对重复元素做了覆盖处理。
        rbTree.add(element);
    }

    @Override
    public void remove(E element) {
        rbTree.remove(element);
    }

    @Override
    public void traversal(Vistor<E> vistor) {
        if (vistor == null)
            return;
//这里选用的是中序遍历，其他遍历方式也可以，只不过中序遍历的数据是排序好的数据
        rbTree.inorder(new Visitor<E>() {

            @Override
            public boolean visit(E e) {
                return vistor.vistor(e);
            }
        });
    }

}

其中的RBTree是使用我们之前写的红黑树。
**注意：

• TreeSet底层使用红黑树实现的，所以添加的元素需要具有可比较性，否则会报错。内部可以使用TreeMap来实现，元素存储在TreeMap的key上，value直接存入null或存入静态Object对象。
• HashSet中存储的元素并不要求具有可比较性。但是由于HashSet底层使用HashMap来实现的，存储元素存储到HashMap的key上，HashMap的key是虽然不要求具有可比较性，但是key必须实现hashCode()和equals()方法（由于这两个方法是Object中的方法，即使不重写也不会报错，但是可能无法满足我们的需求），所以HashSet中存储的元素也必须要实现这两个方法。
• LinkedHashSet中存储的元素并不要求具有可比较性。LinkedHashSet底层使用LinkedHashMap来实现的，所以同HashSet一样，其中存储的元素也必须实现hashCode()和equals()方法。**