• else

遍里链表p，且结果赋值给e; 也可分为3 中情况
1). if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) 当链表中有Node 的key 与参数key 相同时，结束遍历。
2). if ((e = p.next) == null) 链表遍历完时
将需要保存的内容 添加到链表末尾。如果链表长度小于8，结束遍历
3). 链表遍历完,且添加新增内容。链表长度大于等于8 时。
执行 treeifyBin(tab, hash) 函数，然后结束遍历。

static final int MIN_TREEIFY_CAPACITY = 64;
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();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}

treeifyBin(tab, hash) 函数的逻辑是当tab 长度小于64 时就执行resize() 扩容，否则将链表转为红黑树

3. 我们会过来看注释4 处代码

if (e != null) { //当参数key 在tab 中有映射时
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}

onlyIfAbsent 为true 时不修改现有值
当参数key 在tab 中有映射时，根据条件覆盖现有值，并返回旧值。

int hash(Object key) 函数

static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

1. ^ 如果相对应位值相同，则结果为0，否则为1，＆ 如果相对应位都是1，则结果为1，否则为0

a = 1010
b = 0011

a ^ b = 1001
a & b = 0010

2. (h = key.hashCode()) ^ (h >>> 16) 这个方法最重要的一句代码。为什么要做 ^ (h >>> 16)这个操作呢？

是因为在putVal 函数中，是这样是使用的 tab[index = (n - 1) & hash],n 是表的长度，表的长度永远都是2的幂次方，那么n-1的高位应该全是0，做 & 操作时会导致hash 的高位无法参与运算，从而会带来哈希冲突的风险。所以在计算key的哈希值的时候，做(h = key.hashCode()) ^ (h >>> 16)操作。这也就让高位参与到tab[index = (n - 1) & hash]的计算中来了，即降低了哈希冲突的风险又不会带来太大的性能问题。

resize() 函数

final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {//table中已经有数据
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// newCap = oldCap * 2
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; //newThr = oldThr * 2
}
else if (oldThr > 0) //初始化是设置了容量和阈值 使用非空构造函数初始化
//回顾一下构造函数中 threshold = tableSizeFor(initialCapacity) 值为2的幂次方
//原来这个值其实是给newCap 所以需要为2的幂次方
// initial capacity was placed in threshold
newCap = oldThr;
else { //初始化是没有设置容量和阈值， 使用的是空的构造函数初始化 zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {// 上面判断进入 (oldThr > 0) 的情况,没有给newThr 赋值，
// 所以在这里给newThr 赋值
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@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) {//注释5
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;//注释6
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;//注释7
}
}
}
}
}
return newTab;
}

resize() 函数可以分为两个部分

• 设置 newCap、newThr。分析已经写在了代码中，逻辑就是：没有初始化的情况初始化、已经有值的乘以2
• 创建newTab 并重新赋值。这里我们重点解释一下 if ((e.hash & oldCap) == 0)注释5 处的代码。

1. 首先我们知道 tab[index = (n - 1) & hash]，假设oldCap = 16 时

oldCap-1 = … 0000 1111
hash1 = … 0000 0101 -> index1 = 0000 0101 = 5
hash2 = … 0001 0101 -> index2 = 0000 0101 = 5

2. 此时需要扩容 newCap = oldCap*2 = 32

newCap-1 = … 0001 1111
hash1 = … 0000 0101 -> index1 = 0000 0101 = 5
hash2 = … 0001 0101 -> index2 = 0001 0101 = 5 + 16(oldCap)

3. 从以上两步可以看出，在扩容的时候并不是所有index 都会改变的。而改变的关键就是在 hash 值在 oldCap 的位上是否为0。if ((e.hash & oldCap) == 0)注释5 处的代码就类似于一下列子。作用就是判断是否需要位移。

oldCap = … 0001 0000
hash1 = … 0000 0101 -> 0
hash2 = … 0001 0101 -> 1

4. 这也解释了注释6、注释7处的代码

小结

这章我们主要涉及到3个函数

• putVal(…)
  该函数负责数据插入，当size 超过扩容阈值时调用resize()函数扩容，当添加数据的链表长度大于等于8 时将链表转为红黑树。
• hash(Object key)
  在计算key的哈希值的时候，用其自身hashcode值与其低16位做异或操作。这也就让高位参与到index的计算中来了，即降低了哈希冲突的风险又不会带来太大的性能问题。
• resize()
  重新设置table 的容量和扩容阈值，并新建table 把oldTable 的值填充进去。

自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数初中级安卓工程师，想要提升技能，往往是自己摸索成长，但自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年最新Android移动开发全套学习资料》送给大家，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。

由于文件比较大，这里只是将部分目录截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频
如果你觉得这些内容对你有帮助，可以添加下面V无偿领取！（备注Android）

总结

我最近从朋友那里收集到了2020-2021BAT 面试真题解析，内容很多也很系统，包含了很多内容：Android 基础、Java 基础、Android 源码相关分析、常见的一些原理性问题等等，可以很好地帮助大家深刻理解Android相关知识点的原理以及面试相关知识。

这份资料把大厂面试中常被问到的技术点整理成了PDF，包知识脉络 + 诸多细节；还有 高级架构技术进阶脑图 帮助大家学习提升进阶，也节省大家在网上搜索资料的时间来学习，也可以分享给身边好友一起学习。

这里也分享给广大面试同胞们，希望每位程序猿们都能面试成功~

领取方式：点击直达GitHub

Android 基础知识点

Java 基础知识点

Android 源码相关分析

常见的一些原理性问题

腾讯、字节跳动、阿里、百度等BAT大厂 2019-2020面试真题解析

g-x7W8bND2-1711185669028)]

Android 源码相关分析

[外链图片转存中…(img-jgNgnTI9-1711185669028)]

常见的一些原理性问题

[外链图片转存中…(img-m3KuX20x-1711185669028)]

腾讯、字节跳动、阿里、百度等BAT大厂 2019-2020面试真题解析

[外链图片转存中…(img-y8jjem8d-1711185669029)]