Java的 Map以及实现一个简单的红黑树

Map是Java中的一种键值对（Key-Value）数据结构，它提供了高效的键值对的存储和访问。在Java中，常见的Map实现类有HashMap、LinkedHashMap和TreeMap等。这些实现类在底层使用不同的数据结构来存储键值对，以提供不同的性能和特性。

让我们看看官方介绍Map吧（采用机翻）

Map是将键映射到值的对象。map不能包含重复的键; 每个键最多只能映射到一个值。这个接口取代了Dictionary类，Dictionary类是一个完全抽象的类，而不是接口。

Map接口提供了三个集合视图，它们允许将映射的内容视为一组键、一组值或一组键-值映射。映射的顺序定义为映射集合视图上的迭代器返回其元素的顺序。一些类似实现，比如TreeMap类，对它们的顺序做出了特定的保证;其他类，如HashMap类，则不需要。

注意:如果使用可变对象作为映射键，必须非常小心。如果对象的值以影响相等比较的方式更改，而该对象是映射中的键，则不指定映射的行为。这种禁止的一个特殊情况是，不允许map将自身包含为键。虽然允许映射将自身包含为一个值，但建议非常小心。

equals和hashCode方法不再在这样的映射上得到很好的定义。

所有通用的map实现类都应该提供两个“标准”构造函数:

1. 创建空映射的void(无参数)构造函数，
2. 具有单个map类型参数的构造函数，它创建具有与其参数相同的键值映射的新映射。

实际上，后一种构造函数允许用户复制任何映射，生成所需类的等效映射。没有办法强制执行这个建议(因为接口不能包含构造函数)，但是JDK中的所有通用映射实现都遵循这个建议。该接口中包含的“破坏性”方法，即修改其操作的映射的方法，被指定为在该映射不支持该操作时抛出UnsupportedOperationException。如果是这种情况，如果调用对映射没有影响，这些方法可能(但不是必需)抛出UnsupportedOperationException。

例如，在不可修改的映射上调用putAll(Map)方法，如果要“叠加”其映射的映射为空，则可能(但不是必需的)抛出异常。一些映射实现对它们可能包含的键和值有限制。例如，有些实现禁止空键和空值，有些实现对其键的类型有限制。尝试插入不符合条件的键或值将引发未检查异常，通常为NullPointerException或ClassCastException。试图查询是否存在不符合条件的键或值可能会抛出异常，或者简单地返回false;有些实现将展示前一种行为，有些将展示后一种行为。更一般地说，尝试对不符合条件的键或值进行操作，其完成后不会导致在映射中插入不符合条件的元素，可能会抛出异常，也可能成功，这取决于实现的选择。这种异常在该接口的规范中被标记为“可选的”。

Collections Framework接口中的许多方法都是根据equals方法定义的。例如，containsKey(Object key)方法的规范说:“当且仅当此映射包含键k的映射使得(key==null ?)K ==null: key.equals(K))。”此规范不应被解释为暗示调用Map。带有非空参数key的containsKey将导致对任何键k调用key.equals(k)。实现可以自由地实现优化，从而避免equals调用，例如，首先比较两个键的哈希码。(Object.hashCode()规范保证两个哈希码不相等的对象不能相等。)更一般地说，只要实现者认为合适，各种集合框架接口的实现可以自由地利用底层对象方法的指定行为。一些执行递归遍历map的map操作可能会失败，对于map直接或间接包含自身的自引用实例可能会出现异常。这包括clone()、equals()、hashCode()和toString()方法。实现可以选择性地处理自引用场景，但是大多数当前实现都不这样做。

Map的特点

• 键唯一性：Map中的键是唯一的，每个键只能对应一个值。
• 无序性：Map中的键值对是无序的，插入顺序不会影响键值对的存储和访问顺序。
• 键和值的映射关系：每个键都与一个值相关联，通过键可以获取对应的值。
• 允许空键和空值：Map允许使用null作为键和值。
• 可变性：Map是可变的数据结构，可以动态地添加、修改和删除键值对。

Map的实现方式

• HashMap使用哈希表（Hash Table）实现，通过哈希函数将键映射到数组索引，以实现快速的插入、查找和删除操作。它提供了O(1)的平均时间复杂度。
• LinkedHashMap在HashMap的基础上，使用双向链表维护插入顺序，以保持键值对的迭代顺序。
• TreeMap使用红黑树（Red-Black Tree）实现，以保持键的有序性。它提供了O(log n)的时间复杂度。

Map的缺点

• 性能开销：相比于数组或列表，Map的性能开销较大。由于需要维护键的唯一性和映射关系，以及可能的哈希冲突等，Map的操作通常比较耗时。
• 内存占用：Map需要维护额外的数据结构来存储键值对的映射关系，这会占用一定的内存空间。
• 无序性：虽然Map提供了键值对的存储和访问，但是它们是无序的。如果需要有序性，可能需要使用其他数据结构。

示例：

将Map对象转换为List对象

import java.util.ArrayList; import java.util.List; import java.util.Map; public class MapToListExample { public static void main(String[] args) { // 创建一个Map对象 Map<String, Integer> map = Map.of("A", 1, "B", 2, "C", 3); // 将Map对象转换为List对象 List<Map.Entry<String, Integer>> list = new ArrayList<>(map.entrySet()); // 打印转换后的List对象 for (Map.Entry<String, Integer> entry : list) { System.out.println(entry.getKey() + " : " + entry.getValue()); } } }

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19

将HashMap的键值对结构转换为数组对象结构

import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class HashMapToArrayExample { public static void main(String[] args) { // 创建一个HashMap对象 Map<String, Integer> hashMap = new HashMap<>(); hashMap.put("A", 1); hashMap.put("B", 2); hashMap.put("C", 3); // 将HashMap的键值对结构转换为数组对象结构 List<MyObject> array = new ArrayList<>(); for (Map.Entry<String, Integer> entry : hashMap.entrySet()) { MyObject obj = new MyObject(entry.getKey(), entry.getValue()); array.add(obj); } // 打印转换后的数组对象 for (MyObject obj : array) { System.out.println(obj.getKey() + " : " + obj.getValue()); } } } class MyObject { private String key; private Integer value; public MyObject(String key, Integer value) { this.key = key; this.value = value; } public String getKey() { return key; } public Integer getValue() { return value; } }

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45

实现一个简易版本的红黑树

package com.xh.Map; /** * @author HWZ * @date 2024年03月07日 11:01 * @description */ public class RedBlackTree<K extends Comparable<K>, V> { private static final boolean RED = true; private static final boolean BLACK = false; private Node root; private class Node { private K key; private V value; private Node left, right; private boolean color; public Node(K key, V value) { this.key = key; this.value = value; this.color = RED; } } /** * 向红黑树中插入键值对 * @param key 键 * @param value 值 */ public void put(K key, V value) { root = put(root, key, value); root.color = BLACK; } private Node put(Node node, K key, V value) { if (node == null) { return new Node(key, value); } int cmp = key.compareTo(node.key); if (cmp < 0) { node.left = put(node.left, key, value); } else if (cmp > 0) { node.right = put(node.right, key, value); } else { node.value = value; } if (isRed(node.right) && !isRed(node.left)) { node = rotateLeft(node); } if (isRed(node.left) && isRed(node.left.left)) { node = rotateRight(node); } if (isRed(node.left) && isRed(node.right)) { flipColors(node); } return node; } /** * 删除红黑树中指定键的节点 * @param key 键 */ public void delete(K key) { if (!contains(key)) { return; } if (!isRed(root.left) && !isRed(root.right)) { root.color = RED; } root = delete(root, key); if (root != null) { root.color = BLACK; } } private Node delete(Node node, K key) { if (key.compareTo(node.key) < 0) { if (!isRed(node.left) && !isRed(node.left.left)) { node = moveRedLeft(node); } node.left = delete(node.left, key); } else { if (isRed(node.left)) { node = rotateRight(node); } if (key.compareTo(node.key) == 0 && (node.right == null)) { return null; } if (!isRed(node.right) && !isRed(node.right.left)) { node = moveRedRight(node); } if (key.compareTo(node.key) == 0) { Node min = findMin(node.right); node.key = min.key; node.value = min.value; node.right = deleteMin(node.right); } else { node.right = delete(node.right, key); } } return balance(node); } private Node deleteMin(Node node) { if (node.left == null) { return null; } if (!isRed(node.left) && !isRed(node.left.left)) { node = moveRedLeft(node); } node.left = deleteMin(node.left); return balance(node); } /** * 判断红黑树中是否包含指定键 * @param key 键 * @return 是否包含指定键 */ public boolean contains(K key) { return get(key) != null; } /** * 根据键查找红黑树中的值 * @param key 键 * @return 值 */ public V get(K key) { Node node = root; while (node != null) { int cmp = key.compareTo(node.key); if (cmp < 0) { node = node.left; } else if (cmp > 0) { node = node.right; } else { return node.value; } } return null; } /** * 更新红黑树中指定键的值 * @param key 键 * @param value 值 */ public void update(K key, V value) { if (contains(key)) { put(key, value); } } private boolean isRed(Node node) { if (node == null) { return false; } return node.color == RED; } private Node rotateLeft(Node node) { if (node == null || node.right == null) { return node; } Node x = node.right; node.right = x.left; x.left = node; x.color = node.color; node.color = RED; return x; } private Node rotateRight(Node node) { Node x = node.left; node.left = x.right; x.right = node; x.color = node.color; node.color = RED; return x; } private void flipColors(Node node) { node.color = RED; node.left.color = BLACK; node.right.color = BLACK; } private Node moveRedLeft(Node node) { flipColors(node); if (isRed(node.right.left)) { node.right = rotateRight(node.right); node = rotateLeft(node); flipColors(node); } return node; } private Node moveRedRight(Node node) { flipColors(node); if (isRed(node.left.left)) { node = rotateRight(node); flipColors(node); } return node; } private Node balance(Node node) { if (isRed(node)) { node = rotateLeft(node); } if (isRed(node.left) && isRed(node.left.left)) { node = rotateRight(node); } if (isRed(node.left) && isRed(node.right)) { flipColors(node); } return node; } private Node findMin(Node node) { while (node.left != null) { node = node.left; } return node; } }

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71
• 72
• 73
• 74
• 75
• 76
• 77
• 78
• 79
• 80
• 81
• 82
• 83
• 84
• 85
• 86
• 87
• 88
• 89
• 90
• 91
• 92
• 93
• 94
• 95
• 96
• 97
• 98
• 99
• 100
• 101
• 102
• 103
• 104
• 105
• 106
• 107
• 108
• 109
• 110
• 111
• 112
• 113
• 114
• 115
• 116
• 117
• 118
• 119
• 120
• 121
• 122
• 123
• 124
• 125
• 126
• 127
• 128
• 129
• 130
• 131
• 132
• 133
• 134
• 135
• 136
• 137
• 138
• 139
• 140
• 141
• 142
• 143
• 144
• 145
• 146
• 147
• 148
• 149
• 150
• 151
• 152
• 153
• 154
• 155
• 156
• 157
• 158
• 159
• 160
• 161
• 162
• 163
• 164
• 165
• 166
• 167
• 168
• 169
• 170
• 171
• 172
• 173
• 174
• 175
• 176
• 177
• 178
• 179
• 180
• 181
• 182
• 183
• 184
• 185
• 186
• 187
• 188
• 189
• 190
• 191
• 192
• 193
• 194
• 195
• 196
• 197
• 198
• 199
• 200
• 201
• 202
• 203
• 204
• 205
• 206
• 207
• 208
• 209
• 210
• 211
• 212
• 213
• 214
• 215
• 216
• 217
• 218
• 219
• 220
• 221
• 222
• 223
• 224
• 225
• 226
• 227
• 228
• 229
• 230
• 231
• 232
• 233
• 234
• 235
• 236

这个简易版本的红黑树实现包括了插入、删除、查找和修改操作。红黑树的节点使用内部类Node表示，包含了键、值、左子节点、右子节点和颜色属性。

插入操作使用递归实现，并根据红黑树的性质进行旋转和颜色翻转来保持树的平衡性。删除操作也使用递归实现，并根据不同情况进行旋转和颜色翻转来保持树的平衡性。

查找操作根据键的比较逐级向下搜索，直到找到匹配的键或搜索到叶子节点为止。修改操作先判断是否包含指定的键，如果包含则调用插入操作来更新键对应的值。

注意，这只是一个简易版本的红黑树实现，并没有考虑到所有的边界情况和优化。在实际应用中，我们更加建议使用Java标准库中的TreeMap来实现红黑树，它提供了更完善和高效的实现。

上述红黑树代码的测试：

public class RedBlackTreeTest { public static void main(String[] args) { RedBlackTree<Integer, String> tree = new RedBlackTree<>(); // 插入操作 tree.put(5, "Value 5"); tree.put(2, "Value 2"); tree.put(8, "Value 8"); tree.put(1, "Value 1"); tree.put(4, "Value 4"); tree.put(7, "Value 7"); tree.put(9, "Value 9"); // 查找操作 System.out.println(tree.get(4)); // 输出: Value 4 System.out.println(tree.get(10)); // 输出: null // 修改操作 tree.update(4, "New Value 4"); System.out.println(tree.get(4)); // 输出: New Value 4 // 删除操作 tree.delete(2); System.out.println(tree.contains(2)); // 输出: false } }

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26