1、映射Map,存储键值数据对的数据结构(key,value),可以根据键key快速寻找到值Value,可以使用链表或者二分搜索树实现的。
首先定义一个接口,可以使用链表或者二分搜索树进行实现。
1 package com.map;
2
3 /**
4 * @ProjectName: dataConstruct
5 * @Package: com.map
6 * @ClassName: Map
7 * @Author: biehl
8 * @Description: ${description}
9 * @Date: 2020/3/14 17:37
10 * @Version: 1.0
11 */
12 public interface Map<K, V> {
13
14 /**
15 * 映射Map的添加操作,键值对的形式新增元素
16 *
17 * @param key
18 * @param value
19 */
20 public void add(K key, V value);
21
22 /**
23 * 映射Map中根据key的值删除key-value键值对,将key对应的value返回
24 *
25 * @param key
26 * @return
27 */
28 public V remove(K key);
29
30 /**
31 * 判断映射是否包含某个key
32 *
33 * @param key
34 * @return
35 */
36 public boolean contains(K key);
37
38 /**
39 * 映射Map中根据key的值获取到键值对的值
40 *
41 * @param key
42 * @return
43 */
44 public V get(K key);
45
46 /**
47 * 向映射Map中设置键值对,即将key对应的value值修改成新的value值。
48 *
49 * @param key
50 * @param value
51 */
52 public void set(K key, V value);
53
54 /**
55 * 获取到映射的大小
56 *
57 * @return
58 */
59 public int getSize();
60
61 /**
62 * 判断映射Map是否为空
63 *
64 * @return
65 */
66 public boolean isEmpty();
67 }
1.1、基于链表的映射实现的映射Map。
1 package com.map;
2
3 import com.linkedlist.LinkedList;
4
5 /**
6 * @ProjectName: dataConstruct
7 * @Package: com.map
8 * @ClassName: LinkedListMap
9 * @Author: biehl
10 * @Description: ${description}
11 * @Date: 2020/3/14 17:45
12 * @Version: 1.0
13 */
14 public class LinkedListMap<K, V> implements Map<K, V> {
15
16 // 链表是由一个一个节点组成
17 private class Node {
18 // 设置公有的,可以让外部类进行修改和设置值
19 public K key;// 成员变量key存储键值对的键
20 public V value;// 成员变量value存储键值对的值
21 public Node next;// 成员变量next指向下一个节点,指向Node的一个引用
22
23 /**
24 * 含参构造函数
25 *
26 * @param key
27 * @param value
28 * @param next
29 */
30 public Node(K key, V value, Node next) {
31 this.key = key;
32 this.value = value;
33 this.next = next;
34 }
35
36 /**
37 * 无参构造函数
38 */
39 public Node() {
40 this(null, null, null);
41 }
42
43 /**
44 * 如果用户只传了key,那么可以调用含参构造函数,将next指定为null
45 *
46 * @param key
47 */
48 public Node(K key) {
49 this(key, null, null);
50 }
51
52 /**
53 * 重写toString方法
54 *
55 * @return
56 */
57 @Override
58 public String toString() {
59 return key.toString() + " : " + value.toString();
60 }
61
62 }
63
64
65 private Node dummyHead;// Node类型的变量dummyHead,虚拟头节点
66 private int size;// 链表要存储一个一个元素,肯定有大小,记录链表有多少元素
67
68 /**
69 * 无参的构造函数
70 */
71 public LinkedListMap() {
72 // 虚拟头节点的元素是null空,初始化的时候next的值也为null空。
73 dummyHead = new Node(null, null, null);// 初始化一个链表,虚拟头节点dummyHead是一个节点。
74 // 链表大小是0,此时对于一个空的链表来说,是存在一个节点的,虚拟头节点。
75 size = 0;// 大小size为0
76 }
77
78
79 /**
80 * 获取链表的大小,获取链表中的元素个数
81 *
82 * @return
83 */
84 @Override
85 public int getSize() {
86 return size;
87 }
88
89 /**
90 * 判断返回链表是否为空
91 *
92 * @return
93 */
94 @Override
95 public boolean isEmpty() {
96 return size == 0;
97 }
98
99
100 /**
101 * 根据映射Map的key获取到这个节点。
102 *
103 * @param key
104 * @return
105 */
106 private Node getNode(K key) {
107 // 获取到指向虚拟头节点的下一个节点,就是头部节点。
108 Node current = dummyHead.next;
109 // 循环遍历,如果不为空,就继续遍历
110 while (current != null) {
111 // 如果当前节点的键值对的键和你想要查询的键相等的话,就返回该节点
112 if (current.key.equals(key)) {
113 // 返回给当前要查询的节点
114 return current;
115 }
116 // 如果不相等的话,就向下一个节点移动即可。
117 current = current.next;
118 }
119 // 如果链表遍历完了,没有找到,就直接返回空即可。
120 return null;
121 }
122
123 @Override
124 public void add(K key, V value) {
125 // 不允许有相同的key,即key不可以重复的。
126
127 // 首先判断是否已经存在该key
128 Node node = this.getNode(key);
129 // 如果新增的key的值和保存的键值对的key值相等,那么这个新的key不能新增
130 // 如果没有查到这个node,说明就可以新增了
131 if (node == null) {
132 // 这里是在链表的头部添加元素。
133 // 在虚拟头节点的下一个节点,就是头部节点添加这个键值对
134 dummyHead.next = new Node(key, value, dummyHead.next);
135 // 维护size大小
136 size++;
137 } else {
138 // 如果已经保存了该键值对。那么将新增的键值对的key对应的value值替换之前的value值
139 node.value = value;
140 }
141
142 }
143
144 @Override
145 public V remove(K key) {
146 // 定义一个起始节点,该节点从虚拟头节点开始
147 Node prev = dummyHead;
148 // 循环遍历,当前节点的下一个节点不为空就一直遍历
149 while (prev.next != null) {
150 // 如果当前节点的key的值等于想要删除的节点的key的值
151 // 那么,此时prev的下一个节点保存的key,就是将要删除的节点。
152 if (prev.next.key.equals(key)) {
153 // 中断此循环
154 break;
155 }
156 // 如果不是想要删除的节点,继续向下遍历
157 prev = prev.next;
158 }
159
160 // 此时,如果prev的下一个节点不为空,那么该节点就是将要被删除的节点
161 if (prev.next != null) {
162 // 获取到这个将要被删除的节点
163 Node delNode = prev.next;
164 // 把将要被删除的这个节点的下一个节点赋值给prev这个节点的下一个节点,
165 // 就是直接让prev指向将要被删除的节点的下一个节点。
166 prev.next = delNode.next;
167 // 此时将被删除的节点置空
168 delNode.next = null;
169 // 维护size的大小
170 size--;
171 // 返回被删除的节点元素
172 return delNode.value;
173 }
174 // 如果没有找到待删除的节点,返回空
175 return null;
176 }
177
178 @Override
179 public boolean contains(K key) {
180 // 根据key判断映射key里面是否包含key
181 Node node = this.getNode(key);
182 // 如果获取到node不为空,说明有这个元素,返回true。
183 if (node != null) {
184 return true;
185 }
186 return false;
187 }
188
189 @Override
190 public V get(K key) {
191 // 根据key获取到键值对的value值
192 // Node node = this.getNode(key);
193 // // 如果查询的节点返回不为空,说明存在该节点
194 // if (node != null) {
195 // // 返回该节点的value值
196 // return node.value;
197 // }
198 // return null;
199
200 // 根据key获取到键值对的value值
201 Node node = this.getNode(key);
202 return node == null ? null : node.value;
203 }
204
205 @Override
206 public void set(K key, V value) {
207 // 首先判断是否已经存在该key
208 Node node = this.getNode(key);
209 // 如果node节点等于空
210 if (node == null) {
211 throw new IllegalArgumentException(key + " doesn't exist!");
212 } else {
213 // 如果映射Map中存在了该键值对,那么进行更新操作即可
214 node.value = value;
215 }
216 }
217
218 public static void main(String[] args) {
219 LinkedListMap<Integer, Integer> linkedListMap = new LinkedListMap<Integer, Integer>();
220 // 基于链表实现的映射的新增
221 for (int i = 0; i < 100; i++) {
222 linkedListMap.add(i, i * i);
223 }
224
225 // for (int i = 0; i < linkedListMap.getSize(); i++) {
226 // System.out.println(linkedListMap.get(i));
227 // }
228
229
230 // 基于链表实现的映射的修改
231 linkedListMap.set(0, 111);
232 // for (int i = 0; i < linkedListMap.getSize(); i++) {
233 // System.out.println(linkedListMap.get(i));
234 // }
235
236 // 基于链表实现的映射的删除
237 Integer remove = linkedListMap.remove(0);
238 // for (int i = 0; i < linkedListMap.getSize(); i++) {
239 // System.out.println(linkedListMap.get(i));
240 // }
241
242 // 基于链表实现的映射的获取大小
243 System.out.println(linkedListMap.getSize());
244 }
245
246 }
1.2、基于二分搜索树实现的映射Map。
1 package com.map;
2
3 import com.tree.BinarySearchTree;
4
5 /**
6 * @ProjectName: dataConstruct
7 * @Package: com.map
8 * @ClassName: BinarySearchTreeMap
9 * @Author: biehl
10 * @Description: ${description}
11 * @Date: 2020/3/14 19:57
12 * @Version: 1.0
13 */
14 public class BinarySearchTreeMap<K extends Comparable<K>, V> implements Map<K, V> {
15
16 // 二分搜索树的节点类,私有内部类。
17 private class Node {
18 private K key;// 存储元素key;
19 private V value;// 存储元素value;
20 private Node left;// 指向左子树,指向左孩子。
21 private Node right;// 指向右子树,指向右孩子。
22
23 /**
24 * 含参构造函数
25 *
26 * @param key
27 */
28 public Node(K key, V value) {
29 this.key = key;// 键值对的key。
30 this.value = value;// 键值对的value
31 left = null;// 左孩子初始化为空。
32 right = null;// 右孩子初始化为空。
33 }
34 }
35
36
37 private Node root;// 根节点
38 private int size;// 映射Map存储了多少个元素
39
40 /**
41 * 无参构造函数,和默认构造函数做的事情一样的。
42 */
43 public BinarySearchTreeMap() {
44 // 初始化的时候,映射Map一个元素都没有存储
45 root = null;
46 size = 0;// 大小初始化为0
47 }
48
49
50 /**
51 * 返回以node为根节点的二分搜索树中,key所在的节点。
52 *
53 * @param node
54 * @param key
55 * @return
56 */
57 private Node getNode(Node node, K key) {
58
59 // 如果未找到指定的键值对的键值,那么直接返回空即可。
60 if (node == null) {
61 return null;
62 }
63
64 // 如果查询的key值和该节点的key值相等,直接返回该节点即可
65 if (key.compareTo(node.key) == 0) {
66 return node;
67 } else if (key.compareTo(key) < 0) {
68 // 如果查询的key值小于该节点的key值,那么向该节点的左子树查询
69 return getNode(node.left, key);
70 } else if (key.compareTo(key) > 0) {
71 // 如果查询的key值大于该节点的key值,那么向该节点的右子树查询
72 return getNode(node.right, key);
73 }
74 return null;
75 }
76
77
78 /**
79 * 返回以node为根的二分搜索树的最小值所在的节点
80 *
81 * @param node
82 * @return
83 */
84 public Node minimum(Node node) {
85 // 递归算法,第一部分,终止条件,如果node.left是空了,直接返回node节点
86 if (node.left == null) {
87 return node;
88 }
89 // 递归算法,第二部分,向node的左子树遍历
90 return minimum(node.left);
91 }
92
93 /**
94 * 删除掉以node为根的二分搜索树中的最小节点
95 * 返回删除节点后新的二分搜索树的根
96 *
97 * @param node
98 * @return
99 */
100 private Node removeMin(Node node) {
101 if (node.left == null) {
102 Node rightNode = node.right;
103 node.right = null;
104 size--;
105 return rightNode;
106 }
107
108 node.left = removeMin(node.left);
109 return node;
110 }
111
112
113 /**
114 * 向映射Map中添加新的键值对。
115 *
116 * @param key
117 * @param value
118 */
119 @Override
120 public void add(K key, V value) {
121 // 此时,不需要对root为空进行特殊判断。
122 // 向root中插入元素e。如果root为空的话,直接返回一个新的节点,将元素存储到该新的节点里面。
123 root = add(root, key, value);
124 }
125
126 /**
127 * 向以node为根的二分搜索树中插入元素键值对key-value,递归算法
128 * 返回以插入心节点后二分搜索树饿根
129 *
130 * @param node
131 * @param key
132 * @param value
133 * @return
134 */
135 private Node add(Node node, K key, V value) {
136 if (node == null) {
137 // 维护size的大小。
138 size++;
139 // 如果此时,直接创建一个Node的话,没有和二叉树挂接起来。
140 // 如何让此节点挂接到二叉树上呢,直接将创建的节点return返回回去即可,返回给调用的上层。
141 return new Node(key, value);
142 }
143
144 // 递归的第二部分。递归调用的逻辑。
145 if (key.compareTo(node.key) < 0) {
146 // 如果待插入元素e小于node的元素e,递归调用add方法,参数一是向左子树添加左孩子。
147 // 向左子树添加元素e。
148 // 向左子树添加元素e的时候,为了让整颗二叉树发生改变,在node的左子树中插入元素e,
149 // 插入的结果,有可能是变化的,所以就要让node的左子树连接住这个变化。
150
151 // 注意,如果此时,node.left是空的话,这次add操作相应的就会返回一个新的Node节点,
152 // 对于这个新的节点,我们的node.left被赋值这个新的节点,相当于我们就改变了整棵二叉树。
153 node.left = add(node.left, key, value);
154 } else if (key.compareTo(node.key) > 0) {
155 // 如果待插入元素e大于node的元素e,递归调用add方法,参数一是向右子树添加右孩子。
156 // 向右子树添加元素e。
157 node.right = add(node.right, key, value);
158 } else if (key.compareTo(node.key) == 0) {
159 // 如果想要插入的值是已经存在与映射里面了,那么将value值替换就行了。
160 node.value = value;
161 }
162
163 return node;
164 }
165
166 /**
167 * 从二分搜索树中删除元素为key的节点
168 *
169 * @param key
170 * @return
171 */
172 @Override
173 public V remove(K key) {
174 Node node = getNode(root, key);
175 if (node != null) {
176 root = remove(root, key);
177 return node.value;
178 }
179 // 不存在该节点
180 return null;
181 }
182
183 /**
184 * 删除掉以node为根的二分搜索树中健为key的节点,递归算法
185 * 返回删除节点后新的二分搜索树的根
186 *
187 * @param node
188 * @param key
189 * @return
190 */
191 private Node remove(Node node, K key) {
192 if (node == null) {
193 return null;
194 }
195
196 // 递归函数,开始近逻辑
197 // 如果待删除元素e和当前节点的元素e进行比较,如果待删除元素e小于该节点的元素e
198 if (key.compareTo(node.key) < 0) {
199 // 此时,去该节点的左子树,去找到待删除元素节点
200 // 递归调用,去node的左子树,去删除这个元素e。
201 // 最后将删除的结果赋给该节点左子树。
202 node.left = remove(node.left, key);
203 return node;
204 } else if (key.compareTo(node.key) > 0) {
205 // 如果待删除元素e大于该节点的元素e
206 // 去当前节点的右子树去寻找待删除元素节点
207 // 将删除后的结果返回给当前节点的右孩子
208 node.right = remove(node.right, key);
209 return node;
210 } else {
211 // 当前节点元素e等于待删除节点元素e,即e == node.e,
212 // 相等的时候,此时就是要删除这个节点的。
213
214 // 如果当前节点node的左子树为空的时候,待删除节点左子树为空的情况
215 if (node.left == null) {
216 // 保存该节点的右子树
217 Node rightNode = node.right;
218 // 将node和这棵树断开关系
219 node.right = null;
220 // 维护size的大小
221 size--;
222 // 返回原来那个node的右孩子。也就是右子树的根节点,此时就将node删除掉了
223 return rightNode;
224 }
225
226 // 如果当前节点的右子树为空,待删除节点右子树为空的情况。
227 if (node.right == null) {
228 // 保存该节点的左子树
229 Node leftNode = node.left;
230 // 将node节点和这棵树断开关系
231 node.left = null;
232 // 维护size的大小
233 size--;
234 //返回原来那个节点node的左孩子,也就是左子树的根节点,此时就将node删除掉了。
235 return leftNode;
236 }
237
238 // 待删除节点左右子树均为不为空的情况。
239 // 核心思路,找到比待删除节点大的最小节点,即待删除节点右子树的最小节点
240 // 用这个节点顶替待删除节点的位置。
241
242 // 找到当前节点node的右子树中的最小节点,找到比待删除节点大的最小节点。
243 // 此时的successor就是node的后继。
244 Node successor = minimum(node.right);
245 // 此时将当前节点node的右子树中的最小节点删除掉,并将二分搜索树的根节点返回。
246 // 将新的二分搜索树的根节点赋值给后继节点的右子树。
247 successor.right = removeMin(node.left);
248
249 // 因为removeMin操作,删除了一个节点,但是此时当前节点的右子树的最小值还未被删除
250 // 被successor后继者指向了。所以这里做一些size加加操作,
251 size++;
252
253 // 将当前节点的左子树赋值给后继节点的左子树上。
254 successor.left = node.left;
255 // 将node节点没有用了,将node节点的左孩子和右孩子置空。让node节点和二分搜索树脱离关系
256 node.left = node.right = null;
257
258 // 由于此时,将当前节点node删除掉了,所以这里做一些size减减操作。
259 size--;
260
261 // 返回后继节点
262 return successor;
263 }
264
265 }
266
267 @Override
268 public boolean contains(K key) {
269 return this.getNode(root, key) != null;
270 }
271
272 @Override
273 public V get(K key) {
274 Node node = this.getNode(root, key);
275 return node == null ? null : node.value;
276 }
277
278 @Override
279 public void set(K key, V value) {
280 Node node = getNode(root, key);
281 // 如果映射中没有该节点
282 if (node == null) {
283 throw new IllegalArgumentException(key + " doesn't exist!");
284 } else {
285 node.value = value;
286 }
287 }
288
289 /**
290 * 获取到映射Map的大小
291 *
292 * @return
293 */
294 @Override
295 public int getSize() {
296 return size;
297 }
298
299 /**
300 * 判断映射Map是否为空
301 *
302 * @return
303 */
304 @Override
305 public boolean isEmpty() {
306 return size == 0;
307 }
308
309 /**
310 * @return
311 */
312 @Override
313 public String toString() {
314 StringBuilder stringBuilder = new StringBuilder();
315 // 使用一种形式展示整个二分搜索树,可以先展现根节点,再展现左子树,再展现右子树。
316 // 上述这种过程就是一个前序遍历的过程。
317 // 参数一,当前遍历的二分搜索树的根节点,初始调用的时候就是root。
318 // 参数二,当前遍历的这棵二分搜索树的它的深度是多少,根节点的深度是0。
319 // 参数三,将字符串传入进去,为了方便生成字符串。
320 generateBSTString(root, 0, stringBuilder);
321
322 return stringBuilder.toString();
323 }
324
325 /**
326 * 生成以node为根节点,深度为depth的描述二叉树的字符串。
327 *
328 * @param node 节点
329 * @param depth 深度
330 * @param stringBuilder 字符串
331 */
332 private void generateBSTString(Node node, int depth, StringBuilder stringBuilder) {
333 // 递归的第一部分
334 if (node == null) {
335 // 显示的,将在字符串中追加一个空字符串null。
336 // 为了表现出当前的空节点对应的二分搜索树的层次,封装了一个方法。
337 stringBuilder.append(generateDepthString(depth) + "null\n");
338 return;
339 }
340
341
342 // 递归的第二部分
343 // 当当前节点不为空的时候,就可以直接访问当前的node节点了。
344 // 将当前节点信息放入到字符串了
345 stringBuilder.append(generateDepthString(depth) + node.key + "\n");
346
347 // 递归进行调用
348 generateBSTString(node.left, depth + 1, stringBuilder);
349 generateBSTString(node.right, depth + 1, stringBuilder);
350 }
351
352 /**
353 * 为了表现出二分搜索树的深度
354 *
355 * @param depth
356 * @return
357 */
358 private String generateDepthString(int depth) {
359 StringBuilder stringBuilder = new StringBuilder();
360 for (int i = 0; i < depth; i++) {
361 stringBuilder.append("--");
362 }
363 return stringBuilder.toString();
364 }
365
366 public static void main(String[] args) {
367 BinarySearchTreeMap<Integer, Integer> binarySearchTreeMap = new BinarySearchTreeMap<Integer, Integer>();
368 // 基于链表实现的映射的新增
369 for (int i = 0; i < 100; i++) {
370 binarySearchTreeMap.add(i, i * i);
371 }
372 System.out.println(binarySearchTreeMap.toString());
373
374
375 // 基于链表实现的映射的修改
376 binarySearchTreeMap.set(0, 111);
377 // for (int i = 0; i < linkedListMap.getSize(); i++) {
378 // System.out.println(linkedListMap.get(i));
379 // }
380
381 // 基于链表实现的映射的删除
382 Integer remove = binarySearchTreeMap.remove(0);
383 // for (int i = 0; i < linkedListMap.getSize(); i++) {
384 // System.out.println(linkedListMap.get(i));
385 // }
386
387 // 基于链表实现的映射的获取大小
388 System.out.println(binarySearchTreeMap.getSize());
389 }
390 }
2、数据结构之映射Map,可以使用链表或者二分搜索树进行实现。它们的时间复杂度,分别如下所示: