集合框架
集合体系结构
Java集合框架的层次结构？
答案：
Collection (接口)
├── List (有序、可重复)
│ ├── ArrayList (动态数组)
│ ├── LinkedList (双向链表)
│ └── Vector (线程安全的ArrayList)
├── Set (无序、不可重复)
│ ├── HashSet (基于HashMap)
│ ├── LinkedHashSet (保持插入顺序)
│ └── TreeSet (有序，基于红黑树)
└── Queue (队列)
├── PriorityQueue (优先队列)
└── Deque (双端队列)
Map (接口，键值对)
├── HashMap (哈希表)
├── LinkedHashMap (保持插入顺序)
├── TreeMap (有序，红黑树)
├── Hashtable (线程安全，已过时)
└── ConcurrentHashMap (线程安全)List
ArrayList和LinkedList的区别？
答案：
| 特性 | ArrayList | LinkedList |
|---|---|---|
| 底层结构 | 动态数组 | 双向链表 |
| 随机访问 | O(1) | O(n) |
| 插入/删除(头部) | O(n) | O(1) |
| 插入/删除(尾部) | O(1) | O(1) |
| 内存占用 | 连续内存 | 额外指针开销 |
| 适用场景 | 查询多 | 增删多 |
java
// ArrayList示例
List<String> arrayList = new ArrayList<>();
arrayList.add("A"); // 尾部添加 O(1)
arrayList.get(0); // 随机访问 O(1)
arrayList.add(0, "B"); // 头部插入 O(n)
// LinkedList示例
List<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.addFirst("B"); // 头部插入 O(1)
linkedList.get(0); // 随机访问 O(n)ArrayList的扩容机制？
答案：
- 初始容量：默认10
- 扩容时机：当添加元素时，size超过capacity
- 扩容大小：新容量 = 旧容量 * 1.5
- 扩容过程：创建新数组，复制旧数组元素
java
// 源码简化版
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍
if (newCapacity < minCapacity)
newCapacity = minCapacity;
elementData = Arrays.copyOf(elementData, newCapacity);
}优化建议：
- 如果知道大概容量，使用
new ArrayList<>(initialCapacity)避免多次扩容
Set
HashSet如何保证元素不重复？
答案： HashSet底层基于HashMap实现，元素作为HashMap的key，value是固定的PRESENT对象。
java
// HashSet源码
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT) == null;
}去重原理：
- 计算元素的hashCode()
- 根据hash值定位到数组位置
- 如果位置为空，直接插入
- 如果位置有元素，用equals()比较
- 相同则不插入，不同则链表/红黑树存储
注意：自定义对象需要重写hashCode()和equals()
java
class Person {
String name;
int age;
@Override
public int hashCode() {
return Objects.hash(name, age);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Person person = (Person) o;
return age == person.age && Objects.equals(name, person.name);
}
}Map
HashMap的底层实现原理？
答案：
JDK 1.7：数组 + 链表 JDK 1.8+：数组 + 链表 + 红黑树
核心参数：
- 初始容量：16
- 负载因子：0.75
- 树化阈值：链表长度 > 8 且数组长度 >= 64
put流程：
java
1. 计算key的hash值
2. 根据hash值定位数组下标：(n-1) & hash
3. 如果位置为空，直接插入
4. 如果位置有元素：
- key相同，覆盖value
- key不同，链表/红黑树插入
5. 如果size > threshold，扩容java
// 简化版put实现
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 1. 数组为空，初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 2. 计算下标，位置为空直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// 3. 位置有元素，处理冲突
Node<K,V> e; K k;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p; // key相同
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) // 链表长度>=8
treeifyBin(tab, hash); // 树化
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // key存在，覆盖value
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
return oldValue;
}
}
// 4. 检查是否需要扩容
if (++size > threshold)
resize();
return null;
}HashMap的扩容机制？
答案：
- 扩容时机：size > capacity * loadFactor (默认16 * 0.75 = 12)
- 扩容大小：容量翻倍
- rehash：重新计算每个元素的位置
java
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int newCap = oldCap << 1; // 容量翻倍
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// rehash
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 {
// 链表/红黑树的rehash
}
}
}
return newTab;
}为什么负载因子是0.75？
- 时间和空间的权衡
- 太小：浪费空间，频繁扩容
- 太大：冲突增多，性能下降
HashMap为什么线程不安全？
答案：
- JDK 1.7：扩容时可能形成环形链表，导致死循环
- JDK 1.8：
- 多线程put可能导致数据覆盖
- size计数不准确
java
// 数据覆盖示例
// 线程A和B同时put，都判断位置为空
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null); // 后执行的会覆盖先执行的解决方案：
- ConcurrentHashMap
- Collections.synchronizedMap()
- 外部加锁
HashMap和Hashtable的区别？
答案：
| 特性 | HashMap | Hashtable |
|---|---|---|
| 线程安全 | 否 | 是(synchronized) |
| null键值 | 允许 | 不允许 |
| 性能 | 高 | 低 |
| 初始容量 | 16 | 11 |
| 扩容 | 2倍 | 2倍+1 |
| 继承 | AbstractMap | Dictionary |
推荐：不要用Hashtable，用ConcurrentHashMap
ConcurrentHashMap的实现原理？
答案：
JDK 1.7：分段锁(Segment)
- 数组 + Segment + HashEntry
- 每个Segment是一个小的HashMap
- 锁粒度：Segment级别
JDK 1.8：CAS + synchronized
- 数组 + 链表 + 红黑树
- 锁粒度：Node级别（更细）
- 只锁链表/红黑树的头节点
java
// JDK 1.8 put简化版
final V putVal(K key, V value, boolean onlyIfAbsent) {
Node<K,V>[] tab; Node<K,V> f; int n, i, fh;
for (;;) {
if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// 位置为空，CAS插入
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
break;
}
else {
// 位置有元素，synchronized锁住头节点
synchronized (f) {
// 链表/红黑树插入
}
}
}
return null;
}练习题
- 为什么HashMap的容量必须是2的幂次？
- 如何实现一个LRU缓存？(提示：LinkedHashMap)
- TreeMap和HashMap的区别？
- fail-fast和fail-safe机制是什么？