前言
最近突然对Java中的容器产生了兴趣，比如：HashMap是使用什么结构存储数据的？当hash值相同时，会采用什么样的策略？Set是怎么实现的，为何能保证数据的唯一性？当这样的问题想要弄个明白时，我知道，是时候通过查看源码来解惑了，所以打算写关于Java容器的系列文章。
源码解析
存储原理
以哈希函数为对16取余数的哈希表来举例，那么需要有16个槽，槽1、槽2、槽3...槽16形成一个数组，而每个槽中都可能存储多个键值对，所以每个槽中使用链表来存储。
当要存储一个键值对(key,value)时
- 首先对key求hash值，往往是一个非常大的数字
- 对hash求余数，得到槽的下标index
- 将这个键值对插入到链表的首部
接下来，我们通过源码来查看实现的细节。
重要成员变量的说明
//创建HashMap时，最小容量，即最少要创建四个空间
private static final int MINIMUM_CAPACITY = 4;
//HashMap最多能够存储的键值对个数
private static final int MAXIMUM_CAPACITY = 1 << 30;
//即上文中所说的，槽1、槽２......槽16形成的数组，每个位置都存储一个链表的头结点
transient HashMapEntry<K, V>[] table;
源码解析
首先我们来看一下put函数
public V put(K key, V value) {
if (key == null) {
return putValueForNullKey(value);
}
int hash = Collections.secondaryHash(key); //获取key的hash值
HashMapEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1); //相当于对hash取余数，获得数组的下标
for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) { //tab[index]存储了一个链表,这个循环用来遍历链表
if (e.hash == hash && key.equals(e.key)) { //如果以前存储过相同key的键值对
preModify(e);
V oldValue = e.value;
e.value = value; //将旧value存储为新value
return oldValue; //返回旧value
}
}
// No entry for (non-null) key is present; create one
modCount++;
if (size++ > threshold) { //存储的键值对个数比较多了，需要扩容
tab = doubleCapacity(); //将容量扩大为2倍
index = hash & (tab.length - 1); //在扩容后的数组中，对应新的index
}
addNewEntry(key, value, hash, index); //将键值对添加到tab[index]存储的链表中
return null;
}
注释已经写的非常详细了，不再赘述，下面看一下addNewEntry函数
void addNewEntry(K key, V value, int hash, int index) {
table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]);
}
HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) {
this.key = key;
this.value = value;
this.hash = hash;
this.next = next;
}
HashMapEntry是链表的一个节点，它内部的next变量用来指向下一个节点，所以addNewEntry函数的作用就是：把要put的键值对添加到对应链表的首部。
下面我们来看一下get函数：
public V get(Object key) {
if (key == null) {
HashMapEntry<K, V> e = entryForNullKey;
return e == null ? null : e.value;
}
int hash = Collections.secondaryHash(key); //获取key的hash值
HashMapEntry<K, V>[] tab = table;
for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
e != null; e = e.next) { //遍历链表
K eKey = e.key;
if (eKey == key || (e.hash == hash && key.equals(eKey))) { //如果key为同一个引用，或者hash、key都相等
return e.value;
}
}
return null;
}
线程安全性
通过查看源码，发现HashMap并没有处理线程同步问题，所以大家在多个线程操作HashMap时，一定要使用同步来确保数据的准确性。
如果有疑问或者发现本文的错误之处，欢迎评论～
