Map是java开发中比较常用的数据结构，在jdk8中有对Map做一定的优化， 简单来说有以下四点：
- jdk8中会将链表会转变为红黑树
- 新节点插入链表的顺序不相同（jdk7是插入头结点，jdk8因为要遍历链表把链表变为红黑树所以采用插入尾结点）
- hash算法简化
- resize的逻辑修改（jdk7会出现死循环，jdk8不会）(死锁场景：http://www.importnew.com/22011.html)
以下对jdk7中的map做了简单的实现
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
import java.util.List;
import java.util.stream.Stream;
import static java.util.stream.Collectors.toList;
/**
* Map在jdk7中的实现
*
* User: xuguangwu
*/
public class MyHashMap<K, V> {
//默认初始化大小 16
private static final int DEFAULT_INITIAL_CAPACITY = 4;
//默认负载因子 0.75
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
private Entry[] table;
//临界值
private int threshold;
//元素个数
private int size;
public MyHashMap() {
this.table = new Entry[DEFAULT_INITIAL_CAPACITY];
threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
size = 0;
}
public static void main(String[] args) {
MyHashMap myHashMap = new MyHashMap();
myHashMap.put2("1", 1);
myHashMap.put2("2", 2);
myHashMap.put2("3", 3);
myHashMap.put2("4", 4);
myHashMap.put2("5", 5);
myHashMap.put2("6", 6);
List<String> strings = Stream.of("C", "A", "B")
.sorted()
.collect(toList());
System.out.println(myHashMap.get("5"));
}
private int index(K k) {
//根据key的hashcode和table长度取模计算key在table中的位置
return k.hashCode() % DEFAULT_INITIAL_CAPACITY;
}
public void put2(K key, V value) {
int index = index(key);
if (table[index] == null) {
table[index] = new Entry(key, value, null);
} else {
for (Entry<K, V> entry = table[index]; entry != null; entry = entry.next) {
Entry oldEntry = entry;
Entry newEntry = new Entry(key, value, oldEntry);
table[index] = newEntry;
}
}
}
public void put(K key, V value) {
//key为null时需要特殊处理，为简化实现忽略null值
if (key == null) return;
int index = index(key);
//遍历index位置的entry，若找到重复key则更新对应entry的值，然后返回
Entry entry = table[index];
while (entry != null) {
if (entry.getK().hashCode() == key.hashCode() && (entry.getK() == key || entry.getK().equals(key))) {
entry.setV(value);
return;
}
entry = entry.getNext();
}
//若index位置没有entry或者未找到重复的key，则将新key添加到table的index位置
add(index, key, value);
}
private void add(int index, Object key, Object value) {
//将新的entry放到table的index位置第一个，若原来有值则以链表形式存放
Entry entry = new Entry(key, value, table[index]);
table[index] = entry;
//判断size是否达到临界值，若已达到则进行扩容，将table的capacicy翻倍
if (size++ >= threshold) {
resize(table.length * 2);
}
}
private void resize(int capacity) {
if (capacity <= table.length) return;
Entry[] newTable = new Entry[capacity];
//遍历原table，将每个entry都重新计算hash放入newTable中
for (int i = 0; i < table.length; i++) {
Entry<K, V> old = table[i];
while (old != null) {
Entry next = old.getNext();
int index = index(old.getK());
old.setNext(newTable[index]);
newTable[index] = old;
old = next;
}
}
//用newTable替table
table = newTable;
//修改临界值
threshold = (int) (table.length * DEFAULT_LOAD_FACTOR);
// resize++;
}
public V get(K k) {
int index = index(k);
for (Entry<K, V> entry = table[index]; entry != null; entry = entry.next) {
if (entry.k.equals(k)) {
return entry.v;
}
}
return null;
}
class Entry<K, V> {
private K k;
private V v;
private Entry<K, V> next;
public Entry(K k, V v, Entry<K, V> next) {
this.k = k;
this.v = v;
this.next = next;
}
public K getK() {
return k;
}
public void setK(K k) {
this.k = k;
}
public V getV() {
return v;
}
public void setV(V v) {
this.v = v;
}
public Entry<K, V> getNext() {
return next;
}
public void setNext(Entry<K, V> next) {
this.next = next;
}
}
}
