最近被spring的源码搞自闭了，有好几天没写这个分类的文章了。
主要内容
- Hashmap的一些知识点
- Java实现二叉搜索树
Hashmap的一些知识点
JDK8以后采用了数组+链表+红黑树的方式来实现hashmap；使用链表存储的优势是可以降低内存的使用率，而红黑树的优点是查询效率更高。
Hashmap的扩容
扩容的过程？
hashmap的扩容一般是发生在插入元素的时候，当数组的使用率超过负载因子的时候（默认值是0.75），便会进行扩容。扩容为原来的两倍。
为什么总是2倍扩容，为什么初始容量是2的n次幂？
因为插入元素时，需要利用key的hashcode来找到对应的桶位，java并没有采用取模的方式来确定桶位，而是采用length-1进行与运算来确定桶位。如果length是2的倍数，那么length-1的二进制就是全为1的，这样在与key的hashcode进行与运算，hashcode的每一位都能够起到作用。（如果length-1的二进制某一位为0，那么key的hashcode对应的位，无论是1还是0，结果都一样，都是0，显然，这一位在确定桶位的时候，就没有了意义）
为什么要使用红黑树，而是不AVL树？
AVL树和红黑树都是常见的平衡二叉树。AVL更加严格平衡，因此能够有更好的查询效率。对于插入密集型任务红黑树更加适合。
并发环境下使用HashMap会导致什么问题
因为hashmap不是线程安全的，不适用于多线程环境。
- 可能导致get无限循环
在对现场rehash的过程中可能会形成循环链表，导致查找元素的时候一直无法遍历完整个链表，从而出现死循环。最终导致CPU使用率100%。 其原因在于并发下Rehash可能导致循环链表的实现。
- 可能导致put丢失
在put的时候，如果两个产生hash碰撞，导致两个线程得到同样的index去存储，导致覆盖丢失的情况。
java实现二叉查找树
二叉树的中的关键字总是以满足二叉搜索树的性质的方式来存储的：
设x是二叉搜索树的一个节点。如果y是x左子树的一个节点 ，那么y.key<=x.key。如果y是x的右子树中的一个节点，那么y.key>=x.key.
二叉查找树的插入，查找，更新比较简单。而删除操作比较复杂，尤其是待删除的节点既有左子树又有右子树的情况，非常的复杂。
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
|
public class BSTree <key extends Comparable<key>,value> {
private Node root;
private class Node{
private key k;
private value v;
private Node left;
private Node right;
public Node(){};
public Node(key k,value val){
this.k=k;
this.v=val;
}
}
public void insert(key k,value v){
if(root==null){
root=new Node(k,v);
return;
}
Node cur=root;
Node parent=new Node();
boolean isLeftTree=true;
while (cur!=null){
parent=cur;
if(cur.k.compareTo(k)<0){
cur=cur.right;
isLeftTree=false;
}else {
cur=cur.left;
isLeftTree=true;
}
}
Node newNode =new Node(k,v);
if(isLeftTree){
parent.left=newNode;
}else {
parent.right=newNode;
}
}
public boolean delete(key k){
Node cur=root;
Node parent=root;
boolean isLeftTree=true;
while (cur.k!=k){
parent=cur;
if(k.compareTo(cur.k)<0){
cur=cur.left;
isLeftTree=true;
}else {
cur=cur.right;
isLeftTree=false;
}
if(cur==null){
return false;
}
}
if(cur.left==null&&cur.right==null){
if(cur==root){
root=null;
}else if(isLeftTree){
parent.left=null;
}else {
parent.right=null;
}
}else if(cur.right==null){
if(cur==root){
root=cur.left;
}else if(isLeftTree){
parent.left=cur.left;
}else {
parent.right=cur.left;
}
}else if(cur.left==null){
if(cur==root){
root=cur.right;
}else if(isLeftTree){
parent.left=cur.right;
}else {
parent.right=cur.right;
}
} else {
Node successor=getSuccessor(cur);
if(cur==root){
root=successor;
}else if(isLeftTree){
parent.left=successor;
}else{
parent.right=successor;
}
successor.left=cur.left;
}
return true;
}
private Node getSuccessor(Node delNode){
Node successorParent=delNode;
Node successor=delNode;
Node cur=delNode.right;
while (cur!=null){
successorParent=successor;
successor=cur;
cur=cur.left;
}
if(successor!=delNode.right){
successorParent.left=successor.right;
successor.right=delNode.right;
}
return successor;
}
public value get(key k){
Node cur=root;
while (cur.k!=k){
if(cur.k.compareTo(k)<0){
cur=cur.right;
}else {
cur=cur.left;
}
if(cur==null){
return null;
}
}
return cur.v;
}
public boolean update(key k,value newVal){
Node cur=root;
while (cur.k!=k){
if(cur.k.compareTo(k)<0){
cur=cur.right;
}else {
cur=cur.left;
}
if(cur==null){
return false;
}
}
cur.v=newVal;
return true;
}
}
|