【数据结构】映射 TreeMap，HashMap，LinkedHashMap 代码

╰半夏微凉° 2022-11-06 07:00 157阅读 0赞

### 映射 TreeMap，HashMap，LinkedHashMap 代码 ###

*  Map的接口定义 Map.java
 *  红黑树 RBTree 实现 TreeMap
 *   *  TreeMap 分析
 *  哈希表实现 HashMap
 *  HashMap 升级为 LinkedHashMap
 *   *  LinkedHashMap – 删除注意点
     *  LinkedHashMap 完整代码

映射的特点：

*  Map 在有些编程语言中也叫做字典（dictionary，比如 Python）
 *  Map 中的每一个 Key 是唯一的
 *  Map 中的每一个 Key 对应一个 Value  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70]  
    类似 Set，Map 可以直接利用之前学习的链表、二叉搜索树（[AVL树][AVL]、[红黑树][Link 1]）等数据结构来实现

# Map的接口定义 Map.java #

public interface Map<K, V> {
        
    
    	int size();
    	
    	boolean isEmpty();
    	
    	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;
    		public abstract boolean visit(K key, V value);
    	}
    	
    }

# 红黑树 RBTree 实现 TreeMap #

通过 [RBTree][] 实现的 TreeMap。

/**
     * 直接由红黑树实现的映射
     */
    public class TreeMap<K, V> implements Map<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 TreeMap() {
        
    		this(null);
    	}
    	public TreeMap(Comparator<K> comparator) {
        
    		this.comparator = comparator;
    	}
    	
    	/**
    	 * 存放 key 和 value 的红黑树节点类
    	 */
    	private static class Node<K, V> {
        
    		K key;
    		V value;
    		boolean color = RED;
    		Node<K, V> left;
    		Node<K, V> right;
    		Node<K, V> parent;
    		public Node(K key, V value, Node<K, V> parent) {
        
    			this.key = key;
    			this.value = value;
    			this.parent = parent;
    		}
    		public boolean isLeaf() {
         // 是否为叶子结点
    			return left == null && right == null;
    		}
    		
    		public boolean hasTwoChildren() {
         // 是否有两个子节点
    			return left != null && right != null;
    		}
    		
    		public boolean isLeftChild() {
         // 是否为左节点
    			return parent != null && this == parent.left;
    		}
    		
    		public boolean isRightChild() {
         // 是否为右节点
    			return parent != null && this == parent.right;
    		}
    		
    		public Node<K, V> sibling() {
         // 返回兄弟节点
    			if (isLeftChild()) {
        
    				return parent.right;
    			}
    			
    			if (isRightChild()) {
        
    				return parent.left;
    			}
    			return null;
    		}
    	}
    	
    	public int size() {
        
    		return size;
    	}
    
    	public boolean isEmpty() {
        
    		return size == 0;
    	}
    
    	public void clear() {
        
    		root = null;
    		size = 0;
    	}
    
    	public V put(K key, V value) {
        
    		KeyNotNullCheck(key); // 传入元素不能为空
    		
    		// 添加第一个节点
    		if (root == null) {
        
    			root = new Node<>(key, value, null);
    			size++;
    
    			// 新添加节点之后的处理
    			// BST中无需处理，为 AVL树 和 B树提供可覆盖的方法
    			afterPut(root);
    			return null;
    		}
    		
    		// 添加的不是第一个节点
    		// 找到父节点
    		Node<K, V> parent = root;
    		Node<K, V> node = root;
    		int cmp = 0;
    		do {
        
    			cmp = compare(key, node.key);
    			parent = node;
    			if (cmp > 0) {
        
    				node = node.right;
    			} else if (cmp < 0) {
        
    				node = node.left;
    			} else {
         // 相等
    				// 相等时的操作按需求来定，这里选择了覆盖
    				node.key = key;
    				V oldValue = node.value;
    				node.value = value;
    				return oldValue;
    			}
    		} while (node != null);
    
    		// 通过上面的while循环找到了要插入节点的父节点
    		// 看看插入到父节点的哪个位置
    		Node<K, V> newNode = new Node(key, value, parent);
    		if (cmp > 0) {
        
    			parent.right = newNode;
    		} else {
        
    			parent.left = newNode;
    		}
    		size++;
    		
    		// 新添加节点之后的处理
    		// BST中无需处理，为 AVL树 和 B树提供可覆盖的方法
    		afterPut(newNode);
    		return null;
    	}
    
    	public V get(K key) {
        
    		Node<K, V> node = node(key);
    		return node != null ? node.value : null;
    	}
    
    	public V remove(K key) {
        
    		return remove(node(key));
    	}
    	private V remove(Node<K, V> node) {
        
    		if (node == null) return null;
    		Node<K, V> oldNode = node;
    		size--;
    		
    		if (node.hasTwoChildren()) {
         // 度为2的节点
    			// 找到后继节点
    			Node<K, V> s = successor(node);
    			// 用后继节点的值覆盖度为2的节点的值
    			node.key = s.key;
    			node.value = s.value;
    			// 删除后继节点
    			// 这里是因为后面必然会删除node节点
    			// 所以直接将后继节点赋给node,在后面将它删除
    			node = s;
    		}
    		
    		// 删除node节点（node的度必然是1或者0）
    		Node<K, V> replacement = node.left != null ? node.left : node.right;
    		
    		if (replacement != null) {
         // node是度为1的节点
    			// 核心：用子节点替代原节点的位置
    			// 更改parent
    			replacement.parent = node.parent;
    			// 更改parent的left、right的指向
    			if (node.parent == null) {
         // node是度为1的节点并且是根节点
    				root = replacement;
    			} else if (node == node.parent.left) {
        
    				node.parent.left = replacement;
    			} else {
         // node == node.parent.right
    				node.parent.right = replacement;
    			}
    			
    			// 删除节点之后的处理，BST中无需处理，为 AVL树 和 B树提供可覆盖的方法
    			afterRemove(replacement);
    		} else if (node.parent == null) {
         // node是叶子节点并且是根节点
    			root = null;
    			
    			// 删除节点之后的处理，BST中无需处理，为 AVL树 和 B树提供可覆盖的方法
    			afterRemove(node);
    		} else {
         // node是叶子节点，但不是根节点
    			if (node == node.parent.left) {
         // 是左子树
    				node.parent.left = null;
    			} else {
         // node == node.parent.right // 是右子树
    				node.parent.right = null;
    			}
    			
    			// 删除节点之后的处理，BST中无需处理，为 AVL树 和 B树提供可覆盖的方法
    			afterRemove(node);
    		}
    		return oldNode.value;
    	}
    	
    	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(value, node.value)) return true;
    			
    			if(node.left != null){
        
    				queue.offer(node.left);
    			}
    			if(node.right != null){
        
    				queue.offer(node.right);
    			}
    		}
    		return false;
    	}
    	
    	public void traversal(Visitor<K, V> visitor) {
        
    		if (visitor == null) return;
    		traversal(root, visitor);
    	}
    	public 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);
    		
    	}
    	
    	private boolean valEquals(V v1, V v2) {
        
    		return v1 == null ? v2 == null : v1.equals(v2);
    	}
    	
    	protected Node<K, V> predecessor(Node<K, V> node) {
        
    		if (node == null) return null;
    		
    		// 前驱节点在左子树当中（left.right.right.right....）
    		Node<K, V> p = node.left;
    		if (p != null) {
        
    			while (p.right != null) {
        
    				p = p.right;
    			}
    			return p;
    		}
    		
    		// 从父节点、祖父节点中寻找前驱节点
    		while (node.parent != null && node == node.parent.left) {
        
    			node = node.parent;
    		}
    
    		// node.parent == null
    		// node == node.parent.right
    		return node.parent;
    	}
    	
    	protected Node<K, V> successor(Node<K, V> node) {
        
    		if (node == null) return null;
    		
    		// 前驱节点在左子树当中（right.left.left.left....）
    		Node<K, V> p = node.right;
    		if (p != null) {
        
    			while (p.left != null) {
        
    				p = p.left;
    			}
    			return p;
    		}
    		
    		// 从父节点、祖父节点中寻找前驱节点
    		while (node.parent != null && node == node.parent.right) {
        
    			node = node.parent;
    		}
    
    		return node.parent;
    	}
    	
    	private Node<K, V> node(K key) {
        
    		Node<K, V> node = root;
    		while (node != null) {
        
    			int cmp = compare(key, node.key);
    			if (cmp == 0) return node;
    			if (cmp > 0) {
        
    				node = node.right;
    			} else {
         // cmp < 0
    				node = node.left;
    			}
    		}
    		return null;
    	}
    	
    	private void afterRemove(Node<K, V> node) {
        
    		// 如果删除的节点是红色
    		// 或者 用以取代删除节点的子节点是红色
    		if (isRed(node)) {
        
    			black(node);
    			return;
    		}
    		
    		Node<K, V> parent = node.parent;
    		// 删除的是根节点
    		if (parent == null) return;
    		
    		// 删除的是黑色叶子节点【下溢】
    		// 判断被删除的node是左还是右
    		boolean left = parent.left == null || node.isLeftChild();
    		Node<K, V> sibling = left ? parent.right : parent.left;
    		if (left) {
         // 被删除的节点在左边，兄弟节点在右边
    			if (isRed(sibling)) {
         // 兄弟节点是红色
    				black(sibling);
    				red(parent);
    				rotateLeft(parent);
    				// 更换兄弟
    				sibling = parent.right;
    			}
    			
    			// 兄弟节点必然是黑色
    			if (isBlack(sibling.left) && isBlack(sibling.right)) {
        
    				// 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
    				boolean parentBlack = isBlack(parent);
    				black(parent);
    				red(sibling);
    				if (parentBlack) {
        
    					afterRemove(parent);
    				}
    			} else {
         // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
    				// 兄弟节点的左边是黑色，兄弟要先旋转
    				if (isBlack(sibling.right)) {
        
    					rotateRight(sibling);
    					sibling = parent.right;
    				}
    				
    				color(sibling, colorOf(parent));
    				black(sibling.right);
    				black(parent);
    				rotateLeft(parent);
    			}
    		} else {
         // 被删除的节点在右边，兄弟节点在左边
    			if (isRed(sibling)) {
         // 兄弟节点是红色
    				black(sibling);
    				red(parent);
    				rotateRight(parent);
    				// 更换兄弟
    				sibling = parent.left;
    			}
    			
    			// 兄弟节点必然是黑色
    			if (isBlack(sibling.left) && isBlack(sibling.right)) {
        
    				// 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
    				boolean parentBlack = isBlack(parent);
    				black(parent);
    				red(sibling);
    				if (parentBlack) {
        
    					afterRemove(parent);
    				}
    			} else {
         // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
    				// 兄弟节点的左边是黑色，兄弟要先旋转
    				if (isBlack(sibling.left)) {
        
    					rotateLeft(sibling);
    					sibling = parent.left;
    				}
    				
    				color(sibling, colorOf(parent));
    				black(sibling.left);
    				black(parent);
    				rotateRight(parent);
    			}
    		}
    	}
    	
    	private void afterPut(Node<K, V> node){
        
    		Node<K, V> parent = node.parent;
    		
    		// 添加的是根节点 或者 上溢到达了根节点
    		if (parent == null) {
        
    			black(node);
    			return;
    		}
    		
    		// 如果父节点是黑色，直接返回
    		if (isBlack(parent)) return;
    		
    		// 叔父节点
    		Node<K, V> uncle = parent.sibling();
    		// 祖父节点
    		Node<K, V> grand = red(parent.parent);
    		if (isRed(uncle)) {
         // 叔父节点是红色【B树节点上溢】
    			black(parent);
    			black(uncle);
    			// 把祖父节点当做是新添加的节点
    			afterPut(grand);
    			return;
    		}
    		
    		// 叔父节点不是红色
    		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 rotateLeft(Node<K, V> grand) {
        
    		Node<K, V> parent = grand.right;
    		Node<K, V> child = parent.left;
    		grand.right = child;
    		parent.left = grand;
    		afterRotate(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;
    		afterRotate(grand, parent, child);
    	}
    	
    	private void afterRotate(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 {
         // grand是root节点
    			root = parent;
    		}
    		
    		// 更新child的parent
    		if (child != null) {
        
    			child.parent = grand;
    		}
    		
    		// 更新grand的parent
    		grand.parent = parent;
    	}
    
    	private Node<K, V> color(Node<K, V> node, boolean color) {
        
    		if (node == null) return node;
    		node.color = color;
    		return node;
    	}
    	
    	private Node<K, V> red(Node<K, V> node) {
        
    		return color(node, RED);
    	}
    	
    	private Node<K, V> black(Node<K, V> node) {
        
    		return color(node, BLACK);
    	}
    	
    	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 int compare(K k1, K k2) {
        
    		if (comparator != null) {
        
    			return comparator.compare(k1, k2);
    		}
    		return ((Comparable<K>)k1).compareTo(k2);
    	}
    	
    	private void KeyNotNullCheck(K key) {
        
    		if (key == null) {
        
    			throw new IllegalArgumentException("key must not be null");
    		}
    	}
    
    }

## TreeMap 分析 ##

时间复杂度（平均）

*  添加、删除、搜索：O(logn)

特点

*  Key 必须具备可比较性
 *  元素的分布是有顺序的

在实际应用中，很多时候的需求

*  Map 中存储的元素不需要讲究顺序
 *  Map 中的 Key 不需要具备可比较性

不考虑顺序、不考虑 Key 的可比较性，Map 有更好的实现方案，平均时间复杂度可以达到 O(1)

*  那就是采取 哈希表 来实现 Map

# 哈希表实现 HashMap #

通过[哈希表][Link 2]实现 HashMap

@SuppressWarnings({
        "unchecked", "rawtypes"})
    public class HashMap<K, V> implements Map<K, V> {
        
    
        private static final boolean RED = false;
        private static final boolean BLACK = true;
        private int size;
        private Node<K, V>[] table;
        private static final int DEFAULT_CAPACITY = 1 << 4;		 // 数组初始容量
        private static final float DEFAULT_LOAD_FACTOR = 0.75f;  // 装载因子
    
        public HashMap() {
        
            table = new Node[DEFAULT_CAPACITY];
        }
    
        @Override
        public int size() {
        
            return size;
        }
    
        @Override
        public boolean isEmpty() {
        
            return size == 0;
        }
    
        @Override
        public void clear() {
        
            if (size == 0) return;
            size = 0;
            // 将数组的元素清空
            for (int i = 0; i < table.length; i++) {
        
                table[i] = null;
            }
            // Arrays.fill(table, null);
        }
    
        @Override
        public V put(K key, V value) {
        
            resize();
    
            int index = index(key);
            // 取出index位置的红黑树根节点
            Node<K, V> root = table[index];
            if (root == null) {
        
                root = createNode(key, value, null);
                table[index] = root;
                size++;
                fixAfterPut(root);
                return null;
            }
    
            // 来到这里说明，root不为空，
            // 即添加新的节点到红黑树上面
            Node<K, V> parent = root;
            Node<K, V> node = root;
            int cmp = 0;
            K k1 = key;
            int h1 = hash(k1);
            Node<K, V> result = null;
            boolean searched = false; // 是否已经搜索过这个key
            do {
        
                parent = node;
                K k2 = node.key;
                int h2 = node.hash;
                if (h1 > h2) {
        
                    cmp = 1;
                } else if (h1 < h2) {
        
                    cmp = -1;
                } else if (Objects.equals(k1, k2)) {
        
                    cmp = 0;
                } else if (k1 != null && k2 != null
                        && k1 instanceof Comparable
                        && k1.getClass() == k2.getClass()
                        && (cmp = ((Comparable) k1).compareTo(k2)) != 0) {
        
                } else if (searched) {
         // 已经扫描了
                    cmp = System.identityHashCode(k1) < System.identityHashCode(k2) ? -1 : 1;
                } else {
         // searched == false; 还没有扫描，然后再根据内存地址大小决定左右
                    if ((node.left != null && (result = node(node.left, k1)) != null)
                            || (node.right != null && (result = node(node.right, k1)) != null)) {
        
                        // 已经存在这个key
                        node = result;
                        cmp = 0;
                    } else {
         // 不存在这个key
                        searched = true;
                        cmp = System.identityHashCode(k1) < System.identityHashCode(k2) ? -1 : 1;
                    }
                }
    
                if (cmp > 0) {
        
                    node = node.right;
                } else if (cmp < 0) {
        
                    node = node.left;
                } else {
         // 相等
                    V oldValue = node.value;
                    node.key = key;
                    node.value = value;
                    node.hash = h1;
                    return oldValue;
                }
            } while (node != null);
    
            // 看看插入到父节点的哪个位置
            Node<K, V> newNode = createNode(key, value, parent);
            if (cmp > 0) {
        
                parent.right = newNode;
            } else {
        
                parent.left = newNode;
            }
            size++;
    
            // 新添加节点之后的处理
            fixAfterPut(newNode);
            return null;
        }
    
        @Override
        public V get(K key) {
        
            Node<K, V> node = node(key);
            return node != null ? node.value : null;
        }
    
        @Override
        public V remove(K key) {
        
            return remove(node(key));
        }
    
        @Override
        public boolean containsKey(K key) {
        
            return node(key) != null;
        }
    
        @Override
        public boolean containsValue(V value) {
        
            if (size == 0) return false;
            Queue<Node<K, V>> queue = new LinkedList<>();
            for (int i = 0; i < table.length; i++) {
        
                if (table[i] == null) continue;
    
                queue.offer(table[i]);
                while (!queue.isEmpty()) {
        
                    Node<K, V> node = queue.poll();
                    if (Objects.equals(value, node.value)) return true;
    
                    if (node.left != null) queue.offer(node.left);
                    if (node.right != null) queue.offer(node.right);
    
                }
            }
            return false;
        }
    
        @Override
        public void traversal(Visitor<K, V> visitor) {
        
            if (size == 0 || visitor == null) return;
    
            Queue<Node<K, V>> queue = new LinkedList<>();
            for (int i = 0; i < table.length; i++) {
        
                if (table[i] == null) continue;
    
                queue.offer(table[i]);
                while (!queue.isEmpty()) {
        
                    Node<K, V> node = queue.poll();
                    if (visitor.visit(node.key, node.value)) return;
    
                    if (node.left != null) queue.offer(node.left);
                    if (node.right != null) queue.offer(node.right);
                }
            }
        }
    
    
        protected Node<K, V> createNode(K key, V value, Node<K, V> parent) {
        
            return new Node<>(key, value, parent);
        }
    
        protected void afterRemove(Node<K, V> willNode, Node<K, V> removedNode) {
        
        }
    
        /**
         * 当扩容为原来容量的2倍时，节点的索引右两种情况：
         * 扩容为2^3
         * 
         * 1、索引保持不变
         * 	 1010    1010
         * &   11     111
         * ----------------
         *     10     010
         * 
         * 2、新index = 原来的索引 + 旧数组容量
         *   1110    1110
         * &   11     111
         * ----------------
         *     10     110
         */
        private void resize() {
        
            // 装填因子 <= 0.75
            if (size / table.length <= DEFAULT_LOAD_FACTOR) return;
    
            Node<K, V>[] oldTable = table;
            table = new Node[oldTable.length << 1];
    
            Queue<Node<K, V>> queue = new LinkedList<>();
            for (int i = 0; i < oldTable.length; i++) {
        
                if (oldTable[i] == null) continue;
    
                queue.offer(oldTable[i]);
                while (!queue.isEmpty()) {
        
                    Node<K, V> node = queue.poll();
                    if (node.left != null) {
        
                        queue.offer(node.left);
                    }
                    if (node.right != null) {
        
                        queue.offer(node.right);
                    }
    
                    // 挪动代码得放到最后面
                    moveNode(node);
                }
            }
        }
    
        private void moveNode(Node<K, V> newNode) {
        
            // 重置
            newNode.parent = null;
            newNode.left = null;
            newNode.right = null;
            newNode.color = RED;
    
            int index = index(newNode);
            // 取出index位置的红黑树根节点
            Node<K, V> root = table[index];
            if (root == null) {
        
                root = newNode;
                table[index] = root;
                fixAfterPut(root);
                return;
            }
    
            // 添加新的节点到红黑树上面
            Node<K, V> parent = root;
            Node<K, V> node = root;
            int cmp = 0;
            K k1 = newNode.key;
            int h1 = newNode.hash;
            do {
        
                parent = node;
                K k2 = node.key;
                int h2 = node.hash;
                if (h1 > h2) {
        
                    cmp = 1;
                } else if (h1 < h2) {
        
                    cmp = -1;
                } else if (k1 != null && k2 != null
                        && k1 instanceof Comparable
                        && k1.getClass() == k2.getClass()
                        && (cmp = ((Comparable) k1).compareTo(k2)) != 0) {
        
                } else {
        
                    cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
                }
    
                if (cmp > 0) {
        
                    node = node.right;
                } else if (cmp < 0) {
        
                    node = node.left;
                }
            } while (node != null);
    
            // 看看插入到父节点的哪个位置
            newNode.parent = parent;
            if (cmp > 0) {
        
                parent.right = newNode;
            } else {
        
                parent.left = newNode;
            }
    
            // 新添加节点之后的处理
            fixAfterPut(newNode);
        }
    
        protected V remove(Node<K, V> node) {
        
            if (node == null) return null;
    
            Node<K, V> willNode = node;
    
            size--;
    
            V oldValue = node.value;
    
            if (node.hasTwoChildren()) {
         // 度为2的节点
                // 找到后继节点
                Node<K, V> s = successor(node);
                // 用后继节点的值覆盖度为2的节点的值
                node.key = s.key;
                node.value = s.value;
                node.hash = s.hash;
                // 删除后继节点
                node = s;
            }
    
            // 删除node节点（node的度必然是1或者0）
            Node<K, V> replacement = node.left != null ? node.left : node.right;
            int index = index(node);
    
            if (replacement != null) {
         // node是度为1的节点
                // 更改parent
                replacement.parent = node.parent;
                // 更改parent的left、right的指向
                if (node.parent == null) {
         // node是度为1的节点并且是根节点
                    table[index] = replacement;
                } else if (node == node.parent.left) {
        
                    node.parent.left = replacement;
                } else {
         // node == node.parent.right
                    node.parent.right = replacement;
                }
    
                // 删除节点之后的处理
                fixAfterRemove(replacement);
            } else if (node.parent == null) {
         // node是叶子节点并且是根节点
                table[index] = null;
            } else {
         // node是叶子节点，但不是根节点
                if (node == node.parent.left) {
        
                    node.parent.left = null;
                } else {
         // node == node.parent.right
                    node.parent.right = null;
                }
    
                // 删除节点之后的处理
                fixAfterRemove(node);
            }
    
            // 交给子类去处理
            afterRemove(willNode, node);
    
            return oldValue;
        }
    
        private Node<K, V> successor(Node<K, V> node) {
        
            if (node == null) return null;
    
            // 前驱节点在左子树当中（right.left.left.left....）
            Node<K, V> p = node.right;
            if (p != null) {
        
                while (p.left != null) {
        
                    p = p.left;
                }
                return p;
            }
    
            // 从父节点、祖父节点中寻找前驱节点
            while (node.parent != null && node == node.parent.right) {
        
                node = node.parent;
            }
    
            return node.parent;
        }
    
        private Node<K, V> node(K key) {
        
            Node<K, V> root = table[index(key)];
            return root == null ? null : node(root, key);
        }
    
        /**
         * equals 才是判断两个对象相等
         * compareTo 是比大小的，为0只能说明大小相等，不能代表两个对象相等
         *
         * @param node 查找的节点
         * @param k1   传入的额key
         */
        private Node<K, V> node(Node<K, V> node, K k1) {
        
            int h1 = hash(k1);
            // 存储查找结果
            Node<K, V> result = null;
            int cmp = 0;
            while (node != null) {
        
                K k2 = node.key; // 节点的key
                int h2 = node.hash; // 节点的hash值
                // 先比较hash值
                if (h1 > h2) {
        
                    node = node.right;
                } else if (h1 < h2) {
        
                    node = node.left;
                } else if (Objects.equals(k1, k2)) {
         // hash值相等，比较equals
                    return node; // 相等直接返回node
                } else if (k1 != null && k2 != null
                        && k1 instanceof Comparable // 具备可比较性
                        && k1.getClass() == k2.getClass() // 类型相同
                        && (cmp = ((Comparable) k1).compareTo(k2)) != 0
                ) {
         // hash值相等，equals不等，具备可比较性（跳过等于0的情况）
                    node = cmp > 0 ? node.right : node.left; // cmp不等于0，往左 或 往右查找
                } else if (node.right != null && (result = node(node.right, k1)) != null) {
         // hash值相等，equals不等，也不具备可比较性(或cmp=0)，只能遍历查找所有节点
                    return result;
                } else {
         // 只能往左边找
                    node = node.left;
                }
            }
            return null;
        }
    
        /**
         * 根据key生成对应的索引（在桶数组中的位置）
         */
        private int index(K key) {
        
            return hash(key) & (table.length - 1);
        }
    
        /**
         * 搅动计算，h ^ (h >>> 16) 使 h 的所有数字都参与计算
         */
        private int hash(K key) {
        
            if (key == null) return 0;
            int hash = key.hashCode();
            return hash ^ (hash >>> 16);
        }
    
        /**
         * 根据节点中的key生成对应的索引（在桶数组中的位置）
         */
        private int index(Node<K, V> node) {
        
            return node.hash & (table.length - 1);
        }
    
    
        private void fixAfterRemove(Node<K, V> node) {
        
            // 如果删除的节点是红色
            // 或者 用以取代删除节点的子节点是红色
            if (isRed(node)) {
        
                black(node);
                return;
            }
    
            Node<K, V> parent = node.parent;
            if (parent == null) return;
    
            // 删除的是黑色叶子节点【下溢】
            // 判断被删除的node是左还是右
            boolean left = parent.left == null || node.isLeftChild();
            Node<K, V> sibling = left ? parent.right : parent.left;
            if (left) {
         // 被删除的节点在左边，兄弟节点在右边
                if (isRed(sibling)) {
         // 兄弟节点是红色
                    black(sibling);
                    red(parent);
                    rotateLeft(parent);
                    // 更换兄弟
                    sibling = parent.right;
                }
    
                // 兄弟节点必然是黑色
                if (isBlack(sibling.left) && isBlack(sibling.right)) {
        
                    // 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
                    boolean parentBlack = isBlack(parent);
                    black(parent);
                    red(sibling);
                    if (parentBlack) {
        
                        fixAfterRemove(parent);
                    }
                } else {
         // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
                    // 兄弟节点的左边是黑色，兄弟要先旋转
                    if (isBlack(sibling.right)) {
        
                        rotateRight(sibling);
                        sibling = parent.right;
                    }
    
                    color(sibling, colorOf(parent));
                    black(sibling.right);
                    black(parent);
                    rotateLeft(parent);
                }
            } else {
         // 被删除的节点在右边，兄弟节点在左边
                if (isRed(sibling)) {
         // 兄弟节点是红色
                    black(sibling);
                    red(parent);
                    rotateRight(parent);
                    // 更换兄弟
                    sibling = parent.left;
                }
    
                // 兄弟节点必然是黑色
                if (isBlack(sibling.left) && isBlack(sibling.right)) {
        
                    // 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
                    boolean parentBlack = isBlack(parent);
                    black(parent);
                    red(sibling);
                    if (parentBlack) {
        
                        fixAfterRemove(parent);
                    }
                } else {
         // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
                    // 兄弟节点的左边是黑色，兄弟要先旋转
                    if (isBlack(sibling.left)) {
        
                        rotateLeft(sibling);
                        sibling = parent.left;
                    }
    
                    color(sibling, colorOf(parent));
                    black(sibling.left);
                    black(parent);
                    rotateRight(parent);
                }
            }
        }
    
        private void fixAfterPut(Node<K, V> node) {
        
            Node<K, V> parent = node.parent;
    
            // 添加的是根节点 或者 上溢到达了根节点
            if (parent == null) {
        
                black(node);
                return;
            }
    
            // 如果父节点是黑色，直接返回
            if (isBlack(parent)) return;
    
            // 叔父节点
            Node<K, V> uncle = parent.sibling();
            // 祖父节点
            Node<K, V> grand = red(parent.parent);
            if (isRed(uncle)) {
         // 叔父节点是红色【B树节点上溢】
                black(parent);
                black(uncle);
                // 把祖父节点当做是新添加的节点
                fixAfterPut(grand);
                return;
            }
    
            // 叔父节点不是红色
            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 rotateLeft(Node<K, V> grand) {
        
            Node<K, V> parent = grand.right;
            Node<K, V> child = parent.left;
            grand.right = child;
            parent.left = grand;
            afterRotate(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;
            afterRotate(grand, parent, child);
        }
    
        private void afterRotate(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 {
         // grand是root节点（是这棵子树的根节点，既然在一棵树上，说明hashCode相等，即index也相等）
                // root = parent;
                table[index(grand)] = parent;
            }
    
            // 更新child的parent
            if (child != null) {
        
                child.parent = grand;
            }
    
            // 更新grand的parent
            grand.parent = parent;
        }
    
        private Node<K, V> color(Node<K, V> node, boolean color) {
        
            if (node == null) return node;
            node.color = color;
            return node;
        }
    
        private Node<K, V> red(Node<K, V> node) {
        
            return color(node, RED);
        }
    
        private Node<K, V> black(Node<K, V> node) {
        
            return color(node, BLACK);
        }
    
        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;
        }
    
        protected static class Node<K, V> {
        
            int hash;
            K key;
            V value;
            boolean color = RED;
            Node<K, V> left;
            Node<K, V> right;
            Node<K, V> parent;
    
            public Node(K key, V value, Node<K, V> parent) {
        
                this.key = key;
                // 创建节点的时候，就计算key的hash值，并扰动计算
                int hash = key == null ? 0 : key.hashCode();
                this.hash = hash ^ (hash >>> 16);
                this.value = value;
                this.parent = parent;
            }
    
            public boolean hasTwoChildren() {
        
                return left != null && right != null;
            }
    
            public boolean isLeftChild() {
        
                return parent != null && this == parent.left;
            }
    
            public boolean isRightChild() {
        
                return parent != null && this == parent.right;
            }
    
            public Node<K, V> sibling() {
        
                if (isLeftChild()) {
        
                    return parent.right;
                }
    
                if (isRightChild()) {
        
                    return parent.left;
                }
    
                return null;
            }
    
            @Override
            public String toString() {
        
                return "Node_" + key + "_" + value;
            }
        }
    }

# HashMap 升级为 LinkedHashMap #

◼ 在HashMap的基础上维护元素的添加顺序，使得遍历的结果是遵从添加顺序

◼ 假设添加顺序是：37、21、31、41、97、95、52、42、83  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 1]

## LinkedHashMap – 删除注意点 ##

◼ 删除 `度为 2 的节点 node`时，需要注意更换 `node` 与 `前驱\后继`节点 的连接位置  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 2]  
  
  
更换节点的连接位置  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 3]

## LinkedHashMap 完整代码 ##

@SuppressWarnings({
         "rawtypes", "unchecked" })
    public class LinkedHashMap<K, V> extends HashMap<K, V> {
        
    	private LinkedNode<K, V> first;
    	private LinkedNode<K, V> last;
    	
    	@Override
    	public void clear() {
        
    		super.clear();
    		first = null;
    		last = null;
    	}
    	
    	@Override
    	public boolean containsValue(V value) {
        
    		LinkedNode<K, V> node = first;
    		while (node != null) {
        
    			if (Objects.equals(value, node.value)) return true;
    			node = node.next;
    		}
    		return false;
    	}
    	
    	@Override
    	public void traversal(Visitor<K, V> visitor) {
        
    		if (visitor == null) return;
    		LinkedNode<K, V> node = first;
    		while (node != null) {
        
    			if (visitor.visit(node.key, node.value)) return;
    			node = node.next;
    		}
    	}
    	
    	@Override
    	protected void afterRemove(Node<K, V> willNode, Node<K, V> removedNode) {
        
    		LinkedNode<K, V> node1 = (LinkedNode<K, V>) willNode;
    		LinkedNode<K, V> node2 = (LinkedNode<K, V>) removedNode;
    		
    		if (node1 != node2) {
        
    			// 交换linkedWillNode和linkedRemovedNode在链表中的位置
    			// 交换prev
    			LinkedNode<K, V> tmp = node1.prev;
    			node1.prev = node2.prev;
    			node2.prev = tmp;
    			if (node1.prev == null) {
        
    				first = node1;
    			} else {
        
    				node1.prev.next = node1;
    			}
    			if (node2.prev == null) {
        
    				first = node2;
    			} else {
        
    				node2.prev.next = node2;
    			}
    			
    			// 交换next
    			tmp = node1.next;
    			node1.next = node2.next;
    			node2.next = tmp;
    			if (node1.next == null) {
        
    				last = node1;
    			} else {
        
    				node1.next.prev = node1;
    			}
    			if (node2.next == null) {
        
    				last = node2;
    			} else {
        
    				node2.next.prev = node2;
    			}
    		}
    		
    		LinkedNode<K, V> prev = node2.prev;
    		LinkedNode<K, V> next = node2.next;
    		if (prev == null) {
        
    			first = next;
    		} else {
        
    			prev.next = next;
    		}
    		
    		if (next == null) {
        
    			last = prev;
    		} else {
        
    			next.prev = prev;
    		}
    	}
    	
    	@Override
    	protected Node<K, V> createNode(K key, V value, Node<K, V> parent) {
        
    		LinkedNode node = new LinkedNode(key, value, parent);
    		if (first == null) {
        
    			first = last = node;
    		} else {
        
    			last.next = node;
    			node.prev = last;
    			last = node;
    		}
    		return node;
    	}
    	
    	private static class LinkedNode<K, V> extends Node<K, V> {
        
    		LinkedNode<K, V> prev;
    		LinkedNode<K, V> next;
    		public LinkedNode(K key, V value, Node<K, V> parent) {
        
    			super(key, value, parent);
    		}
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70]: /images/20221023/06ede443e3b74f8fabeeef413343d86f.png
[AVL]: https://blog.csdn.net/qq_32727095/article/details/112462399
[Link 1]: https://blog.csdn.net/qq_32727095/article/details/112667573
[RBTree]: https://blog.csdn.net/qq_32727095/article/details/114382514
[Link 2]: https://blog.csdn.net/qq_32727095/article/details/114521787
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 1]: /images/20221023/e131d6b84ff34873b1b889ad8acc9679.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 2]: /images/20221023/363084fe80224505b2c1d872427b5414.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 3]: /images/20221023/27613f863ea940d997014374aa77e3d0.png