上篇文章我们通过部分源码和结构图了解了HashMap的数据结构，感兴趣的小伙伴看这里HashMap实现原理基础篇。
这一篇，我们基于HashMap的实现原理，了解HashMap重新调整大小(Resize)这个过程。
Resize前言
还记得上篇HashMap实现原理基础篇中提到，HashMap的内部结构实际上链表的数组，底层是数组，数组的每一项储是链表，而链表中的存储的是Entry对象，Entry是一个静态内部类，其重要属性有key、 value 和 next。 Entry[]的长度一定后，随着Map里面数据的越来越长，会影响HashMap的性能。于是HashMap在此做了优化，随着map的size越来越大，就要resize(重新调整Entry[]的大小)。 Entry[]会以一定的规则加长长度。这个resize的过程，简单的说就是把Entry扩充为2倍，之后重新计算index，再把节点再放到新的Entry中。
想要了解这个resize的详细过程，思考如下几个问题：
- 1.为什么resize要将Entry扩充为原来的2倍? 这个过程是怎样的? 这样做有什么好处?
- 2.那些唬人的名词： Capacity， bucket，Load factor 都是什么?
回答这些问题，并不容易，若无头绪，为何不看源码？
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public HashMap(int initialCapacity, float loadFactor) {
//初始容量不能<0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//初始容量不能 > 最大容量值，HashMap的最大容量值为2^30
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//负载因子不能 <=0
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// 计算出大于 initialCapacity 的最小的 2 的 n 次方值。
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
//设置HashMap的阈值
threshold = (int)(capacity * loadFactor);
table = new Entry[capacity];
init();
}
由以上代码段，我们知道，当系统开始初始化 HashMap 时，系统会创建一个长度为 capacity 的 Entry数组
public V put(K key， V value) {
if (key == null)
//null总是放在数组的第一个链表中
return putForNullKey(value);
int hash = hash(key.HashCode());
int i = indexFor(hash， table.length);
//遍历链表
for (Entry<K，V> e = table[i]; e != null; e = e.next) {
Object k;
//如果key在链表中已存在，则替换为新value
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;
}
/**
* HashMap 添加节点
*
* @param hash 当前key生成的hashcode
* @param key 要添加到 HashMap 的key
* @param value 要添加到 HashMap 的value
* @param 要添加的结点对应到数组的位置下标
*/
void addEntry(int hash， K key， V value， int bucketIndex) {
Entry<K，V> e = table[bucketIndex];
//参数e， 是Entry.next
table[bucketIndex] = new Entry<K，V>(hash， key， value， e);
// threshold=load factor*current capacity
//如果size大于等于阈值 threshold，则扩充table大小。
if ((size >= threshold) && (null != table[bucketIndex])) {
//扩容之后，数组长度变了
resize(2 * table.length);
//hash值是根据key与数组长度取模算的,长度变了,当然要重新计算hash值
hash = (null != key) ? hash(key) : 0;
//数组长度变了，数组的下标与长度有关，需重算。
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
/**
* 是否为链表
* 1. 原来数组bucketIndex处为null，则直接插入
* 2. 原来数组bucketIndex有值，则根据Entry的构造函数，
把新的结点存于数组中，原来数据用新结点的next指向
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMap.Entry<K, V> e = table[bucketIndex];
table[bucketIndex] = new HashMap.Entry<>(hash, key, value, e);
size++;
}
addEntry方法可看出resize的条件与扩充大小
最后我们分析下resize的源码，鉴于JDK1.8引入红黑树，较复杂，为了便于理解我们仍然使用JDK1.7的代码，本质上区别不大。
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
//扩容前的数组大小如果已经达到最大(2^30)了
if (oldCapacity == MAXIMUM_CAPACITY) {
//修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
threshold = Integer.MAX_VALUE;
return;
}
//初始化一个新的Entry数组
Entry[] newTable = new Entry[newCapacity];
//将数据转移到新的Entry数组里
transfer(newTable);
//更新table为最新newTable
table = newTable;
//更新阈值
threshold = (int)(newCapacity * loadFactor);
}
生成一个新的table数组（entry数组），然后根据新的Capacity和负载因子去生成新的临界值
void transfer(Entry[] newTable) {
//src引用了旧的Entry数组
Entry[] src = table;
int newCapacity = newTable.length;
//遍历旧的Entry数组
for (int j = 0; j < src.length; j++) {
//取得旧Entry数组的每个元素
Entry<K, V> e = src[j];
if (e != null) {
//释放旧Entry数组的对象引用
src[j] = null; //（for循环后，旧的Entry数组不再引用任何对象）
do {
//此处采用链表的头插法,新结点插入数组中
//而原始结点作为新结点的next指向
Entry<K, V> next = e.next;
//重新计算每个元素在数组中的位置
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e; //将元素放在数组上
e = next; //访问下一个Entry链上的元素
} while (e != null);
}
}
}
//按位与运算，都为真时才为真
static int indexFor(int h, int length) {
return h & (length - 1);
}
看完源码，再了解这些概念就容易多了:
Capacity(容量)：当系统开始初始化 HashMap 时，系统会创建一个长度为 capacity 的 Entry数组。
bucket(桶)：基于Entry数组，这个数组里可以存储元素的位置被称为bucket，每个 bucket 都有其指定索引，系统可以根据其索引快速访问该 bucket 里存储的元素。
Load factor(负载因子)：Load factor就是Entry集合填满程度的最大比例 eg: 0.75
resize(重新调整大小): 那么当Entry的数目大于capacity*load factor时就需要调整Entry的大小，这个过程成为resize，resize为当前Entry数组的2倍。
bucket的概念，结合上篇文章的链表结构图，在此标注下：
bucket.png
关于Resize，查阅API（其实看过源码已经很清楚了）：
Initial capacity The capacity is the number of buckets in the hash table， The initial capacity is simply the capacity at the time the hash table is created。
Load factor The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased。
翻译过来，简单的说：Capacity（容量）就是bucket（桶）的总长度，Load factor（负载因子）就是bucket填满程度的最大比例eg: 0.75。如果对迭代性能要求很高的话不要把capacity设置过大，也不要把load factor设置过小。当bucket中的entries的数目大于capacity * load factor时就需要调整bucket的大小为当前的2倍。
举个栗子：Capacity为16，Load factor为0.75，那么在桶的填充总数大于12（16 * 0.75=12）时，resize这个HashMap，新的长度为32（16 * 2 = 32）
回顾上文： 随着map的size越来越大，(超过load factor*current capacity)，就要resize。 那么Entry[]会以一定的规则加长长度。简单的说就是把Entry扩充为2倍
当超过限制的时候会resize，因为我们使用的是2次幂的扩展(指长度扩为原来2倍)，那么元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。例如我们从16扩展为32时，具体的变化如下所示：Initializes or doubles table size。 If null， allocates in accord with initial capacity target held in field threshold。 Otherwise， because we are using power-of-two expansion， the elements from each bin must either stay at same index， or move with a power of two offset in the new table。
移位.png
因此元素在重新计算hash之后，n变为之前的2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：
移位1.png
那么我们在扩充HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+"oldCap"。可以看看下图为16扩充为32的resize示意图：
eg1.png
这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是 0 还是 1 可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。
有一点注意区别，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是从上图可以看出，JDK1.8不会倒置。有兴趣的同学可以研究下JDK1.8的resize源码。
了解了以上概念与resize的过程，我们复习下关于HashMap的面试题：
1.HashMap的结构与特点？
HashMap是数组的链表，底层是数组结构，数组的每一项又是链表。HashMap存储着Entry对象，其内部
结构Entry(hash, key, value, next)对象。是基于Hash表的Map接口的非同步实现，存储键值对时，它可以
接收null键与null值
2.了解HashMap的工作原理吗？
2.通过hash的方法，使用put和get方法存储和获取对象。存储对象时，我们将K/V传给put方法时，它调用
hashCode计算hash从而得到数组位置index，进一步存储，HashMap会根据当前bucket的占用情况自动调
整容量(超过Load Facotr则resize为原来的2倍)。获取对象时，我们将K传给get，它调用hashCode计算
hash从而得到bucket位置，并进一步调用equals()方法确定键值对。如果发生碰撞的时候，可以使用链地址
法解决冲突，将新的元素插入到数组的index位置，并将之前
链表中的元素用next指向。
3.你知道hash的实现吗？为什么要这样实现？
在Java 1.8的实现中，是通过hashCode()的高16位异或低16位实现的 (h = k.hashCode()) ^ (h >>> 16)
，主要是从速度、功效、质量来考虑的，这么做可以在bucket的n比较小的时候，也能保证考虑到高低bit
都参与到hash的计算中，同时不会有太大的开销。
4.如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？
4.如果超过了负载因子(默认0.75)，则会重新resize一个原来长度两倍的HashMap，并且重新调用hash方法。
5.HashMap与HashTable的区别
关于HashMap:在官方文档中是这样描述HashMap的：
Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.
翻译: Hashtable 实现了Map接口,此实现提供了可选择的操作,允许null值,但不允许null键, (HashMap几乎可以等价于Hashtable，除了HashMap是非synchronized的，并可以接受null(HashMap可以接受为null的键值(key)和值(value)，而Hashtable则不行) 此类不保证有序,特别是不保证顺序持久不变.
几个关键的信息：基于Map接口实现、允许null键/值、非同步、不保证有序(比如插入的顺序)、也不保证序不随时间变化。(由于HashMap允许null键,所以通过if(key == null))的方式,并不能判断某个key键是否存在,而是用containesKey(key)的方式)
1.线程安全与性能：
Hashtable是线程安全的，而HashMap是线程不安全的。Hashtable的安全由同步锁synchronized来保证，所
以，在单线程环境下，Hashtable比HashMap要慢。如果只需要单一线程，使用HashMap性能比Hashtable
要好。Java 5提供了ConcurrentHashMap，它是HashTable的替代，比HashTable的扩展性更好。
ConcurrentHashMap使用了线程锁分段技术，每次访问只允许一个线程修改哈希表的映
射关系，所以是线程安全的。
2.对null值的处理不同
HashTable不允许null值(key和value都不可以)如果设置了null值会报空指针的错误. 而HashMap允许null
(key和value都可以).可以有一个或者多个键对应的值为null.因此,在HashMap中不能由get()方法来判断
HashMap中是否存在某个键,而应该用containsKey()方法来判断.
3.HashMap不能保证随着时间的推移Map中的元素次序是不变的。
本篇是HashMap进阶篇，基于<HashMap实现原理基础篇>基础之上，详细描述了resize的过程，以及这个过程中涉及到的一些重要概念。最后以面试题的形式进行收尾，将这些知识点串联在一起。
参考文档：http://www.importnew.com/18633.html
喜欢学习，乐于分享，不麻烦的话，给个❤鼓励下吧！
网友评论