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
class MyHashMap<K,V>{
private Node<K, V>[] table;
private int size;
class Node<K,V>{
protected K key;
protected V value;
protected int hash;
protected Node<K, V> next;
public Node(K key, V value, int hash) {
this.key = key;
this.value = value;
this.hash = hash;
}
}
public MyHashMap(int capacity){
table = new Node[capacity];
}
public Iterator<Node<K, V>> iterator(){
return new Itr();
}
class Itr implements Iterator<Node<K, V>>{
private int currentIndex;//当前桶的位置
private Node<K, V> nextNode;//返回的下一个数据节点
private Node<K, V> currentNode; //上一次next返回的数据节点
public Itr(){
if(MyHashMap.this.isEmpty()){
return;
}
for(int i=0; i < table.length; i++){
currentIndex = i;
Node<K, V> firstNode = table[i];
if(firstNode != null){
nextNode = firstNode;
return;
}
}
}
@Override
public boolean hasNext() {
return nextNode != null;
}
@Override
public Node<K, V> next() {
//返回下一个数据节点
currentNode = nextNode;
//nextNode指向自己的next
nextNode = nextNode.next;
if(nextNode == null){
//说明当前桶的链表已经遍历完毕
//寻找下一个非空的桶
for(int i=currentIndex+1; i<MyHashMap.this.table.length; i++){
//设置当前桶位置
currentIndex = i;
Node<K,V> firstNode = MyHashMap.this.table[currentIndex];
if(firstNode != null){
nextNode = firstNode;
break;
}
}
//nextNode保存的就是下一个非空的数据节点
}
return currentNode;
}
@Override
public void remove() {
if(currentNode == null){
return;
}
K currentKey = currentNode.key;
MyHashMap.this.remove(currentKey);
currentNode = null;
}
}
public void resize(){
//扩容桶table
Node<K, V>[] newTable = new Node[table.length * 2];
for(int i=0; i<table.length; i++){
//将oldTable中每一个位置映射到newTable中
rehash(i, newTable);
}
this.table = newTable;
}
public void rehash(int index, Node<K,V>[] newTable){
Node<K, V> currentNode = table[index];
if(currentNode == null){
return;
}
Node<K, V> lowListHead = null; //低位的头
Node<K, V> lowListTail = null; //低位的尾
Node<K, V> highListHead = null; //高位的头
Node<K, V> highListTail = null; //高位的尾
//currentNode表示oleTable下index位置中当前节点
while(currentNode != null){
//当前节点在newTable中的位置
int newIndex = newTable.length-1 & hash(currentNode.key);
if(newIndex == index){
//映射到原先下标处
if(lowListHead == null){
lowListHead = currentNode;
lowListTail = currentNode;
}else{
lowListTail.next = currentNode;
lowListTail = lowListTail.next;
}
}else{
//newIndex与index不等，映射到高位下标处
if(highListHead == null){
highListHead = currentNode;
highListTail = currentNode;
}else{
highListTail.next = currentNode;
highListTail = lowListTail.next;
}
}
currentNode = currentNode.next;
}
//将lowList head->tail之前的节点链接到index位置
if(lowListTail != null){
newTable[index] = lowListHead;
lowListHead.next = null;
}
//将highList head->tail之前的节点链接到index+table.length位置
if(highListTail != null){
newTable[index+this.table.length] = highListHead;
highListHead.next = null;
}
}
public int hash(Object key) {
int h;
return (h = key.hashCode()) ^ (h >>> 16);
}
public void put(K key, V value){
//确定所要添加元素的位置
int hash = hash(key);//散列码
int index = table.length-1 & hash;//确定的位置
//newNode -》table[index] == null || key在map不存在
//table[index]已经存在数据
//table[index]不存在数据
Node<K, V> firstNode = table[index];//得到该位置的第一个节点
if(firstNode == null){
table[index] = new Node(key, value, hash);
size++;
}else{
//第一种情况 key已经存在 考虑新值覆盖旧值
//第二种情况 key不存在
封装一个新的node尾插法插入链表
if(firstNode.key.equals(key)){
firstNode.value = value; //新值替换旧值
}else{
Node<K,V> tmp = firstNode;
while(tmp.next != null && !tmp.key.equals(key)){
tmp = tmp.next;
}
if(tmp.next == null){
if(tmp.key.equals(key)){
tmp.value = value; //新值替换旧值
}else{
tmp.next = new Node(key, value, hash);
size++;
}
}else{
tmp.value = value;
}
}
}
}
public boolean remove(K key){
int hash = hash(key);
int index = table.length-1 & hash;
Node<K, V> firstNode = table[index];
if(firstNode == null){
return false;
}else{
if(firstNode.next == null){
if(firstNode.key.equals(key) && firstNode.hash == hash){
//为什么判断key是否相等的同时还需要判断散列码
table[index] = null;
return true;
}
}
Node<K,V> tmpPrev = firstNode;
Node<K, V> tmp = firstNode.next;
while(tmp.next != null){
if(tmp.key.equals(key) && tmp.hash == hash){
//tmp之前节点的next指向tmp.next
tmpPrev.next = tmp.next;
size--;
}else{
tmpPrev = tmp;
tmp = tmp.next;
}
}
}
return false;
}
public Node<K,V> get(K key){
//获取对应key所在数组的index
int hash = hash(key);//散列码
int index = table.length - 1 & hash; //定位key记录所在的位置
Node<K, V> firstNode = table[index];
if (firstNode == null) {
return null;
}
if (hash == firstNode.hash && key == firstNode.key) {
return firstNode;
} else {
//遍历链表
Node<K, V> currentNode = firstNode.next;
while (currentNode != null) {
if (currentNode.hash == hash && currentNode.key == key) {
return currentNode;
}
currentNode = currentNode.next;
}
}
return null;
}
public boolean isEmpty(){
return size == 0;
}
}
public class TestDemo11 {
public static void main(String[] args) {
}
}

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
 * static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
16
* static final int MAXIMUM_CAPACITY = 1 << 30;
* static final float DEFAULT_LOAD_FACTOR = 0.75f;
* static final int TREEIFY_THRESHOLD = 8; 桶上的节点个数大于8时会转为红黑树
* static final int UNTREEIFY_THRESHOLD = 6; 桶上的绩点个数小于6时会转为链表
* static final int MIN_TREEIFY_CAPACITY = 64; 桶中结构转化为红黑树对用的table的最小大小
* transient Node<K,V>[] table; 存储元素的数组 总是2的幂次方
* transient Set<Map.Entry<K,V>> entrySet;
哈希表中节点的集合
* transient int size;
* transient int modCount;
* int threshold; 临界值
* final float loadFactor;
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}

1
2
static class Entyr<K,V>extends WeakReference<Object>Entry 继承自WeakHashMap