DS06:集合与映射

集合特点

集合通常由一组无序的，不能重复的元素构成。

封装的集合接口如下：

public interface Set<E> {
    void add(E e);
    void remove(E e);
    boolean contains(E e);
    int getSize();
    boolean isEmpty();
}

集合实现

基于BST实现的集合为有序集合，基于链表实现的集合为无序集合

基于二叉树

由之前构建二叉树可知，当元素数值在二叉树中存在时，我们并没有对其进行处理，因此利用二叉树（或者说二叉搜索树）构建集合具有天然的优势。Java代码实现如下：

public class BSTSet<E extends Comparable<E>> implements Set<E> {

    private BST<E> bst;

    public BSTSet() {
        bst = new BST<>();
    }

    @Override
    public void add(E e) {
        bst.add(e);
    }

    @Override
    public void remove(E e) {
        bst.remove(e);
    }

    @Override
    public boolean contains(E e) {
        return bst.contains(e);
    }

    @Override
    public int getSize() {
        return bst.getSize();
    }

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

基于链表等线性结构

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

    private LinkedList<E> list;

    public LinkedListSet() {
        list = new LinkedList<>();
    }

    @Override
    public void add(E e) {
        if(!list.contains(e)) {
            list.addFirst(e);   // 在头部添加复杂度为O(1)
        }
    }

    @Override
    public void remove(E e) {
        list.removeElement(e);
    }

    @Override
    public boolean contains(E e) {
        return list.contains(e);
    }

    @Override
    public int getSize() {
        return list.getSize();
    }

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

复杂度分析

基于链表的增删改查复杂度都为O(n)级别

而基于二叉搜索树的则为O(h)级别（h为二叉树的高度）。依据二叉树的性质，最好的情况（平衡）为O(log n) ，最差为O(n)。

映射特点

映射通俗来讲就是存储（键，值）数据对的数据结构，可以根据键（Key）来寻找值（Value）。

如下是映射的接口及需要实现的方法

public interface Map<K, V> {
    void add(K key, V value);
    V remove(K key);
    boolean contains(K key);
    V get(K key);
    void set(K key, V newValue);
    int getSize();
    boolean isEmpty();
}

基于二叉树

实现基本框架

public class BSTMap<K extends Comparable<K>, V> implements Map<K, V> {

    private class Node {
        public K key;
        public V value;
        public Node left, right;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            left = null;
            right = null;
        }
    }

    private Node root;
    private int size;

    public BSTMap() {
        root = null;
        size = 0;
    }
}

其余诸如添加元素、删除元素等操作，与二叉搜索树中的相应操作完全一致，只是每个节点中有两个值而已。

基于链表的实现

将链表中存储的值由一个变为两个，如下：

private class Node {
    public K key;
    public V value;
    public Node next;

    public Node(K key, V value, Node next) {
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public Node(K key, V value) {
        this(key, value, null);
    }

    public Node() {
        this(null, null, null);
    }
}

其余增删操作与链表中逻辑一致，只是增加元素的时候需要判断元素是否存在。

复杂度分析

基于链表实现的映射的增删改查都为O(n)级别

基于BST实现的映射的增删改查为O(h)级别，这与集合中的复杂度分析是一致的。

Donate