Java基础

Day1：Java 集合

目标：

Collection
├── ArrayList
├── LinkedList
└── HashMap

1. 为什么 ArrayList 查询快，而 LinkedList 查询慢？

ArrayList 底层是连续内存空间，可以通过数组下标直接计算出元素地址，因此随机访问时间复杂度是 O(1)。LinkedList 底层是双向链表，每个节点只知道前后节点的位置，因此访问第 n 个元素需要从头或尾开始遍历，时间复杂度是 O(n)。

2. 为什么 LinkedList 插入快，但项目中却很少使用？

实际场景中基本都是查询和遍历，例如分页查询，获取数组中第几个元素什么的。链表虽然插入和删除快，但是也要先查找遍历到指定元素才可以。而且从中间插入的需求实际业务中很少遇到。我基本没有用过linkedList

2.1 那 LinkedList 真有比 ArrayList 快的时候吗？

有。
如果已经拿到了链表节点，例如 ListIterator 已经定位到了当前位置，或者频繁在队列头尾插入删除，那么 LinkedList 确实比 ArrayList 更合适。
但普通业务开发很少直接操作链表节点，所以实际项目中使用率很低。

3. ArrayList 为什么要自动扩容，而不是固定长度？

如果没有动态数组，就需要自己 System.arraycopy。
并且数组是 Java 语言的基础类型。
Java 希望：

数组：

简单
高效
固定长度

ArrayList：

自动扩容。

所以

数组：

负责性能。

ArrayList：

负责易用。

4. HashMap 为什么比遍历 List 查找快？

假设有100万人。现在找张三。
第一种：一个一个找O(n)
第二种：按姓氏放。张一个桶。李一个桶。王一个桶。

是不是快很多？

这就是：

Hash。

它本质就是：

通过计算规则，把数据快速定位到某个桶（Bucket）。

所以 HashMap 的第一层不是链表，而是：

Bucket[]

一个桶数组。

4.1 为什么 HashMap 不是按姓氏分组？

姓氏只是举例。
实际 HashMap 是调用 key 的 hashCode()，经过扰动函数计算，再通过 (n - 1) & hash 定位到桶，而不是按照某种业务规则分组。

5. 为什么 HashMap 不直接把冲突元素都放在链表里，而是后来又引入了红黑树？

链表查找只能一个一个遍历，太慢了。红黑树的查找效率为o(log2n)。
红黑树不是查找最快的树，但它在查找、插入、删除三者之间取得了最好的平衡，因此 Java 选择了红黑树。

6. ArrayList 为什么扩容 1.5 倍？

扩容太小会导致频繁复制数组，扩容太大会浪费内存，因此 JDK 采用 1.5 倍作为空间利用率和扩容成本之间的折中。

7. ArrayList 为什么线程不安全？

例如：

1	list.add(a)

两个线程：

同时：

add。

可能：

size = 10

线程A
↓
准备放10

线程B
↓
准备放10

↓

覆盖
↓
size++
↓

数据丢了

Day2：HashMap

目标：

HashMap
├── 一、为什么要有 hashCode()
├── 二、equals() 和 hashCode() 为什么必须一起重写
├── 三、ConcurrentHashMap 为什么线程安全
└── 四、Iterator 和 fail-fast

1. 为什么 HashMap 查找时不能只用 equals()？为什么还需要 hashCode()？

hashcode可以快速定位到hash表的某个桶，算法类似于取余（实际上是位运算）。定位到桶后再用equals确定具体的元素。
如果直接用equals，因为 equals 是 O(n)，需要遍历整个集合。而 hashCode 可以通过哈希算法快速定位到某个 Bucket，把查找范围缩小到一个桶内，然后再调用 equals 比较，大部分情况下查找复杂度接近 O(1)。

2. 为什么重写了 equals()，就必须重写 hashCode()？如果不重写会发生什么？

因为hashmap是通过hashcode定位桶的，如果要保证hashmap正常工作，必须保证equals相同的话，hashcode也必须相同。

2.1 那 hashCode 相同，equals 一定相同吗？

不是。

例如：

1 2	"Aa".hashCode() "BB".hashCode()

hash一样。但是equals为false。并且hash也有可能冲突。

3. HashMap 和 ConcurrentHashMap 最大的区别是什么？

HashMap 本身没有任何同步机制，多线程同时 put 或扩容可能导致数据覆盖、数据丢失等问题。ConcurrentHashMap 在 JDK8 中结合 CAS 和 synchronized 实现线程安全，并且采用更细粒度的同步策略，而不是对整个 Map 加锁，因此既保证了线程安全，又具有较好的并发性能。

4. 为什么 ConcurrentHashMap 的性能通常比给整个 HashMap 加一把大锁更高？

因为ConcurrentHashMap是分桶加锁的，操作A桶的时候，没有必要把B桶加锁。
锁粒度越小，并发越高。

5. 为什么增强 for 循环里直接 remove() 会抛 ConcurrentModificationException？

因为Iterator里面有一个expectedModCount，当进行遍历的时候，expectedModCount一直在和list的modCount进行比较。
遍历过程中集合结构发生变化，Iterator 无法保证遍历结果正确，因此直接失败。

6. 为什么使用 Iterator.remove() 就不会抛这个异常？

因为Iterator内部会进行维护expectedModCount。

7. HashMap容量都是16 32 64 128 （跟(n-1)&hash有关）

容量必须是 2 的幂，位运算才能均匀分布到每一个桶。

8. 为什么HashMap扩容都是2倍？

扩容迁移的时候很方便。只需要看扩容新增的那个高位是1还是0，0的话不用动，1的话移动到原索引 + 旧容量的位置，不用重新计算hash

9. HashMap 为什么允许 null Key

HashMap规定了null.hashCode()=0。
ConcurrentHashMap不允许是因为会产生歧义，不知道是因为key不存在还是value为null。Hashmap也有这个问题，但是可以用containsKey。
ConcurrentHashMap value也不允许null，是为了降低实现的复杂度。ConcurrentHashMap 作为高并发容器，希望 API 尽量简单、一致，不提供 HashMap 中对 null 的特殊支持。