Set集合

Set集合的特点是不存放重复的元素，常用于去重，而它的具体实现可以用到其他的一些数据结构如：动态数组、链表、二叉搜索树。

/*** Set集合与其抽象方法* @param <E>*/
public interface Set<E> {int size();boolean isEmpty();boolean contains(E element);void clear();void add(E element);void remove(E element);void traversal(Visitor<E> visitor);/*** 定义抽象类Visitor，用于自定义访问方式* @param <E>*/public abstract class Visitor<E>{boolean stop;public abstract boolean visit(E element);//如果访问到某个元素，返回true}
}

Java中提供了HashSet、TreeSet、LinkedHashSet三种常用的Set实现。

我们可以先作一个简单的了解：
如果想要一个能进行快速访问的Set，那么可以使用HashSet。
如果想要一个排序Set，那么可以使用TreeSet。
如果想要记录下插入时的顺序时，那么可以使用LinedHashSet。

使用双向链表实现Set集合

在List集合内部实例化双向链表，通过链表对象实现Set集合。

/*** 使用双向链表实现集合* @param <E>*/
public class ListSet<E> implements Set<E>{//双向链表private List<E> list=new DoubleLinkedList<>();@Overridepublic int size() {return list.size();//返回链表大小}@Overridepublic boolean isEmpty() {return list.isEmpty();//判断链表是否为空}@Overridepublic boolean contains(E element) {return list.contains(element);//通过链表接口判断是否存在元素}@Overridepublic void clear() {list.clear();}@Overridepublic void add(E element) {int index=list.indexOf(element);//获取当前元素在链表中的索引if(index==List.ELEMENT_NOT_FOUND)//元素索引未找到，不重复，可以添加list.add(element);else //已有重复元素list.set(index,element);//覆盖原有元素}@Overridepublic void remove(E element) {int index=list.indexOf(element);if(index==List.ELEMENT_NOT_FOUND)//未找到元素return;elselist.remove(index);}@Overridepublic void traversal(Visitor<E> visitor) {if(null==visitor)return;//没有指定访问方式，直接退出int size=list.size();for(int i=0;i<size;i++)if(visitor.visit(list.get(i)))return;}
}

使用红黑树实现Set集合

我们可以使用不同的二叉搜索树来实现Set集合，但一般更倾向于选择性能更好的红黑树，但使用二叉搜素树实现的集合有一个缺点，就是存放的元素间必须能相互比较。

public class TreeSet<E> implements Set<E>{private RBTree<E> tree=new RBTree<>();//在内部创建红黑树@Overridepublic int size() {return tree.size();}@Overridepublic boolean isEmpty() {return tree.isEmpty();}@Overridepublic boolean contains(E element) {return tree.contains(element);}@Overridepublic void clear() {tree.clear();}@Overridepublic void add(E element) {if(null==element)//自定义规则，不能放空元素return ;tree.add(element);//由于红黑树本身不能存放重复的元素，所以不需要额外处理}@Overridepublic void remove(E element) {tree.remove(element);}@Overridepublic void traversal(Visitor visitor) {tree.inorderTraversal(new BST.Visitor<E>() {//使用中序遍历@Overridepublic boolean visit(E element) {return visitor.visit(element);}});}
}