仅针对JDK 1.7.0_80版本
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(); } 复制代码
java.util.HashMap#put
public V put(K key, V value) { if (table == EMPTY_TABLE) { // 如果table为空,初始化table inflateTable(threshold); } if (key == null) // 如果key为null -> 如果key为null则hash值为0,将元素存放在table[0]中 // 如果table[0]为null,则将其放置在table[0]除 // 如果table[0]不为null,则寻找table[0]的节点中key为null的节点并设置新value return putForNullKey(value); // 计算key的hash int hash = hash(key); // 确定hash对应在table中的index int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { // 处理table[i] // 如果table[i] 不为空 Object k; // if (e.hash == hash && // key的hash相等 ((k = e.key) == key || key.equals(k))) { // map的链表结构节点的key == 待保存的key。或者 key equals。 // 此时表示待保存的元素的key已存在map中 // 替换旧值并返回就值 V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null; } 复制代码
java.util.HashMap#indexFor
static int indexFor(int h, int length) { // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2"; // 首先因为需要确定在table中的index,所以最后的结果范围必须为 [0, capacity-1] // 那正常的操作逻辑是使用 h % length // 而又因为位运算的 & 操作其实是比 % 操作更高效的 // 所以此处采用了 & 操作 // 那为了确保 在进行 & 操作后的结果能够全部覆盖到 [0, capacity-1] 的范围 // 所以需要将 capacity 设置为2的整数次幂 // 因为 2^n 的二进制位 0000 0000 0000 0000 0000 0000 0001 0000 // 而 2^n -1 的二进制码为 0000 0000 0000 0000 0000 0000 0000 1111 // 再进行 & 操作时 就能够覆盖到[0, capacity-1] return h & (length-1); } 复制代码
java.util.HashMap#inflateTable
private void inflateTable(int toSize) { // Find a power of 2 >= toSize // 找到最接近于大于等于指定值的2的幂设定为初始容量 int capacity = roundUpToPowerOf2(toSize); // 设置扩容阈值 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); // 初始化table table = new Entry[capacity]; initHashSeedAsNeeded(capacity); } 复制代码
java.util.HashMap#roundUpToPowerOf2
// 获取到比与number最接近且大于number的2的整次幂的正整数 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; // number 如果 > 1 --> Integer.highestOneBit((number - 1) << 1) // 如number为23 0000 0000 0000 0000 0000 0000 0001 0111 // number - 1 0000 0000 0000 0000 0000 0000 0001 0110 // << 1 0000 0000 0000 0000 0000 0000 0010 1100 // 44 // highestOneBit -> 32 } 复制代码
java.lang.Integer#highestOneBit
public static int highestOneBit(int i) { // HD, Figure 3-1 // 将一个整数右移一位,然后做或操作 // 例如,此时 i = 22 // i = 22 0000 0000 0000 0000 0000 0000 0001 0110 // i >> 1 0000 0000 0000 0000 0000 0000 0000 1011 // | 0000 0000 0000 0000 0000 0000 0001 1111 // >> 2 0000 0000 0000 0000 0000 0000 0000 1111 // | 0000 0000 0000 0000 0000 0000 0001 1111 // >> 4 0000 0000 0000 0000 0000 0000 0000 0000 // | 0000 0000 0000 0000 0000 0000 0001 1111 // >> 8 0000 0000 0000 0000 0000 0000 0000 0000 // | 0000 0000 0000 0000 0000 0000 0001 1111 // >> 16 0000 0000 0000 0000 0000 0000 0000 0000 // | 0000 0000 0000 0000 0000 0000 0001 1111 // --> i 0000 0000 0000 0000 0000 0000 0001 1111 // i>>>1 0000 0000 0000 0000 0000 0000 0000 1111 // i - (i>>>1) 0000 0000 0000 0000 0000 0000 0001 0000 // 返回 16 // 所以可以看出 -> 这些操作的结果是将原始的数值保留最高为为1的结果 ,因为只存在一位上为1,所以返回的结果为2的整数次幂,且为小于i且最接近i的数。 i |= (i >> 1); i |= (i >> 2); i |= (i >> 4); i |= (i >> 8); i |= (i >> 16); return i - (i >>> 1); } 复制代码
java.util.HashMap#initHashSeedAsNeeded
final boolean initHashSeedAsNeeded(int capacity) { // 初始化的时候hashSeed为0,此处false boolean currentAltHashing = hashSeed != 0; boolean useAltHashing = sun.misc.VM.isBooted() && // vm启动时会为其赋值为true (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); // capacity(8) >= 2147483647 --> false // useAltHashing -> false // false ^ false -> false boolean switching = currentAltHashing ^ useAltHashing; if (switching) { hashSeed = useAltHashing ? sun.misc.Hashing.randomHashSeed(this) : 0; } // 此时hashSeed依旧为0 return switching; } 复制代码
sun.misc.VM#isBooted
private static volatile boolean booted = false; public static boolean isBooted() { return booted; } 复制代码
java.util.HashMap.Holder
private static class Holder { /** * Table capacity above which to switch to use alternative hashing. */ static final int ALTERNATIVE_HASHING_THRESHOLD; static { // 这里的altThreshold值可以通过测试的出为null String altThreshold = java.security.AccessController.doPrivileged( new sun.security.action.GetPropertyAction( "jdk.map.althashing.threshold")); int threshold; try { threshold = (null != altThreshold) // null != null -> false ? Integer.parseInt(altThreshold) // static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE; : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT; // 2147483647 // disable alternative hashing if -1 if (threshold == -1) { // false threshold = Integer.MAX_VALUE; } if (threshold < 0) { // false throw new IllegalArgumentException("value must be positive integer."); } } catch(IllegalArgumentException failed) { throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed); } ALTERNATIVE_HASHING_THRESHOLD = threshold; // 2147483647 } } 复制代码
测试代码
import sun.misc.VM; import java.util.HashMap; public class Test { public static void main(String[] args) { HashMap<String, String> map = new HashMap<>(); System.out.println("VM.isBooted(): " + VM.isBooted()); String altThreshold = java.security.AccessController.doPrivileged( new sun.security.action.GetPropertyAction( "jdk.map.althashing.threshold")); System.out.println("altThreshold: " + altThreshold); map.put("222", "333"); System.out.println("VM.isBooted(): " + VM.isBooted()); System.out.println("altThreshold: " + altThreshold); } } 复制代码
输出结果为:
VM.isBooted(): true altThreshold: null VM.isBooted(): true altThreshold: null 复制代码
java.util.HashMap#putForNullKey
private V putForNullKey(V value) { for (Entry<K,V> e = table[0]; e != null; e = e.next) { // e为数组中taile[0]中的节点 // e != null -> 表示table[0]中已存在节点数据 // 找到table[0]中节点的key为null的节点 并设置新value,返回旧value // 如果不存在 -> 跳出循环 if (e.key == null) { // 如果节点的key为null V oldValue = e.value; // 将新的value设置到节点中,将旧的value返回 e.value = value; e.recordAccess(this); return oldValue; } } modCount++; // 在table[0]中没有找到key为null的节点 // 将key为null的节点添加到hash为0的位置即table[0]中 addEntry(0, null, value, 0); return null; } 复制代码
java.util.HashMap#addEntry
void addEntry(int hash, K key, V value, int bucketIndex) { // 当前map中的数据可数 是否到达扩容阈值,并且table[index]已经存在值 if ((size >= threshold) && (null != table[bucketIndex])) { // 所以在addEntry中 // 只有 当前map的size 到达 扩容阈值 并且 // 待增加元素的index出的table[index]已经有元素时 // 才会触发扩容 resize(2 * table.length); // 计算hash -> 如果key为null则hash为0,此时会将元素放到table[0]中 hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); } 复制代码
java.util.HashMap#createEntry
void createEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; // 创建一个新的Entry并存放在table[index]处,注意Entry的构造方法,会将当前table[index]传入 // 使新创建的Entry的next指向table[index] -> 表明在链表中新增元素时增加在头结点处 table[bucketIndex] = new Entry<>(hash, key, value, e); // size + 1 size++; } 复制代码
java.util.HashMap.Entry#Entry
Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } 复制代码
java.util.HashMap#hash
TODO
final int hash(Object k) { int h = hashSeed; // 以hashSeed当前为0为例 if (0 != h && k instanceof String) { // hashSeed不为0时,如果key为String类型,则采用其他计算hash方式 return sun.misc.Hashing.stringHash32((String) k); } h ^= k.hashCode(); h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } 复制代码
java.util.HashMap#resize
void resize(int newCapacity) { // 保存一个旧table的引用 Entry[] oldTable = table; // 旧table容量 int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { // 旧table容量已达到允许最大值 -> 无法扩容。增大扩容阈值并返回 threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; // 初始化一个新的table // 将旧table中的节点移动到新的table中 // 根据刚才对initHashSeedAsNeeded()的分析 -> 只有在newCapacity >= Integer.MAX_VALUE时,才会启用hashSeed transfer(newTable, initHashSeedAsNeeded(newCapacity)); // 在完成节点数据转移后,将newTable赋值给HashMap的table引用变量 table = newTable; // 重新设置扩容阈值 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); // 扩容结束 } 复制代码
java.util.HashMap#transfer
void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) { // 遍历旧table数组中的每个节点 while(null != e) { Entry<K,V> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } // 为便于理解 此处先假设所有的index都不需要更改(实际情况中为要么不变,要么更改为当前index + capacity。 int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } } } 复制代码
transfer
说明,为便于说明,假设此时旧的table以及新建的table->newTable如下图
假设此时我们对table[0]中的数据进行transfer。在while循环中,第一次循环,在代码执行到第9行时,结构如下图:
假设当前table[0]中所有的节点在新table中的index都为0,下面代码执行如图
e.next = newTable[i]; newTable[i] = e; e = next; 复制代码
执行完第1行后
执行完第2行后
执行完第3行后
然后while继续循环知道最终完成效果如下:
从效果上可以发现,transfer
会将之前链表上的元素逆序后存储在新table中的链表中,当然这种做法也会导致在多线程transfer
时的线程安全问题(后续会详细说明)。
然后继续遍历处理table中的其他节点达到数据转移到new table中。
java.util.HashMap#get
public V get(Object key) { if (key == null) // 如果key为null return getForNullKey(); Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue(); } 复制代码
java.util.HashMap#getForNullKey
private V getForNullKey() { if (size == 0) { return null; } // 已经将key为null的元素存放在table[0]中 for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) return e.value; } return null; } 复制代码
java.util.HashMap#getEntry
final Entry<K,V> getEntry(Object key) { if (size == 0) { return null; } // 计算hash,如果key为null则hash为0 int hash = (key == null) ? 0 : hash(key); // 确定hash在table中的index for (Entry<K,V> e = table[indexFor(hash, table.length)]; // 遍历table[index] 链表结构 e != null; e = e.next) { Object k; if (e.hash == hash && // hash相等 ((k = e.key) == key || (key != null && key.equals(k)))) // key相等==,或者key equals // 找到元素,返回e return e; } return null; } 复制代码