在Java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。
在JDK1.7和JDK1.8中HashMap的底层实现上是有区别的。在JDK1.7中HashMap底层使用的是数据+链表来实现的，而在JDK1.8中除了数组和链表之外，又新增加了红黑数。下面就先就JDK1.7的源码进行分析，最后再说明一下JDK1.8和JDK1.7当中的区别。
数组+链表
// 声明一个空的数组
static final Entry<?,?>[] EMPTY_TABLE = {};
transient Entry<K,V>[] table = (Entry<K,V>)EMPTY_TABLE;
数组出现了，那链表在什么地方呢？其实这个Entry就是一个链表：
static class Entry<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Entry<K,V> next; // 指向下一个节点
Entry(int hash, K key, V value, Entry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
除此之外HashMap的源码还定义了一些十分重要的变量：
// 默认的数组初始大小 默认16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// HashMap的最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// HashMap中元素个数
int size;
// 阈值 与扩容有关
int threshold;
// 负载因子
int loadFactor;
构造方法
看任何一个类不仅要看它定义了哪些重要的成员变量，构造方法也是十分重要的。它可以告诉我们在构造类对象的时候都做了哪些工作：
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;
this.threshold = initialCapacity
init();
}
平常我们使用的时候一般都是使用的第一个无参的构造函数。无参构造函数又会去重新调用下面的有参构造函数。掐面的一些if语句就是在进行一些检查，后面则是把对参数进行初始化。init是一个空方法，是在HashMap的子类LinkedHashMap当中实现了。如果我们使用的是无参构造，那么此时loadFactor的值就是0.75，loadFactor 的值就是16。
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操作之前首先会判断数组是否是空的。很明显当我们第一次向HashMap中放元素的时候，肯定会进入这个if语句进行数组的初始化:
private void inflateTable(int toSize) {
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
inflateTable()方法中的toSize传入的值是threshold，而threshold在上文中我们知道被赋值为了默认的数组长度。roundUpToPowerOf2()方法的目的是找到一个距离你传入的数字最近的一个2的幂次方的一个数字。假如传入toSize的值为15，那么最终返回的capacity就是16。相应的假如传入了17，那么capacity就是32。这就牵扯到了HashMap中的一个面试题：为什么要用一个2的幂次方的一个数字区作为数组的大小？这里先抛出这个问题，稍后进行解释。下面则利用返回的capacity去真正的初始化数组。initHashSeedAsNeeded()则是与扩容有关，后面在讲到扩容的时候再讲这个方法的逻辑。
接着讲put()方法。那么在初始化数组之后会对key为null的情况做一个单独的处理。这里又会出现一个面试题HashMap的key可不可以为null？很明显是可以的，不然就不会对key为null的时候单独处理，否则直接抛出一个异常就可以了：
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
在for循环中我们可以看到首先从数组下标为0的地方取出Entry。也就是说key为null的情况下元素是存放在数组下标为0的位置。下面就是取出旧值，把新值存放进去然后再返回旧值。
分析完了key为null的情况，下面则会调用hash()方法对去计算出key的hash值：
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);
}
可以看到这里进行了很多的 ^ (异或运算) 和右移的操作呢？一句话：为了更好的散列性，减少hash碰撞，提升HashMap中get的效率。为了理解为什么要这样做首先要理解二进制运算的一些基本概念：
首先来分析为什么是 ^ 运算?我们知道二进制是以0和1表示的。就会出现4中情况0和0，0和1，1和0，1和1，也就是下面：
0011
0101
根据上面的表格可以得知 ^ 运算的结果是 0110，得到的0和1的概率是各百分之50，而 & 运算的结果是0001，结果偏向0，而 | 运算得到的结果是0111，结果更偏向1。
右移操作则是高位补0，低位舍弃。这样做是为了让高位和低位都参与运算。例如二进制 1001 1111，假设右移了4位，那么右移之后就是0000 1001，那么久可以让高位1001 和低位 1111进行计算。
下面的indexFor()方法则是根据计算出来的hash值以及数组的长度去计算出Entry在数组的中的下标。
static int indexFor(int h, int length) {
return h & (length-1);
}
在分析这个方法之前我们需要知道hash值一般是很大的一个数字，会远远的大于数组的长度16。那应该怎么样才能得到一个小于16的数字呢？很简单，只需要对hash值进行取模运算，也就是 hash%16，这样得出来的数字就一定小于16。可以HashMap的源码却是把计算得到的哈希值和数组的长度减去1的值进行了一个 & 操作。为了明白源码当中为什么要用 & 运算而不是 % 运算，首先要明白 & 运算是一个二进制运算， 特点是相同位的数字都为1，则为1，否则就为0。(在Java中一个int的大小是4个字节，一个字节是8位，也就是说一个int值的二进制有32位。为了方便演示，这里就只用8位来演示，效果是一样的)：
length = 16 的二进制： 0001 0000
length-1 = 15的二进制：0000 1111
假设现在有一个hash值是 0101 0101，那么和 0000 1111 进行完 &运算之后得到的值是：0000 0101，转换成10进制则是4。根据&运算的规则来看0000 1111高4位都是0，那么计算出来结果的高4位也都是0。低4位都是1，那么真正决定最后计算出来的值则是取决于hash值的低4位。于是我们可以很容易的得出计算出来的二进制的取值范围是 0000 0000 和 0000 1111之间，转换成十进制就是 0 和 15之间。其实这和直接hash%16得到的结果是一样的，之所以这样做也是为了性能的考虑。因为计算机最终识别的就是 0 和 1 这样的二进制数据。这也就是上面提过的面试题为什么HashMap中的数组长度为什么要是2的一个幂次方数的答案。因为只有2的幂次方数才会有上面这样的效果。
历经千辛万苦终于得到了元素在数组中的下标，下面的for循环是干了些什么呢？其实也很简单，就是当key相同的时候，把value进行替换并返回旧的值。
Map<String,Integer> map = new HashMap<>();
map.put("key",1);
Integer result = map.put("key", 2);
上面这段代码最终得到的result的值就是1，这就是这个for循环的作用。下面就是正式的向HashMap中放元素了：
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在什么情况下会进行扩容？假定现在不进行扩容，那么则会创建一个Entry对象并进行存放：
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++;
}
首先取出数组对应下标的元素，然后创建一个新的元素，并把它的next指针指向之前的旧元素，并且把这个新的元素放到数组中。最后把HashMap的长度+1。
添加元素的过程
总结一下put过程中比较重要的知识点：
- 数组的初始化是在第一次put操作的时候，并且数组的长度一定是2的幂次方数
- HashMap允许key为null的情况存在，并且key为null的时候，元素存放在数组的第一个位置
- 计算hash值的时候使用大量的异或和右移是为了更高的散列性，提高性能。如果计算出的hash值总是在数组的相同的位置，那么就会导致该下标位置的链表长度越来越长，导致get操作的时候性能不高
- 在JDK1.7中HashMap的扩容发生在添加元素之前。扩容的条件是HashMap的元素个数大于阈值并且数组对应下标的位置有元素
- 在JDK1.7中HashMap插入元素是在头结点插入的。这样做是为了提高插入的效率。否则则需要遍历链表，如果链表比较长则会影响性能
get
理解了put的过程，那么对应的get的过程就会变得很简单了。我们甚至可以猜到，肯定是通过key来计算出hash值，再获得在数组中的下标，然后再获得对应下标的Entry。接着就是遍历链表。如果key相同，那么则返回对应的value。
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
这里能看到和put时对应的对key为null和非null进行了相应的处理。这里我们只看key不为null的逻辑：
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
//计算key的 hash值
int hash = (key == null) ? 0 : hash(key);
//定位到Entry[] 数组中的存储位置，开始遍历该位置是否有链表存在
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
//判断是否有键位key 的entry实体。有就返回。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
可以看到和我们猜测的是一样的，而JDK的源码也确实是这么实现的。
扩容
在讲解put操作的时候我们简单的提了一下HashMap扩容。下面我们先通过图的方式先了解一下
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//创建一个长度为newCapacity的数组
Entry[] newTable = new Entry[newCapacity];
//将table中的元素复制到newTable中
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) { //是否需要重新计算Hash值
e.hash = null == e.key ? 0 : hash(e.key);
}
//计算在新的数组中存储的下标
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
假设之前中HashMap中的元素是这样存放的，那么现在来了一个新的元素4，计算后它的下标也是2，那么根据上面put操作得出的扩容的条件得知现在要进行扩容了。首先创建一个新的空数组，长度为6。根据transfer()方法可以得知 e 就是元素1，那么next 就是2。下面用画图的方式展示元素转移的过程(假设在计算之后新的下标也是在2的位置)：
e.next = newTable[i]
newTable[i] = e
e = next
这只是第一次循环，由于元素2不等于null，则会再进行一次循环：
e.next = newTable[i]
newTable[i] = e
e = next
如此循环直到遍历完所有的元素：
前面我们假设新的下标也是2，那么到底是在什么地方呢？其实我们可以根据之前的方法再算一遍新的下标到底会是什么。首先扩容之后数组的长度乘2，也就是32。那么length -1，也就是31的二进制则是 0001 1111。
那么与上之前的hash值：
0001 1111
0101 0101
结果：0001 0101
现在和没扩容之前进行得到的值0000 0101 对比一下我们发现他们的区别就是在高4位的最后一位上的不同。那么扩容前和扩容后的下标转换成十进制之后则分别是4和20，相差了16，刚好是扩容之前数组的长度。假如扩容之前的hash值是0100 0101，那么进行 & 运算：
0001 1111
0100 0101
结果：0000 0101
可以发现扩容后得到的值和扩容之前的是一样的，都是4。那么我们可以得知在进行扩容之后得到的下标要么是原来的下标，要么就是之前的下标加上扩容之前的数组长度就是新的下标。
JDK1.8中的HashMap
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
可以看到在计算hash值的时候比1.7版本简单了许多，这也是因为加入了红黑数而带来的改变。1.7版本中之所以那么复杂是为了让元素更均匀的分布在数组上，而1.8加入了红黑树之后，就没必要分布那么的均匀，性能的问题由红黑树保证。这其实也是一种简化，同时也提升了效率。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果数据是空的，则会去初始化数组 resize()在1.8中兼顾初始化数组和扩容的功能
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 这里还是先用hash&length-1获取下标然后判断数组对应的位置有没有元素
if ((p = tab[i = (n - 1) & hash]) == null)
// 没有则新建一个元素放入该位置
tab[i] = newNode(hash, key, value, null);
else {
// 该下标已经存在元素
Node<K,V> e; K k;
// key相同 则会去替换
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果该位置是红黑树 则存到红黑树上
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 是链表的话则遍历链表
for (int binCount = 0; ; ++binCount) {
// 遍历到最后一个
if ((e = p.next) == null) {
// 创建新的节点放在链表的尾部 这与1.7放在链表头部是不同的
p.next = newNode(hash, key, value, null);
// 如果链表的长度大于等于 7
// TREEIFY_THRESHOLD 是1.8新增的成员变量
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 把链表转红黑树
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 替换旧值并返回旧值
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 大于阈值则去扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
简单分析完了1.8中的put()方法我们可以总结出来和1.7中不同的地方：
- 1.8中新增了红黑数。目的是因为当HashMap中的元素比较多的时候，很可能会出现链表的长度很长的情况，那么在进行get操作的时候，性能就会很低。所以在1.8中当链表的长度大于等于TREEIFY_THRESHOLD - 1的时候就会把链表转换成红黑树
- 1.8中的扩容是发生在添加元素之后才进行的，1.7则是先扩容再进行添加
- 1.8中存放元素的时候是放在链表的尾部的，而1.7是放在链表的头部。这是因为需要判断链表的长度是否大于等于TREEIFY_THRESHOLD - 1。而链表的长度只能通过循环累加来获得。既然反正都要循环，那干脆就直接放在了链表的尾部。
总结
HashMap采用hash算法来决定Map中key的存储，并通过hash算法来增加集合的大小。hash表里可以存储元素的位置称为桶，如果通过key计算hash值发生冲突时，那么将采用链表的形式，来存储元素。HashMap的扩容操作是一项很耗时的任务，所以如果能估算Map的容量，最好给它一个默认初始值，避免进行多次扩容。HashMap的线程是不安全的，多线程环境中推荐是ConcurrentHashMap。
网友评论