在我们面试中,HashMap几乎是必问项,因为HashMap在工作学习中都十分重要,
只有我们了解了其底层实现原理,才能更高效地使用它
那么,在本篇博文中,本人就先来讲解下有关HashMap1.7的重要知识点:
首先是 数据存储结构:
数据存储结构：
从上图中,我们能够看出:
在JDK1.7版本,HashMap主要是以
数组+链表形式存储的
那么,接下来,本人就来带同学们深究下源码:
源码剖析：
首先，本人先来介绍一个类 —— Entry类：
Entry类：
为什么要介绍这个类呢？
答曰：
因为
JDK1.7版本中，HashMap存储键值对，就是使用该类型
Entry类 源码：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key; // 存储 “键”
V value; // 存储 “值”
Entry<K,V> next; // 存储 “下一个节点”
final int hash; // 存储 当前键值对的“hash值”，便于之后的put操作
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = 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;
}
/**
* 比较顺序：
* 1、目标对象的 类型
* 2、目标对象的 “键”
* 3、目标对象的 “值”
* @param o 要比较的对象
* @return
*/
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;
}
public final int hashCode() {
return (key==null ? 0 : key.hashCode()) ^
(value==null ? 0 : value.hashCode());
}
public final String toString() {
return getKey() + "=" + getValue();
}
/**
* (jdk未实现)
* 每当调用HashMap中 已存在的键k 的put（k，v）覆盖条目中的值时，都会调用此方法。
*/
void recordAccess(HashMap<K,V> m) {
}
/**
* (jdk未实现)
* 每当从表中删除条目时，都会调用此方法。
*/
void recordRemoval(HashMap<K,V> m) {
}
}
接下来，本人来介绍下 JDK1.7版本中的 HashMap类 的 成员属性：
成员属性：
在HashMap中，有以下 三个重要参数：
- size (容量)
- loadFactor (负载因子)
- threshold (扩容阈值)
容量 —— capacity：
容量范围：必须是2次幂 且 小于最大容量(2的30次方)初始容量= 哈希表创建时的容量默认容量= 1<<4 = 2^4(十进制) =16
/**
* 默认初始容量，必须为2的幂。
* (至于为何必须是2次幂，将在下文中的 初始化环节 进行讲解)
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
/**
* 最大容量，如果两个构造函数都使用参数隐式指定了更高的值，则使用该容量。
* 必须是两个<= 1 << 30的幂。
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
负载因子 —— loadFactor：
意义：HashMap在其 扩容前 可达到大小的一种尺度- 加载因子越大、填满的元素越多：
空间利用率高、但冲突的机会加大、查找效率变低（因为链表变长了）- 加载因子越小、填满的元素越少：
空间利用率小、冲突的机会减小、查找效率高（链表不长）
/**
* 在构造函数中未指定时使用的负载因子。
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 哈希表的负载因子。
*/
final float loadFactor;
扩容阈值 —— threshold：
扩容阈值（threshold）：当 哈希表的大小 大于等于 threshold 时，就会扩容哈希表（即 扩充HashMap的容量）扩容：
对哈希表进行resize操作（即 重建内部数据结构），从而哈希表将具有大约两倍的桶数threshold = capacity * load factor
/**
* 映射容量的默认阈值，高于默认值时，散列度会降低，需要选择新的hash表
*/
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
/**
* 要调整大小的下一个大小值 (capacity * load factor).
*/
int threshold;
其它成员属性：
/**
* 空数组，在数组进行初始化时会使用到，
* 仅用于判断，不修改内容
*/
static final Entry<?,?>[] EMPTY_TABLE = {};
/**
* 用于存储数据的数组，根据需要调整大小。
* 长度必须始终为2的幂。
* (至于为何必须是2次幂，将在下文中进行讲解)
* HashMap的实现方式 = 拉链法，Entry数组上的每个元素本质上是一个单向链表
*/
transient Entry[] table = (Entry<K,V>[]) EMPTY_TABLE; // transient关键字： 实例化对象的该属性 不参加“序列化”
/**
* 此映射中包含的 键值对数(真实“键值对”数)
*/
transient int size; // transient关键字： 实例化对象的该属性 不参加“序列化”
/**
* 对该HashMap进行结构修改的次数结构修改是指更改HashMap中的映射次数或以其他方式修改其内部结构
* （例如，重新哈希）的修改。
* 此字段用于使HashMap的Collection-view上的迭代器快速失败。
* （请参见ConcurrentModificationException）。
*/
transient int modCount;
相信许多同学在看完上述内容后，仍是对其中很多属性的意义不明确
那么，下面本人就来通过一张图展示下 每个属性的意义：
接下来，有了上述的铺垫，本人就来展示下 HashMap类 的 核心方法源码：
- new HashMap()
- hashmap.put(key, value)
- hashmap.containsKey(key)
- hashmap.keySet()
- hashmap.get(key)
- hashmap.putAll(Map<? extends K, ? extends V> m);
- hashmap.remove(Object key);
- hashmap.containsValue(Object value);
- hashmap. keySet();
- hashmap.values();
- hashmap.clear();
- hashmap.size();
- hashmap.isEmpty();
在我们使用 HashMap时，基本上都是通过如下顺序：
- 构造初始化
- put类填充
- 其它操作
那么，本人就按照上面的顺序，来带同学们一一剖析：
构造方法:
JDK对于HashMap类，提供了如下四种 构造函数：
/**
* 构造一个具有 指定“初始容量”和“负载因子” 的 “空HashMap”
*
* @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) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// HashMap的最大容量只能是MAXIMUM_CAPACITY，哪怕传入的 > 最大容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
this.loadFactor = loadFactor;
// 设置 扩容阈值 = 初始容量
// 注：此处不是真正的阈值，是为了扩展table，该阈值后面会重新计算
threshold = initialCapacity;
init(); // 空方法，以便 子对象的扩展
}
/**
* 构造一个具有 “指定初始容量” 和 默认负载因子（0.75）的空HashMap。
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 使用默认的初始容量（16）和默认的加载因子（0.75）构造一个空的HashMap。
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
/**
* 使用默认的初始容量（16）和默认的加载因子（0.75）
* 构造一个具有与指定Map相同的映射关系的新HashMap。
*
* @param m the map whose mappings are to be placed in this map
* @throws NullPointerException if the specified map is null
*/
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
putAllForCreate(m);
}
在看完上述的源码之后，相信同学们会发现：
当我们执行完 构造函数 后，只是对 容量（capacity） 和 加载因子(Load factor) 两个属性 进行了赋值，并没有对 table数组进行初始化
实际上，真正初始化哈希表（table数组）是 在第1次添加键值对时，即第1次调用put()方法 时
put()方法：
/**
* 将指定值与该映射中的指定键值对。
* 如果该映射先前包含该键值对，则将替换旧值。
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
// 懒加载模式，每次调用put()方法都会先判断数组是否已经初始化了
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
/*
遍历 当前哈希表，查找 “目标键”是否存在：
若存在，则覆盖旧值，并将旧值返回
若不存在，则向 哈希表 中添加 新的键值对，并返回null
*/
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
// 若 hash值相等，则称这种情况为“哈希碰撞”，
// 若发生 “哈希碰撞”，则通过 equals()方法来判断 两个key 是否 “一致”
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++; // 修改一次 哈希表的容量，则使得modCount加一
addEntry(hash, key, value, i);
return null;
}
那么，本人根据上述的源码，来绘制一张 流程图：
流程图：
在上图中，我们能够看到：
put()方法的执行，主要是 如下步骤：
- 判断 哈希表(table数组) 是否 未初始化
- 判断 目标key 是否为 null
- 根据 目标key 生成 相应的hash值
- 根据 hash值 和 哈希表(table数组) 的长度 ，生成 当前键值对所在 哈希表(table数组) 中的 下标
那么，本人根据这张流程图，来逐一讲解下 put()方法 中，所运用到的 方法：
inflateTable(threshold) 方法：
private void inflateTable(int toSize) {
// 取容量为大于等于toSize的2的指数次幂，原因在后面讲解
int capacity = roundUpToPowerOf2(toSize);
// 临界值最大只能取MAXIMUM_CAPACITY+1
// 如果未指定capacity和loadFactor，那么threshold=12
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
// 计算hashSeed，不超过MAXIMUM_CAPACITY就会一直保持为0，映射了最后一个属性
initHashSeedAsNeeded(capacity);
}
在上述方法中，我们能够看到：
还是调用了其它两个方法
那么，本人现在来 讲解下 那两个方法：
roundUpToPowerOf2(int number)方法：
/**
* 返回一个 比参数大的、最小的 2次幂
* @param number 目标参数
* @return 比参数大的、最小的 2次幂
*/
private static int roundUpToPowerOf2(int number) {
/*
若 参数 超过了 最大容量，返回 最大容量
否则，返回 比参数大的、最小的 2次幂
*/
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
继续解析 higestOneBit()方法：
higestOneBit()方法：
作用：
返回 比所传参数小 的 最大二次幂
源码展示：
/**
* 返回一个 比所传参数小 的 最大二次幂
* @param i 目标参数
* @return 比所传参数小 的 最大二次幂
*/
public static int highestOneBit(int i) {
// HD, Figure 3-1
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
return i - (i >>> 1);
}
原理解析：
参数 为 int类型
一个int有且仅有 32位
按照 每一行代码 的 调用执行，只要参数不为0随着每一步的 右移或等运算，会将 整个int的低16位全部转换为1
最后再将计算结果执行如下代码：
i - (i >>> 1)
就会使得 仅原参数的最高位的1 保留下来，
而正巧，每个2次幂数，都是 仅一位为1的int
看完 higestOneBit()方法 的源码，相信很多同学和本人初学时一样，抱有如下疑问：
为什么指定 长度 时，需要 二次幂 呢？
那么，这个答案，将在下文中的 indexFor()源码讲解 中进行解释。
initHashSeedAsNeeded(int num)方法：
/**
* 根据 参数 初始化 hashSeed
* @param capacity 当前哈希表 容量
* @return
*/
final boolean initHashSeedAsNeeded(int capacity) {
//当我们初始化的时候hashSeed为0,0!=0 这时为false.
boolean currentAltHashing = hashSeed != 0;
//isBooted()这个方法里面返回了一个boolean值,我们看下面的代码
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean switching = currentAltHashing ^ useAltHashing;
if (switching) {
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
}
(这个方法暂时不需要深究，在下文的总结段本人将详细讲解！)
putForNullKey(V value)方法:
/**
* 键为null 的 put()方法
* 若找到，则覆盖
* 若没找到，则 使得modCount加1，并添加键为null、值为value 的键值对
*/
private V putForNullKey(V value) {
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;
}
hash(int h)方法:
/**
* 将补充哈希函数应用于给定的hashCode，以防止质量差的哈希函数。
* 这很关键，因为HashMap使用2的幂的哈希表，否则哈希表在低位无差异时会遇到冲突。
* 注意：空键始终映射到哈希0，因此索引为0。
*/
static int hash(int h) {
// 这个函数确保在 每个位元位置 上
// 仅以 常数倍数 存在差异的哈希码 有一个 有限的冲突数(在 默认负载因子 下约为 8)
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
（这个方法 只是用来生成hash值，也不用深究）
在上文的 inflateTable(threshold) 方法 中的 roundUpToPowerOf2(int number)方法 中的 higestOneBit()方法 的讲解中，
本人讲到：
roundUpToPowerOf2(int number)方法 的作用是 返回 比所传参数小 的 最大二次幂
那么，为什么要操作 2次幂 呢？
答曰：
请看 indexFor(int h, int length)方法
indexFor(int h, int length)方法:
/**
* 返回哈希码h的索引
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
虽然上述的方法的源码 仅1行，
但是让我们来细品下这行代码的作用：
我们都知道：
数组下标的范围 和 数组长度 的关系：
$$
0 <= 下标范围 < 数组长度
$$
而 h & (length-1) 的范围是： [0, length-1]，恰好符合 数组下标 和 数组长度 的关系
但是，这又和本人上文中所讲解的 inflateTable()方法 时 初始化的长度必须是2次幂 有什么关系呢？
答曰：
由于我们要将 length-1 后，与所求得的 hash 进行 &运算
是为了取得hash的后几位，且在length内
那么，我们假设长度为16，则length-1的二进制表示为：
1111
这样，我们&运算的结果，就在 [0, length-1]中
但是，这样的结果，要求的是 length-1的二进制表示为全1，也就是说：length的二进制必须有且只有一个1，即：2次幂
相信看到上文的解释，同学们会惊叹于jdk开发者的天才脑洞！
而最后的方法当然就是 加入新的键值对操作 —— addEntry(int hash, K key, V value, int bucketIndex)方法：
addEntry(int hash, K key, V value, int bucketIndex)方法:
/**
* 将具有指定键，值和哈希码的新条目添加到指定存储桶。
* 如果合适，此方法负责调整表的大小。
*
* 子类重写此方法以更改put方法的行为。
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e); // “头插” 新节点
if (size++ >= threshold) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0; // 重新计算该Key对应的hash值
bucketIndex = indexFor(hash, table.length); // 重新计算该Key对应的hash值的存储数组下标位置
}
createEntry(hash, key, value, bucketIndex);
}
可以看到：
当我们加入一个新的键值对时，会执行如下步骤：
1、将 哈希表 的 目标下标(上述方法计算得到的) 中的元素(null或链表的表头) 取出
2、将 当前元素 插入 取出的链表 的 表头，并将 哈希表的目标下标元素 改为 当前元素
3、计算 当前size 是否大于等于 扩容阈值，并使得 当前size+1
4、若 当前size 到达 扩容阈值，则 扩容 至 原哈希表的2倍
那么，我们现在来看看上述方法所运用到的、同时也是容器类中非常重要的方法 —— resize()方法：
resize()方法：
/**
* 将此映射的内容重新映射到容量更大的新数组中。
* 当此映射中的键数达到其阈值时，将自动调用此方法。
* 如果当前容量为MAXIMUM_CAPACITY，则此方法不会调整map的大小，而是将阈值设置为Integer.MAX_VALUE。
* 这具有防止将来通话的效果。
*
* @param newCapacity the new capacity, MUST be a power of two;
* must be greater than current capacity unless current
* capacity is MAXIMUM_CAPACITY (in which case value
* is irrelevant).
*/
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) { // 若 旧容量 是 最大值，就不能再扩容了，只能改变“扩容阈值”
threshold = Integer.MAX_VALUE;
return;
}
/*
若 旧容量 小于 最大值：
创建新的数组空间(大小为所传参数)，将原哈希表中的数据 转存到 新哈希表 中
并 改变“扩容阈值” 为 新容量*负载因子 和 最大容量+1 中的 最小值
*/
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity)); // 将原哈希表中的数据 转存到 新哈希表 中
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
那么,我们再来看看 转存方法 —— transfer()方法:
transfer(Entry[] newTable)方法:
/**
* 将所有条目从当前表传输到newTable
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
// 遍历数组，仅遍历数组下标元素
for (Entry<K, V> e : table) { // 遍历 原哈希表 的 所有数据
while (null != e) {
Entry<K, V> next = e.next;
// 只有产生了新的hash表才需要重新计算hash值
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
/*
计算 当前节点 在 新哈希表 中的下标,
newCapacity = 原capacity*2，则indexFor()的结果为：
oldIndex(原哈希的比最后一位&掉的位是0) 或 oldIndex + oldCapacity(原哈希的比最后一位&掉的位是1)
*/
int i = indexFor(e.hash, newCapacity); // 计算结果为:i = oldIndex 或 i = oldIndex + oldCapacity
/*
将 当前元素 “头插”入当前数组元素的链表
*/
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
这个转存方法,是 导致HashMap线程不安全的元凶!
为什么呢?
我们这样来思考:
假设原哈希表有2个数组空间(仅假设,便于画图示意)
现在有两个线程同时运行到了resize()方法中,且都运行到了 transfer()方法
第二个线程 仅运行到 Entry<K, V> next = e.next; 就失去了临界资源
第一个线程 开始转存 原哈希表 到 第一个哈希表空间
根据上文的讲解,原哈希表中仅有的那条链表,仅能存储到新哈希表 的 下标0 和 下标2 的数组单元中
我们假设 这条链表的所有元素都存储到了 下标为2 的数组单元中
这时,线程2开始运行,开始执行之后的代码
但是,由于之前 线程2 执行过 Entry<K, V> next = e.next;
因此,之后的执行,会是如下形式:
继续一轮循环
这时,当下一轮的 e.next = newTable[i];执行时, 就开始 "无限循环"了
如上图所示,出现了 "长度为2 的 循环链表"
之后,两个指针就在 这两个节点中来回"游走",直至CPU耗尽!
而这,就是 HashMap类 的 线程安全问题,
它也有一个凶名赫赫 的外号 —— HashMap死锁
那么,分析到这里,put()操作也就分析完毕了!
接下来,其余方法,本人仅展示 源码 以及 略微讲解,
(因为 集合类最重要的方法是 存储)
get(Object key)方法:
public V get(Object key) {
// 得到key=null的value值，可能为空
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
具体流程,如源码所示:
下面是 get()方法中用到的 两个方法:
getForNullKey():
/**
* get（）的卸载版本以查找空键。
* 空键映射到索引0
* 为了在两个最常用的操作（获取和放置）中提高性能，此空情况被拆分为单独的方法，但在其他条件中并入了条件。
*/
private V getForNullKey() {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
getEntry(Object key):
/**
* 返回与HashMap中的指定键关联的条目。
* 如果HashMap不包含该键的映射，则返回null。
*/
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
// 计算hash值
int hash = (key == null) ? 0 : hash(key);
// 遍历指定数组下标的链表，找到满足条件的Entry
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
// key可以是同一对象，也可以是不同的对象，只要equals比较成立即可
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
remove(Object key):
/**
* 如果存在，则从此映射中删除指定键的映射。
*
* @param key key whose mapping is to be removed from the map
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
removeEntryForKey(Object key):
/**
* 删除并返回与HashMap中的指定键关联的条目。
* 如果HashMap不包含此键的映射，则返回null
*/
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
// 这里是最基本的链表删除进行的遍历
while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
// 删除使原table数组产生了变化，所以modCount要改变
modCount++;
size--;
if (prev == e)
// 当数据为链表头节点时，只用略过头节点即可
table[i] = next;
else
// 当数据不为链表头节点时，需将前一节点的next指向删除节点的后一节点
prev.next = next;
// HashMap中没有真正实现，不用考虑
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
// 返回删除后的节点，e可能为null
return e;
}
keySet():
/**
* 返回此映射中包含的键的Set视图。
* 该集合由map支持，因此对map的更改会反映在集合中，反之亦然。
* 如果在对集合进行迭代时修改了映射（通过迭代器自己的remove操作除外），则迭代的结果不确定。
* 该集合支持元素删除，该元素通过Iterator.remove，Set.remove，removeAll，retainAll和clear操作从映射中删除相应的映射。
* 它不支持add或addAll操作。
*/
public Set<K> keySet() {
// transient volatile Set<K> keySet = null;
// 这里的keySet和values一样都是AbstractMap<K,V>抽象类中的成员
Set<K> ks = keySet;
// 懒加载模式 初始化keyset
return (ks != null ? ks : (keySet = new KeySet()));
}
private final class KeySet extends AbstractSet<K> {
public Iterator<K> iterator() {
return newKeyIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
return HashMap.this.removeEntryForKey(o) != null;
}
public void clear() {
HashMap.this.clear();
}
}
values():
/**
* 返回此映射中包含的值的Collection视图。
* 集合由map支持，因此对map的更改会反映在集合中，反之亦然
* 如果在对集合进行迭代时修改了map（通过迭代器自己的remove操作除外），则迭代的结果是不确定的。
* 集合支持元素删除，该元素通过Iterator.remove，Collection.remove，removeAll，retainAll和clear操作从映射中删除相应的映射。
* 它不支持add或addAll操作。
*/
public Collection<V> values() {
// transient Collection<V> values = null;
// 这里的keySet和values一样都是AbstractMap<K,V>抽象类中的成员
Collection<V> vs = values;
// 懒加载模式 初始化values
return (vs != null ? vs : (values = new Values()));
}
private final class Values extends AbstractCollection<V> {
public Iterator<V> iterator() {
return newValueIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsValue(o);
}
public void clear() {
HashMap.this.clear();
}
}
containsValue(Object value):
/**
* 如果此映射将一个或多个键映射到指定值，则返回true。
*
* @param value value whose presence in this map is to be tested
* @return <tt>true</tt> if this map maps one or more keys to the
* specified value
*/
public boolean containsValue(Object value) {
if (value == null)
return containsNullValue();
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;
return false;
}
相信同学们在看玩上述的源码解析后，还存在部分疑惑
那么，在剖析完源码后，本人来小结下 HashMap 的相关知识点：
总结：
为什么HashMap要扩容？
可能会有同学有这样的问题：
HashMap 存储数据 的 数据结构 是
数组+链表
那么就不会像 List 和 Set 一样，出现 “存储空间不足”问题
(这里的存储空间是指 自己申请的空间不够用，并 不是 指 内存存储空间，因为内存空间不足是无可避免的)
那 为什么HashMap要扩容？
答曰：
为了 缩短查询效率
链表越长，我们查询时候，要遍历的节点数就越多，
因此，当 扩容是为了 增加离散度、缩短查询效率
modCount属性 有什么用？
答曰：
在源码中，我们能够发现：
当 HashMap中存储的元素改变 时，modCount 就会加一
那么，回顾下本人《【JUC剖析】专栏总集篇》中所讲解的 乐观锁机制
没错，modCount 就是 乐观锁的“版本号”
modCount 表示了 HashMap的改变次数，是HashMap类创造者提供的一种 快速失败的容错机制
而modCount主要用于HashMap的一个内部类：HashMap迭代器 —— HashIterator类 中：
HashIterator类 源码：
private abstract class HashIterator<E> implements Iterator<E> { // 集成 “迭代器接口”
Entry<K,V> next; // next entry to return
int expectedModCount; // For fast-fail
int index; // current slot
Entry<K,V> current; // current entry
HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
}
public final boolean hasNext() {
return next != null;
}
final Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if ((next = e.next) == null) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
public void remove() {
if (current == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Object k = current.key;
current = null;
HashMap.this.removeEntryForKey(k);
expectedModCount = modCount;
}
}
可以看到：
modCount 在 HashIterator类 中 充当了 乐观锁的作用
除此之外，modCount可以说是没有其它用途了！
initHashSeedAsNeeded()方法 有什么用？
那么，本人再来展示下 initHashSeedAsNeeded()方法的源码：
initHashSeedAsNeeded()方法 源码：
/**
* 根据 参数 初始化 hashSeed
* @param capacity 当前哈希表 容量
* @return
*/
final boolean initHashSeedAsNeeded(int capacity) {
//当我们初始化的时候hashSeed为0,0!=0 这时为false.
boolean currentAltHashing = hashSeed != 0;
//isBooted()这个方法里面返回了一个boolean值,我们看下面的代码
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean switching = currentAltHashing ^ useAltHashing;
if (switching) {
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
}
我们不妨倒着推导下：
我们也能够看到：hashSeed属性 在之前一直是0
因此，currentAltHashing变量 在次之前一直是1，
useAltHashing变量 为1 的条件是 本类的类构造器是 Bootstrap ClassLoader 且 当前哈希表容量 大于 Holder.ALTERNATIVE_HASHING_THRESHOLD
而 Holder.ALTERNATIVE_HASHING_THRESHOLD的值为我们通过 启动参数jdk.map.althhashing.threshold 设置的
(不相信的同学请自行查阅源码)
而当 useAltHashing 为 1 时，switching 为 true
只有当 switching 为 true时，才能改变hashSeed
而当hashSeed修改后，继续运行调用其的父方法inflateTable() 的 父方法put() 后的代码
int hash = hash(key);
中，会用到hashSeed属性：
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);
}
总而言之：
initHashSeedAsNeeded(方法的目的是改变hashSeed
而 hashSeed 是为了 方便根据不同场合，使用 启动参数jdk.map.althhashing.threshold 来 增加散列度
那么，至此，HashMap1.7讲解完毕！