说到HashMap相信大家并不陌生，这是一个非常常用的以键值对形式存储的数据结构，但是对其内部原理可能不是很了解，它的内部是以什么形式存储的，它的存取的性能号称能达到O(1)又是如何实现的，我们从源码来做个简要的分析。
主要成员变量
我们先来看以下HashMap主要有哪些成员变量
//最小值
private static final int MINIMUM_CAPACITY = 4;
//最大值，2的30次方
private static final int MAXIMUM_CAPACITY = 1 << 30;
//加载因子
static final float DEFAULT_LOAD_FACTOR = .75F;
//大小
transient int size;
//独立的entry，专用用来处理key为null的情况
transient HashMapEntry<K, V> entryForNullKey;
//加载的阀值，当size超过这个值时，将会调用doubleCapacity()方法扩容
private transient int threshold;
//存储数据的主要容器，一个HashMapEntry数组
transient HashMapEntry<K, V>[] table;
//分别是存储key和value的集合
private transient Set<K> keySet;
private transient Collection<V> values;
//存储Entry的集合
private transient Set<Entry<K, V>> entrySet;
可以看到存储数据的主要容器是一个数组，而HashMapEntry是我们循环遍历HashMap时的Entry的子类，下面我们看一下这个类
static class HashMapEntry<K, V> implements Entry<K, V> {
final K key;
V value;
final int hash;
HashMapEntry<K, V> next;
HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) {
...
}
...
}
table中的元素类型HashMapEntry，我们称之为桶，HashMapEntry里一个变量hash用于存储key的哈希值，还有一个next变量也是HashMapEntry类型，可见HashMapEntry是一个单链表结构，每一个桶都可以存储多个元素。
下面是HashMap的主要构造函数
public HashMap(int capacity) {
... //参数判断和capacity为0时的空表创建
//将capacity控制在既定的范围内并保证capacity为偶数
if (capacity < MINIMUM_CAPACITY) {
capacity = MINIMUM_CAPACITY;
} else if (capacity > MAXIMUM_CAPACITY) {
capacity = MAXIMUM_CAPACITY;
} else {
capacity = Collections.roundUpToPowerOfTwo(capacity);
}
makeTable(capacity); //创建一个容量大小为capacity的数组
}
makeTable方法中有如下代码：
threshold = (newCapacity >> 1) + (newCapacity >> 2);
其中threshold表示HashMap扩容的阀值，意思是在初始化时threshold等于总容量*0.75（加载因子），一旦HashMap中存储的元素数量超过threshold，就会对整个HashMap就行扩容。
扩容的方法如下
private HashMapEntry<K, V>[] doubleCapacity() {
HashMapEntry<K, V>[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
return oldTable; //如果旧数组的容量已经达到最大值，则直接返回
}
int newCapacity = oldCapacity * 2; //将容量大小增加到以前的两倍
HashMapEntry<K, V>[] newTable = makeTable(newCapacity);
if (size == 0) { //如果当前大小为空，则直接返回新数组
return newTable;
}
//把oldTable中的元素重新整理到newTable中
for (int j = 0; j < oldCapacity; j++) {
/*
* Rehash the bucket using the minimum number of field writes.
* This is the most subtle and delicate code in the class.
*/
HashMapEntry<K, V> e = oldTable[j];
if (e == null) {
continue;
}
int highBit = e.hash & oldCapacity;
HashMapEntry<K, V> broken = null;
newTable[j | highBit] = e;
for (HashMapEntry<K, V> n = e.next; n != null; e = n, n = n.next) {
int nextHighBit = n.hash & oldCapacity;
if (nextHighBit != highBit) {
if (broken == null)
newTable[j | nextHighBit] = n;
else
broken.next = n;
broken = e;
highBit = nextHighBit;
}
}
if (broken != null)
broken.next = null;
}
return newTable;
}
在重新组装table的过程使用了两个for循环遍历其中的元素，有一点复杂，我们先看HashMap的put方法，看看元素是如何存储的。
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); //计算出key的对应桶的下标
for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
if (e.hash == hash && key.equals(e.key)) {
preModify(e);
V oldValue = e.value;
e.value = value;
return oldValue; //key存在的情况下，直接更新value
}
}
// No entry for (non-null) key is present; create one
modCount++;
if (size++ > threshold) {
tab = doubleCapacity(); //size大于threshold时，调用扩容的方法，得到一个新的table
index = hash & (tab.length - 1);
}
addNewEntry(key, value, hash, index); //将新的桶更新到table中
return null;
}
put方法中，先计算出key的hash值，然后通过和table数组的最大index进行&操作，得到key在table里相对应的下标index，然后针对table[index]进行链表遍历，通过比较hash值和equals方法查找桶内是否存在相同的key，如果存在，则将新的value代替旧的存入，将旧的vaule返回；否则创建一个新的Entry，作为这个桶的头节点，最后返回空值。其实doubleCapacity方法只是将oldTable的遍历和newTable的定位及插入逻辑合并到了一起，原理跟put方法是十分类似的。
然后我们来看一下put方法的时间复杂度，该方法其实分为4个步骤，1.根据key计算出其hash值，并计算得到相应桶的下标index。2.查找table中index下标的Entry。3.遍历Entry为头节点的链表得到我们要找的Entry。4.取出Entry的value。
其中1、2、4步都能在O(1)时间内完成。我们之前了解到当size超过总容量*0.75后，会进行扩容，所以大部分情况下(key的hash分布较为均匀)，每个桶中的元素个数 <= 1，极少数情况 >=2，所以第三步也可以在O(1)内完成，我们可以认为其整体时间复杂度为O(1)。
get方法的逻辑跟put基本一样，有兴趣可以自行了解一下。
网友评论