-
Notifications
You must be signed in to change notification settings - Fork 84
/
HashTable.java
160 lines (143 loc) · 2.86 KB
/
HashTable.java
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
import java.util.TreeMap;
/**
* 哈希表
*
* @author ronglexie
* @version 2018/9/6
*/
public class HashTable<K, V> {
/** 最大容忍度,及上界*/
public static final int upperTol = 10;
/** 最小容忍度,及下界*/
public static final int lowerTol = 2;
/** 初始化容量*/
public static final int initCapacity = 7;
private TreeMap<K, V>[] hashTable;
private int M;
private int size;
public HashTable(int M){
this.M = M;
size = 0;
hashTable = new TreeMap[M];
for (int i = 0; i < M; i++) {
hashTable[i] = new TreeMap<>();
}
}
public HashTable(){
this(initCapacity);
}
public int getSize(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
private int hash(K key){
return key.hashCode() & 0x7fffffff % M;
}
/**
* 向哈希表中添加元素
*
* @param key
* @param value
* @return void
* @author ronglexie
* @version 2018/9/6
*/
public void add(K key, V value){
TreeMap<K, V> treeMap = hashTable[hash(key)];
if (treeMap.containsKey(key)){
treeMap.put(key,value);
}else {
treeMap.put(key,value);
size ++;
//扩容
if(size >= upperTol * M){
resize(2*M);
}
}
}
/**
* 从哈希表中移除元素
*
* @param key
* @return V
* @author ronglexie
* @version 2018/9/6
*/
public V remove(K key){
TreeMap<K, V> treeMap = hashTable[hash(key)];
V result = null;
if(treeMap.containsKey(key)){
result = treeMap.remove(key);
size --;
//缩容
if(size < lowerTol * M && M / 2 > initCapacity){
resize(M/2);
}
}
return result;
}
/**
* 修改哈希表中的元素
*
* @param key
* @param value
* @return void
* @author ronglexie
* @version 2018/9/6
*/
public void set(K key, V value){
TreeMap<K, V> treeMap = hashTable[hash(key)];
V result = null;
if(!treeMap.containsKey(key)){
throw new IllegalArgumentException(key + "doesn't exists!");
}
treeMap.put(key, value);
}
/**
* 查询哈希表中是否包含某个元素
*
* @param key
* @return boolean
* @author ronglexie
* @version 2018/9/6
*/
public boolean contains(K key){
return hashTable[hash(key)].containsKey(key);
}
/**
* 从哈希表中获取一个元素
*
* @param key
* @return V
* @author ronglexie
* @version 2018/9/6
*/
public V get(K key){
return hashTable[hash(key)].get(key);
}
/**
* 修改容量
*
* @param newCapacity
* @return void
* @author ronglexie
* @version 2018/9/7
*/
private void resize(int newCapacity) {
TreeMap<K, V>[] newHashTable = new TreeMap[newCapacity];
for (int i = 0; i < newCapacity; i++) {
newHashTable[i] = new TreeMap<>();
}
int oldM = this.M;
this.M = newCapacity;
for (int i = 0; i < oldM; i++) {
TreeMap<K, V> treeMap = hashTable[i];
for (K key : treeMap.keySet()) {
newHashTable[hash(key)].put(key, treeMap.get(key));
}
}
this.hashTable = newHashTable;
}
}