14_映射（Map）

Map在有些编程语言中也叫做字典（dictionary,比如Python、Ojective-C、Swift等）

Map的每一个key是唯一的

Snip20200906_1.png

类似Set，Map可以直接使用链表，二叉搜索树（AVL树、红黑树）等数据结构来实现

接口设计

• int size(){}
• boolean isEmpty(){}
• void clear(){}
• void put(K key,V value){}
• V get(K key){}
• void remove(K key){}
• boolean containsKey(K key){}
• boolean containsValue(V value){}
• traversal(Visitor<K,V> visitor){}
• public static abstract class Visitor<K,V>{ boolean stop; public abstract boolean visit(K key,V value); }

代码实现

package Map;

import Set.LZLinkedListSet;
import Set.RBTree.LZBinaryTree;
import Set.RBTree.LZRBTree;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;

public class LZTreeMap<K,V> {

    private static final boolean RED = false;
    private static final boolean BLACK = true;

    private int size;
    private Node<K,V> root;

    private Comparator<K> comparator;

    public LZTreeMap(){
        this(null);
    }

    public LZTreeMap(Comparator<K> comparator){
        this.comparator = comparator;
    }

    /**
     * Map的大小
     */
    public int size(){
        return size;
    }

    /**
     * Map是否为空
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 清空Map
     */
    public void clear(){
        root = null;
        size = 0;
    }

    public void put(K key,V value){
        keyNotNullCheck(key);
        //添加的是第一个节点
        if (root == null){
            root = new Node<K,V>(key,value,null);
            size++;
            //添加新节点之后的处理
            afterAdd(root);
            return;
        }
        //添加的不是第一个节点
        Node<K,V> parent = root;
        Node<K,V> node = root;
        int cmp = 0;
        while (node != null){
            cmp = (compare(key,node.key));
            parent = node;
            if (cmp<0){
                node = node.left;
            }else if(cmp>0){
                node = node.right;
            }else {
                node.key = key;
                node.value = value;
                return;
            }
        }

        Node<K,V> newNode = new Node<>(key,value,parent);
        if (cmp>0){
            parent.right = newNode;
        }else {
            parent.left = newNode;
        }
        size++;

        //添加新节点之后的处理
        afterAdd(newNode);
    }

    public V get(K key){
        Node<K,V> node = node(key);
        if (node == null) return null;
        return node.value;
    }

    public void remove(K key){
        Node<K,V> node = node(key);
        if (node == null) return;
        size--;

        if (node.left != null && node.right != null){  //度为2的节点
            Node<K,V> s = successor(node); //找到后继节点
            node.key = s.key; //用后继节点的值覆盖度为2的节点的值
            node.value = s.value;
            node = s; //删除后继节点
        }

        //删除node节点，node节点的度必然是1或者0
        //删除叶子节点
        if (node.left == null && node.right == null){
            if (node.parent == null){
                root = null;
            }else if(node == node.parent.left){
                node.parent.left = null;
            }else {
                node.parent.right = null;
            }
            //删除节点之后的处理
            afterRemove(node,null);
        }else { //删除度为1的节点
            Node<K,V> replacement = node.left != null?node.left:node.right;
            replacement.parent = node.parent;
            if (node.parent == null){
                root = replacement;
            }else if (node == node.parent.left){
                node.parent.left = replacement;
            }else {
                node.parent.right = replacement;
            }
            //删除节点之后的处理
            afterRemove(node,replacement);
        }

    }

    public boolean containsKey(K key){
        return node(key) != null;
    }

    public boolean containsValue(V value){
        if (root == null) return false;
        Queue<Node<K,V>>  queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            Node<K,V> node = queue.poll();
            if (valEquals(node.value,value)) return true;
            if (node.left != null){
                queue.offer(node.left);
            }
            if (node.right != null){
                queue.offer(node.right);
            }
        }
        return false;
    }

    void traversal(Visitor<K,V> visitor){
        if (visitor == null) return;
        traversal(root,visitor);
    }

    private void traversal(Node<K,V> node,Visitor<K,V> visitor){
        if (node == null || visitor.stop) return;
        traversal(node.left,visitor);
        if (visitor.stop)return;
        visitor.visit(node.key, node.value);
        traversal(node.right,visitor);
    }

    public static abstract class Visitor<K,V>{
        boolean stop;
        public abstract boolean visit(K key,V value);
    }

    private boolean valEquals(V v1, V v2) {
        return v1 == null ? v2 == null : v1.equals(v2);
    }

    /**
     * key非空检查
     * @param key
     */
    private void keyNotNullCheck(K key){
        if (key == null){
            throw new IllegalArgumentException("key must not be null");
        }
    }

    /**
     * 根据key找到对应节点
     */
    private Node<K,V> node(K key){
        Node<K,V> node = root;
        while (node != null){
            int cmp = compare(node.key, key);
            if (cmp<0){
                node = node.right;
            }else if(cmp>0){
                node = node.left;
            }else {
                return node;
            }
        }
        return null;
    }

    private int compare(K e1,K e2){
        if (comparator != null) return comparator.compare(e1,e2);
        return ((Comparable<K>)e1).compareTo(e2);
    }

    private void afterAdd(Node<K,V> node) {
        //判断情况1，是否是根节点
        if (node.parent == null) {
            black(node);
            return;
        }

        //判断情况2，父节点是否是黑色
        if(isBlack(node.parent)) return;

        //判断情况4，叔父节点是否是红色，如果是红色，不需要旋转，B树节点溢出
        if (isRed(node.parent.sibling())){
            black(node.parent);
            black(node.parent.sibling());
            Node<K,V> parent = red(node.parent.parent);
            afterAdd(parent);
            return;
        }

        //符合情况3，旋转，B树节点不会溢出
        Node<K,V> parent = node.parent;
        Node<K,V> grand = red(parent.parent); //将祖父节点染成红色

        if (parent.isLeftChild()){  //L
            if (node.isLeftChild()){ //LL
                black(parent);
            }else { //LR
                black(node);
                rotateLeft(parent);
            }
            rotateRight(grand);
        }else { //R
            if (node.isLeftChild()){ //RL
                black(node);
                rotateRight(parent);
            }else {  //RR
                black(parent);
            }
            rotateLeft(grand);
        }
    }

    private void afterRemove(Node<K,V> node, Node<K,V> replaceNode) {

        //如果符合情况1，被删除节点是红色节点，那么直接删除即可
        if (isRed(node)) return;

        //如果符合情况2，被删除节点的替代节点是红色节点，那么将替代节点染成黑色即可
        if (isRed(replaceNode)){
            black(replaceNode);
            return;
        }

        //符合情况三，被删除节点是黑色叶子节点
        Node<K,V> parent = node.parent;

        //3.1 被删除节点是根节点，那么直接删除即可
        if (parent == null) return;

        // 判断被删除的node是左还是右
        boolean left = parent.left == null || node.isLeftChild();
        Node<K,V> sibling = left ? parent.right : parent.left;
        // 黑色叶子节点被删除后，会导致B树节点下溢
        if (left){  //被删除的节点在左边，兄弟节点在右边
            // 3.2 兄弟节点是红色
            // 染色：兄弟节点染成黑色，父节点染成红色
            // 旋转：父节点左旋，让兄弟节点的左子节点成为兄弟节点，让原来的兄弟节点成为祖父节点
            if (isRed(sibling)){
                black(sibling);
                red(parent);
                rotateLeft(parent);
                //更换兄弟节点
                sibling = parent.right;
            }

            // 兄弟节点必然是黑色，
            // 3.3 如果兄弟节点至少有一个红色子节点，可以向兄弟节点借一个
            if (isRed(sibling.left) || isRed(sibling.right)){
                // 兄弟节点的左侧是红色子节点，
                // 符合RL的情况，让兄弟节点先左旋，使红色子节点成为新的兄弟节点
                if (isBlack(sibling.right)){
                    rotateLeft(sibling);
                    sibling = parent.right;
                }

                //染色
                color(sibling,colorOf(parent));
                black(parent);
                black(sibling.right);

                //父节点右旋
                rotateLeft(parent);
            }else{
                // 3.4 兄弟节点没有一个红色子节点，父节点向下合并
                boolean parentBlack = isBlack(parent);
                red(sibling);
                black(parent);
                //如果parent是黑色节点，会导致parent也下溢
                if (parentBlack){
                    afterRemove(parent,null);
                }
            }
        }else { //被删除的节点在右边，兄弟节点在左边

            // 3.2 兄弟节点是红色
            // 染色：兄弟节点染成黑色，父节点染成红色
            // 旋转：父节点右旋，让兄弟节点的右子节点成为兄弟节点，让原来的兄弟节点成为祖父节点
            if (isRed(sibling)){
                black(sibling);
                red(parent);
                rotateRight(parent);
                //更换兄弟节点
                sibling = parent.left;
            }

            // 兄弟节点必然是黑色，
            // 3.3 如果兄弟节点至少有一个红色子节点，可以向兄弟节点借一个
            if (isRed(sibling.left) || isRed(sibling.right)){
                // 兄弟节点的右侧是红色子节点，
                // 符合LR的情况，让兄弟节点先左旋，使红色子节点成为新的兄弟节点
                if (isBlack(sibling.left)){
                    rotateLeft(sibling);
                    sibling = parent.left;
                }

                //染色
                color(sibling,colorOf(parent));
                black(parent);
                black(sibling.left);

                //父节点右旋
                rotateRight(parent);
            }else{
                // 3.4 兄弟节点没有一个红色子节点，父节点向下合并
                boolean parentBlack = isBlack(parent);
                red(sibling);
                black(parent);
                //如果parent是黑色节点，会导致parent也下溢
                if (parentBlack){
                    afterRemove(parent,null);
                }
            }
        }
    }

    //左旋
    private void rotateLeft(Node<K,V> grand){
        Node<K,V> parent = grand.right;
        Node<K,V> child = parent.left;
        grand.right = child;
        parent.left = grand;
        afterRote(grand,parent,child);
    }

    //右旋
    private void rotateRight(Node<K,V> grand){
        Node<K,V> parent = grand.left;
        Node<K,V> child = parent.right;
        grand.left = child;
        parent.right = grand;
        afterRote(grand,parent,child);
    }

    private void afterRote(Node<K,V> grand, Node<K,V> parent, Node<K,V> child){

        // 更新parent的父节点
        parent.parent = grand.parent;

        if (grand.isLeftChild()){
            grand.parent.left = parent;
        }else if(grand.isRightChild()){
            grand.parent.right = parent;
        }else {
            root = parent;
        }

        //更新child
        if (child != null){
            child.parent = grand;
        }

        //更新grand的父节点
        grand.parent = parent;
    }

    /**
     * 找到后继节点
     */
    public Node<K,V> successor(Node<K,V> node){
        if(node == null) return null;
        if (node.right != null){
            Node<K,V> rightNode = node.right;
            while (rightNode.left != null){
                rightNode = rightNode.left;
            }
            return rightNode;
        }

        while (node.parent != null && node == node.parent.right){
            node = node.parent;
        }
        return node.parent;
    }

    /**
     * 将节点染色
     * @param node
     * @param color
     * @return 染色后的节点
     */
    private Node<K,V> color(Node<K,V> node, boolean color){
        if (node == null) return node;
        node.color = color;
        return node;
    }

    /**
     * 将节点染成红色
     * @param node
     * @return
     */
    private Node<K,V> red(Node<K,V> node){
        return color(node,RED);
    }

    /**
     * 将节点染成黑色
     * @param node
     * @return
     */
    private Node<K,V> black(Node<K,V> node){
        return color(node,BLACK);
    }

    /**
     * 返回节点的颜色
     * @param node
     * @return
     */
    private boolean colorOf(Node<K,V> node){
        return node == null ? BLACK: node.color;
    }

    /**
     * 判断节点是否是黑色节点
     * @param node
     * @return
     */
    private boolean isBlack(Node<K,V> node){
        return colorOf(node) == BLACK;
    }

    /**
     * 判断节点是否是红色节点
     * @param node
     * @return
     */
    private boolean isRed(Node<K,V> node){
        return colorOf(node) == RED;
    }

    private static class Node<K,V>{
        public K key;
        public V value;
        public Node<K,V> left;
        public Node<K,V> right;
        public Node<K,V> parent;
        boolean color = RED;
        public Node(K key, V value, Node<K,V> parent){
            this.key = key;
            this.value = value;
            this.parent = parent;
        }

        /**
         * 是否是叶子节点
         * @return
         */
        public boolean isLeaf() {
            return left == null && right == null;
        }

        /**
         * 是否有两个子树
         * @return
         */
        public boolean hasTwoChildren() {
            return left != null && right != null;
        }

        /**
         * 是否是父节点的左子节点
         * @return
         */
        public boolean isLeftChild() {
            return parent != null && this == parent.left;
        }

        /**
         * 是否是父节点的右子节点
         * @return
         */
        public boolean isRightChild() {
            return parent != null && this == parent.right;
        }

        /**
         * 返回兄弟节点
         * @return 返回兄弟节点
         */
        public Node<K,V> sibling(){
            if (isLeftChild()) {
                return parent.right;
            }

            if (isRightChild()) {
                return parent.left;
            }
            return null;
        }

    }

}

TreeMap分析

• 时间复杂度（平均）
  添加、删除、搜索的平均时间复杂度都是O(logn)
• 特点
  • key必须具备可比较性
  • 元素的分布是有顺序的

在实际应用中，很多时候的需求是，Map中存储的元素不需要讲究顺序、key不需要具备可比较性，

如果不考虑顺序、不考虑key的可比较性，Map有更好的实现方案，平均时间复杂度可以达到O(1)，那就是采取哈希表来实现Map