侧边栏壁纸
博主头像
Dioxide-CN博主等级

茶边话旧,看几许星迢露冕,从淮海南来。

  • 累计撰写 54 篇文章
  • 累计创建 30 个标签
  • 累计收到 24 条评论

目 录CONTENT

文章目录

Map接口

Dioxide-CN
2023-01-08 / 0 评论 / 3 点赞 / 30 阅读 / 1,266 字
温馨提示:
本文最后更新于 2023-01-08,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

Map接口

Map集合的特点

  1. 能够存储唯一的列数据(唯一,不可重复)Set
  2. 能够存储可以重复的数据(可重复)List
  3. 值的顺序取决于键的顺序
  4. 键和值都可以存储 null 元素

TreeMap

image-1673188128382

本质上就是红黑树的实现:

  1. 每个节点要么是红色要么是黑色
  2. 根节点必须是黑色
  3. 每个叶子节点(空节点)是黑色
  4. 每个红色节点的两个子节点必须是黑色
  5. 任意节点到每个叶子节点的路径包含相同数量的黑色节点
private static final boolean RED   = false;
private static final boolean BLACK = true;

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;                 /* key     */
    V value;               /* value   */
    Entry<K,V> left;       /* 左节点   */
    Entry<K,V> right;      /* 右节点   */
    Entry<K,V> parent;     /* 父节点   */
    boolean color = BLACK; /* 节点颜色 */
}

put()方法

public V put(K key, V value) {  
    return put(key, value, true);  
}

private V put(K key, V value, boolean replaceOld) {
	// 将 root 赋值给局部变量 null
    Entry<K,V> t = root;
    if (t == null) {
	    // 初始操作
        addEntryToEmptyMap(key, value);
        return null;
    }
    int cmp;
    Entry<K,V> parent; // 父节点
    Comparator<? super K> cpr = comparator; // 获取比较器
    if (cpr != null) {
	    // t 是迭代过程中的插入节点父节点的循环节点
        do {
	        // 将 root 赋值给 parent 节点
            parent = t;
            // 和 root 节点比较值的大小
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left; // 父节点的左子节点赋给 t
            else if (cmp > 0)
                t = t.right; // 父节点的右子节点赋给 t
            else {
	            // 和父节点的 key 相等直接修改值
                V oldValue = t.value;
                if (replaceOld || oldValue == null) {
                    t.value = value;
                }
                // 将修改前的值进行返回
                return oldValue;
            }
        } while (t != null);
        // 一直向下找,直到完成插入操作
    } else {
        Objects.requireNonNull(key);
        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
        // 同样的逻辑但是使用的是自定义的比较器
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else {
                V oldValue = t.value;
                if (replaceOld || oldValue == null) {
                    t.value = value;
                }
                return oldValue;
            }
        } while (t != null);
    }
    // 将插入的 key value 封装成一个 Entry 对象
    addEntry(key, value, parent, cmp < 0);
    return null;
}

private void addEntryToEmptyMap(K key, V value) {
	// 检查 key 是否为空
    compare(key, key);
	// 将要添加的 key value 封装为一个 Entry 对象并赋值给 root 对象
    root = new Entry<>(key, value, null);  
    size = 1; // 容量设置为 1
    modCount++;  
}

private void addEntry(K key, V value, Entry<K, V> parent, boolean addToLeft) {  
    Entry<K,V> e = new Entry<>(key, value, parent);  
    if (addToLeft)
        parent.left = e; // 插入的节点在 parent 节点的左侧
    else
        parent.right = e; // 插入的节点在 parent 节点的右侧
    fixAfterInsertion(e); // 实现红黑树的平衡
    size++; // size 增加
    modCount++;
}

对插入操作结束后,会对红黑树进行一次平衡操作 fixAfterInsertion() 即对左右子树进行旋转操作。

红黑树的平衡操作

private void fixAfterInsertion(Entry<K,V> x) {
	// 设置添加节点的颜色为红色
    x.color = RED;
    // 循环的条件:添加的节点不为空,不是root节点,父节点的颜色为红色
    while (x != null && x != root && x.parent.color == RED) {
	    // 父节点是祖父节点的左节点
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
	        // 获取父节点的兄弟节点 叔叔节点
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            // 叔叔节点是红色
            if (colorOf(y) == RED) {
	            // 设置父节点为黑色
                setColor(parentOf(x), BLACK);
	            // 设置叔叔节点为黑色
                setColor(y, BLACK);
                // 设置祖父节点的颜色为红色
                setColor(parentOf(parentOf(x)), RED);
                // 将祖父节点设置为插入节点在下一次循环中再做一次平衡
                x = parentOf(parentOf(x));
            // 叔叔节点是黑色
            } else {
				// 判断插入节点是否为父节点的右侧节点
                if (x == rightOf(parentOf(x))) {
	                // 将父节点作为插入节点
                    x = parentOf(x);
                    // 左旋 必然伴随父节点的右旋
                    rotateLeft(x);
                }
                // 设置父节点为黑色
                setColor(parentOf(x), BLACK);
	            // 设置祖父节点的颜色为红色
                setColor(parentOf(parentOf(x)), RED);
                // 右旋
                rotateRight(parentOf(parentOf(x)));
            }
		// 父节点是祖父节点的右节点
        } else {
	        // 获取父节点的兄弟节点 叔叔节点
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            // 叔叔节点为红色
            if (colorOf(y) == RED) {
	            // 变色处理
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
	            // 插入节点在父节点的右侧
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);
                    // 右旋
                    rotateRight(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                // 左旋
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    // 根节点颜色设置为黑色
    root.color = BLACK;
}

红黑树的左旋和右旋

左旋

// 左旋
private void rotateLeft(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> r = p.right;
        p.right = r.left;
        if (r.left != null)
            r.left.parent = p;
        r.parent = p.parent;
        if (p.parent == null)
            root = r;
        else if (p.parent.left == p)
            p.parent.left = r;
        else
            p.parent.right = r;
        r.left = p;
        p.parent = r;
    }
}

右旋

// 右旋
private void rotateRight(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> l = p.left;
        p.left = l.right;
        if (l.right != null) l.right.parent = p;
        l.parent = p.parent;
        if (p.parent == null)
            root = l;
        else if (p.parent.right == p)
            p.parent.right = l;
        else p.parent.left = l;
        l.right = p;
        p.parent = l;
    }
}
3

评论区