- JDK8之前，在构造方法中创建长度16的Entry[] table数组
- JDK8之后，在第一次调用put方法时创建数组Node[] table
存储过程
hashMap.put("a",1);
hashMap.put("b",1);
hashMap.put("c",1);
hashMap.put("a",2);
hashMap.put("a",1) 调用String类重写的hashCode方法，结合数组长度 (length – 1) & hashCode 计算出索引
哈希表底层采用何种算法计算的哈希值？还有哪些算法可以计算哈希值？
底层采用key的hashCode值结合数组长度进行无符号右移、按位异或、按位与计算出索引
还可以采用：平方取中法、取余数、伪随机数法
取余数：hashCode % 数组长度 10 % 8 = 2
取余的效率略低，位运算的效率高
- 索引处没有数据，直接存储 a = 1 b = 1
- 索引处有数据，底层会比较哈希值是否一致，如果不一致就创建一个节点存储该元素，这种方式称为拉链法
- 存储a=2时，比较哈希值，a的哈希值等于a，发生哈希碰撞；调用该类equals方法比较key是否相等
- 相等：覆盖之前的value，并返回该value
- 不相等：继续向下比较，如果都不相等就拉链法存储该数据
如果链表长度大于阈值8并且数组长度大于64则将链表转化为红黑树
面试题：
-
何时发生哈希碰撞？什么是哈希碰撞？如何解决哈希碰撞？
如果key计算出的哈希值相同就是hash碰撞，JDK8之前使用链表解决，JDK8之后使用链表 + 红黑树解决 -
如果两个键的hash值相同，如何存储元素？
通过equals方法比较key，如果相同就覆盖，不相同继续存储 -
如何扩容？
在不断添加的过程中就进行扩容，每次扩容数组的容量 * 2，并将原有的元素拷贝到新数组中并重新计算哈希值，效率较低 -
为什么引入红黑树？为何阈值大于8时转化为红黑树？
JDK8之前使用数组 + 链表，即使散列函数取的再好也很难达到数组中的元素百分百均匀分布。当HashMap中大量元素都存放在一个桶中，这个桶里就有一个很长的链表，这时遍历单链表的时间复杂度就是ON，完全失去了HashMap的优势，针对这种情况JDK8引入了红黑树（查找的复杂度为logn）解决这个问题。当链表长度很小时，即使遍历速度也很快，但是链表变长一定会对查询的性能有影响，所以才需要转化为树。
至于为何阈值为8，需要在后续查看源码时得到解释。
注意：
- size是HashMap中键值对的数量，不等于数组长度。
- threshold（临界值） = capacity * loadFactor 。这个值是当前数组已占用的长度的最大值。size超过这个临界值就重新resize，扩容之后的容量是之前容量的两倍。
源码
继承结构
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {}
HashMap继承自 AbstractMap<K,V>，实现了Map<K,V> 接口，而AbstractMap<K,V> 本身也实现了Map接口：
public abstract class AbstractMap<K,V> implements Map<K,V> {}
在Java的集合框架中，类似的写法很多，最开始写Java集合框架的时候，Josh Bloch认为这样写可能在某些地方是有价值的，后续发现这是个失误。
HashMap的成员变量
默认初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认初始化容量16，必须是2的整数幂
为什么这样能减少哈希碰撞？
计算哈希桶索引的时候，实际上使用的是hash & (length - 1) ，因为位运算的效率是比取余高的。
2的n次方实际上就是1后面加上n个0，2的n次方 – 1实际上就是n个1
- 如果数组长度是2的n次幂
长度为8时，假设hash值为3
3 & (8 - 1)
0000 0011 3
0000 1111 7
----------
0000 0011 index = 3
长度为8时，假设hash值为2
0000 0010 2
0000 0111 7
---------
0000 0010 index = 2
- 如果数组长度不是2的n次幂
长度为9时，假设hash值为3
3 & (9 - 1)
0000 0011 3
0000 1000 8
----------
0000 0000 index = 0
长度为9时，假设hash值为2
0000 0010 2
0000 1000 7
---------
0000 0000 index = 0
总结：如果数组长度不是2的n次幂，不同hash计算出的索引很可能冲突，设置为2的n次幂实际上是将索引的变化都交给hashCode来决定
注意：如果不考虑效率问题，使用取余的话，就不必设置为2的n次幂了
- 如果创建集合时指定默认初始化容量为10
会找离这个数最近的最大2整数次幂
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;
this.threshold = tableSizeFor(initialCapacity);
}
static final int tableSizeFor(int cap) {
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
public static int numberOfLeadingZeros(int i) {
// HD, Count leading 0's
if (i <= 0)
return i == 0 ? 32 : 0;
int n = 31;
if (i >= 1 << 16) { n -= 16; i >>>= 16; }
if (i >= 1 << 8) { n -= 8; i >>>= 8; }
if (i >= 1 << 4) { n -= 4; i >>>= 4; }
if (i >= 1 << 2) { n -= 2; i >>>= 2; }
return n - (i >>> 1);
}
cap – 1是为了防止指定初始化容量为2的整数次幂时经过计算出现错误
分析numberOfLeadingZeros方法：
public static int numberOfLeadingZeros(int i) {
// HD, Count leading 0's
if (i <= 0)
return i == 0 ? 32 : 0;
int n = 31;
if (i >= 1 << 16) { n -= 16; i >>>= 16; }
if (i >= 1 << 8) { n -= 8; i >>>= 8; }
if (i >= 1 << 4) { n -= 4; i >>>= 4; }
if (i >= 1 << 2) { n -= 2; i >>>= 2; }
return n - (i >>> 1);
}
方法目的：
返回i的最高非零位前面的n个0的个数，包括符号位。（如果i小于0则返回0，等于0则返回32。）
例：10的二进制为：0000 0000 0000 0000 0000 0000 0000 1010
java的int长度为32位，那么这个方法返回的就是28。
解析：
源码中用到了二分法对i进行判断，因为int型长度为32，所以先判断i是不是大于2^16，如果大于则无符号右移16位，继续进行计算。
这样重复4次直到得到n的值。
示例：
2的18次方加上30的值，用二进制表示就是： 0000 0000 0000 0100 0000 0000 0001 1110
首先：
if (i >= 1 << 16) { n -= 16; i >>>= 16; }
判断为true，得到n = 15，i = 4;
然后：
if (i >= 1 << 8) { n -= 8; i >>>= 8; }
不符合判断条件
然后：
if (i >= 1 << 4) { n -= 4; i >>>= 4; }
不符合判断条件
然后：
if (i >= 1 << 2) { n -= 2; i >>>= 2; }
判断为true，得到n = 13， i = 1;
最后相当于13 - 0 = 13
返回13
继续回到调用处：
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;
this.threshold = tableSizeFor(initialCapacity);
}
static final int tableSizeFor(int cap) {
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1); //得到这个数的二进制位前面0的个数
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
-1 进行无符号右移：
11111111 11111111 11111111 11111111 >>> 前面0的个数
假设2的18次方 + 30，前面就有13个0
得到：00000000 00000111 11111111 11111111
原数：00000000 00000100 00000000 00011110
00000000 00000111 11111111 11111111
00000000 00000000 00000000 00000001
----------------------------------------
00000000 00001000 00000000 00000000 2^19
这时进行判断：
static final int tableSizeFor(int cap) {
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
如果n小于0，返回1，代表-1没有进行右移，也就是原数前面没有0。
如果n > 0，判断此时n是否达到最大容量，是就返回最大容量，不是就返回n + 1
总结：求出n前面有多少个0，将-1 >>> 0的个数，得到的结果 + 1就是离这个数最近的最大2的整数次幂。
集合最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
树门限
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
树门限为何是8？
Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they become too small (due to removal or resizing) they are converted back to plain bins. In usages with well-distributed user hashCodes, tree bins are rarely used. Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution
(http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, the expected occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
factorial(k)). The first values are:
因为树的节点大约是普通节点的两倍，所以我们只在桶包含足够的节点时才使用树节点（参见TREEIFY_THRESHOLD）。当树变的太小（由于删除或调整），就被转换为普通的桶。在使用分布良好的用户hashCode时，很少使用树桶。理想情况下，在随机哈希值下，桶中节点的频率服从泊松分布。
(http://en.wikipedia.org/wiki/Poisson_distribution)，默认调整阈值为0.75，平均参数约为0.5，尽管由于调整粒度的差异很大。忽略方差，列表大小k的预期出现次数是(exp(-0.5) * pow(0.5, k) / factorial(k))。第一个值是：
0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
更多的情况：不到千万分之一
如果一开始就变为红黑树，TreeNode占用的空间是普通Node的两倍，所以只有桶中包含足够多的节点时才会转化为TreeNode，足够多的值就是TREEIFY_THRESHOLD决定的，当节点变少时（由UNTREEIFY_THRESHOLD决定）又转化为链表。当我们查看源码时，长度到达8转化为红黑树，长度降为6转化为普通链表。
总的来说，不在一开始就转化为TreeNode，而在达到8转化为TreeNode实际上是对时间和空间的权衡。
当hashCode离散性很好时，转为树的概率非常小，因为数据均匀分布在每个哈希桶中，几乎不会有达到阈值的情况。但是在随机hashCode的情况下，离散性变的很差，但是JDK不能阻止用户实现不好的hash算法，因此就会导致不均匀的数据分布。不过理想情况下使用随机hashCode算法所有哈希桶中节点的分布频率会遵循泊松分布，我们可以看到，链表长度达到8的概率是千万分之六。几乎是不可能的。所以选择8是由概率统计决定的。Java的每一项改动都是严谨和科学的。
其他解释：
红黑树平均查找长度是log(n)，如果长度为8，平均查找长度为3，而链表的平均查找长度为n/2，当长度为8时平均查找长度为4，这时才有转换为树的必要，如果长度小于等于6，log(6) = 2.6，6 / 2 = 3，虽然会快一点，但是转化为树结构和生成树也是要占用时间的。
红黑树的删除需要左右旋/变色，小于6时在红黑树上删除的效率没有链表高。
数组长度>=64?
树化有两个条件必须满足：链表长度达到8和数组长度达到64
static final int MIN_TREEIFY_CAPACITY = 64;
为了避免扩容、树化的冲突，这个值不能小于 4 * (TREEIFY_THRESHOLD = 8)
存放元素的个数
//不是数组长度，是元素个数
transient int size;
记录修改次数
//每次扩容和更改map结构的计数器
transient int modCount;
缓存
transient Set<Map.Entry<K,V>> entrySet;
临界值
int threshold; //实际大小 > 临界值（容量 * 负载因子） 会进行扩容
size >= threshold时，考虑进行resize，这是数组扩容的标准。
但是构造方法中threshold被赋值为tableSizeFor的结果，也就是计算后的数组长度，在put方法中会重新计算threshold
加载因子
final float loadFactor;
说明：
- loadFactor 加载因子，用来衡量HashMap满的程序，表示HashMap的疏密程度，影响hash操作到同一个桶的概率
计算hashMap的实时加载因子：size / capacity，而不是占用桶的数量 / capacity。capacity是桶的数量
loadFactory太大导致查找元素效率低，太小导致数组的利用率低。默认值为0.75f是官方给出的一个比较好的临界值
当HashMap容纳的元素达到数组长度的75%时，表示HashMap太挤了需要扩容，而扩容的操作涉及rehash，拷贝等操作，非常消耗性能，所以实际开发中可以通过创建HashMap集合对象指定初始化容量来避免。
同时在HashMap的构造器中可以指定loadFactory。
2.为什么加载因子设置为0.75，初始化临界值为12？
loadFactory越趋近于1，数组越密集，也会导致链表长度增加
loadFactory趋近于0，数组越稀疏
构造方法
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
double dt = Math.ceil(s / (double)loadFactor); //size / loadFactory = capacity 向上取整
int t = ((dt < (double)MAXIMUM_CAPACITY) ?
(int)dt : MAXIMUM_CAPACITY);
if (t > threshold) //threshold最开始为0
threshold = tableSizeFor(t); //计算边界值，其实此时的边界值就是数组容量
} else {
resize();
}
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
public HashMap(int initialCapacity) {
this(initialCapacity, 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;
this.threshold = tableSizeFor(initialCapacity);
}
大家可能认为此处是bug，应该这样写：
this.threshold = tableSizeFor(initialCapacity) * loadFactory;
这样才符合临界值的含义，但构造方法中并没有初始化table，table的初始化被延迟到了put方法中，在put方法中会重新计算threshold。
根据其他Map创建Map：
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
double dt = Math.ceil(s / (double)loadFactor); //size / loadFactory = capacity 向上取整
int t = ((dt < (double)MAXIMUM_CAPACITY) ?
(int)dt : MAXIMUM_CAPACITY);
if (t > threshold) //threshold最开始为0
threshold = tableSizeFor(t); //计算边界值，其实此时的边界值就是数组容量
} else {
resize();
}
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
s / (double)loadFactor 的操作是，假如当前8 / 0.75 = 10.667 ，向上取整为11，可以在创建后再向其中添加一个元素而不会进行扩容。避免进行扩容。
成员方法
put方法
- 通过hash值计算key的映射下标
- 如果没有元素，直接插入
- 如果有元素
- 没有散列冲突，直接插入
- 有散列冲突
a. 如果该桶使用红黑树处理冲突，调用红黑树的方法插入数据
b. 如果该桶使用链表，使用equals比较key，key相等就覆盖并返回旧值，key不等就使用拉链法
- size > 阈值，resize
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
//键为null，转化为0
}
假设计算出的hashCode值为：1111 1111 1111 1111 1111 0000 1110 1010
1111 1111 1111 1111 1111 0000 1110 1010 h
0000 0000 0000 0000 1111 1111 1111 1111 h >>> 16
------------------------------------------------- ^ 操作
1111 1111 1111 1111 0000 1111 0001 0101 hash
0000 0000 0000 0000 0000 0000 0000 1111 n - 1 (n默认为16)
------------------------------------------------- & 操作
0000 0000 0000 0000 0000 0000 0000 0101 index = 5
以上的操作等同于 hashCode % 数组长度
这个操作的意思是，假如n很小，n = 16，n - 1 = 1111，假如直接与hashCode的值进行按位异或操作，实际上只用了hashCode值的后四位，如果hashCode高位变化大，低位变化小，这样很容易造成散列冲突。这个操作就是把高位的变化和地位的变化都使用了。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0) //第一次put进行扩容
n = (tab = resize()).length; //resize扩容，将table创建并赋值
if ((p = tab[i = (n - 1) & hash]) == null) //计算数组下标。等同于取余，只是取余效率低。
tab[i] = newNode(hash, key, value, null); //如果没有元素，直接存储，并不需要返回值
else { //代表下标位置是有元素的
Node<K,V> e; K k; //e用来key相等的node节点，p是下标位置的元素
if (p.hash == hash && //如果出现hash冲突，并且key相等
((k = p.key) == key || (key != null && key.equals(k))))
e = p; //e记录冲突的节点，表明要覆盖
else if (p instanceof TreeNode) //如果当前桶中是树节点
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { //遍历链表节点
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) { //如果达到末尾
p.next = newNode(hash, key, value, null); //创建新节点挂在链表上
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st //如果到达门限值
treeifyBin(tab, hash); //在该方法中判断是否数组长度>=64
break; //跳出循环
}
if (e.hash == hash && //遍历判断是否出现哈希冲突，e代表当前遍历中的节点
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e; //继续查找下一个节点
}
/*
在循环结束后，e == null，说明挂载最后一个位置，e != null，出现hash冲突
*/
}
if (e != null) { // key相同
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value; //覆盖值
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold) //在resize中计算新的threshold
resize();
afterNodeInsertion(evict);
return null;
}
resize() 扩容
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; //第一次为null
int oldCap = (oldTab == null) ? 0 : oldTab.length; // oldCap = 0
int oldThr = threshold; //0
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // 第一次执行这个else zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY; //默认容量16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //新临界值，临界值在此处计算
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; //12给成员变量
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //创建数组
table = newTab; //局部变量赋值给成员变量
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
treeifyBin 方法：
//替换桶中所有的链接节点，除非表太小，否则将修改大小
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize(); //扩容，说明只要链表长度超过8就会扩容
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null; //hd 头 tl 尾
do {
TreeNode<K,V> p = replacementTreeNode(e, null); //链表头
if (tl == null) //尾节点
hd = p; //新节点给hd
else {
p.prev = tl; //新节点的前指针域指向原先的尾
tl.next = p; //原先的尾节点指向新增加的节点
}
tl = p; //尾节点指向新添加的节点
} while ((e = e.next) != null); //遍历链表
//此时单链表中的节点转化为TreeNode，还是链表。
if ((tab[index] = hd) != null) //将table数组中下标位置的元素替换为TreeNode的链表
hd.treeify(tab);
}
}
进入replacementTreeNode方法：
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) { //p是链表头
return new TreeNode<>(p.hash, p.key, p.value, next);
}
内容相同，变为TreeNode，然后经过treeify方法转变为红黑树，这个方法才是旋转的关键。
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
resize方法
扩容时机
- HashMap中的元素个数超过数组长度 * 负载因子的时候，就会进行数组扩容，loadFactory的默认值(DEFAULT_LOAD_FACTORY)是0.75。扩容非常消耗性能。
- 如果链表中元素个数到达了8个，并且数组长度没有到达64，hashMap会先扩容。如果已经达到了64，链表会转换为红黑树，节点类型由Node变为TreeNode。
进行扩容，会伴随着一次重新的hash分配，并且会遍历hash表中所有的元素，这是非常耗时的。尽量避免resize
HashMap在扩容时，使用到rehash方式非常巧妙，因为每次扩容都是翻倍，与原来计算的(length – 1) & hash的结果相比，只是多了一个bit位。所以节点要么在原来的位置，要么在 原位置 + 旧容量 这个位置
假如从16扩容到32
(n - 1) & hash
数组长度为16
0000 0000 0000 0000 0000 0000 0001 0000 n = 16
0000 0000 0000 0000 0000 0000 0000 1111 n - 1 = 15
1111 1111 1111 1111 0000 1111 0000 0101 hash1
1111 1111 1111 1111 0000 1111 0001 0101 hash2
-------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0101 index1 = 5
0000 0000 0000 0000 0000 0000 0000 0101 index2 = 5
数组长度扩容到32
0000 0000 0000 0000 0000 0000 0010 0000 n = 32
0000 0000 0000 0000 0000 0000 0001 1111 n - 1 = 31
1111 1111 1111 1111 0000 1111 0000 0101 hash1
1111 1111 1111 1111 0000 1111 0001 0101 hash2
---------------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0101 index1 = 5
0000 0000 0000 0000 0000 0000 0001 0101 index2 = 5 + 16
因为扩容之后，(n – 1) & hash 只是多了一个bit位，这个bit位要么是0，要么是1
- 如果为0：还在原来的位置
- 如果为1：位置 = 原位置 + 旧容量（1这一位的权重）
只需要看原来的hash值新值的那个bit位是1还是0就可以了。是0的话索引没有变，是1的话索引变为（原索引 + oldCap），示意图：
这种巧妙的rehash方式，省去了重新计算hash值的时间，而且同时，由于新值的bit位是0还是1可以认为是随机的，在resize的过程中既保证了rehash每个桶的节点数一定 ≤ 原有桶的节点数，保证了rehash之后不会出现更严重的hash冲突。均匀的把之前的冲突的节点分散到了新的桶中。
resize 方法：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length; //16
int oldThr = threshold; //12
int newCap, newThr = 0;
if (oldCap > 0) { //true
if (oldCap >= MAXIMUM_CAPACITY) { //false
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) //newCap = oldCap << 1 扩容 && 16 >=DEFAULT_CAP
newThr = oldThr << 1; // double threshold //阈值变为2倍
}
else if (oldThr > 0) // initial capacity was placed in threshold //上一个if成立不执行
newCap = oldThr;
else { // zero initial threshold signifies using defaults //不执行
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) { //第一个if中确定是24
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; //12变为24
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //创建新的数组
table = newTab; //赋值给成员变量，还没有数据
if (oldTab != null) { //true
for (int j = 0; j < oldCap; ++j) { //遍历旧数组
Node<K,V> e;
if ((e = oldTab[j]) != null) { //数组中的数据交给e，链表头或者null
oldTab[j] = null; //断开数组这个位置的链表，方便GC
if (e.next == null) //链表单个节点
newTab[e.hash & (newCap - 1)] = e; //新长度 - 1 & e的哈希值，实际上就是多的bit位的影响
else if (e instanceof TreeNode) //红黑树
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order //链表
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next; //链表头是e
if ((e.hash & oldCap) == 0) { //判断高位是否为0，是0放在原位置不动
if (loTail == null) //新链表尾为空，说明链表为空
loHead = e; //元素交给链表头
else //新链表尾不空，说明链表不空
loTail.next = e; //挂在尾节点后方
loTail = e; //尾节点指向
}
else { //高位是1，需要移动
if (hiTail == null) //移动的新链表
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) { //保持不变的新链表不为空
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) { //移动的新链表不为空
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
remove方法
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) { //数组存在，长度大于0，该位置不为null
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash && //p是链表头，删除的元素和key值相等，
((k = p.key) == key || (key != null && key.equals(k))))
node = p; //取出链表头p给node
else if ((e = p.next) != null) { //说明链表不只有头
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e; //遍历链表，找到key相等的元素，将该元素赋值给node
break;
}
p = e; //p指向了e的上一个节点
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value || //node存储的不空，key匹配
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p) //相等，说明没有遍历链表
tab[index] = node.next; //直接置null
else //node和链表头不相等，说明遍历了链表，p指向了node（e）的上一个节点
p.next = node.next; //直接解引用断开node的链接。
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
get方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(key)) == null ? null : e.value;
}
final Node<K,V> getNode(Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;
if ((tab = table) != null && (n = tab.length) > 0 && //数组存在，有元素，获取index处的第一个元素
(first = tab[(n - 1) & (hash = hash(key))]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first; //返回的是节点，get返回节点的value
if ((e = first.next) != null) { //需要遍历链表
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
使用建议
指定合适的初始化容量，《阿里巴巴Java开发手册》：
initialCapacity = (需要存储的元素个数 / 加载因子) + 1
如果设置为7，经过JDK转化会变为8。但是在存储到6个元素的时候，8 * 0.75 = 6 立刻进行扩容，这不是我们希望的。
通过上述公式计算得到10，JDK转化为16，这就大大减少了扩容几率。
当HashMap内部维护的哈希表容量达到75%，触发rehash（遍历数组将每个链表转化为loList和hiList再放到相应的位置上），rehash的过程比较耗费时间。
当我们明确知道HashMap中元素的个数时，设置初始化容量在性能上是个很好的选择，只不过会牺牲一些内存。
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。