HashMap源码分析 - JDK7和JDK8有什么区别
前几天的文章中对JDK8的HashMap源码进行了分析，这篇文章是基于JDK8的基础上来分析下与JDK7的HashMap的区别。以下的源码主要为JDK7中HashMap的源码。
一、变量
JDK7中内部的变量比较简单，并且这些通用的变量在JDK8中也都是有的。具体变量如下：
//hashMap默认初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量 2的30次
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认加载（扩容）因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//空数组
static final Entry<?, ?>[] EMPTY_TABLE = {};
//数组
transient Entry<K, V>[] table = (Entry<K, V>[]) EMPTY_TABLE;
//元素容量大小
transient int size;
//扩容临界值 = 初始容量 * 加载因子
int threshold;
//加载因子 变量
final float loadFactor;
//修改次数，并发情况下修改map会抛异常
transient int modCount;二、构造函数
//指定初始容量的构造函数，默认加载因子为0.75
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//无参构造函数 默认容量为16，默认加载因子为0.75
public HashMap() {
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();
}如果构造函数为指定扩容临界值和指定加载因子的临界值时，threshold会被直接赋值为指定的初始容量大小。而在jdk8中会做一次计算，计算出当前容量大小距离2的次幂最近的数，方便后续做二进制运算。
//指定初始化集合
public HashMap(Map<? extends K, ? extends V> m) {
//如果m的容量大小>当前默认的16，则取最大值
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
//存放元素
putAllForCreate(m);
}三、HashMap内部类
· JDK8
内部类有Node类和TreeNode类，表明内部是数组+链表或数组+红黑树的底层结构。
· JDK7
内部结构为数组+链表的底层结构。
//内部结构 为一个单项链表节点
static class Entry<K, V> implements Map.Entry<K, V> {
final K key;
V value;
Entry<K, V> next;
int hash;
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;
}
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();
}
void recordAccess(java.util.HashMap<K, V> m) {
}
void recordRemoval(java.util.HashMap<K, V> m) {
}
}三、HashMap存放元素
· hash值计算区别
JDK8中计算比较简单实际上就是用key的hash值的高低位进行异或运算，可求得hash值。下图为JDK8中计算hash值的源码
//计算key的hash值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}JDK7中计算比较复杂，要进行多次移位和异或运算。
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}JDK7中需要进行复杂的运算其实主要就是为了提高key的散列性，减少hash冲突。在JDK8中将运算变了简单，不代表8中不需要减少hash冲突，只不过在JDK8中使用了红黑树，当数组内所有元素小于64个时会优先进行扩容，当元素大于64个并且数组中的链表长度大于8时会转换为红黑树，因此在8中提高了查询性能，就不再用复杂的hash算法，保证部分性能。
最终数组下标的确认的计算方式都一样，hash值和数组最大下标进行与运算。
· 存放元素区别
//存放元素
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
//计算hash值
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;
}//插入结点
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);
}//插入结点，注意这里原来的链表被插入到新插入元素的后面 即新插入的结点放置于数组中的头结点
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K, V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}从上述源码中可以看出，插入元素的位置是有本质上的区别。JDK7中是通过插入头结点的方式，而在JDK8中是通过插入尾结点的方式。
· 扩容
//扩容为原来的2倍
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
//是否已达到最大值
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//构建新的数组，容量为之前的2呗
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
//计算下一个临界值
threshold = (int) Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}//复制元素到新的数组中
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;
}
}
}上述为JDK7的扩容过程，扩容数组大小和JDK8一样扩容为原来的2倍，只不过在JDK8中新数组下标的确认是通过简单的计算：原来数组容量+原来数组下标为扩容后的数组下标。而JDK7后在对数组进行遍历时、对链表中的所有元素进行复制时，都需要对每一个元素的数组下标进行重新计算，然后复制到新的扩容后的数组中，这里扩容后的复制插入也是头插法。
另外JDK7的扩容在并发情况下容易出现环形链表的问题。
· 环形链表问题分析
形成环形链表关键在于这一步，在并发环境下比较危险。
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;
}
}
}假设当前map中的数组下标为1的结点中只存在一个元素。在并发条件下两条线程同时进行put操作，就会导致两条线程都会进行扩容操作。
假设当前map中数组的size为2，下标为1的链表中只有1个key的hash值为11的元素，并发插入两个key的hash值为5和1的的元素，根据put的特性，依次插入到头结点中。插入操作完成后两个线程中链表元素数量已经超过扩容临界值，则需要进行扩容操作。
假设线程一先进行扩容操作，对key1—>5—>11进行扩容操作，此时的e和next的关系如下图所示：
重新计算数组下标，线程一扩容过程如下：
接下来线程二进行扩容操作，此时的key-5和key-1已经存在指向关系。
线程二进行扩容，还是继续观察代码：
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;
}
}
然后由于线程一存在key-5和key-1的关系是key5—>key1，因此实际上线程二扩容后的真实关系是存在一个环形链表，如下图所示：
此时在形成环形链表的情况下，如果调用了get方法，并且key的hash值与数组下标最大值求与后，结果为1，如get(9)，那么根据map的特性，会依次遍历链表，进行查找，造成了死循环。
不过，对于HashMap来说，他并不是线程安全的，在多线程情况下，本就不应该这样使用，如果需要线程安全的可以考虑下HashTable或ConcurrentHashMap。而且在JDK8中采用了尾插法的方式，所以这样情况在JDK8中已经被优化了。