第11章. 集合(Set)

集合(Set)

一、集合的特点

集合的特点：

1. 不存放重复的元素
2. 常用于去重

二、集合的实现方式

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

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

三、集合的接口实现

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);
    
    abstract class Visitor<E> {
        boolean stop;
        public abstract boolean visist(E element);
    }
}

四、链表实现集合(ListSet)

package DataStructure._06集合;

import java.util.LinkedList;
import java.util.List;

/**
 * @author keyongkang
 * @create 2022-08-12-15:53
 */
public class ListSet<E> implements Set<E> {

    // 双向链表实现集合
    private List<E> list = new LinkedList<>();

    /**
     * 返回集合的大小
     * @return
     */
    @Override
    public int size() {
        return list.size();
    }

    /**
     * 判断集合是否为空
     * @return
     */
    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    /**
     * 清空集合
     */
    @Override
    public void clear() {
        list.clear();
    }

    /**
     * 判断集合是否包含某个元素
     * @param element
     * @return
     */
    @Override
    public boolean contains(E element) {
        return list.contains(element);
    }

    /**
     * 向集合中添加元素,如果元素不存在,则直接添加;如果元素存在,则覆盖
     * @param element
     */
    @Override
    public void add(E element) {
        if (!list.contains(element)) {
            list.add(element);
        } else {
            int index = list.indexOf(element);
            // 将新值覆盖旧值
            list.set(index, element);
        }
    }


    /**
     * 向集合中移除元素
     * @param element
     */
    @Override
    public void remove(E element) {
        if (list.contains(element)) {
            list.remove(element);
        }
    }


    /**
     * 遍历集合
     * @param visitor
     */
    @Override
    public void traversal(Visitor<E> visitor) {
        if (visitor == null) return;

        int size = list.size();
        for (int i = 0; i < size; i ++) {
            if (visitor.visist(list.get(i))) return;
        }
    }
}

添加、删除、搜索的时间复杂度都是O(n)。

五、红黑树实现集合(TreeSet)

package DataStructure._06集合;

import DataStructure._03二叉树.tree.RBTree;

/**
 * @author keyongkang
 * @create 2022-08-12-16:22
 */
public class TreeSet<E> implements Set<E> {

    // 红黑树实现集合
    private RBTree<E> tree = new RBTree<>();
    
    public TreeSet() {
        this(null);
    }
    
    public TreeSet(Comparable<E> comparator) {
        tree = new RBTree<>(comparator);
    }

    @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) {
        
    }
}

添加、删除、搜索的时间复杂度都是O(logn)。

六、TreeSet的局限性

使用二叉搜索树(红黑树)来实现集合的话，有一个限制：元素必须具备可比较性。(源自二叉搜索树的性质)

所以当TreeSet中要存入自己实现的类作为元素时，该类必须实现Comparable接口或者在创建Set时传入一个该类的Comparator比较器。

七、Map与Set

Map的所有key组合在一起，其实就是一个Set。

因此，Set可以间接利用Map来作为内部实现。

map.put(element，null);

八、TreeMap实现TreeSet

如果Map去掉value，只保留key。那么Map就变为了Set。

九、Java官方的TreeSet

Java官方的TreeSet的内部实现使用的是TreeMap。