没有为数组table分配内存空间（有一个入参为指定Map的构造器例外）
而是在执行put操作的时候才真正构建table数组
put函数
public V put(K key, V value) { //如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold， //此时threshold为initialCapacity 默认是1<<4(24=16) if (table == EMPTY_TABLE) { inflateTable(threshold); } //如果key为null，存储位置为table[0]或table[0]的冲突链上 if (key == null) return putForNullKey(value); int hash = hash(key);//对key的hashcode进一步计算，确保散列均匀 int i = indexFor(hash, table.length);//获取在table中的实际位置 for (Entry<K,V> e = table[i]; e != null; e = e.next) { //如果该对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧value 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++;//保证并发访问时，若HashMap内部结构发生变化，快速响应失败 addEntry(hash, key, value, i);//新增一个entry return null; }
inflateTable函数
- 用于为主干数组table在内存中分配存储空间
- 通过roundUpToPowerOf2(toSize)可以确保capacity为大于或等于toSize的最接近toSize的二次幂，比如toSize=13,则
capacity=16;to_size=16,capacity=16;to_size=17,capacity=32.
private void inflateTable(int toSize) { int capacity = roundUpToPowerOf2(toSize);//capacity一定是2的次幂 /**此处为threshold赋值，取capacity*loadFactor和MAXIMUM_CAPACITY+1的最小值， capaticy一定不会超过MAXIMUM_CAPACITY，除非loadFactor大于1 */ threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); table = new Entry[capacity]; initHashSeedAsNeeded(capacity); }
roundUpToPowerOf2函数
使得数组长度一定为2的次幂，Integer.highestOneBit是用来获取最左边的bit（其他bit位为0）所代表的数值.
private static int roundUpToPowerOf2(int number) { // assert number >= 0 : "number must be non-negative"; return number >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1; }
hash函数
- 用了很多的异或，移位等运算
- 对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀
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); }
indexFor
以上hash函数计算出的值，通过indexFor进一步处理来获取实际的存储位置
/** * 返回数组下标 */ static int indexFor(int h, int length) { return h & (length-1); }
1、h&（length-1）保证获取的index一定在数组范围内
举个例子，默认容量16，length-1=15，h=18,转换成二进制计算为index=2
2、位运算对计算机来说，性能更高一些（HashMap中有大量位运算）
addEntry函数
void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length);//当size超过临界阈值threshold，并且即将发生哈希冲突时进行扩容 hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); }
- 当发生哈希冲突并且size大于阈值的时候，需要进行数组扩容
- 扩容时，需要新建一个长度为之前数组2倍的新的数组
- 然后将当前的Entry数组中的元素全部传输过去，扩容后的新数组长度为之前的2倍
- 扩容相对来说是个耗资源的操作
