Java集合框架个人疑点（持续更新

1.modCount 是什么？

在ArrayList、linkedList、HashMap等容器中继承自父类的属性，可以记录修改次数

做什么

在数据结构对应迭代器中使用，保证线程安全。

配套有Fail-Fast机制，如果使用迭代器过程中有其他线程修改了map，通过modCount对照发现不一致，直接抛出ConcurrentModificationException，

2.ArrayList扩容1.5倍 是什么？

在ArrayList的grow方法执行具体的扩容操作时，将newCapacity设置为oldCapacity + （oldCapacity >> 1），也就是扩容1.5倍

（初始容量是10

为什么？

充分利用空间，且不会频繁进行扩容操作移位操作可以减少浮点数，降低运算时间和运算次数

3.ArrayDeque优于linkedList 是什么？

linkedList同时实现List和Deque接口，底层通过双向链表实现，可以用作栈和队列甚至列表ArrayDeuqe实现Deque接口，底层通过循环数组实现，是Java推荐用来实现栈和队列的数据结构

为什么？

数组存储更加节省空间数组的随机访问性质优于链表添加或删除头尾元素时，循环数组不会影响其他数组元素，时间复杂度还是O(1)，链表只有在迭代期间删除当前元素时会更快

4.hash(k)&(table.length - 1) 是什么？

在HashMap的getEntry方法中，得到冲突链表的语句是Entry e = table[hash&(table.length-1)];它等价于hash(k)%table.length

为什么？

HashMap要求table.length是2的指数倍，table.length-1所得的数二进制低位全是1，与hash(k)相与时，会将哈希值的高位抹掉，得到余数

5.HashMap加载因子0.75 是什么？

加载因子=size/capacity，用来衡量HashMap目前的装载程度。当哈希表中条目数超出了加载因子与当前容量乘积时需要扩容，*2

为什么？

根据泊松分布，是提高空间利用率和减少查询成本的折中

6.红黑树 基础概念

是对2-3-4树，一种阶数为4的B树的一种实现使用红节点+黑节点的方式表示原B树中节点元素数量＞1的节点，只有一个元素的节点是黑色节点大体特征如下：

每个节点要么是红色，要么是黑色根节点必须是黑色红色节点不能连续（即红色节点的孩子和父亲都不能是红色对于每个节点，从该点至null（树尾端）的任何路径，都含有相同个数的黑色节点

核心操作

查找树的结构发生变化时，红黑树的约束条件可能被破坏，需要通过调整使得查找树重新满足红黑树的约束条件。调整可以分为两类：一类是颜色调整，即改变某个节点的颜色；另一类是结构调整，即改变检索树的结构关系。包含两个基本操作：左旋(Rotate Left)，右旋(Rotate Right)

左旋：将x的右子树绕x逆时针旋转，使得x的右子树成为x的父亲，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-glktMkJ6-1647309875056)(Java集合框架个人疑点.assets/TreeMap_rotateLeft.png)]

右旋：将x的左子树绕x顺时针旋转，使得x的左子树成为x的父亲，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-X4Qp1A9H-1647309875058)(Java集合框架个人疑点.assets/TreeMap_rotateRight.png)]

以TreeMap作承载看红黑树的调整过程

以插入操作为例，删除操作同理

首先插入节点应该为红色，这样默认满足规则4。接下来考虑与规则3可能案发生的冲突：即当前节点与父亲节点都为红色。这个时候的具体操作分三种情况考虑。这里设冲突节点中，当前节点为Node，父节点为pNode，祖父节点为ppNode，叔父节点为yNode

当Node与pNode和pNode与ppNode的关系一致（比如都为左孩子或都为右孩子），且yNode为红色时，进行颜色调整。将pNode和yNode的颜色换为黑色，ppNode的颜色换为红色当Node与pNode和pNode与ppNode的关系不一致（比如不都为左孩子），且yNode为红色时，进行结构调整。如果Node为右孩子就左旋，Node为左孩子就右旋当Node与pNode和pNode与ppNode的关系不一致（比如不都为左孩子），且yNode为黑色时，需要同时进行结构和颜色调整

7.HashMap实现线程安全 方法

通过collections.synchronizedMap()接口方法**HashTable也是用synchronized关键字保证线程安全**

重写HashMap，通过java.util.Concurrent.ConcurrentHashMap()方法

原理

通过给所有方法都加上synchronized关键字来实现互斥

采用Nonfairsync锁，将HashMap拆分成各个独立的块，减少锁之间的冲突

区别