HashMap 在我们的项目开发当中会经常用到，今天我们通过它常用方法的源码来解析它的内部实现机制
构造方法
HashMap hashMap = new HashMap();
private static final int MINIMUM_CAPACITY = 4;
transient HashMapEntry<K, V>[] table;
private static final Entry[] EMPTY_TABLE
= new HashMapEntry[MINIMUM_CAPACITY >>> 1];
public HashMap() {
table = (HashMapEntry<K, V>[]) EMPTY_TABLE;
threshold = -1; // Forces first put invocation to replace EMPTY_TABLE
}
从构造方法可以看出它内部是一个HashMapEntry<K, V>对象的数组，(MINIMUM_CAPACITY >>> 1等于2)，数组的初始化大小是2
从上面可以得出结论：HashMap内部是以一个HashMapEntry<K, V>对象的数组来存储数据的，并且数组的初始化大小是2。
HashMapEntry<K, V>是什么？
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) {
this.key = key;
this.value = value;
this.hash = hash;
this.next = next;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
@Override public final boolean equals(Object o) {
if (!(o instanceof Entry)) {
return false;
}
Entry<?, ?> e = (Entry<?, ?>) o;
return Objects.equal(e.getKey(), key)
&& Objects.equal(e.getValue(), value);
}
@Override public final int hashCode() {
return (key == null ? 0 : key.hashCode()) ^
(value == null ? 0 : value.hashCode());
}
@Override public final String toString() {
return key + "=" + value;
}
}
它实现了Entry接口，我们put的key，value就是存在这个对象当中，下面我们来看看它的put方法
put方法
@Override
public V put(K key, V value) {
if (key == null) {
return putValueForNullKey(value);
}
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);
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;
}
}
// No entry for (non-null) key is present; create one
modCount++;
if (size++ > threshold) {
tab = doubleCapacity();
index = hash & (tab.length - 1);
}
addNewEntry(key, value, hash, index);
return null;
}
第一行代码就是判断如果key为Null 调用putValueForNullKey 方法
private V putValueForNullKey(V value) {
HashMapEntry<K, V> entry = entryForNullKey;
if (entry == null) {
addNewEntryForNullKey(value);
size++;
modCount++;
return null;
} else {
preModify(entry);
V oldValue = entry.value;
entry.value = value;
return oldValue;
}
}
void addNewEntryForNullKey(V value) {
entryForNullKey = new HashMapEntry<K, V>(null, value, 0, null);
}
首先把entryForNullKey赋值给entry， 如果entry为空，就创建一个HashMapEntry<K, V>对象，如果entry不为空首先执行preModify方法，这个方法是个空方法，没有具体的实现，然后下面就是把新添加的value值赋值给entryForNullKey对象的value
从上面可以得出结论：HashMap可以存放key为null的数据，但是只可以有一条，再添加key为null的数据会覆盖之前的数据。
如果key不为Null，继续往下看
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);
首先通过key计算出hash值，然后再计算出index，index就是数组的下标，我们先看下最后面的添加方法
void addNewEntry(K key, V value, int hash, int index) {
table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]);
}
因为不同的key计算出来的下标index有可能是相同的，也就是说我第一次put计算出来的index和第二次put计算出来的index是有可能相同的，遇到这种情况怎么处理呢？我们来看看HashMapEntry构造方法
HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) {
this.key = key;
this.value = value;
this.hash = hash;
this.next = next;
}
首先实例化一个HashMapEntry对象，key，value分别赋值，如果现在要存储数据的index下标已经有数据了，就会把旧数据放到我现在新数据的next 属性上，然后再把新数据放到数组的index下标上，也就是说如果遇到了index相同的情况，它会以单链表的形式来存储数据，最先添加的数据会放在链表的最后面，最晚添加的数据会在链表的header位置；看完添加数据方法我们再返回来看它的其他代码逻辑。
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;
}
}
这个循环是：如果我计算出的index下标已经存有数据，然后得到这个对象，如果key和hash值都相同，就说明添加了key值重复的数据，会把相同key值对象的value给覆盖掉；也就是说HashMap的key是唯一的，如果key值相同以最晚添加的数据为准。
我们知道数组的大小在创建的时候就固定了，HashMap用数组存储数据，为什么它可以无限制的添加数据呢？我们通过下面代码来分析
modCount++;
if (size++ > threshold) {
tab = doubleCapacity();
index = hash & (tab.length - 1);
}
addNewEntry(key, value, hash, index);
如果size++ > threshold, size是添加数据的大小，threshold表示数组总容量的3/4，也就是说如果添加数据的大小大于数组总容量的3/4会执行下面的代码，我们来看看doubleCapacity方法
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;
}
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;
}
先从方面的第一行开始看
HashMapEntry<K, V>[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
return oldTable;
}
如果当前数组的长度大于最大值MAXIMUM_CAPACITY，就返回当前的数组，
(MAXIMUM_CAPACITY == 1 << 30 == 1073741824)，这是HashMap的最大容量，继续往下看
int newCapacity = oldCapacity * 2;
HashMapEntry<K, V>[] newTable = makeTable(newCapacity);
if (size == 0) {
return newTable;
}
首先把原来数组长度乘以2，传给makeTable方法
private HashMapEntry<K, V>[] makeTable(int newCapacity) {
@SuppressWarnings("unchecked") HashMapEntry<K, V>[] newTable
= (HashMapEntry<K, V>[]) new HashMapEntry[newCapacity];
table = newTable;
threshold = (newCapacity >> 1) + (newCapacity >> 2); // 3/4 capacity
return newTable;
}
首先new一个newCapacity大小的数组替换原来的数组，然后设置threshold 值，这行代码的后面有注释： 3/4 capacity，大家可以自己计算计算，方法完成以后，如果size为0就直接返回这个新数组，不为0就往下走
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;
}
上面代码就是把旧数组中的数据移动到了新的数组当中
if (nextHighBit != highBit) {
if (broken == null)
newTable[j | nextHighBit] = n;
else
broken.next = n;
broken = e;
highBit = nextHighBit;
}
这段代码看不太懂，有大神懂的话麻烦告诉一下，谢谢了。
下面就是获得新数组，算出index位置，然后添加进去；到此put方法就解析完了。
总结
从put方法可以看出HashMap内部维护的是一个HashMapEntry对象的数组，这个对象包括我们添加的key，value，hash，next等属性，put方法通过key得到hash值。然后通过hash值来计算存放在数组中的index下标，如果index相同，就会以一个单向链表的形式存放数据，最先添加的数据放在链接的最尾部；因为数组创建的时候是要固定大小的，所有在添加数据的同时，添加的数据量大于数组总量的3/4时，就会重新创建一个原来数组大小2位的新数组来存储数据。
HashMap其他方法分析：http://www.jianshu.com/p/336b1b45d140
