学习资料；
- 《Java程序性能优化》
- 美团点评技术团队 Java 8系列之重新认识HashMap
- 张旭童大佬 面试必备：HashMap源码解析（JDK8）
这篇笔记是第二次整理，第一次是16年11月份，只是之前能写出来的太少，中途而废。最近又来看HashMap的东西，比上次看时理解的东西多了些，就重新整理下
目前，HashMap内，还是有很多问题，不明白，以后会再做补充
重点学习HashMap，本篇学习笔记，会有很多错误，请指出
1. Map接口
实现map接口的主要有四个HashTable,HashMap,LinkedHashMap,TreeMap
HashTable,HashMap区别：
-
HashTable的大部分方法都做了同步，而HashMap没有。HashMap不是线程安全的 -
HashTable不允许key，value为null，而HashMap可以为null - 两者对
key的hash算法和hash值到内存索引的映射算法不同
HashMap优点特性就是高性能，存放和查询是很高效的，缺点就是无序性，存入的元素，在遍历时是无序的
LinkedHashMap继承自HashMap，除了具备HashMap高性能优点外，还具有有序性。LinkedHashMap在HashMap的基础上，增加了一个链表来存放元素的顺序
LinkedHashMap可以简单理解为一个维护了元素次序表的HashMap
LinkedHashMap提供了两种类型的顺序：存放(插入)元素时的顺序，最近访问顺序
可以使用3个参数的构造方法来指定排序行为
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder)
accessOrder为true时，按照元素最后访问时间来排序，默认情况下为false
当为true时，使用get()执行来一次获取操作时，当前元素会被挪到整个LinkedHashMap最末尾位置
需要注意的是，当设置accessOrder为true时，不能用于Iterator遍历
不要在迭代器模式中修改被迭代的集合
TreeMap实现了SortMap接口，可以对元素进行排序
TreeMap排序是指根据条件对存入的key进行按照规则进行了排序，是基于元素本身的固有顺序。而LinkedHashMap只是基于元素进入集合的顺序或者访问的先后顺序进行排序
TreeMap为了确定key的排序，可以通过两种方式来指定
- 通过
TreeMap的构造方法，public TreeMap(Comparator<? super K> comparator)，指定一个Comparator - 使用一个自身实现了
Comparable接口的key
TreeMap内部实现是基于红黑树。红黑树是一种平衡查找树，统计性能要优于平衡二叉树。具有良好的最坏情况运行时间，可以在O(log n)时间内做查找、插入和删除，其中n代表树中元素的数目
详细可以看HashMap、Hashtable、HashSet 和 ConcurrentHashMap 的比较
2. JDK1.8中的HashMap
在之前学习时，写过一个Java基础学习——HashMap原理学习，可以帮助理解原理学习
个人理解，举例：
一家超大型购物商场，拥有一百万种不同品牌的商品
假如，当世界上第一家这样规模的大型商场开业时，由于没啥经验，商场的工作人员从仓库取出商品摆放时，从商场门口开始，在仓库拿到啥就开始摆放啥，也不管物品是啥，只要能放得下，就依次摆放。而等到顾客来买东西时，全靠随缘。除非打5折，否则一年也卖不出多少东西
现实这种情况根本不会发生，为了方便顾客快速定位商品的相对准确位置，会 根据商品的固有属性来分区
例如，我最爱的农夫山泉，就会放在一个饮品区，和各种纯净水以及其他的喝的，摆在一个相对集中的区域。我到了一家从来没有去过的大型商场去买农夫山泉， 购买效率很大程度取决于我用了多久找到农夫山泉所在的饮品区，到了饮品区，再快速定位到纯净水货架。实际生活中，一般情况下，即使很大型的商场，也可以比较快速的买到一瓶
确定饮水区的过程可以看作为HashMap中涉及hash操作的整个过程
hashMap内存结构图
图来自美团技术点评 Java 8系列之重新认识HashMap
简单说来，HashMap就是将key做hash算法，然后将hash值映射到内存地址，之后可以直接获取key所对应的数据
HashMap就可以简单看作这样一家超大型超市，根据不同商品固有属性key，做hash算法后，得到一个index，便得知该商品所处区域，也就是快速计算得到链表数组索引。而一个品牌的商品肯定不止一个，这样做hash算法后，结果index肯定会有冲突，这时就要用到货架链表，将同一个品牌的商品依次摆放在货架上，最终，一个key就和value建立的映射
JDK1.8中，HashMap内部结构是数组(哈希桶)+链表+红黑树
HashMap的高性能需要下面3点：
-
hash()算法必须是高效的 -
hash值映射内存地址，也就是计算数组索引，映射算法必须是高效的 - 根据内存地址，数组索引，可以直接获取得对应的值
最常用到的就是put()，get()方法
Map<String, String> map = new HashMap<>();
map.put("1", "a");
map.put("2", "b");
for (String key : map.keySet()) {
System.out.println("key = " + key + " ;;; value = " + map.get(key));
}
if (map.containsKey("1")) {
map.remove("1");
}
System.out.println("size = " + map.size());
本次重点学习存放put()，扩容resize()
2.1 构造方法
有 4 个 构造方法，最经常使用的是空参的
public HashMap()-
public HashMap(int initialCapacity)，指定容量 -
public HashMap(int initialCapacity, float loadFactor)，指定容量、负载因子 -
public HashMap(Map<? extends K, ? extends V> m)，存放另一个HashMap
/**
* The default initial capacity - MUST be a power of two.
* 默认大小
*
* 使用空参构造方法时，默认初始化大小 16
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The load factor used when none specified in constructor.
* 默认负载因子
*
* 默认情况下的加载因子，可以通过构造方法来改变
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
* 链表数组
*
* 这个table会在 HashMap 第一次使用时被创建，一般会在 put()方法时
*
* table.length 一直都会是 2 的 n 次方，这样设计的目的在于
* 扩容时，更加高效的统计数组的index，用位运算替代取余操作
*/
transient Node<K,V>[] table;
/**
* Constructs an empty HashMap with the default initialcapacity
* (16) and the default load factor (0.75).
*
* 空构造方法：初始化 负载因子(loadFactor)为 0.75
* 此时，默认容量大小为 16，阈值就是 12
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
使用空参构造方法时，指定loadFactor为默认值0.75
负载因子是0 ～ 1之间的浮点数，决定了在扩容之前，HashMap的内部数组链表的填充度
阈值(threshold) = 容量(capacity) * 负载因子(load factor)
当HashMap的实际容量超过阈值时，HashMap便会扩容。因此，实际上HashMap的实际填充率不会超过负载因子
负载因子也可以设置为1或者大于1，但此时会导致大量的hash冲突
负载因子越大，使用越少的内存空间，而一个数组索引位置上的链表长度就越大，一个链表中存放的元素越多，越容易引起hash值冲突。使用get()方法进行获取元素操作，进行遍历链表时的效率也就越低
相反，负载因子越小，一个数组索引位置上的链表，长度越小，一个链表中存放的元素越少，虽然遍历的效率高了，但也就浪费了较多空间
transient，不需要被序列化的属性可以使用。目前不理解，先不管
2.2 Node，键值对单向链表
Node[]table数组中的元素，Node就是存放key，value的对象，结构是单向链表，每个Node都会指向下一个，若没有next就指向null
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // hash 值
final K key;
V value;
Node<K,V> next; // 下一个键值对
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
// 将key 和 value的hash值，异或
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
// 设置 Value，并将覆盖的旧value返回
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
// 比较两个Node对象是否相等
// 比较key value是否完全相等
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
2.3 数组索引计算
在1.7中，HashMap内部是数组 + 链表
在1.8中，链表的长度一旦超过8时，就会转为红黑树
// 1.8 增加的变量
static final int TREEIFY_THRESHOLD = 8;
高效确定一个元素key所在链表的索引，需要两步：
- 计算元素
健key的hash值，hash(Object key)方法 - 利用计算得到的
hash，获取数组索引，indexFor(hash(key),table.length)
HashMap的高效性，很关键一部分就在于hash()算法以及indexFor()
当使用put()方法存放一个元素时，首先会根据key计算hash值，之后利用hash值，确定该元素所属链表的索引index。也就说这个两步走，在put()中是必须要走的
JDK1.8中对计算索引两步走又进行了优化,先了解1.7的实现
2.3.1 在JDK1.7中的实现
目前不懂为啥1.7中，这样来设计计算hash值，在知乎看到了也有人问这个问题：
JDK 源码中 HashMap 的 hash 方法原理是什么？
最高票的回答很赞，而且在回答中答主给了自己的学习笔记How is hashCode() calculated in Java?，很有深度
两步走，第一步，计算hash值
final int hash(Object k) {
int h = 0;
//这个特殊选项先不去管它
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
//第一件事：调用Key自带的hashCode()函数获得初始哈希值
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
//初始哈希值做进一步优化（注：^为“异或”操作）
//异或：每一位上的值相同返回0，不同返回1。
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
调用key类型自带的hashCode()函数，计算原始哈希值
在最后计算hash值时，用了4次^运算，1.8中做的优化便是由4次变做了1次
又看到了这篇：HashMap hash方法分析
看懂似懂非懂的
这里原理为啥这么写的，先不管了，先记结论
结论:
无论1.X的JDK，这个hash()方法的优化目的都是为了防止Object key自身的hashCode()方法实现比较差，为了使hash值更加均衡，减少hash冲突
两步走，第二步，计算索引值
indexFor()的目的是为计算index，在买农夫山泉的例子中，就是快速定位饮品区，然后可以快速找到农夫山泉货架这个步骤
实际生活中，超市不会一个货架只摆放一瓶农夫山泉。在元素多时，HashMap也不会一个链表只存放一个元素
HashMap的最大容量是Integer.MAX_VALUE，但table.length一定不会是这么大。若一个元素占用一个链表，那需要一个容量为2 ^ 31 - 1的数组，这样虽然index不会存在冲突，但空间上是不允许的
计算这样一个index首先想到的便是除法散列法
// 求模数实际是通过一个除法运算得到
h % length
在JDK1.7中，计算链表所处的数组索引index用的是h & (length-1)
用的是&而不是%
这便是代码设计者牛B的地方
// 1.8 中已删除，
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 :
// "length must be a non-zero power of 2";
return h & (length-1);
}
HashMap中链表的length总是2的n次方，length总是2的n次方时，h & (length-1)运算等价于对length取模，也就是h%length，但&具有更高的效率
这也是为啥要将table.lenth设计为总是2的n次方原因
2的n次方，必然是偶数，length -1 为奇数，转换成二进制之后，最后一位为1
当h & (length-1)时，最后一位的是0还是1，就取决于h的值，也就是说index的奇偶性取决于h
假如length不一定是2的n次方，当length为奇数时，length-1转换成二进制后，最后一位是0，这样无论h为多少，h & (length-1)时，最后一位的都是0，这样index都是偶数，数组只有偶数索引处有值，也就造成了空间浪费
结论：
h & (length-1)既高效又能使index分布均匀
2.3.2 1.8中的实现
在1.8代码中，indexFor(int h, int length)删除了，在确定index值时，简化成了tab[i = (n - 1) & hash]，其中hash便是hash(Object key)方法计算的值，使用的原理和indexFor()还是一样的，只是减少了一次方法调用
1.8中获取索引index
/**
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
只进行了一次^运算，h值自身的高16位 和 低16位进行^运算
混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来
这也弥补了取余时只有低位参与运算，而导致hash冲突变多的情况
这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销
HashMap哈希算法例图.png
图来自美团技术点评 Java 8系列之重新认识HashMap
看到有人说(h = key.hashCode()) ^ (h >>> 16)这一步处理，是扰动函数，目的就是为了是使hash值分布更均匀，之后再计算index也能减少冲突
2.4 put放入
put()
在put()方法内，调用了putVal()方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
当key已经存在的情况下，会将旧的value替换，并返回旧的value
putVal()
- 判断
HashMap内的链表数组table是否已经创建过，也就是判断是否为初始化状态 - 确定
index，判断数组index位置上是否有链表，没有就创建，有就准备遍历 - 判断链表上第一元素键值对是否和要存入的目标键值对相等;相等就直接进行覆盖操作
- 判断链表是否已转为红黑树
- 遍历链表，过程中确定是否进行转换红黑树操作，以及根据目标键值对确定是加到链表尾部还是覆盖操作
-
put目标键值对成功，++size，判断是否需要扩容，并返回null
/**
* onlyIfAbsent，为true时，不改变已经存在的value
* evict，为false时，说明是在初始化状态中调用
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// tab，临时链表数组 ; p ，节点，临时键值对
// n，临时数组长度； i， index
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 步骤1: table为null或者 lenght等于 0 ，说明需要初始化，先扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 步骤2: 确定index，index上链表为null，就创建链表
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// index上链表不为 null，就说明index冲突，链表已存在
// 之后开始准备遍历链表，此时的p，是链表的头，链表上的第一个元素
else {
Node<K,V> e; K k;
// 步骤3：将要存入的对象键值对，与p进行比较
// 若相等，就说明需要将value进行覆盖，直接进行覆盖操作
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 步骤4: p是否已转为红黑树
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 此时，还为链表
else {
// 步骤5: 遍历链表
for (int binCount = 0; ; ++binCount) {
// 在尾部节点添加要存入的目标键值对
// 当链表内元素个数为8时，就将链表转换为红黑树，并结束
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 存在覆盖节点，结束循环，进行覆盖操作
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 此时，p.next 不为 null，没有到链表尾部，并且覆盖节点不存在
// 将e赋给p，进行下一轮
p = e;
}
}
// 覆盖操作
// e不 null， 说明上面有覆盖节点，进行了 e = p 操作
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// HashMap子类LinkedHashMap需要重写的方法
afterNodeAccess(e);
return oldValue;
}
}
// 步骤6
// 此时，已经成功存入目标键值对，之后主要就是判断是否需要扩容
// 记录HashMap结构被改变次数
++modCount;
// 判断是非需要进行扩容
// size 先加 1
if (++size > threshold)
resize();
// HashMap子类LinkedHashMap需要重写的方法
afterNodeInsertion(evict);
// 返回 null
return null;
}
afterNodeAccess(e)和afterNodeInsertion(evict)这两个方法先不用管，是为LinkedHashMap准备的
modCount这个值是用来记录HashMap内结构被改变的次数
HashMap不是线程安全的，在使用iterator进行迭代时，通过这个值来判断，如果修改了HashMap结构，便会抛出异常
整个put()方法流程：
hashMap put方法执行流程图
图来美团点评技术团队 Java 8系列之重新认识HashMap
2.5 扩容
当HashMap容量到达阈值时，再进行put操作就会进行扩容操作
扩容是1.8代码改动比较大的地方，但原理是不变的。1.7更好理解，先看1.7中的实现
2.5.1 1.7版本
每次扩容操作都是2倍
resize()
void resize(int newCapacity) {
// 将table赋给临时的oldTable
Entry[] oldTable = table;
// 判断当前oldTable.length是否为 1 >> 30
// 是，就直接将阈值设置为最大容量
// 之后便不会再进行扩容
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 创建一个大小为newCapacity 的 Entry数组
Entry[] newTable = new Entry[newCapacity];
// 将 oldTable 数据装进 newTable
transfer(newTable);
// 将新的数组赋给table
table = newTable;
// 修改为新的阈值
threshold = (int)(newCapacity * loadFactor);
}
transfer()
将数组链表中的元素装进新的扩容后的链表数组
需要考虑的是，容量变大后，如何进行稀释元素
void transfer(Entry[] newTable) {
// 临时 Entry 数组
Entry[] src = table;
// 新的容量
int newCapacity = newTable.length;
// 遍历数组
for (int j = 0; j < src.length; j++) {
// 当前index上的链表
Entry<K,V> e = src[j];
// 当前index上有元素
if (e != null) {
// 释放旧Entry数组的对象引用
src[j] = null;
// 遍历链表
do {
// 临时 next 键值对
Entry<K,V> next = e.next;
// 计算 e 新的index
int i = indexFor(e.hash, newCapacity);
// 进行标记，将e.next指向链表头
// 这里是单链表的头插法
// 新元素放在链表头，旧元素放链表尾部
e.next = newTable[i];
// 将键值对e 放在链表数组 i 位置上的链表头位置
newTable[i] = e;
// 进行下一轮
e = next;
} while (e != null);
}
}
}
1.7的版本，遍历链表，根据链表元素的key重新计算index，之后采用单链表的头插法进行扩容后的链表填充操作
在进行transfer操作时，对于一个e键值对对象来说，e.next指向的是newTable[i]，i位置上链表的头
此时分2种情况，其实是一回事，感觉说2种情况更容易理解
当newTable[i] == null时，也就是此index上的链表第一次放入键值对元素，此时，e.next就是为null了，e就作为此链表的尾部了，在单链表中，尾部节点的next为null
当newTable[i] != null，说明index发生了冲突，也就是此index上的链表已经存在元素了，e.next指向了newTable[i]，也就是指向了上次放入的键值对元素，之后newTable[i] = e
下面举个例子说明下扩容过程。假设了我们的hash算法就是简单的用key进行mod 一下表的大小，也就是数组的长度。其中哈希桶数组table[]的size=2， 所以key = 3、7、5，put顺序依次为 5、7、3。在mod 2以后都冲突在table[1]这里了。这里假设负载因子loadFactor=1，即当键值对的实际大小size 大于table的实际大小时进行扩容。接下来的三个步骤是哈希桶数组 resize成4，然后所有的Node重新rehash的过程
jdk1.7扩容例图
例子来美团点评技术团队 Java 8系列之重新认识HashMap
2.5.2 1.8版本
1.8的版本在稀释操作时，做了优化
HashMap的初始化容量为16，扩容是在之前的容量基础上的2倍，最终一定还是2的n次方
扩容后，元素的位置有两种情况：原来的位置；原位置2次幂的位置
HashMap 1.8 哈希算法例图1
n为table.length，图a表示扩容前的key1和key2两种key确定索引位置的示例，图b表示扩容后key1和key2两种key确定索引位置的示例
其中hash1是key1对应的哈希与高位运算结果
元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：
HashMap 1.8 哈希算法例图2
1.8中，并不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成原索引+oldCap
jdk1.8 HashMap扩容例图
这样既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket
在1.7中，扩容时，往新链表插入数据时，使用的是头插法，在产生hash冲突时，同一个index的元素，在新链表中会倒置。而1.8中，不会
摘抄自美团点评技术团队 Java 8系列之重新认识HashMap
- 初始化
newCap，newThr，并确定resize()是初始化还是元素存放数到达了阈值 - 开始遍历链表数组，判断
index处是否有链表 - 遍历每个链表
- 判断链表内是不是只有一个键值对
- 判断链表是否转位了红黑树
- 进行键值对
稀释操作，根据e.hash & oldCap，确定下标是低位还是高位
final Node<K,V>[] resize() {
// 临时oldTab数组
Node<K,V>[] oldTab = table;
// 旧的容量，初始化阶段,在HashMap没有放入键值对时为0
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 旧的阈值
int oldThr = threshold;
// 初始化新的容量，新的阈值
int newCap, newThr = 0;
// 步骤1
// 旧的容量大于0
if (oldCap > 0) {
// 判断是否已经到了上限，无需再扩容的容量
// 若到了，就将阈值直接设置为最大容量
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 新的容量大于默认大小16，乘2后小于容量上限
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 阈值 2 倍
newThr = oldThr << 1;
}
// 此时容量oldCap = 0，链表数组table为null， 阈值大于0
// 说明，是使用了`new HashMap(cap，thr)`，指定了容量和阈值
else if (oldThr > 0)
// 将阈值设置为旧的阈值
newCap = oldThr;
// oldCap == 0 ， oldThr == 0，table为null，阈值也为0
// 说明是使用了`new HashMap()`
else {
// 将新的容量设置为默认大小16
newCap = DEFAULT_INITIAL_CAPACITY;
// 默认阈值
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 此时对应的是`new HashMap(cap，thr)`，指定了容量和阈值这种情况
if (newThr == 0) {
// 计算阈值
float ft = (float)newCap * loadFactor;
// 设置新的阈值
newThr = (newCap < MAXIMUM_CAPACITY
&&
ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);
}
// 将获取的newThr赋给threshold，也就是更新HashMap的阈值
threshold = newThr;
// 建立临时链表数组
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// 将新的链表数组引用指向table
table = newTab;
// 当oldTab不为null时，之前有存放过键值对
// 遍历
if (oldTab != null) {
// 步骤2
// 先遍历链表数组
for (int j = 0; j < oldCap; ++j) {
// 临时键值对
Node<K,V> e;
// 步骤3
// 若在 j 位置上，有链表
if ((e = oldTab[j]) != null) {
// 将 j 位置的链表引用释放
oldTab[j] = null;
// 步骤4
// e.next 为 null
// 链表内只有一个键值对
if (e.next == null)
// 根据新的容量进行 & 运算来计算 index
// 将 e 放在新计算的index位置
newTab[e.hash & (newCap - 1)] = e;
// 步骤5
// e 是否为 红黑树
// 此时，说明hash冲突，链表上有超过个键值对，转换成了红黑树
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 链表上有键值对，但还没超过8个
// 利用hash值来计算扩容后键值对所出链表的位置
// 1.8 的优化点：省去了一次重新计算index的过程
else {
// 步骤6
// 对于此时的 e 来说，扩容后，有两种情况：
// 放在原链表的原下标处，也就是低位，low位
// 放在扩容后的新下标处，也就是高位，high位
// high 位= low位 + 原哈希桶容量
// 低位链表的头结点、尾节点
Node<K,V> loHead = null, loTail = null;
// 高位链表的头结点、尾节点
Node<K,V> hiHead = null, hiTail = null;
// e.next 临时节点
Node<K,V> next;
do {
// 临时节点赋值
next = e.next;
// e.hash & oldCap 计算 mask 范围
// 结果可以分为: 等于0 大于0
// 等于0，位于原链表原下标位置
// 大于0，位于扩容后新链表high位
if ((e.hash & oldCap) == 0) {
// 尾节点为 null ，说明链表之前没有存放过键值对
if (loTail == null)
// 赋值头节点
loHead = e;
else
// 尾节点next 指为 e
// 尾节点的next 暂时为自身
loTail.next = e;
// 将e引用赋给尾节点
// 第一个元素插入时，由于只有一个节点
// 既是头节点又是尾节点
loTail = e;
}
// 高位同上
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 低位节点存在
if (loTail != null) {
// 将尾节点 next 置 null
loTail.next = null;
// 低位放在原index处
newTab[j] = loHead;
}
// 高位同上
if (hiTail != null) {
hiTail.next = null;
// 高位放在原 index+oldCap 处
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
关于e.hash & oldCap
在知乎看到了解释：
jdk1.8 HashMap put时确定元素位置的方法与扩容拷贝元素确定位置的方式冲突？
e.hash & oldCap
摘自上面的知乎链接
2.6 get()获取
get()方法也是高频使用的方法
public V get(Object key) {
Node<K,V> e;
// 先根据 key 计算 hash 值
// 若不存在，就返回 null
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
getNode()
- 根据
hash和key快速定位目标所在链表 - 判断头节点是否为获取目标。是，直接返回目标
- 查看链表中是否还有其他节点；没有直接返回
null - 判断链表是否转为
红黑树；是，就进行遍历红黑树查找操作 - 遍历链表，查找目标；找打就返回目标，否则直接返回
null - 此时，说明
HashMap内没有查找的目标，返回null
final Node<K,V> getNode(int hash, Object key) {
// 链表数组
Node<K,V>[] tab;
// 头节点
Node<K,V> first, e;
// table.length
int n;
// 临时健key
K k;
// 步骤1: 链表数组不为 null 并且能找打目标链表
// 关键点在于 tab[(n - 1) & hash])，找到链表，确定头节点
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 步骤2 ：判断头节点是否就是查找的目标
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 步骤3: 链表中还有其他节点
// 说明此时头节点不是获取目标
if ((e = first.next) != null) {
// 步骤4 ： 是否为红黑树
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 步骤5 ： 链表没有被转为红黑树
// 遍历链表
do {
// 判断是否为目标
if (e.hash == hash &&((k = e.key) == key
|| (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
// 步骤6 ： 返回 null
return null;
}
获取方法的流程倒是比put()简单，关键点在于确定有效的头节点
3. 最后
红黑树不会，以后单独进行学习，不过目前不影响HashMap整体的流程学习
引用较多，侵删
有错误，请指出
共勉 : ）
网友评论