HashMap源码分析(JDK1.7)
HashMap JDK1.7 概述
HashMap是一个以Key-Value键值对方式存储的集合，每一个键值对也叫做Entry。
HashMap里面的数组
几个重要参数
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
-
DEFAULT_INITIAL_CAPACITY：默认HashMap初始大小。初始在初始默认状态下，HashMap中的数组长度Capacity为16，长度是2的幂。 -
DEFAULT_LOAD_FACTOR：负载因子。默认LoadFactor为0.75。 -
MAXIMUM_CAPACITY：HashMap最大容量。HashMap的容量是有限的。
当HashMap.Size >= Capacity * LoadFactor时，HashMap将进行Resize操作，为什么HashMap初始默认长度为16，目的是为了降低hash碰撞的几率。我们先看平时常用的Put和Get的方法。
Put方法
以下为JDK1.7中HashMap中的put方法，我们来举个例子说明一下整体过程。
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
当我们调用put方法：put("apple", 0)，往Hashmap中插入一个key为apple，value为0的元素，从源码中来看，经过两个判空的操作后，来到了int hash = hash(key);这一步，这一步是对插入元素的key进行做一次hash函数取到hash值，再来到int i = indexFor(hash, table.length);计算到这个元素在Hashmap中的index，
假设计算出的index为2，那么当前Hashmap：
index2插入一个元素
经过了多次
put操作，Hashmap中的元素越来越多，用hash函数难免会遇到index冲突，比如
index2冲突了
出现这种情况的时候Hashmap使用链表来解决这种情况，HashMap数组的每一个元素不止是一个Entry对象，也是一个链表的头节点，当新的Entry映射到了冲突的位置，会使用头插法插入到链表的头部（使用头插法是因为HashMap的发明者认为，后插入的Entry被查找的可能性更大）：
头插法插入到冲突位置
Get方法
以下为JDK1.7中HashMap中的get方法及getEntry方法，同样举例说明整体过程：
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
当我们调用get方法，将key传入传入到getEntry，首先是hash函数操作：int hash = (key == null) ? 0 : hash(key);，取到hash值，然后来到for循环
for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next)，
调用indexFor取到对应的index，如果存在上面提到Hashmap中index冲突，一个位置存在多个Entry的情况，这时候先取到index位置中链表的头结点，判断key的值是否为所要查找的key的值是否相等
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))，
如果不相等则继续e = e.next取得链表下一个节点，继续判断key，最终找到key相等的结果返回出去。
index冲突，查找链表中并判断key
高并发下的HashMap存在的问题
当调用put方法的时候，会调用到put方法中的addEntry方法，addEntry方法具体如下：
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
HashMap的容量是有限的，当HashMap.Size >= Capacity * LoadFactor时，在addEntry时就会触发resize方法
HashMap在高并发下会出现问题，问题出在其resize方法中的transfer方法。
我们来看一下resize方法：
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
resize时会创建出一个2倍原来HashMap的长度的Entry数组，接着调用transfer方法，transfer方法的作用是遍历原Entry数组，把所有的Entry重新Hash到新数组，一下是addEntry
方法：
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
长度扩大以后，Hash的规则也随之改变
而这一段代码：
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
就是重新计算hash，然后放到新的数组的代码，在执行最后三行代码时，即使index冲突，也会使用头插的方式插入Entry。
当有两个线程同时对一个已经到临界扩容状态的HashMap进行操作时，两个线程都对该HashMap进行resize操作，假设线程B进入到transfer里面Entry<K,V> next = e.next;后挂起，然后线程A完成了所有resize操作，线程B继续操作，线程A操作后的由于存在Entry重新分配后顺序改变，线程Btransfer方法将引发Entry链表成环的状况，此后如果调用get查找一个不存在key的而且hash恰好位于链表的位置，则会引发死循环，这就是HashMap在1.7及1.7版本一下时高并发存在的问题。
