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
| public class MyHashMap<K, V> {
class Node<K, V>{
/**
* 键
*/
private K key;
/**
* 值
*/
private V value;
/**
* 后继
*/
private Node<K, V> next;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
public Node(K key, V value, Node<K, V> next) {
this.key = key;
this.value = value;
this.next = next;
}
}
/**
* 默认容量
*/
private static final int DEFAULT_CAPACITY = 16;
/**
* 默认负载因子
*/
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* MyHashMap的大小
*/
private int size;
/**
* 桶数组
*/
private Node<K, V>[] buckets;
/**
* 无参构造方法，设置桶数组大小为默认容量
*/
public MyHashMap(){
this.buckets = new Node[DEFAULT_CAPACITY];
this.size = 0;
}
/**
* 有参构造器，设置桶的容量
* @param capacity int
*/ public MyHashMap(int capacity){
buckets = new Node[capacity];
this.size = 0;
}
/**
* 哈希函数，获取哈希地址
* @param key K
* @return int
*/ private int hash(K key, int length){
return Math.abs(key.hashCode() & (length - 1));
}
/**
* 添加方法
* @param key K
* @param value V
*/ public void put(K key, V value){
if (size >= buckets.length * DEFAULT_LOAD_FACTOR) {
resize();
}
putVal(key, value, buckets);
}
/**
* 将元素存入Node数组
* @param key K
* @param value V
* @param table Node
*/ private void putVal(K key, V value, Node<K,V>[] table) {
//获取插入位置
int index = hash(key, table.length);
Node<K, V> node = table[index];
//如果要插入的位置为空，则插入元素
if (node == null) {
table[index] = new Node<>(key, value);
size++;
return; }
//如果不为空，说明发生了哈希冲突，遍历链表使用链地址法
while (node != null){
//如果元素的key和节点的相同，则覆盖
if ((node.key.hashCode() == key.hashCode()) && (node.key == key || node.key.equals(key))){
node.value = value;
return; }
node = node.next;
}
//新建节点插入链表头部
Node<K, V> kvNode = new Node<>(key, value, table[index]);
table[index] = kvNode;
size++;
}
/**
* 扩容
*/
private void resize() {
//创建两倍容量的新数组
Node<K, V>[] newNode = new Node[buckets.length * 2];
rehash(newNode);
buckets = newNode;
}
/**
* 重新哈希元素
* @param newNode Node<K,V>[]
*/ private void rehash(Node<K,V>[] newNode) {
//重新MyHashMap设置大小
this.size = 0;
//将旧的桶数组的元素移到新的桶数组中
for (int i = 0; i < buckets.length; i++){
if (buckets[i] == null){
continue;
}
Node<K, V> node = buckets[i];
while (node != null){
//将元素放入新的桶数组
putVal(node.key, node.value, newNode);
node = node.next;
}
}
}
/**
* 获取元素
* @param key K
* @return V
*/ public V get(K key){
//获取地址
int index = hash(key, buckets.length);
if (buckets[index] == null) {
return null;
}
Node<K, V> node = buckets[index];
while (node != null){
if ((node.key.hashCode() == key.hashCode()) && (node.key == key || node.key.equals(key))){
return node.value;
}
//如果链表存在遍历链表
if (node.next != null){
node = node.next;
}
}
return null;
}
/**
* 移除元素
* @param key K
*/ public void remove(K key){
//获取地址
int index = hash(key, buckets.length);
if (buckets[index] == null) {
return;
}
if (buckets[index].key.equals(key)) {
buckets[index] = buckets[index].next;
return; // 移除成功，结束操作
}
Node<K, V> node = buckets[index];
while (node.next != null) {
if (node.next.key.equals(key)) {
node.next = node.next.next;
return; // 移除成功，结束操作
}
node = node.next; // 继续遍历链表下一个节点
}
}
/**
* 返回MyHashMap大小
* @return int
*/ public int size(){
return this.size;
}
}
|