Skip to content

Commit 1260f6c

Browse files
fengyuan-liangfengyuan-liang
committed
LinkedHashMap学习
LinkedHashMap学习
1 parent f91d58a commit 1260f6c

7 files changed

Lines changed: 2934 additions & 22 deletions

File tree

‎AlgorithmAndDataStructure/10-映射.md‎

Lines changed: 0 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -947,22 +947,3 @@ private int compare(K k1, K k2) {
947947
setColor(x, BLACK);
948948
}
949949
```
950-
951-
952-
953-
954-
955-
956-
957-
958-
959-
960-
961-
962-
963-
964-
965-
966-
967-
968-

‎AlgorithmAndDataStructure/11-Hash表.md‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -168,6 +168,30 @@ public int hash(Object key){
168168

169169
对于上面的 & 运算取代 % 运算的奥秘，如果只是因为确保元素都能够正常进入我们的数组，那么这也太过于肤浅了，HashMap的魅力不止于此，等我们手写到HashMap扩容逻辑的时候，**我们再来看这个伏笔**🤞
170170

171+
>其实我们用 % 运算计算索引也是可以的，但是我们需要注意以下的几点规则
172+
173+
- 建议把哈希表的长度设计为素数（质数）
174+
- 可以大大减小哈希冲突
175+
176+
右边表格列出了不同数据规模对应的最佳素数，特点如下：
177+
178+
- 每个素数略小于前一个素数的2倍
179+
- 每个素数尽可能接近2的幂（2 n）
180+
181+
| 除数为偶数 | 除数为质数 |
182+
| :--------: | :--------: |
183+
| 10%8 = 2 | 10%7 = 3 |
184+
| 20%8 = 4 | 20%7 = 6 |
185+
| 30%8 = 6 | 30%7 = 2 |
186+
| 40%8 = 0 | 40%7 = 5 |
187+
| 50%8 = 2 | 50%7 = 1 |
188+
| 60%8 = 4 | 60%7 = 4 |
189+
| 70%8 = 6 | 70%7 = 0 |
190+
191+
这里其实我们有一个最佳实践：
192+
193+
![image-20220719222240066](https://cdn.fengxianhub.top/resources-master/202207192222479.png)
194+
171195
### 3.3 如何生成key的hash值
172196

173197
key 的常见种类可能有：

‎AlgorithmAndDataStructure/12-LinkedHashMap.md‎

Lines changed: 169 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,169 @@
1+
# LinkedHashMap
2+
3+
我们先来总结一下HashMap的特点：
4+
5+
- HashMap是查询效率最高的数据结构（O(1)级别）
6+
- HashMap存储元素是无序的
7+
8+
如果我们想要按照添加元素的顺序遍历，显然HashMap是达不到我们的要求的，`TreeMap`可以满足我们的要求，但是效率没有HashMap高
9+
10+
接下来介绍一种新的数据结构——LinkedHashMap
11+
12+
LinkedHashMap就是在HashMap的基础上维护元素的添加顺序，使得遍历的结果是遵从添加顺序的
13+
14+
![image-20220721093424064](https://cdn.fengxianhub.top/resources-master/202207210934379.png)
15+
16+
## 1. 实现添加逻辑
17+
18+
其实我们实现也很简单，就是在添加元素的时候用指针将每个添加的元素串起来就好了
19+
20+
```java
21+
/**
22+
* <p>
23+
* LinkedHashMap,红黑树上面的所有结点都用线连接起来了
24+
* </p>
25+
*
26+
* @since: 2022/7/21 9:35
27+
* @author: 梁峰源
28+
*/
29+
public class LinkedHashMap<K, V> extends HashMap<K, V> {
30+
31+
/* 需要记录链表的头尾结点 */
32+
private LinkedNode<K, V> first;
33+
private LinkedNode<K, V> last;
34+
35+
/**
36+
* LinkedHashMap结点
37+
*/
38+
protected static class LinkedNode<K, V> extends Node<K, V> {
39+
// 指向上一个结点的指针和指向下一个结点的指针
40+
LinkedNode<K, V> prev;
41+
LinkedNode<K, V> next;
42+
43+
public LinkedNode(K key, V value, Node<K, V> parent) {
44+
super(key, value, parent);
45+
}
46+
}
47+
48+
@Override
49+
public void forEach(BiConsumer<? super K, ? super V> action) {
50+
// 从头结点开始遍历
51+
LinkedNode<K, V> node = first;
52+
while (node != null) {
53+
action.accept(node.key, node.value);
54+
node = node.next;
55+
}
56+
}
57+
58+
@Override
59+
public void traversal(Visitor<K, V> visitor) {
60+
if (visitor == null) return;
61+
LinkedNode<K, V> node = first;
62+
while (node != null) {
63+
if (visitor.visit(node.key, node.value)) return;
64+
node = node.next;
65+
}
66+
}
67+
68+
/**
69+
* 我们需要在创建结点的时候用指针将其串起来
70+
*/
71+
@Override
72+
protected Node<K, V> createNode(K k, V v, Node<K, V> parent) {
73+
LinkedNode<K, V> node = new LinkedNode<>(k, v, parent);
74+
// 添加头结点
75+
if (first == null) {
76+
first = last = node;
77+
} else {
78+
// 非头结点
79+
last.next = node;
80+
node.prev = last;
81+
last = node;
82+
}
83+
return node;
84+
}
85+
86+
/**
87+
* 清空结点需要将first和last去掉，不然不会进行GC
88+
*/
89+
@Override
90+
public void clear() {
91+
super.clear();
92+
first = null;
93+
last = null;
94+
}
95+
}
96+
```
97+
98+
测试一下：
99+
100+
```java
101+
@Test
102+
public void test01() {
103+
Person p1 = new Person(18, 650, "张三");
104+
Person p2 = new Person(18, 65, "张三");
105+
Person p3 = new Person(23, 65, "李四");
106+
Map<Person, String> map = new LinkedHashMap<>();
107+
map.put(p1, "张三");
108+
map.put(p2, "李四");
109+
map.put(p3, "王五");
110+
map.forEach((k, v) -> System.out.println(v));
111+
}
112+
```
113+
114+
结果：
115+
116+
```java
117+
张三
118+
李四
119+
王五
120+
```
121+
122+
可以发现，结果确实有序了😄
123+
124+
## 2. 删除逻辑
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+

‎README.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -57,7 +57,7 @@
5757
**RabbitMQ**
5858

5959
- [RabbitMQ基本使用](/SpringCloud/黑马SpringCloud-阿里巴巴/3-RabbitMQ.md)
60-
- [RabbitMQ高级特性](/SpringCloud/黑马SpringCloud-阿里巴巴/RabbitMQ-高级篇.md)
60+
- [RabbitMQ高级特性](/SpringCloud/黑马SpringCloud-阿里巴巴/11-RabbitMQ-高级篇.md)
6161

6262
**ElasticSearch**
6363

0 commit comments

Comments
 (0)