Java1.7全网最深入HashMap源码解析 Java1.7全网最深入HashMap源码解析

存储结构
属性成员
构造函数：
hash方法
Map中添加数据

put方法
流程图
源码
inflateTable方法
putForNullKey方法
addEntry方法
createEntry方法

扩容方法

resize方法
transfer方法

从HashMap中获取数据

get方法

从HashMap中删除数据

remove方法

对HashMap的其他操作

1.7和1.8版本区别

数据结构
hash值计算方式
扩容机制

文章图片

存储结构 【Java1.7全网最深入HashMap源码解析】内部包含了一个 Entry 类型的数组 table。Entry 存储着键值对。它包含了四个字段，从 next 字段我们可以看出 Entry 是一个链表。即数组中的每个位置被当成一个桶，一个桶存放一个链表。HashMap 使用拉链法来解决冲突，同一个链表中存放哈希值和散列桶容量取模运算结果相同的 Entry。

文章图片

啊啊

transient Entry[] table; //位桶数组/** * Entry类实现了Map.Entry接口 * 即实现了getKey()、getValue()、equals(Object o)和hashCode()等方法**/static class Entry implements Map.Entry {final K key; // 键V value; // 值Entry next; // next指针int hash; //hashCode()方法计算出的hash值/** * 构造方法，创建一个Entry * 参数：哈希值h，键值k，值v、下一个节点n */Entry(int h, K k, V v, Entry n) {value = https://www.it610.com/article/v; next = n; key = k; hash = h; }// 返回与此项对应的键public final K getKey() {return key; }// 返回与此项对应的值public final V getValue() {return value; }public final V setValue(V newValue) {V oldValue = value; value = newValue; return oldValue; }/** * equals（）* 作用：判断2个Entry是否相等，必须key和value都相等，才返回true*/ public final boolean equals(Object o) {if (!(o instanceof Map.Entry))return false; Map.Entry e = (Map.Entry)o; Object k1 = getKey(); Object k2 = e.getKey(); if (k1 == k2 || (k1 != null && k1.equals(k2))) {Object v1 = getValue(); Object v2 = e.getValue(); if (v1 == v2 || (v1 != null && v1.equals(v2)))return true; }return false; }/** * hashCode（） */ public final int hashCode() { return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue()); }public final String toString() {return getKey() +"=" + getValue(); }/** * 当向HashMap中添加元素时，即调用put(k,v)时， * 对已经在HashMap中k位置进行v的覆盖时，会调用此方法 * 此处没做任何处理 */void recordAccess(HashMap m) {}/** * 当从HashMap中删除了一个Entry时，会调用该函数 * 此处没做任何处理 */void recordRemoval(HashMap m) {} }

属性成员

// 1. 容量（capacity）： HashMap中数组的长度// a. 容量范围：必须是2的幂 & <最大容量（2的30次方）// b. 初始容量 = 哈希表创建时的容量// 默认容量 = 16 = 1<<4 = 00001中的1向左移4位 = 10000 = 十进制的2^4=16static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 最大容量 =2的30次方（若传入的容量过大，将被最大值替换）static final int MAXIMUM_CAPACITY = 1 << 30; // 2. 加载因子(Load factor)：HashMap在其容量自动增加前可达到多满的一种尺度// a. 加载因子越大、填满的元素越多 = 空间利用率高、但冲突的机会加大、查找效率变低（因为链表变长了）// b. 加载因子越小、填满的元素越少 = 空间利用率小、冲突的机会减小、查找效率高（链表不长）// 实际加载因子final float loadFactor; // 默认加载因子 = 0.75static final float DEFAULT_LOAD_FACTOR = 0.75f; // 3. 扩容阈值（threshold）：当哈希表的大小 ≥ 扩容阈值时，就会扩容哈希表（即扩充HashMap的容量） // a. 扩容 = 对哈希表进行resize操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数// b. 扩容阈值 = 容量 x 加载因子int threshold; //默认的threshold值static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE; // 4. 其他 // 存储数据的Entry类型数组，长度 = 2的幂 // HashMap的实现方式 = 拉链法，Entry数组上的每个元素本质上是一个单向链表transient Entry[] table = (Entry[]) EMPTY_TABLE; //HashMap内部的存储结构是一个数组，此处数组为空，即没有初始化之前的状态static final Entry[] EMPTY_TABLE = {}; // HashMap的大小，即 HashMap中存储的键值对的数量transient int size;

构造函数：

构造函数仅用于接收初始容量大小（capacity）、负载因子(Load factor)，但仍无真正初始化哈希表（存储数组table）
此处先给出结论：真正初始化存储数组table是在第1次调用put（）添加键值对时

/*** 构造函数1：默认构造函数（无参）实际上是调用构造函数3：指定“容量大小”和“加载因子”的构造函数*/public HashMap() {// 传入默认的容量（16）和负载因子（0.75）this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); }/*** 构造函数2：指定“容量大小”的构造函数实际上是调用指定“容量大小”和“加载因子”的构造函数*/public HashMap(int initialCapacity) {// 传入指定的容量，和默认的负载因子this(initialCapacity, DEFAULT_LOAD_FACTOR); }/*** 构造函数3：指定“容量大小”和“加载因子”的构造函数* 加载因子 & 容量都由自己指定*/public HashMap(int initialCapacity, float loadFactor) {// HashMap的最大容量只能是MAXIMUM_CAPACITY，哪怕传入的 > 最大容量//如果大于最大容量，还是赋值为1 << 30if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY; // 设置加载因子this.loadFactor = loadFactor; // 设置扩容阈值 = 初始容量// 注：此处不是真正的阈值，是为了扩展table，该阈值后面会重新计算threshold = initialCapacity; init(); // 一个空方法用于未来的子对象扩展}/*** 构造函数4：包含“子Map”的构造函数* 即构造出来的HashMap包含传入Map的映射关系* 加载因子 & 容量 = 默认*/public HashMap(Map m) {// 设置容量大小 & 加载因子 = 默认this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); // 该方法用于初始化数组 & 阈值，下面会详细说明inflateTable(threshold); // 将传入的子Map中的全部元素逐个添加到HashMap中putAllForCreate(m); }}

hash方法 hash(Object k)：计算key的hash值
该函数在JDK 1.7 和 1.8 中的实现不同，但原理（扰动函数）一样使得根据key生成的哈希码（hash值）分布更加均匀、更具备随机性，避免出现hash值冲突（即指不同key但生成同1个hash值）

JDK 1.7 做了9次扰动处理 = 4次位运算 + 5次异或运算
JDK 1.8 简化了扰动函数 = 只做了2次扰动 = 1次位运算 + 1次异或运算

/*** 确定位桶数组下标主要分为2步：计算hash值、根据hash值再计算得出最后数组位置*/// a. 根据键值key计算hash值 ->> 分析1int hash = hash(key); // b. 根据hash值最终获得 key对应存放的数组Table中位置 ->> 分析2int i = indexFor(hash, table.length); // JDK 1.7实现：将键key 转换成哈希码（hash值）操作= 使用hashCode() + 4次位运算 + 5次异或运算（9次扰动）static final int hash(int h) {h ^= k.hashCode(); h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }// JDK 1.8实现：将键key 转换成哈希码（hash值）操作 = 使用hashCode() + 1次位运算 + 1次异或运算（2次扰动）// 1. 取hashCode值： h = key.hashCode() //2. 高位参与低位的运算：h ^ (h >>> 16)static final int hash(Object key) {int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); // a. 当key = null时，hash值 = 0，所以HashMap的key 可为null// 注：对比HashTable，HashTable对key直接hashCode（），若key为null时，会抛出异常，所以HashTable的key不可为null// b. 当key ≠ null时，则通过先计算出 key的 hashCode()（记为h），然后对哈希码进行扰动处理：按位异或（^）哈希码自身右移16位后的二进制}/*** 函数源码分析2：indexFor(hash, table.length)* JDK 1.8中实际上无该函数，但原理相同，即具备类似作用的函数*/static int indexFor(int h, int length) {return h & (length-1); // 将对哈希码扰动处理后的结果与运算(&) （数组长度-1），最终得到存储在数组table的位置（即数组下标、索引）}

Map中添加数据
put方法
put(int hash, K key, V value, int bucketIndex)：向HashMap添加数据（成对存放 key - value）

文章图片

流程图

文章图片

源码

/*** 函数使用原型*/map.put("name", "huangkaiyu"); map.put("age", 21); public V put(K key, V value)// 1.如果哈希表未初始化（即 table为空) if (table == EMPTY_TABLE) { // 则使用构造函数传入的阈值(即初始容量) 初始化数组tableinflateTable(threshold); }// 2. 判断key是否为空值null// 若key == null，则将该键值对放在table [0]（本质：key = Null时，hash值 = 0，故存放到table[0]中）if (key == null)return putForNullKey(value); //若 key ≠ null，则计算存放数组 table 中的位置（下标、索引）//计算hash值int hash = hash(key); //传入hash值和table长度算出indexint i = indexFor(hash, table.length); // 3. 遍历table[indexFor]对应的链表判断该key对应的值是否已存在for (Entry e = table[i]; e != null; e = e.next) {Object k; //若该key已存在（即 key-value已存在），则用替换原来的值if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = https://www.it610.com/article/e.value; e.value = value; e.recordAccess(this); return oldValue; //并返回旧的value}}//改动计数器+1modCount++; // 若该key不存在，则将“key-value”添加到table中addEntry(hash, key, value, i); return null; }

inflateTable方法
inflateTable(int toSize)：初始化数组（table）、扩容阈值（threshold）
注意：
真正初始化哈希表（初始化存储数组table）是在第1次添加键值对时，即第1次调用put（）时

/*** put中调用*/if (table == EMPTY_TABLE) { //此处传入的是构造函数时设置的阈值(即初始容量)，不是真正的扩容阈值inflateTable(threshold); }private void inflateTable(int toSize) {// 1. 将传入的容量大小转化为：>传入容量大小的最小的2的次幂（传入18转化得32）int capacity = roundUpToPowerOf2(toSize); // 2. 重新计算阈值 threshold = 容量 * 加载因子（之前存的是容量）threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); // 3.传入容量初始化位桶数组table（作为数组长度）table = new Entry[capacity]; initHashSeedAsNeeded(capacity); }/*** roundUpToPowerOf2(toSize)* 作用：将传入的容量大小转化为：>传入容量大小的最小的2的幂* 特别注意：容量大小必须为2的幂*/private static int roundUpToPowerOf2(int number) {//若超过了最大值，则设置为最大值；否则，设置为大于传入容量大小的最小的2的次幂return number >= MAXIMUM_CAPACITY? MAXIMUM_CAPACITY: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;

putForNullKey方法
putForNullKey(V value)：当 key ==null时，将该 key-value 的存储位置规定为数组table 中的第1个位置，即table [0]

/***put()方法调用时传入的key为空*/if (key == null)return putForNullKey(value); /*** 遍历以table[0]为首的链表，寻找是否存在key==null 对应的键值对有就替换并返回旧值，没有就调用addEntry（）将（null，value）添加到链表中*/private V putForNullKey(V value) {for (Entry e = table[0]; e != null; e = e.next) { //如果链表结点key为空if (e.key == null) {//保存旧值V oldValue = https://www.it610.com/article/e.value; //链表赋新值e.value = value; e.recordAccess(this); //返回旧值return oldValue; }}//改动次数+1modCount++; // 若没有key==null的键，那么调用addEntry（）将其加入链表addEntry(0, null, value, 0); // a. addEntry（）的第1个参数hash值传入0（当key = null时，也有hash值 = 0，所以HashMap的key 可为null）// c. 对比HashTable，由于HashTable对key直接hashCode（），若key为null时，会抛出异常，所以HashTable的key不可为null// d. 此处只需知道是将 key-value 添加到HashMap中即可，关于addEntry（）的源码分析将等到下面再详细说明，return null; }

addEntry方法
addEntry(int hash, K key, V value, int bucketIndex)：添加键值对（Entry ）到 HashMap中

/*** put中key不存在调用，将Entry对象存入链表*/void addEntry(int hash, K key, V value, int bucketIndex) {// 1. 插入前先判断是否需要扩容// 如果元素个数>=扩容阈值并且对应数组下标不为空if ((size >= threshold) && (null != table[bucketIndex])) { //扩容2倍resize(2 * table.length); // 重新计算Key对应的hash值hash = (null != key) ? hash(key) : 0; // 重新计算该Key对应的hash值的存储数组下标位置 bucketIndex = indexFor(hash, table.length); }//如果不需要扩容，则创建1个新的Entry并放入到数组中createEntry(hash, key, value, bucketIndex); }

createEntry方法
createEntry(int hash, K key, V value, int bucketIndex)

/*** 分析2：createEntry(hash, key, value, bucketIndex); * 作用：若容量足够，则创建1个新的数组元素（Entry）并放入到数组中*/void createEntry(int hash, K key, V value, int bucketIndex) { // 1. 把table中该位置原来的Entry保存Entry e = table[bucketIndex]; // 2. 在table中该位置新建一个Entry：将原头结点位置（数组上）的键值对放入到（链表）后1个节点中、将需插入的键值对放入到头结点中（数组上）-> 从而形成链表// 即在插入元素时，是在链表头插入的，table中的每个位置永远只保存最新插入的Entry，旧的Entry则放入到链表中（即解决Hash冲突）table[bucketIndex] = new Entry<>(hash, key, value, e); // 3. 哈希表的键值对数量计数增加size++; }

扩容方法
resize方法
resize(int newCapacity)：扩容为原来两倍
在扩容resize（）过程中，在将旧数组上的数据转移到新数组上时，转移操作 = 按旧链表的正序遍历链表、在新链表的头部依次插入，即在转移数据、扩容后，容易出现链表逆序的情况
设重新计算存储位置后不变，即扩容前 = 1->2->3，扩容后 = 3->2->1
此时若（多线程）并发执行 put（）操作，一旦出现扩容情况，则容易出现环形链表，从而在获取数据、遍历链表时形成死循环（Infinite Loop），即死锁的状态 = 线程不安全

/*** resize(2 * table.length)* 作用：当容量不足时（容量 > 阈值），则扩容（扩到2倍）*/ void resize(int newCapacity) {// 1. 保存旧数组（old table） Entry[] oldTable = table; // 2. 保存旧容量（数组长度）int oldCapacity = oldTable.length; // 3. 若旧容量已经是系统默认最大容量了，那么将扩容阈值设置成整型的最大值，退出 if (oldCapacity == MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE; return; }// 4. 根据新容量（2倍容量）新建1个数组，即新tableEntry[] newTable = new Entry[newCapacity]; // 5. 将旧数组上的数据（键值对）转移到新table中，从而完成扩容transfer(newTable); // 6. 新数组table引用到HashMap的table属性上table = newTable; // 7. 重新设置阈值threshold = (int)(newCapacity * loadFactor); }

transfer方法
transfer(Entry[] newTable)：

/*** transfer(newTable); * 作用：将旧数组上的数据（键值对）转移到新table中，从而完成扩容* 过程：按旧链表的正序遍历链表采用头插法插入新链表*/ void transfer(Entry[] newTable) {// 1. src指向原tableEntry[] src = https://www.it610.com/article/table; // 2. 获取新数组的大小int newCapacity = newTable.length; // 3. 通过遍历旧table，将键值对转移到新table上for (int j = 0; j < src.length; j++) { // 创建辅助entry指向旧数组中的元素Entry e = src[j]; if (e != null) {// 释放旧数组的对象引用（for循环后，旧数组不再引用任何对象）src[j] = null; //开始遍历do { //创建辅助指针next（因是单链表，故要保存下1个结点，否则转移后链表会断开）Entry next = e.next; // 重新计算每个元素的存储位置int i = indexFor(e.hash, newCapacity); //头插法插入e.next = newTable[i]; newTable[i] = e; // e跳到下一个entrye = next; } while (e != null); // 循环直到遍历完数组上的所有数据元素}} }

从HashMap中获取数据
get方法
public V get(Object key)：根据键key，向HashMap获取对应的值

public V get(Object key) {// 1. 当key == null时，则到table[0]为头结点的链表去检索if (key == null)return getForNullKey(); // 2. 当key ≠ null时，去获得对应值 Entry entry = getEntry(key); return null == entry ? null : entry.getValue(); } /*** getForNullKey()* 作用：当key == null时，在table[0]中去寻找对应 key为null的键值对*/ private V getForNullKey() {if (size == 0) {return null; }// 遍历以table[0]为头结点的链表，寻找 key==null 对应的值for (Entry e = table[0]; e != null; e = e.next) {// 从table[0]中取key==null的value值 if (e.key == null)return e.value; }return null; } /*** getEntry(key)* 作用：当key ≠ null时，去获得对应值*/final Entry getEntry(Object key) { //如果元素个数为空返回nullif (size == 0) {return null; }// 1. 计算key对应的hash值int hash = (key == null) ? 0 : hash(key); // 2. 根据hash值计算出对应的数组下标// 3. 遍历对应index的数组元素为头结点的链表，检索键值对for (Entry e = table[indexFor(hash, table.length)]; e != null; e = e.next) {Object k; // 若 hash值 & key 相等，则证明该Entry = 我们要的键值对// 通过==或者equals（）判断key是否相等if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e; }return null; }

从HashMap中删除数据
remove方法
remove(Object key)：删除该键值对

public V remove(Object key) {Entry e = removeEntryForKey(key); return (e == null ? null : e.value); }final Entry removeEntryForKey(Object key) {if (size == 0) {return null; }// 1. 计算hash值int hash = (key == null) ? 0 : hash(key); // 2. 计算存储的数组下标位置int i = indexFor(hash, table.length); //prev记录要删除entry的前一个entryEntry prev = table[i]; //e记录要删除的entryEntry e = prev; while (e != null) {//辅助指针，指向下一个entryEntry next = e.next; Object k; //如果key相等if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) {modCount++; //改动次数+1size--; //元素个数-1// 若删除的是链表的头结点 if (prev == e) // 则将头结点的next引用存入table[i]中table[i] = next; //否则将当前结点的前1个结点中的next指向当前结点的下一个结点（直接越过当前Entry）elseprev.next = next; e.recordRemoval(this); return e; }//prev指向当前结点prev = e; //e指向下一个结点e = next; }//遍历结束e为null，表示没找到返回nullreturn e; }

对HashMap的其他操作 HashMap除了核心的put（）、get（）函数，还有以下主要使用的函数方法

void clear();	清除哈希表中的所有键值对
int size();	返回哈希表中所有键值对的数量 = 数组中的键值对 + 链表中的键值对
boolean isEmpty();	判断HashMap是否为空；size == 0时表示为空
void putAll(Map m);	将指定Map中的键值对复制到此Map中
boolean containsKey(Object key);	判断是否存在该键的键值对；是则返回true
boolean containsValue(Object value);	判断是否存在该值的键值对；是则返回true

源码

/*** 函数：isEmpty()* 作用：判断HashMap是否为空，即无键值对；size == 0时表示为空 */public boolean isEmpty() {return size == 0; } /*** 函数：size()* 作用：返回哈希表中所有键值对的数量 = 数组中的键值对 + 链表中的键值对*/public int size() {return size; } /*** 函数：clear()* 作用：清空哈希表，即删除所有键值对* 原理：将数组table中存储的Entry全部置为null、size置为0*/ public void clear() {//改动次数＋1modCount++; //全部元素设空Arrays.fill(table, null); //元素个数清0size = 0; }/*** 函数：putAll(Map m)* 作用：将指定Map中的键值对复制到此Map中* 原理：类似Put函数*/ public void putAll(Map m) {// 1. 统计需复制多少个键值对int numKeysToBeAdded = m.size(); if (numKeysToBeAdded == 0)return; // 2. 若table还没初始化，先用刚刚统计的复制数去初始化tableif (table == EMPTY_TABLE) {inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold)); }// 3. 若需复制的数目 > 阈值，则需先扩容 if (numKeysToBeAdded > threshold) {int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1); if (targetCapacity > MAXIMUM_CAPACITY)targetCapacity = MAXIMUM_CAPACITY; int newCapacity = table.length; while (newCapacity < targetCapacity)newCapacity <<= 1; if (newCapacity > table.length)resize(newCapacity); }// 4. 开始复制（实际上不断调用Put函数插入）for (Map.Entry e : m.entrySet())put(e.getKey(), e.getValue()); } /*** 函数：containsKey(Object key)* 作用：判断是否存在该键的键值对；是则返回true* 原理：调用get（），判断是否为Null*/public boolean containsKey(Object key) {return getEntry(key) != null; } /*** 函数：containsValue(Object value)* 作用：判断是否存在该值的键值对；是则返回true*/public boolean containsValue(Object value) {// 若value为空，则调用containsNullValue()if (value =https://www.it610.com/article/= null)return containsNullValue(); // 若value不为空，则遍历链表中的每个Entry，通过equals（）比较values 判断是否存在Entry[] tab = table; for (int i = 0; i < tab.length ; i++)for (Entry e = tab[i] ; e != null ; e = e.next)if (value.equals(e.value)) return true; //返回truereturn false; }// 判断是否有空值 private boolean containsNullValue() {Entry[] tab = table; for (int i = 0; i < tab.length ; i++)for (Entry e = tab[i] ; e != null ; e = e.next)if (e.value == null)return true; return false; }

1.7和1.8版本区别 JDK 1.8 的优化目的主要是：减少 Hash冲突 & 提高哈希表的存、取效率

数据结构

版本	存储结构	数组&链表结点实现类	红黑树的实现类	初始化方式
JDK1.7	数组+链表	Entry类	无红黑树	单独函数：inflateTable()
JDK1.8	数组+链表+红黑树	Node类	TreeNode类	直接集成在扩容函数：resize()中

hash值计算方式

版本	hash值计算方式
JDK1.7	1.hashcode计算
JDK1.8	按照扩容后的规律计算（扩容后的位置=原位置 or 原位置 +旧容量）

扩容机制

版本	重hash计算位置
JDK1.7	1.Object.hashCode计算 2. 9次扰动处理 =4次位运算+5次异或运算
JDK1.8	1.Object.hashCode计算 2. 2次扰动处理 =1次位运算+1次异或运算