数据结构——映射(Map)

一、概述

映射是一种快速的键查找数据结构体，可用于灵活地对其单个元素进行索引。与 MATLAB® 软件中仅允许通过整数索引获取元素的大多数数组数据结构体不同，映射的索引几乎可以是任何数值标量或字符向量。

指向映射元素的索引称为键。这些键以及与其相关的数据值都存储在映射内。映射的每个条目都包含一个唯一键及其相应的值。

定义

映射指的就是Map。它是由键值对（key，value）组成的集合。特点是：键具有唯一性，但是值可以重复。在scala中，Map也可分为不可变Map和可变Map。若添加重复key的新值，则新值覆盖旧值。不可变Map指的是元素、长度均不可变。

特点

• 存储键值(Key, Value)数据对的数据结构
• 根据键(Key)，寻找值(Value)
• 非常容易使用链表或二分搜索树进行实现
• Java中的HashMap和TreeMap底层分别基于哈希表和红黑树进行实现

二、代码实现

• 非常容易使用链表或二分搜索树进行实现

2.1 创建映射类接口

public interface Map<K, V> {

    /**
     * 添加元素
     * @param key
     * @param value
     */
    void add(K key, V value);

    /**
     * 删除元素，返回元素对应的value
     * @param key
     * @return
     */
    V remove(K key);

    /**
     * 是否包含key
     * @param key
     * @return
     */
    boolean contains(K key);

    /**
     * 修改元素key对应的value
     * @param key
     * @param value
     */
    void set(K key, V value);

    /**
     * 获取key对应的value
     * @param key
     * @return
     */
    V get(K key);

    /**
     * 映射的元素个数
     * @return
     */
    int getSize();

    /**
     * 映射是否为空
     * @return
     */
    boolean isEmpty();
}

2.2 基于链表实现映射

/**
 * @Author: huangyibo
 * @Date: 2022/2/15 20:39
 * @Description: 基于链表实现映射
 */

public class LinkedListMap<K, V> implements Map<K, V> {

    private class Node<K, V>{
        public K key;

        public V value;

        public Node<K, V> next;

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

        @Override
        public String toString() {
            return key.toString() +" : " + value.toString();
        }
    }

    private Node<K, V> dummyHead;

    private Integer size;

    public LinkedListMap(){
        dummyHead = new Node<>(null, null);
        size = 0;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 获取key对应的node，不存在返回null
     * @param key
     * @return
     */
    private Node<K, V> getNode(K key){
        Node<K, V> cur = dummyHead.next;
        while (cur != null){
            if(cur.key.equals(key)){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    @Override
    public boolean contains(K key) {
        return getNode(key) != null;
    }

    @Override
    public V get(K key){
        Node<K, V> node = getNode(key);
        return node == null ? null : node.value;
    }

    @Override
    public void add(K key, V value) {
        Node<K, V> node = getNode(key);
        if(node != null){
            //key已存在，则更新
            node.value = value;
            return;
        }

        //key不存在，则新增
        Node<K, V> newNode = new Node<>(key, value);
        dummyHead.next = newNode.next = dummyHead.next;
        size ++;
    }

    @Override
    public void set(K key, V value) {
        Node<K, V> node = getNode(key);
        if(node == null){
            //不存在直接抛异常
            throw new IllegalArgumentException(key + " doesn't exist!");
        }

        //key已存在，则更新
        node.value = value;
    }

    @Override
    public V remove(K key) {
        Node<K, V> prev = dummyHead;
        //循环判断key是否存在
        while (prev.next != null) {
            if(prev.next.key.equals(key)){
                break;
            }
            prev = prev.next;
        }

        //如果key存在，则进行删除
        if(prev.next != null){
            Node<K, V> delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
            size --;
            return delNode.value;
        }

        //key不存在，返回null
        return null;
    }
}

2.3 基于二分搜索树实现映射

/**
 * @Author: huangyibo
 * @Date: 2022/2/15 21:14
 * @Description: 基于二分搜索树实现映射
 */

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

    //二分搜索树节点类
    private class Node<K extends Comparable<K>, V>{

        public K key;

        public V value;

        public Node<K, V> left;

        public Node<K, V> right;

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

        @Override
        public String toString() {
            return key.toString() +" : " + value.toString();
        }
    }

    // 根节点
    private Node<K, V> root;

    // 树容量
    private Integer size;

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

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public int getSize() {
        return size;
    }

    /**
     * 向二分搜索树添加新的元素(key,value)
     * @param key
     * @param value
     */
    @Override
    public void add(K key, V value){
        //向根节点添加元素e
        root = add(root, key, value);
    }

    /**
     * 向以node为根的二分搜索树中插入元素(key,value)，递归算法
     * @param node
     * @param key
     * @param value
     * @return 返回插入新元素的二分搜索树的根
     */
    private Node<K, V> add(Node<K, V> node, K key, V value){
        if(node == null){
            size ++;
            return new Node<>(key, value);
        }

        //递归调用，元素添加到node.left
        if(key.compareTo(node.key) < 0){
            node.left = add(node.left, key, value);
        }else if(key.compareTo(node.key) > 0){
            //递归调用，元素添加到node.right
            node.right = add(node.right, key, value);
        }else {
            node.value = value;
        }
        //返回当前根节点
        return node;
    }

    /**
     * 根据key从当前以当前node为根节点中寻找value, 不存在返回null
     * @param node
     * @param key
     * @return
     */
    private Node<K, V> getNode(Node<K, V> node, K key){
        //递归终止条件
        if(node == null){
            return null;
        }

        //待寻找key比当前节点key小，递归调用node.left
        if(key.compareTo(node.key) < 0){
            return getNode(node.left, key);
        }else if(key.compareTo(node.key) > 0){
            //待寻找key比当前节点key大，递归调用node.right
            return getNode(node.right, key);
        }else {
            //待寻找key和当前节点key相等，直接返回
            return node;
        }
    }

    @Override
    public boolean contains(K key) {
        return getNode(root, key) != null;
    }

    @Override
    public void set(K key, V value) {
        Node<K, V> node = getNode(root, key);
        if(node == null){
            //不存在直接抛异常
            throw new IllegalArgumentException(key + " doesn't exist!");
        }

        //key已存在，则更新
        node.value = value;
    }

    @Override
    public V get(K key) {
        Node<K, V> node = getNode(root, key);
        return node == null ? null : node.value;
    }

    /**
     * 返回以node为根的二分搜索树的最小值所在的节点
     * @param node
     * @return
     */
    private Node<K, V> minimum(Node<K, V> node){
        if(node.left == null){
            return node;
        }
        return minimum(node.left);
    }

    /**
     * 删除以node为根的二分搜索树中的最小节点，
     * 返回删除节点后新的二分搜索树的根
     * @param node
     * @return
     */
    private Node<K, V> removeMin(Node<K, V> node){
        if(node.left == null){
            Node<K, V> rightNode = node.right;
            node.right = null;
            size --;
            return rightNode;
        }
        //递归调用node.left
        node.left = removeMin(node.left);
        return node;
    }

    /**
     *
     * @param e
     */
    /**
     * 从二分搜索树中删除元素键为key的节点, 并返回value, 不存在返回null
     * @param key
     * @return
     */
    @Override
    public V remove(K key){
        Node<K, V> node = getNode(root, key);
        if(node == null){
            //不存在直接返回null
            return null;
        }
        //存在
        root = remove(root, key);
        return node.value;
    }

    /**
     * 删除以node为根的二分搜索树中键为key的节点，递归递归方式
     * 返回删除节点后新的二分搜索树的根
     * @param node
     * @param key
     * @return
     */
    private Node<K, V> remove(Node<K, V> node, K key){
        //节点为空，直接返回
        if(node == null){
            return null;
        }
        if(key.compareTo(node.key) < 0){
            //待删除元素key小于当前节点的键，向左递归寻找
            node.left = remove(node.left, key);
            return node;
        }else if(key.compareTo(node.key) > 0){
            //待删除元素key大于当前节点的键，向右递归寻找
            node.right = remove(node.right, key);
            return node;
        }else {
            //待删除节点左子树为空
            if(node.left == null){
                Node<K, V> rightNode = node.right;
                node.right = null;
                size --;
                return rightNode;
            }

            //待删除节点右子树为空
            if(node.right == null){
                Node<K, V> rightNode = node.left;
                node.left = null;
                size --;
                return rightNode;
            }

            //待删除节点左、右子树不为空
            //找到比待删除节点大的最小节点，即待删除节点右子树最小节点
            //用这个节点顶替待删除节点的位置

            //找到比待删除节点大的最小节点，即待删除节点右子树最小节点
            Node<K, V> successor = minimum(node.right);
            //删除比待删除节点大的最小节点，并将返回值给succeer的右孩子
            successor.right = removeMin(node.right);
            //node.left赋值给successor.left
            successor.left = node.left;
            //node节点和二分搜索树脱离关系
            node.left = node.right = null;
            return successor;
        }
    }
}

参考：
https://blog.csdn.net/love905661433/article/details/82984708

https://ww2.mathworks.cn/help/matlab/matlab_prog/overview-of-the-map-data-structure.html