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()方法。**
