HashMap 可以说是我们在开发中经常使用的到, 在 Java 的数据结构基础里，HashMap 无疑是一个非常重要的数据结构 现在看看源码里面的方法具体都干了一下什么
简单使用
1
2
3
4
5
6
7
|
HashMap<String, String> map = new HashMap<>();
map.put(null, null);
map.put("1", "22");
map.put("2", "33");
map.put("1", "22");
map.get("2");
map.remove("2"); |
首先看看源码中都有那些成员变量, 然后我们根据上面的数据存储方式,看看源码中经历了什么
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
//默认的初始容量为16，必须是2的幂次方。
static final int DEFAULT_INITIAL_CAPACITY =1 << 4; // 16;
//最大容量，默认为2的30次方，
static final int MAXIMUM_CAPACITY = 1 << 30;
//加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 一个空的数组
static final HashMapEntry<?,?>[] EMPTY_TABLE = {};
//数组表，大小可以改变，且大小必须为2的幂
transient HashMapEntry<K,V>[] table = (HashMapEntry<K,V>[]) EMPTY_TABLE;
//当前实时的Map中key-value映射的个数
transient int size;
//当实际大小超过临界值时，会进行扩容threshold = 加载因子*容量 ==》 16*0.75=12
int threshold;
//加载因子 0.75
final float loadFactor = DEFAULT_LOAD_FACTOR;
//Hash表结构性修改次数
transient int modCount; |
无参数构造方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public HashMap() {
// 当我们直接 new 对象创建的时候, 根据我们上面的成员变量可以知道, 创建了一个容量为16,加载因子为0.75
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
// 然后是直接到了这个地方
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 这里做了一个判断, 比最大值还大的时候, 默认最大值的容量大小
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// 成员变量的赋值操作
this.loadFactor = loadFactor;
threshold = initialCapacity;
init(); // 这个默认是一个空的实现, 到这里, 我们就算是结束了
} |
在上面的注释中发现加载因子, 何为加载因子, 我们都知道 HashMap 是一个动态扩容的散列列表, 那么他是怎么触发扩容的呢, 他是 (当前的实时容量 > 集合容量*加载因子 ) 比如我们默认第一次初始化的容量是16, 那么16 * 0.75 = 12, 一般这个值的作用是用来判断是否需要扩容的, 其实是否需要扩容还有另外一个触发条件,后面会分析到
有参构造
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//这里还是一样的, 只不过自己指定了大小
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
threshold = initialCapacity;
init();
} |
存储数据put方法
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
|
public V put(K key, V value) {
// 一开始table为空的时候，创建一个数组，初始化容量大小和加载因子threshold
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 这句话说明可以存储一个为null的key的元素
if (key == null)
return putForNullKey(value);
// 根据key计算出hash值
int hash = hash(key);
// 根据hash值和表的长度, 计算元素需要存储的位置, (后续也可以直接根据key,其实换算后的index值,就可以快速确定元素在表中的位置, 像数组直接查询index的位置一样,速度快)
int i = indexFor(hash, table.length);
// 判断是否存在key相同的元素，有则会覆盖
for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//如果key相同的话, 就直接覆盖value值,更新作用, 也就是说, key相同的话,会覆盖旧的元素
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this); // 更新了数据都会回调这个方法
//如果相同key，则返回修改了的老元素，结束方法
return oldValue;
}
}
// 计数器增加1（如果是修改老元素的话，不会计数的）
modCount++;
//添加新元素， key不相同, 根据hash值,key,value, 表中的位置,将元素存储起来
addEntry(hash, key, value, i);
return null;
} |
创建表
1
2
3
4
5
6
7
8
9
10
11
12
|
/**
* Inflates the table.
*/
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize // 找一个2的倍数
int capacity = roundUpToPowerOf2(toSize);
// 按照上面的描述, 首次是16大小, 16 * 0.75 = 12,threshold为12
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity]; // 创建了Evtry对象, 下面看看这个对象的结构
initHashSeedAsNeeded(capacity);
} |
数据结构的方式, Entry对象
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
|
static class Entry<K,V> implements Map.Entry<K,V> {
final K key; // 存储的kay
V value;
Entry<K,V> next; // 链向下一个 对象
int hash; // 转换的hash值
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
// 重写了equals方法,对元素进行比较
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
public final int hashCode() {
return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
public final String toString() {
return getKey() + "=" + getValue();
}
/**
* This method is invoked whenever the value in an entry is
* overwritten by an invocation of put(k,v) for a key k that's already
* in the HashMap.
*/
void recordAccess(HashMap<K,V> m) {
}
/**
* This method is invoked whenever the entry is
* removed from the table.
*/
void recordRemoval(HashMap<K,V> m) {
}
} |
存储可以为null的key键
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
private V putForNullKey(V value) {
// 查找key为null的位置， 修改老元素，并返回
for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) {
// 这里和上面的操作是一样的, 如果是key相同的话,也做到更新,覆盖的操作
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
// 返回老元素
return oldValue;
}
}
modCount++;
// 增加元素key为null的元素
addEntry(0, null, value, 0);
return null;
} |
添加新的元素 addEntry()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
void addEntry(int hash, K key, V value, int bucketIndex) {
// 这里就是触发扩容的条件了
// 如果size大于临界值的话,将进行扩容
// 有两个条件： 1当前元素存储的个数大于阀值 + 是否发生了hash冲突
if ((size >= threshold) && (null != table[bucketIndex])) {
// 进行扩容,原来的2倍
resize(2 * table.length);
// 下面是扩容后，重新计算value需要存储的位置
// 如果key为null的话,那么hash值为0
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
// 根据hash值重新 计算在表中的位置
bucketIndex = indexFor(hash, table.length);
}
// 数据插入
createEntry(hash, key, value, bucketIndex);
} |
createEntry 创建新的对象
1
2
3
4
5
6
7
8
9
10
11
12
|
void createEntry(int hash, K key, V value, int bucketIndex) {
//情况1: 当没有发生hash冲突的时候 table[bucketIndex] 为null, e == null ，然后创建一个新的HashMapEntry<>(hash, key, value, null); 给 table[bucketIndex]
// 情况2: 当发送了hash冲突的时候， 那么table[bucketIndex] 和 e 都不为空了，
// 那么就形成了一个单链表 table[bucketIndex] = new HashMapEntry<>(hash, key, value（新的值）, 原来的值 e);
HashMapEntry<K,V> e = table[bucketIndex];
table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
size++; //计数
}
} |
get方法
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
|
public V get(Object key) {
if (key == null) //获取key 为null的value值
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
// getEntry方法
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
// 根据key计算出hash值
int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
// 使用hash值,计算元素在表中的位置,找到后,将改元素返回
for (HashMapEntry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
//查找key相同的返回
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
} |
删除元素
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
|
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
// 删除成功, 将删除的 value 返回
return (e == null ? null : e.value);
}
// removeEntryForKey方法
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e != null) {
Entry<K,V> next = e.next;
Object k;
// 遍历循环，查找key相同的，删除，
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++; // 修改的次数
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
} |
总结
好了, 到这里差不多分析完了, 总结一下, 创建过程, 添加数据,删除数据,都做了那些事情
底层的数据结构是其实是数组(数组+链表) (链表散列,即是数组和链表的结合体)
创建一个对象,默认初始化都容量大小为 16, 除非是自己指定了大小, 然后初始化加载因子为 0.75, 然后添加数据, 创建表, 创建 threshold, 然后对为 null 的key, 进行判断存储, 如果不为 null 的值, 对 key 进行 hash, 计算将要存储在表中的位置, 然后 for 循环遍历查找是否存在这个 key 的 value, 存在则更新, 然后将其返回, 否则添加数据, 然后判断是否扩容(当前的实时的容量大小是否 >= threshold + 是否发生了 hash 冲突) , 符合条件触发为 2 的倍数扩容, 然后添加元素
获取元素: 通过 key 计算 hash 值, 然后根据hash值计算在表中的位置, 通过比较 key 是否相同, 相同则返回
删除元素: 通过 key 计算 hash 值, 然后计算在表中的位置, 通过比较 key 是否相同, 相同将其删除, 然后返回