十九、集合Set

2022-02-02 本文已影响0人咸鱼Jay

1、简介

集合的特点

不存放重复的元素
常用于去重
2.1. 存放新增 IP，统计新增 IP 量
2.2. 存放词汇，统计词汇量
2.3. ......

public interface Set<E> {
    int size();
    boolean isEmpty();
    void clear();
    boolean contains(E element);
    void add(E element);
    void remove(E element);
    void traversal(Visitor<E> visitor);
    
    public static abstract class Visitor<E> {
        boolean stop;
        public abstract boolean visit(E element);
    }
}

思考：集合的内部实现能否直接利用以前讲过的数据结构？

动态数组

链表

二叉搜索树（AVL树、红黑树）

2、代码实现

2.1、使用链表实现ListSet

public class ListSet<E> implements Set<E>{

    private List<E> list = new LinkedList<E>();
    
    @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) {
//      if(list.contains(element)) return;
//      list.add(element);
        int index = list.indexOf(element);
        if(index != List.ELEMENT_NOT_FOUND) {// 存在就覆盖
            list.set(index, element);
        }else {// 不存在就添加
            list.add(element);
        }
    }

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

    @Override
    public void traversal(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;
        }
    }
}

2.2、使用红黑树实现TreeSet

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

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

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

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

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

    @Override
    public void add(E element) {
        tree.add(element);
    }

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

    @Override
    public void traversal(Visitor<E> visitor) {
        tree.inorder(new BinaryTree.Visitor<E>() {
            @Override
            public boolean visit(E element) {
                return visitor.visit(element);
            }
        });
    }
}

使用红黑树来实现这个集合，其实是有一个限制： $\color{#ed7d30}{元素必须具备可比较性}$ 。如果不具备可比较性，它是没办法加进去的。如果我们通过链表或者数组实现的话，它是没有任何限制。所以这里TreeSet需要传入一个比较器：