13_集合(Set)

集合的特点

不存放重复的元素

集合的用处

常用于去重

• 存放新增IP，统计新增IP量
• 存放词汇，统计词汇量

集合的接口设计

• int size(){} //集合的大小
• boolean isEmpty(){} //集合是否为空
• void clear(){} //清空
• boolean contains(E element){} //搜索，集合是否包含某个元素
• void add(E element){} // 添加元素
• void remove(E element){} // 移除元素
• void traveral(){} //遍历

注意：集合重复元素，所以没有索引的概念

集合的实现

• 动态数组
• 链表
• 二叉搜索树（红黑树、AVL树）

使用链表实现

/**
 * 集合 —— 链表实现
 */

package Set;

public class LZLinkedListSet<E> {

    private LZLinkedList<E> list = new LZLinkedList<>();

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

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

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

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

    public void add(E element){
        int index = list.indexOf(element);
        if (index == list.ELEMENT_NOT_FOUND){
            list.add(element);
        }else {
            list.set(index,element);
        }
    }

    public void remove(E element){
        int index = list.indexOf(element);
        if (index != list.ELEMENT_NOT_FOUND){
            list.remove(index);
        }
    }

    public void traveral(Visitor<E> visitor){
        if (visitor == null) return;
        int size = list.size();
        for (int i = 0;i<size;i++){
            if (visitor.visit(list.get(i))) return;;
        }

    }

    public static abstract class Visitor<E> {
        public abstract boolean visit(E element);
    }

}

使用Map（Map内部采用红黑树实现）实现

LZTreeMap类代码见下一篇文章

package Set;

public class LZTreeSet2<E> {

    private LZTreeMap<E,Object> treeMap = new LZTreeMap<>();

    public int size(){
        return treeMap.size();
    }

    public boolean isEmpty(){
        return treeMap.isEmpty();
    }

    public void clear(){
        treeMap.clear();
    }

    public boolean contains(E element){
        return treeMap.containsKey(element);
    }

    public void add(E element){
        treeMap.put(element,null);
    }

    public void remove(E element){
        treeMap.remove(element);
    }

    public void traversal(LZTreeSet.Visitor<E> visitor){
        treeMap.traversal(new LZTreeMap.Visitor<E, Object>() {
            public boolean visit(E key,Object value){
                return visitor.visit(key);
            }
        });
    };

    public static abstract class Visitor<E> {
        public abstract boolean visit(E element);
    }

}

集合的时间复杂度

• 使用红黑树实现
  添加、删除、搜索都是O(logn)
• 使用链表实现
  • 搜索：O(n)
  • 添加：O(n)
  • 删除：O(n)

红黑树实现的局限性

元素必须具备可比较性