扩容就是在put方法中实现的,来看代码
public V put(K key, V value) { // 如果table引用指向成员变量EMPTY_TABLE，那么初始化HashMap（设置容量、临界值，新的Entry数组引用） if (table == EMPTY_TABLE) { inflateTable(threshold); } // HashMap 支持key为null if (key == null) //key为null单独调用存储空key的方法 return putForNullKey(value); //计算key的hash值 int hash = hash(key); // 根据hash值和表当前的长度，得到一个在数组中的下标,重点关注一下indexFor方法的实现。 // 该算法主要返回一个索引，0 到 table.length-1的数组下标。 int i = indexFor(hash, table.length); //接下来，找到 table[i]处，以及该处的数据链表，看是否存在相同的key;判断key相同， // 首先判断hash值是否相等，然后再 判断key的equals方法是否相等 for (Entry<K, V> e = table[i]; e != null; e = e.next) { Object k; //首先判断hash,如果对象的hashCode方法没有被重写,那么hash值相等两个对象一定相等 //并且判断如果key相等或者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; }我们来一步一步看,首先来看第一个判断
// 如果table引用指向成员变量EMPTY_TABLE，那么初始化HashMap（设置容量、临界值，新的Entry数组引用） if (table == EMPTY_TABLE) { inflateTable(threshold); }如果这个判断成立,也就是说这个数组还没有进行过初始化,则调用inflateTable(threshold);方法来进行初始化,传入的参数为临界值,我们来看inflateTable方法
private void inflateTable(int toSize) { // Find a power of 2 >= toSize // 首先计算容量, toSize 容量为 threshold,在构造方法中，threshold默认等于初始容量，也就是16 int capacity = roundUpToPowerOf2(toSize); // 然后重新计算 threshold的值，默认为 capacity * loadFactor //Math.min 方法用于返回两个参数中的最小值 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); //初始化数组 容量为 capacity table = new Entry[capacity]; initHashSeedAsNeeded(capacity); }roundUpToPowerOf2方法,简单来看一下这个方法的作用
private static int roundUpToPowerOf2(int number) { // assert number >= 0 : "number must be non-negative"; //判断参数的值是否大于最大容量 return number >= MAXIMUM_CAPACITY //如果大于将返回最大容量 ? MAXIMUM_CAPACITY /** * 如果小于1返回1 * highestOneBit方法可以简单理解为返回小于等于输入的数字最近的2的次方数 * 例如 * 2的1次方 2 * 2的2次方 4 * 2的3次方 8 * 2的4次方 16 * 2的5次方 32 * 小于15,并且距离15最近的2的次方数 : 8 * 小于16,并且距离15最近的2的次方数 : 16 * 小于17,并且距离15最近的2的次方数 : 16 */ : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1; }具体方法实现就不继续研究了,不是这篇的主题,继续来看inflateTable方法中内容
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);这一步操作是重新计算threshold的值,也就是临界值,通过计算出的容量大小乘以负载因子大小来算出临界值的大小
Math.min方法是判断两个值大小,返回小的那个,如果参数具有相同的值，则结果为相同的值。如果任一值为NaN，则结果为NaN
之后将初始化一个Entry类型的数组赋值给table
//初始化数组 容量为 capacity table = new Entry[capacity];那么我们现在来看一下这个Entry类
static class Entry<K, V> implements Map.Entry<K, V> { final K key; V value; Entry<K, V> next; int hash; }那么和开头举的例子Node基本一样的思路,在类中单独定义一个用来存储下一个节点的变量next
回到put方法,来看下一个判断
// HashMap 支持key为null if (key == null) //key为null单独调用存储空key的方法 return putForNullKey(value);我们来看一下这个putForNullKey方法
private V putForNullKey(V value) { //获取下标为0的Entry节点 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; }