-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathCode_02_RandomPool.java
More file actions
76 lines (63 loc) · 2.12 KB
/
Copy pathCode_02_RandomPool.java
File metadata and controls
76 lines (63 loc) · 2.12 KB
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
package algorithm.basic05;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
/**
* @Created by mood321
* @Date 2019/11/6 0006
* @Description TODO
*/
public class Code_02_RandomPool {
public static class Pool<K> {
private HashMap<K, Integer> keyIndexMap;
private HashMap<Integer, K> indexKeyMap;
private int size;
public Pool() {
this.keyIndexMap = new HashMap<K, Integer>();
this.indexKeyMap = new HashMap<Integer, K>();
this.size = 0;
}
public void insert(K key) {
if(!keyIndexMap.containsKey(key)){
keyIndexMap.put(key,this.size);
indexKeyMap.put(this.size++,key);
}
}
/**
* 这里删除要 考虑他原来size的问题
* @param key
*/
public void delete(K key) {
if(this.keyIndexMap.containsKey(key)){
Integer oldIndex = this.keyIndexMap.get(key);// 要删除的下标
K k = this.indexKeyMap.get(--this.size);// 原来最后最后一个值
keyIndexMap.put(k,oldIndex);//
indexKeyMap.put(oldIndex,k);//
keyIndexMap.remove(key); //
}
}
public K getRandom() {
if (this.size == 0) {
return null;
}
int randomIndex = (int) (Math.random() * this.size); // 0 ~ size -1
return this.indexKeyMap.get(randomIndex);
}
}
public static void main(String[] args) {
Pool<String> pool = new Pool<String>();
pool.insert("1");
pool.insert("2");
pool.insert("3");
pool.delete("1");
System.out.println(pool.keyIndexMap.get("1"));
pool.insert("1");
System.out.println(pool.keyIndexMap.get("1"));
System.out.println(pool.getRandom());
System.out.println(pool.getRandom());
System.out.println(pool.getRandom());
System.out.println(pool.getRandom());
System.out.println(pool.getRandom());
System.out.println(pool.getRandom());
}
}