【算法】查找

Posted on | In ,

顺序查找（无序链表）

符号表中使用的数据结构的一个简单选择是链表，每个结点存储一个键值对。

示意

Markdown

实现

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
public class SequentialSearch<Key, Value> {
	private Node first;
	private int n;
	
	private class Node{
		Key key;
		Value value;
		Node next;
		
		public Node (Key key, Value value, Node next){
			this.key = key;
			this.value = value;
			this.next = next;
		}
	}
	
	public void put(Key key, Value value){
		for (Node x = first; x != null; x = x.next){
			if (key.equals(x.key)){
				x.value = value;
				return;
			}
		}
		
		first = new Node(key, value, first);
		n++;
	}
	
	public Value get(Key key){
		for (Node x = first; x != null; x = x.next){
			if (key.equals(x.key))
				return x.value;
		}
		
		return null;
	}
	
	public void delete(Key key){
		if (isEmpty())
			return;
		
		if (key.equals(first.key))
			first = first.next;
		else
			deleteNode(first, key);
		
		n--;
	}
	
	private void deleteNode(Node x, Key key){
		if (x.next == null)
			return;
		
		if (key.equals(x.next.key))
			x.next = x.next.next;
		else
			deleteNode(x.next, key);
	}
	
	public Iterable<Key> keys(){
		Queue<Key> queue = new Queue<Key>();
		
		for (Node x = first; x != null; x = x.next)
			queue.enqueue(x.key);
		
		return queue;
	}
	
	public int size(){
		return n;
	}
	
	public boolean isEmpty(){
		return size() == 0;
	}
	
	public boolean contains(Key key){
		return get(key) != null;
	}
}

特点

在含有N对键值的基于（无序）链表的符号表中，未命名的查找和插入操作都需要N次比较。命中的查找在最坏情况下需要N次比较。特别地，向一个空表中插入N个不同的键需要~N^2/2次比较。

二分查找（有序数组）

符号表使用的数据结构是一对平行的数组，一个存储键一个存储值。

计算小于给定键的键的数量：首先将key和中间键比较，如果相等则返回其索引；如果小于中间键则在左半部分查找；大于则在右半部分查找。

示意

Markdown
Markdown

实现

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
public class BinarySearch<Key extends Comparable<Key>, Value> {
	private int n;
	private Key[] keys;
	private Value[] values;
	
	public BinarySearch(int capacity){
		keys = (Key[]) new Comparable[capacity];
		values = (Value[]) new Object[capacity];
	}
	
	public void put(Key key, Value value){
		int i = rank(key);
		
		if (i < n && key.compareTo(keys[i]) == 0){
			values[i] = value;
			return;
		}
		
		for (int j = n; j > i; j--){
			keys[j] = keys[j-1];
			values[j] = values[j-1];
		}
		
		keys[i] = key;
		values[i] = value;
		n++;
	}
	
	public Value get(Key key){
		if (isEmpty())
			return null;
		
		int i = rank(key);
		
		if (i < n && key.compareTo(keys[i]) == 0)
			return values[i];
		else
			return null;
	}
	
	public int rank(Key key){
		int lo = 0;
		int hi = n - 1;
		
		while (lo <= hi){
			int mid = lo + (hi - lo) / 2;
			int compare = key.compareTo(keys[mid]);
			
			if (compare < 0)
				hi = mid - 1;
			else if (compare > 0)
				lo = mid + 1;
			else
				return mid;
		}
		
		return lo;
	}
	
	public void delete(Key key){
		if (isEmpty())
			return;
		
		int i = rank(key);
		
		if (key.compareTo(keys[i]) != 0)
			return;
		
		for (int j = i + 1; j < n; j++){
			keys[j-1] = keys[j];
			values[j-1] = values[j];
		}
		
		keys[n] = null;
		values[n] = null;
		n--;
	}
	
	public int size(){
		return n;
	}
	
	public int size(Key lo, Key hi){
		if (hi.compareTo(lo) < 0)
			return 0;
		else if (contains(hi))
			return rank(hi) - rank(lo) + 1;
		else
			return rank(hi) - rank(lo);
	}
	
	public Key floor(Key key){
		int i = rank(key);
		
		if (i < n && key.compareTo(keys[i]) == 0)
			return keys[i];
		
		if (i == 0)
			return null;
		else
			return keys[i-1];
	}
	
	public Key ceiling(Key key){
		int i = rank(key);
		return keys[i];
	}
	
	public Iterable<Key> keys(){
		return keys(min(), max());
	}
	
	public Iterable<Key> keys(Key lo, Key hi){
		Queue<Key> queue = new Queue<Key>();
		
		for (int i = rank(lo); i < rank(hi); i++)
			queue.enqueue(keys[i]);
		
		if (contains(hi))
			queue.enqueue(hi);
		
		return queue;
	}
	
	public boolean isEmpty(){
		return size() == 0;
	}
	
	public boolean contains(Key key){
		return get(key) != null;
	}
	
	public Key min(){
		return keys[0];
	}
	
	public Key max(){
		return keys[n-1];
	}
	
	public Key select(int k){
		return keys[k];
	}
	
	public void deleteMin(){
		delete(min());
	}
	
	public void deleteMax(){
		delete(max());
	}
}

特点

在N个键的有序数组中进行二分查找最多需要（lgN+1）次比较（无论是否成功）。

向大小为N的有序数组中插入一个新的元素在最坏情况下需要访问～2N次数组，因此向一个空符号表中插入N个元素在最坏情况下需要访问~N^2次数组。

比较

Markdown

二叉查找树

定义一个类表示二叉查找树上的一个结点。每个结点都含有一个键、一个值、一条左链接、一条右链接和一个结点计数器。左链接指向一棵由小于该结点的所有键组成的二叉查找树，右链接指向一棵由大于该结点的所有键组成的二叉查找树。变量N给出了以该结点为根的子树的结点总数。

示意

Markdown

实现

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
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
public class BinarySearchTree<Key extends Comparable<Key>, Value> {
	private Node root;
	
	private class Node{
		Key key;
		Value value;
		Node left;
		Node right;
		int n;
		
		public Node(Key key, Value value, int n){
			this.key = key;
			this.value = value;
			this.n = n;
		}
	}
	
	public void put(Key key, Value value){		
		root = put(root, key, value);
	}
	
	private Node put(Node x, Key key, Value value){
		if (x == null)
			return new Node(key, value, 1);
		
		int compare = key.compareTo(x.key);
		
		if (compare < 0)
			x.left = put(x.left, key, value);
		else if (compare > 0)
			x.right = put(x.right, key, value);
		else
			x.value = value;
		
		x.n = size(x.left) + size(x.right) + 1;
		
		return x;
	}
	
	public Value get(Key key){
		return get(root, key);
	}
	
	private Value get(Node x, Key key){
		if (x == null)
			return null;
		
		int compare = key.compareTo(x.key);
		
		if (compare < 0)
			return get(x.left, key);
		else if (compare > 0)
			return get(x.right, key);
		else
			return x.value;
	}
	
	public void delete(Key key){
		root = delete(root, key);
	}
	
	private Node delete(Node x, Key key){
		if (x == null)
			return null;
		
		int compare = key.compareTo(x.key);
		
		if (compare < 0)
			x.left = delete(x.left, key);
		else if (compare > 0)
			x.right = delete(x.right, key);
		else{
			if (x.left == null)
				return x.right;
			else if (x.right == null)
				return x.left;
			
			Node t = x;
			
			x = min(t.right);
			x.right = deleteMin(t.right);
			x.left = t.left;
		}
		
		x.n = size(x.left) + size(x.right) + 1;
		return x;
	}
	
	public void deleteMin(){
		root = deleteMin(root);
	}
	
	private Node deleteMin(Node x){
		if (x.left == null)
			return x.right;
		
		x.left = deleteMin(x.left);
		x.n = size(x.left) + size(x.right) + 1;
		
		return x;
	}
	
	public void deleteMax(){
		root = deleteMax(root);
	}
	
	private Node deleteMax(Node x){
		if (x.right == null)
			return x.left;
		
		x.right = deleteMax(x.right);
		x.n = size(x.left) + size(x.right) + 1;
		
		return x;
	}
	
	public Key min(){
		return min(root).key;
	}
	
	private Node min(Node x){
		if (x.left == null)
			return x;
		else
			return min(x.left);
	}
	
	public Key max(){
		return max(root).key;
	}
	
	private Node max(Node x){
		if (x.right == null)
			return x;
		else
			return max(x.right);
	}
	
	public Key floor(Key key){
		Node x = floor(root, key);
		
		if (x == null)
			return null;
		else
			return x.key;
	}
	
	private Node floor(Node x, Key key){
		if (x == null)
			return null;
		
		int compare = key.compareTo(x.key);
		
		if (compare == 0)
			return x;
		else if (compare < 0)
			return floor(x.left, key);
		else {
			Node y = floor(x.right, key);
			
			if (y != null)
				return y;
			else
				return x;
		}
	}
	
	public int rank(Key key){
		return rank(root, key);
	}
	
	private int rank(Node x, Key key){
		if (x == null)
			return 0;
		
		int compare = key.compareTo(x.key);
		
		if (compare < 0)
			return rank(x.left, key);
		else if (compare > 0)
			return rank(x.right, key) + size(x.left) + 1;
		else
			return size(x.left);
	}
	
	public Key select(int k){
		return select(root, k).key;
	}
	
	private Node select(Node x, int k){
		if (x == null)
			return null;
		
		int t = size(x.left);
		
		if (t > k)
			return select(x.left, k);
		else if (t < k)
			return select(x.right, k-t-1);
		else
			return x;
	}
	
	public Key ceiling(Key key){
		Node x = ceiling(root, key);
		
		if (x == null)
			return null;
		else
			return x.key;
	}
	
	private Node ceiling(Node x, Key key){
		if (x == null)
			return null;
		
		int compare = key.compareTo(x.key);
		
		if (compare == 0)
			return x;
		else if (compare > 0)
			return ceiling(x.right, key);
		else {
			Node y = ceiling(x.left, key);
			
			if (y != null)
				return y;
			else
				return x;
		}
	}
	
	public int size(){
		return size(root);
	}
	
	private int size(Node x){
		if (x == null)
			return 0;
		else
			return x.n;
	}
	
	public int size(Key lo, Key hi){
		if (hi.compareTo(lo) < 0)
			return 0;
		else if (contains(hi))
			return rank(hi) - rank(lo) + 1;
		else
			return rank(hi) - rank(lo);
	}
	
	public Iterable<Key> keys(){
		return keys(min(), max());
	}
	
	public Iterable<Key> keys(Key lo, Key hi){
		Queue<Key> queue = new Queue<Key>();
		keys(root, queue, lo, hi);
		return queue;
	}
	
	private void keys (Node x, Queue<Key> queue, Key lo, Key hi){
		if (x == null)
			return;
		
		int compareLo = lo.compareTo(x.key);
		int compareHi = hi.compareTo(x.key);
		
		if (compareLo < 0)
			keys(x.left, queue, lo, hi);
		
		if (compareLo <= 0 && compareHi >= 0)
			queue.enqueue(x.key);
		
		if (compareHi > 0)
			keys(x.right, queue, lo, hi);
	}
	
	public boolean isEmpty(){
		return size() == 0;
	}
	
	public boolean contains(Key key){
		return get(key) != null;
	}
}

特点

在由N个随机键构造的二叉查找树中，查找命中平均所需的比较次数为2lnN（约为1.39lgN），插入操作和查找未命中平均所需的比较次数为2lnN（约为1.39lgN）。

在一棵二叉查找树中，所有操作在最坏情况下所需的时间都和树的高度成正比。

比较

Markdown

红黑二叉查找树

只要谨慎地使用左旋转、右旋转和颜色转换这三种简单的操作，就能够保证插入操作后红黑树和2-3树的一一对应关系：

  1. 如果右子结点是红色的而左子结点是黑色的，进行左旋转
  2. 如果左子结点是红色的且它的左子结点也是红色的，进行右旋转
  3. 如果左右子结点均为红色，进行颜色转换

示意

Markdown

实现

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
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
public class RedBlackTree<Key extends Comparable<Key>, Value> {
	private static final boolean RED = true;
	private static final boolean BLACK = false;
	private Node root;
	
	private class Node{
		Key key;
		Value value;
		Node left;
		Node right;
		int n;
		boolean color;
		
		public Node(Key key, Value value, int n, boolean color){
			this.key = key;
			this.value = value;
			this.n = n;
			this.color = color;
		}
	}
	
	private boolean isRed(Node x){
		if (x == null)
			return BLACK;
		
		return x.color == RED;
	}
	
	private Node rotateLeft(Node h){
		Node x = h.right;
		h.right = x.left;
		x.left = h;
		
		x.color = h.color;
		h.color = RED;
		x.n = h.n;
		h.n = size(h.left) + size(h.right) + 1;
		
		return x;
	}
	
	private Node rotateRight(Node h){
		Node x = h.left;
		h.left = x.right;
		x.right = h;
		
		x.color = h.color;
		h.color = RED;
		x.n = h.n;
		h.n = size(h.left) + size(h.right) + 1;
		
		return x;
	}
	
	private void flipColors(Node h){
		h.left.color = !h.left.color;
		h.right.color = !h.right.color;
		h.color = !h.color;
	}
	
	private Node balance(Node h){
		if (isRed(h.left) && isRed(h.left.left))
			h = rotateRight(h);
		
		if (isRed(h.right))	
			h = rotateLeft(h);
		
		if (isRed(h.left) && isRed(h.right))
			flipColors(h);
		
		h.n = size(h.left) + size(h.right) + 1;
		
		return h;
	}
	
	private Node moveRedLeft(Node h){
		flipColors(h);
		
		if (isRed(h.right.left)){
			h.right = rotateRight(h.right);
			h = rotateLeft(h);
		}
		
		return h;
	}
	
	private Node moveRedRight(Node h){
		flipColors(h);
		
		if (isRed(h.left.left))
			h = rotateRight(h);
		
		return h;
	}
	
	public void put(Key key, Value value){
		root = put(root, key, value);
		root.color = BLACK;
	}
	
	private Node put(Node h, Key key, Value value){
		if (h == null)
			return new Node(key, value, 1, RED);
		
		int compare = key.compareTo(h.key);
		
		if (compare < 0)
			h.left = put(h.left, key, value);
		else if (compare > 0)
			h.right = put(h.right, key, value);
		else
			h.value = value;
		
		if (isRed(h.left) && isRed(h.left.left))
			h = rotateRight(h);
		
		if (!isRed(h.left) && isRed(h.right))	
			h = rotateLeft(h);
		
		if (isRed(h.left) && isRed(h.right))
			flipColors(h);
		
		h.n = size(h.left) + size(h.right) + 1;
		
		return h;
	}
	
	public Value get(Key key){
		return get(root, key);
	}
	
	private Value get(Node x, Key key){
		while (x != null){
			int compare = key.compareTo(x.key);
			
			if (compare < 0)
				x = x.left;
			else if (compare > 0)
				x = x.right;
			else
				return x.value;
		}
		
		return null;
	}
	
	public void delete(Key key){
		if (!isRed(root.left) && !isRed(root.right))
			root.color = RED;
		
		root = delete(root, key);
		
		if (!isEmpty())
			root.color = BLACK;
	}
	
	private Node delete(Node h, Key key){
		if (key.compareTo(h.key) < 0){
			if (!isRed(h.left) && !isRed(h.left.left))
				h = moveRedLeft(h);
			
			h.left = delete(h.left, key);
		}
		else{
			if (isRed(h.left))
				h = rotateRight(h);
			//如果被查找的键在树的底部，可以直接删除它
			if (h.right == null && key.compareTo(h.key) == 0)
				return null;
			
			if (!isRed(h.right) && !isRed(h.right.left))
				h = moveRedRight(h);
			//如果不在，需要将它和它的后继结点交换
			if (key.compareTo(h.key) == 0){
				h.key = min(h.right).key;
				h.value = get(h.right, min(h.right).key);
				h.right = deleteMin(h.right);
			}
			else
				h.right = delete(h.right, key);
		}
		
		return balance(h);
	}
	
	public void deleteMin(){
		if (!isRed(root.left) && !isRed(root.right))
			root.color = RED;
		
		root = deleteMin(root);
		
		if (!isEmpty())
			root.color = BLACK;
	}
	
	private Node deleteMin(Node h){
		if (h.left == null)
			return null;
		
		if (!isRed(h.left) && !isRed(h.left.left))
			h = moveRedLeft(h);
		
		h.left = deleteMin(h.left);
		
		return balance(h);
	}
	
	public void deleteMax(){
		if (!isRed(root.left) && !isRed(root.right))
			root.color = RED;
		
		root = deleteMax(root);
		
		if (!isEmpty())
			root.color = BLACK;
	}
	
	private Node deleteMax(Node h){
		if (isRed(h.left))
			h = rotateRight(h);
		
		if (h.right == null)
			return null;
		
		if (!isRed(h.right) && !isRed(h.right.left))
			h = moveRedRight(h);
		
		h.right = deleteMax(h.right);
		
		return balance(h);
	}
	
	public int size(){
		return size(root);
	}
	
	private int size(Node x){
		if (x == null)
			return 0;
		else
			return x.n;
	}
	
	public int size(Key lo, Key hi){
		if (hi.compareTo(lo) < 0)
			return 0;
		else if (contains(hi))
			return rank(hi) - rank(lo) + 1;
		else
			return rank(hi) - rank(lo);
	}
	
	public int rank(Key key){
		return rank(root, key);
	}
	
	private int rank(Node x, Key key){
		if (x == null)
			return 0;
		
		int compare = key.compareTo(x.key);
		
		if (compare < 0)
			return rank(x.left, key);
		else if (compare > 0)
			return rank(x.right, key) + size(x.left) + 1;
		else
			return size(x.left);
	}
	
	public Key select(int k){
		return select(root, k).key;
	}
	
	private Node select(Node x, int k){
		if (x == null)
			return null;
		
		int t = size(x.left);
		
		if (t > k)
			return select(x.left, k);
		else if (t < k)
			return select(x.right, k-t-1);
		else
			return x;
	}
	
	public Key floor(Key key){
		Node x = floor(root, key);
		
		if (x == null)
			return null;
		else
			return x.key;
	}
	
	private Node floor(Node x, Key key){
		if (x == null)
			return null;
		
		int compare = key.compareTo(x.key);
		
		if (compare == 0)
			return x;
		else if (compare < 0)
			return floor(x.left, key);
		else {
			Node y = floor(x.right, key);
			
			if (y != null)
				return y;
			else
				return x;
		}
	}
	
	public Key ceiling(Key key){
		Node x = ceiling(root, key);
		
		if (x == null)
			return null;
		else
			return x.key;
	}
	
	private Node ceiling(Node x, Key key){
		if (x == null)
			return null;
		
		int compare = key.compareTo(x.key);
		
		if (compare == 0)
			return x;
		else if (compare > 0)
			return ceiling(x.right, key);
		else {
			Node y = ceiling(x.left, key);
			
			if (y != null)
				return y;
			else
				return x;
		}
	}
	
	public Key min(){
		return min(root).key;
	}
	
	private Node min(Node x){
		if (x.left == null)
			return x;
		else
			return min(x.left);
	}
	
	public Key max(){
		return max(root).key;
	}
	
	private Node max(Node x){
		if (x.right == null)
			return x;
		else
			return max(x.right);
	}
	
	public Iterable<Key> keys(){
		return keys(min(), max());
	}
	
	public Iterable<Key> keys(Key lo, Key hi){
		Queue<Key> queue = new Queue<Key>();
		keys(root, queue, lo, hi);
		return queue;
	}
	
	private void keys (Node x, Queue<Key> queue, Key lo, Key hi){
		if (x == null)
			return;
		
		int compareLo = lo.compareTo(x.key);
		int compareHi = hi.compareTo(x.key);
		
		if (compareLo < 0)
			keys(x.left, queue, lo, hi);
		
		if (compareLo <= 0 && compareHi >= 0)
			queue.enqueue(x.key);
		
		if (compareHi > 0)
			keys(x.right, queue, lo, hi);
	}
	
	public boolean contains(Key key){
		return get(key) != null;
	}
	
	public boolean isEmpty(){
		return size() == 0;
	}
}

特点

一棵大小为N的红黑树的高度不会超过2lgN。

一棵大小为N的红黑树中，根结点到任意结点的平均路径长度为~1.00lgN。

在一棵红黑树中，以下操作在最坏情况下所需的时间是对数级别的：查找（get）、插入（put）、查找最小键、查找最大键、floor、ceiling、rank、select、删除最小键（deleteMin）、删除最大键（deleteMax）、删除（delete）和范围查询。

比较

Markdown

散列

使用散列的查找算法分为两步。第一步是用散列函数将被查找的键转化为数组的一个索引（散列函数）；第二步就是一个处理碰撞冲突的过程（拉链法和线性探测法）。

因为需要的是数组的索引而不是一个32位的整数，在实现中会将默认的hashCode()方法和除留余数法结合起来产生一个0到M-1的整数，方法如下：

1
2
3
private int hash(Key x){
    return (x.hashCode() & 0x7fffffff) % M;
}

这段代码会将符号位屏蔽（将一个32位整数变为一个31位非负整数），然后用除留余数法计算它除以M的余数。在使用这样的代码一般会将数组的大小M取为素数以充分利用原散列值的所有位。

基于拉链法的散列表（链表数组）

将大小为M的数组中的每个元素指向一条链表，链表中的每个结点都存储了散列值为该元素的索引的键值对。

查找分两步：首先根据散列值找到对应的链表，然后沿着链表顺序查找相应的键。

示意

Markdown

实现

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
public class SeparateChainHash<Key, Value> {
	private int M;
	private int N;
	private SequentialSearch<Key, Value>[] st;
	
	public SeparateChainHash(int M){
		this.M = M;
		this.N = 0;
		
		st = (SequentialSearch<Key, Value>[]) new SequentialSearch[M];
		for (int i = 0; i < M; i++)
			st[i] = new SequentialSearch();
	}
	
	private int hash(Key x){
	    return (x.hashCode() & 0x7fffffff) % M;
	}
	
	public void put(Key key, Value value){
		int m = hash(key);
		
		if (!contains(key))
			N++;
		
		st[m].put(key, value);
	}
	
	public Value get(Key key){
		int m = hash(key);
		return st[m].get(key);
	}
	
	public void delete(Key key){
		int m = hash(key);
		
		if (contains(key))
			N--;
		
		st[m].delete(key);
	}
	
	public Iterable<Key> keys(){
		Queue<Key> queue = new Queue<Key>();
		
		for (int i = 0; i < st.length; i++) {
			for (Key key : st[i].keys())
				queue.enqueue(key);
		}
		
		return queue;
	}

	public boolean contains(Key key){
		return get(key) != null;
	}
	
	public int size(){		
		return N;
	}
	
	public boolean isEmpty(){
		return size() == 0;
	}
}

特点

在一张含有M条链表和N个键的散列表中，任意一条链表中的键的数量均在N/M的常熟因子范围内的概率无限趋于1，未命中查找和插入操作所需的比较次数为～N/M。

基于线性探测法的散列表（并行数组）

用大小为M的数组保存N个键值对，其中M>N，需要依靠数组中的空位解决碰撞冲突。基于这种策略的所有方法被统称为开放地址散列表。

最简单的方法叫做线性探测法：当碰撞发生时（当一个键的散列值已经被另一个不同的键占用），直接检查散列表中的下一个位置（将索引值加1）。这样的线性探测可能会产生三种结果：

  1. 命中，该位置的键和被查找的键相同
  2. 未命中，键为空（该位置没有键）
  3. 继续查找，该位置的键和被查找的键不同

示意

Markdown

实现

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
public class LinearProbingHash<Key, Value> {
	private int M;
	private int N;
	private Key[] keys;
	private Value[] values;
	
	public LinearProbingHash(int M){
		this.M = M;
		keys = (Key[]) new Object[M];
		values = (Value[]) new Object[M];
	}
	
	private int hash(Key x){
	    return (x.hashCode() & 0x7fffffff) % M;
	}
	
	private void resize(int m){
		LinearProbingHash<Key, Value> tmp = new LinearProbingHash<Key, Value>(m);
		
		for (int i = 0; i < M; i++){
			if (keys[i] != null)
				tmp.put(keys[i], values[i]);
		}
		
		this.M = m;
		keys = tmp.keys;
		values = tmp.values;
	}
	
	public void put(Key key, Value value){
		if (N >= M / 2)
			resize(2 * M);
		
		int m = hash(key);
		
		for (m = hash(key); keys[m] != null; m = (m + 1) % M){
			if (keys[m].equals(key)){
				values[m] = value;
				return;
			}
		}
		
		keys[m] = key;
		values[m] = value;
		N++;
	}
	
	public Value get(Key key){
		for (int m = hash(key); keys[m] != null; m = (m + 1) % M){
			if (keys[m].equals(key))
				return values[m];
		}
		
		return null;
	}
	
	public void delete(Key key){
		int m;
		
		for (m = hash(key); keys[m] != null; m = (m + 1) % M){
			if (keys[m].equals(key)){
				keys[m] = null;
				values[m] = null;
				break;
			}
		}
		
		for (m = (m + 1) % M; keys[m] != null; m = (m + 1) % M){
			Key k = keys[m];
			Value v = values[m];
			
			keys[m] = null;
			values[m] = null;
			
			put(k, v);
			N--;
		}
		
		N--;
		
		if (N > 0 && N == M / 8)
			resize(M / 2);
	}
	
	public Iterable<Key> keys(){
		Queue<Key> queue = new Queue<Key>();
		
		for (int i = 0; i < M; i++){
			if (keys[i] != null)
				queue.enqueue(keys[i]);
		}
		
		return queue;
	}
	
	public boolean contains(Key key){
		return get(key) != null;
	}
	
	public int size(){		
		return N;
	}
	
	public boolean isEmpty(){
		return size() == 0;
	}
}

特点

在一张大小为M并含有N=aM个键的基于线性探测的散列表中，命中和未命中的查找所需的探测次数分别为：

Markdown

假设一张散列表能够自己调整数组的大小，初始为空。执行任意数序的t次查找、插入和删除操作所需的时间和t成正比，所使用的内存量总是在表中的键的总数的常数因子范围内。

  1. 线性探测的平均成本取决于元素在插入数组后聚集成的一组连续的条目，也叫做键簇。短小的键簇才能保证较高的效率，因此需要动态调整数组的大小来保证使用率在1/8到1/2之间。

比较

将a=N/M称为散列表的使用率。对于基于拉链法的散列表，a是每条链表的长度，因此一般大于1；对于基于线性探测的散列表，a是表中已被占用的空间的比例，它是不可能大于1的。

特点

  1. 每种类型的键都需要一个优秀的散列函数
  2. 性能保证来自于散列函数的质量
  3. 散列函数的计算可能复杂而且昂贵
  4. 难以支持有序性相关的符号表操作

比较

Markdown

总结

Markdown
Markdown