Version: Next

映射 Map

Map 在一些编程语言中也叫做字典 (Dictionary)

接口设计

方法	功能
int size()	元素数目
void clear()	清空
V put(K key, V value)	插入
V get(K key)	获取
V remove(K key)	删除
boolean containsKey(K key)	包含键
boolean containsValue(V value)	包含值
void traversal(Visitor<K, V> visitor)	观察者模式

可以直接利用链表、二叉搜索树等数据结构来实现

创建接口

MyMap 接口

public interface MyMap<K, V> {
    int size();

    void clear();

    V put(K key, V value);

    V get(K key);

    V remove(K key);

    boolean containsKey(K key);

    boolean containsValue(V value);

    void traversal(Visitor<K, V> visitor);

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

红黑树实现

TreeMap

架构

public class MyTreeMap<K, V> implements MyMap<K, V> {
    private static final boolean RED = false;
    private static final boolean BLACK = true;

    private Comparator<K> comparator = null;

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

    public int size;
    public Node<K, V> rootNode;


    public boolean isEmpty() {
        return this.size == 0;
    }

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

    @Override
    public void clear() {
        rootNode = null;
        size = 0;
    }

    @Override // 返回被覆盖掉的旧值
    public V put(K key, V value) {
      return null;
    }

    @Override
    public V get(K key) {
        return null;
    }

    @Override
    public V remove(K key) {
        return null;
    }

    @Override
    public boolean containsKey(K key) {
        return false;
    }

    @Override
    public boolean containsValue(V value) {
        return false;
    }

    @Override
    public void traversal(Visitor<K, V> visitor) {

    }

    protected Node<K, V> createNode(K key, V value, Node<K, V> parentNode) {
        return new Node<>(key, value, parentNode);
    }

    private void afterPut(Node<K, V> newNode) {
        Node<K, V> parentNode = newNode.parentNode;

        if (parentNode == null) {
            black(newNode); // 添加的是根节点，设置为黑色
            return;
        }
        // 处理不需要额外操作的4种情况，即parent为black的情况
        if (isBlack(parentNode)) return;// 父节点为黑，不需要做任何处理
        // 叔父节点
        Node<K, V> uncle = parentNode.sibling();
        // 祖父节点
        Node<K, V> grand = parentNode.parentNode;
        // 处理uncle不是red的4种情况
        if (isRed(uncle)) { // 如果uncle是红色
            // 仅需染色
            // parent、uncle染为黑色
            black(parentNode);
            black(uncle);
            // grand作为新节点添加上上层节点
            // 染为红色，递归添加
            afterPut(red(grand));
            return;
        }

        // uncle不是Red的4中情况，涉及旋转，旋转实现与AVL树一模一样
        if (parentNode == grand.leftNode) { // L
            if (newNode == parentNode.leftNode) { // LL
                // parent染为黑色，grand染为红色
                black(parentNode);
                red(grand);
                // grand右旋
                rotateRight(grand);
            } else if (newNode == parentNode.rightNode) { // LR
                // 自己染为黑色，grand染为红色，
                black(newNode);
                red(grand);
                // parent左旋，grand右旋
                rotateLeft(parentNode);
                rotateRight(grand);
            }
        } else if (parentNode == grand.rightNode) {  // R
            if (newNode == parentNode.leftNode) { // RL
                // 自己染为黑色，grand染为红色，
                black(newNode);
                red(grand);
                // parent右旋，grand左旋
                rotateRight(parentNode);
                rotateLeft(grand);
            } else if (newNode == parentNode.rightNode) { // RR
                // parent染为黑色，grand染为红色
                black(parentNode);
                red(grand);
                // grand左旋
                rotateLeft(grand);
            }
        }
    }

    // 判断节点颜色
    private boolean colorOf(Node<K, V> node) {
        return node == null ? BLACK : (node).color;
    }

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

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

    // 给节点着色
    private Node<K, V> color(Node<K, V> node, boolean color) {
        if (node != null) (node).color = color;
        return node;
    }

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

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

    //旋转
    private void rotateLeft(Node<K, V> g) { // 可认为是g
        Node<K, V> p = g.rightNode; // aka p
        //        g.rightNode = p.leftNode; // 1.
        Node<K, V> child = p.leftNode;
        g.rightNode = child; // 1.
        p.leftNode = g; // 2.
        afterRotate(g, p, child);
    }

    // 右旋转
    private void rotateRight(Node<K, V> g) {
        Node<K, V> p = g.leftNode;
        //        g.leftNode = p.rightNode;
        Node<K, V> child = p.rightNode;
        g.leftNode = child;
        p.rightNode = g;
        afterRotate(g, p, child);
    }

    private void afterRotate(Node<K, V> g, Node<K, V> p, Node<K, V> child) {
        // p 成为子树根节点
        if (g.isLeftChild())
            g.parentNode.leftNode = p;
        else if (g.isRightChild())
            g.parentNode.rightNode = p;
        else
            rootNode = p; // p成为整棵树的根节点
        // 维护父节点 T2、g、p
        p.parentNode = g.parentNode;
        g.parentNode = p;
        if (child != null)// aka t2
            child.parentNode = g;
    }

    private void keyNotNullCheck(K key) {
        if (key == null) throw new IllegalArgumentException("节点 KEY 不能为空");
    }

    /**
     * 比较两个元素的大小
     *
     * @param key1 元素1
     * @param key2 元素2
     * @return 0: 表示 element1等于element2; 大于0 代表 element1 > element2; 小于0: element1 < element2
     */
    private int compare(K key1, K key2) {
        if (this.comparator != null) // 存在外部传入的比较器
            return this.comparator.compare(key1, key2);
        else // 没有外部比较器，强制使用Comparable
            return ((Comparable<K>) key1).compareTo(key2); // 强制类型转换为Comparable实现类
    }

    // 红黑树节点
    private static class Node<K, V> {

        K key;
        V value;
        boolean color = RED; // 默认为红色

        Node<K, V> leftNode;
        Node<K, V> rightNode;
        Node<K, V> parentNode; // 父节点

        /**
         * 构造方法
         * 传入节点值并制定父节点，不适用左右节点，因为左右节点是否存在的情况比较复杂，
         * 而一颗树中，只有根节点没有父节点，其余节点都有父节点
         */
        public Node(K key, V value, Node<K, V> parentNode) {
            this.key = key;
            this.value = value;
            this.parentNode = parentNode;
        }

        public boolean isLeaf() {
            return leftNode == null && rightNode == null;
        }

        /**
         * 返回节点是否有两个孩子
         */
        public boolean hasTwoChildren() {
            return leftNode != null && rightNode != null;
        }

        // 返回节点的兄弟节点
        public Node<K, V> sibling() {
            if (isLeftChild()) return parentNode.rightNode;
            if (isRightChild()) return parentNode.leftNode;
            return null;
        }

        public boolean isLeftChild() {
            return parentNode != null && this == parentNode.leftNode;
        }

        public boolean isRightChild() {
            return parentNode != null && this == parentNode.rightNode;
        }
    }
}

put

基于 KEY 进行比较，如果旧值被覆盖，那么将旧值返回

public V put(K key, V value) {
    // 非空判断
    keyNotNullCheck(key);

    // 判断根节点是否存在
    if (this.rootNode == null) {
//            this.rootNode = new Node<>(element, null);
        this.rootNode = createNode(key, value, null);
        size++;
        afterPut(rootNode); // 平衡
        return null; // 没有旧值
    }

    // 根节点已经存在
    // 1. 找到父节点
    Node<K, V> currentNode = rootNode; // 当前正在比较的树节点
    Node<K, V> parentNode = null; // 记录当前节点的父节点
    int compareResult = 0; // 比较大小的结果
    // 一直往下找
    while (currentNode != null) {
        compareResult = compare(key, currentNode.key); // 比较大小
        // 在currentNode向下迭代之前，先记录它，等current迭代之后，这个记录值就成了current的parent
        parentNode = currentNode;

        if (compareResult < 0) { // element < 当前节点
            // 找左节点
            currentNode = currentNode.leftNode;
        } else if (compareResult > 0) { // element > 当前节点
            // 找右节点
            currentNode = currentNode.rightNode;
        } else { // 相等 覆盖旧节点
            V oldValue = currentNode.value;
            currentNode.value = value;
            return oldValue;
        }
    }
    // 跳出循环，已经走到了树的叶子节点，此时currentNode一定指向null，parent就是current的爸爸
    // 2. 创建新节点
    Node<K, V> newNode = createNode(key, value, parentNode);
    // 3. parent.left 或 parent.right指向创建的节点
    if (compareResult > 0) // 插入到父节点的右
        parentNode.rightNode = newNode;
    else // 插入到父节点的左
        parentNode.leftNode = newNode;

    size++;
    afterPut(newNode); // 平衡

    return null;
}

映射 Map#

接口设计#

创建接口#

红黑树实现#

架构#

put#

映射 Map

接口设计

创建接口

红黑树实现

架构

put