Dai Wei

二分查找依赖的不是“数组”三个字，而是搜索空间存在单调性：某个判定在分界点一侧为假，另一侧为真。每次检查中点并排除一半区间，因此查找次数为 O(log n)。 写对二分的关键是固定区间语义。闭区间 [left,right] 中循环条件为 left <= right；命中后若找最左位置，应保存答案并令 right=mid-1，否则依据大小移动边界。中点使用 left + (right-left)/2 可避免加法溢出。 12345678answer = nonewhile left <= right: mid = left + (right-left)/2 if predicate(mid): answer = mid right = mid - 1 else: left = mid + 1 普通查值的判定是 a[mid] 与目标的比较；寻找第一个不小于目标的位置，是找首次满足 a[i] >= target；答案二分则把索引换成可能答案，例如最小运载能力、最大可行距离。此时必须先证明 predicate(x) 随 x 单调，并给出一定覆...

LinkedList 实现双向链表，同时实现 List 与 Deque，可在头尾 O(1) 插删；随机访问需遍历，工程里多数场景仍被 ArrayList 取代。 核心概念节点 Node<E> 含 item、prev、next；维护 first/last 与 size。继承 AbstractSequentialList，随机访问的 get(index) 会从头或尾折半遍历，O(n)。实现队列/栈：offer/poll/peek、push/pop。不支持 RandomAccess，增强 for 仍可用迭代器顺序访问。 关键机制与实践头尾操作 addFirst/addLast 仅改指针，O(1)。中间插入 先定位再链接，平均 O(n)。Josh Bloch 曾公开表示很少用 LinkedList——常数因子大、缓存不友好。真正需要双端队列时，可评估 ArrayDeque（数组环形缓冲，通常更快）。 123Deque<String> dq = new LinkedList<>();dq.addFirst("head")...

LinkedHashMap 继承 HashMap，在哈希桶之外用双向链表串起所有条目，从而支持按插入顺序或访问顺序迭代——是实现简易 LRU 的经典结构。 核心概念Entry 扩展 HashMap 的 Node，增加 before/after 指针。构造参数 accessOrder：false 为插入顺序，true 为访问顺序（get 会把节点移到链表尾）。覆盖 afterNodeAccess 等钩子维护链表。迭代按链表走，复杂度 O(n)，与 bucket 数量无关，遍历往往比 HashMap 更稳定。 关键机制与实践LRU 思路：accessOrder=true，重写 removeEldestEntry 在 size 超限时删最老（链表头）条目。注意线程安全需外包同步或使用 Caffeine 等专业缓存。与 TreeMap 按 key 排序不同，LinkedHashMap 顺序是插入或访问时间语义。 12345LinkedHashMap<String, String> lru = new LinkedHashMap<>(16, 0.75f, tru...

HashMap 基于哈希表，JDK 8 为 数组 + 链表 + 红黑树：冲突链过长时树化降低查找至 O(log n)。非线程安全，允许一个 null 键与多个 null 值。 核心概念默认容量 16，负载因子 0.75，阈值 capacity * loadFactor 触发扩容为 2 倍。hash 扰动：(h = key.hashCode()) ^ (h >>> 16) 再 (n-1) & hash 定位桶。链表长度 ≥8 且 table 长度 ≥64 时转红黑树；≤6 退化为链表。扩容时 rehash 节点到新表，JDK 8 优化为按位拆链。 关键机制与实践put：无桶则新建 Node；hash 相同再比 key equals；冲突尾插或树插入。get 沿链或树查找。重写 key 的 hashCode/equals 是正确使用前提。并发场景用 ConcurrentHashMap，不要用 Collections.synchronizedMap 冒充高并发方案。 12345// JDK 8 扰动函数思想：高 16 位参与索引，减少碰撞static fi...

DelayQueue 是无界阻塞队列，元素须实现 Delayed（按剩余延迟时间排序）。队头是最早到期的元素；take 在元素未到期时会阻塞等待。 核心概念底层 PriorityQueue 按 getDelay(NOW) 小顶堆排序。ReentrantLock + Condition available 协调并发。put/offer 入堆并 signal；take 循环检查队头 delay 是否 ≤0，否则 awaitNanos 睡到最近到期时间。用于定时任务、缓存过期、订单超时关闭等。 关键机制与实践ScheduledThreadPoolExecutor 的延迟调度与 DelayQueue 思想相近。自定义任务实现 Delayed：在 compareTo 与 getDelay 中保持一致的排序语义（通常按到期时间戳）。注意系统时钟调整对 TimeUnit 换算的影响；高精度场景评估 System.nanoTime()。 123456public class DelayTask implements Delayed { private final l...

CopyOnWriteArrayList（COW）在写时复制整个底层数组，读操作无锁访问快照，适合读远多于写、且能容忍短暂不一致的监听器、白名单等场景。 核心概念内部 volatile Object[] array 持有当前快照。add/set/remove：lock → 复制新数组 → 修改 → 原子替换 array 引用 → unlock。迭代器持有创建时的数组引用，不会抛 ConcurrentModificationException（快照迭代）。写开销 O(n)，读 O(1) 且无锁。 关键机制与实践典型用途：Servlet 监听器列表、配置热更新、Rx 订阅者集合。写频繁时复制成本与 GC 压力巨大，应换 Collections.synchronizedList 或并发队列。元素需稳定：迭代过程中看到的是旧快照，新写入对已有迭代器不可见。 123CopyOnWriteArrayList<Runnable> listeners = new CopyOnWriteArrayList<>();listeners.add(this...

ConcurrentHashMap 是线程安全的哈希表：JDK 7 用 Segment 分段锁 限制竞争范围；JDK 8 改为 Node 数组 + CAS + synchronized 桶头，结构更接近 HashMap，并发度与内存更优。 核心概念JDK 7：固定 Segment 数组，每个 Segment 继承 ReentrantLock，内部小型 HashMap。JDK 8：单 table，put 空桶 CAS 占位，冲突则 synchronized 锁链表/树头节点；扩容多线程协助迁移。size() 用 baseCount + CounterCell 分散计数。不允许 null 键值（与 HashMap 不同，避免歧义）。 关键机制与实践读操作大多无锁（volatile 读 table 与 Node val/next）。computeIfAbsent 等原子复合操作适合缓存场景。迭代器弱一致性，不抛 CME，但可能反映部分更新。与 Collections.synchronizedMap 比：CHM 粒度更细，读扩展性更好。 12ConcurrentH...

ArrayList 是最常用的动态数组实现：随机访问 O(1)，尾部追加均摊 O(1)，中间插入删除需搬移元素。理解扩容与 modCount 能解释很多线上异常。 核心概念底层 transient Object[] elementData，size 记录元素个数。JDK 8+ 空构造延迟分配，首次 add 才扩到默认 10。扩容：grow 约为 1.5 倍（newCapacity = old + (old >> 1)），复制到新数组。实现 RandomAccess 标记支持快速下标访问。 关键机制与实践add(E) 尾插；add(index, E) 需 System.arraycopy 腾位。remove 同理左移或右移。迭代器检查 expectedModCount == modCount，结构修改抛 ConcurrentModificationException（fail-fast）。subList 是原列表视图，父列表修改会影响子列表。 123List<String> list = new ArrayList<>(16);list.ad...

ArrayBlockingQueue 是基于数组的有界阻塞队列，生产者与消费者共用一把 ReentrantLock，通过两个 Condition 实现「队满等待 / 队空等待」。 核心概念内部环形数组 + takeIndex/putIndex/count 维护头尾与元素个数。构造时可指定公平/非公平锁。实现 BlockingQueue：put 队满阻塞，take 队空阻塞；还有 offer/poll 超时非阻塞变体。单锁设计简单，高并发下锁竞争可能成为瓶颈。 关键机制与实践入队：lock → while 满则 notFull.await → 写入数组 → 更新索引 → notEmpty.signal → unlock。出队对称。size() 在锁内读取 count，一致性好。线程池 ThreadPoolExecutor 常用有界队列配合拒绝策略，防止无界堆积 OOM。 123BlockingQueue<Task> q = new ArrayBlockingQueue<>(100);q.put(task)...

集合面试下篇聚焦并发与特殊队列：CHM 演进、BlockingQueue 家族、CopyOnWrite 与 WeakHashMap 等，常与线程池、缓存一起考。 核心概念ConcurrentHashMap：7 分段锁 vs 8 CAS+synchronized。BlockingQueue：ArrayBlockingQueue 有界单锁、LinkedBlockingQueue 可选容量、SynchronousQueue 不存元素直接交接。CopyOnWriteArrayList：写时复制，读无锁。PriorityQueue 小顶堆，非线程安全。WeakHashMap 弱引用键，利于缓存自动回收。 关键机制与实践线程池队列选型：有界 ArrayBlockingQueue + 拒绝策略防 OOM；SynchronousQueue 配合 maximumPoolSize 实现直接 handoff。CHM 的 computeIfAbsent 做本地缓存；注意 value 加载勿过慢阻塞桶锁。对比 HashTable、Collections.synchronizedXxx 的全表锁与 CH...