LLD 案例 1：停车场

需求澄清

停车场是 LLD 的“Hello World”，正因为人人都准备过，面试官会更在意细节。先和面试官对齐：

功能需求

1. 多层，每层有多个车位；车位分三种尺寸：小（摩托）、中（轿车）、大（货车、巴士）。
2. 小车可以停大车位，反之不行。
3. 多个入口发停车票，多个出口收费。
4. 按小时计费，不足一小时按一小时算，不同尺寸单价不同。
5. 能查询每层各尺寸的空位数。

非功能需求

• 多入口并发进车时，同一个车位不能分给两辆车。
• 计费规则、分配策略将来可能变化。

明确不做：支付网关、会员体系、车牌识别（当作外部输入）。

核心实体

类	职责
ParkingLot	门面，对外暴露 park / unpark
Level	一层，持有该层的车位
Spot	车位：id、尺寸、所在层
Vehicle	车牌 + 所需尺寸
Ticket	票号、车辆、车位、入场时间
SpotAllocator	找空位并占用（可替换策略）
PricingStrategy	根据票和离场时间算费用

ParkingLot
 ├── Level* ── Spot*
 ├── SpotAllocator   (按尺寸维护空闲池)
 ├── PricingStrategy <── HourlyPricing
 └── activeTickets   (ticketId → Ticket)

Ticket ──> Vehicle, Spot, entryTime

车型用 enum Size { SMALL, MEDIUM, LARGE } 就够了，不需要 Car、Bus 这样的子类层级——它们之间唯一的差别是尺寸，这是数据而不是行为。

分配策略：怎么快速找到空位

最朴素的做法是遍历所有层所有车位，O(总车位数)。几千个车位其实也跑得动，但面试官通常会追问优化。

更好的做法：每种尺寸维护一个空闲池，按“离入口近”排序，比如用 (level, number) 作为排序键的 TreeSet 或最小堆。

free:
  SMALL  -> [L1-03, L1-07, L2-01, ...]
  MEDIUM -> [L1-10, L1-11, ...]
  LARGE  -> [L3-01, ...]

分配时从“能容纳该车的最小尺寸”开始依次尝试：轿车先看 MEDIUM，空了再看 LARGE。从池里取出即占用，O(log n)；离场时放回对应的池。

注意需求里有多个入口，而“离入口近”只对某一个入口成立。两种处理：

• 和面试官约定以主入口（或电梯厅）为基准，所有入口共用一套排序。这是默认答案，简单。
• 每个入口各维护一套排序。同一个车位会同时出现在多个入口的有序集合里，分配时要在全局占用表里原子地标记占用，其他集合里的这条记录在弹出时发现已占用就跳过（惰性删除）。

核心代码

enum Size { SMALL, MEDIUM, LARGE }   // 声明顺序即从小到大

class SpotAllocator {
    // 每个 TreeSet 按 (level, number) 排序，构造时初始化
    private final Map<Size, TreeSet<Spot>> free = new EnumMap<>(Size.class);

    synchronized Optional<Spot> allocate(Size need) {
        for (Size s : Size.values()) {
            if (s.compareTo(need) < 0) continue;      // 太小，跳过
            Spot spot = free.get(s).pollFirst();      // 取最近的一个
            if (spot != null) return Optional.of(spot);
        }
        return Optional.empty();
    }

    synchronized void release(Spot spot) {
        free.get(spot.size()).add(spot);
    }
}

class ParkingLot {
    // 字段：allocator, pricing, clock, active (ConcurrentHashMap)
    Ticket park(Vehicle v) {
        Spot spot = allocator.allocate(v.size())
            .orElseThrow(() -> new IllegalStateException("Lot full"));
        Ticket t = new Ticket(nextId(), v, spot, clock.instant());
        active.put(t.id(), t);
        return t;
    }

    long unpark(String ticketId) {
        Ticket t = active.remove(ticketId);
        if (t == null) throw new IllegalArgumentException("Unknown ticket");
        long fee = pricing.fee(t, clock.instant());
        allocator.release(t.spot());
        return fee;
    }
}

Size.values() 按声明顺序从小到大，正好实现“先尝试最贴合的尺寸”。时钟用注入的 clock，方便测试计费。

计费

class HourlyPricing implements PricingStrategy {
    public long fee(Ticket t, Instant exit) {
        long mins = Duration.between(t.entry(), exit).toMinutes();
        long hours = Math.max(1, (mins + 59) / 60);   // 向上取整，至少 1 小时
        return hours * centsPerHour.get(t.spot().size());
    }
}

金额用整数（分），别用 double。这是个小细节，但面试官会注意到。

并发

多个入口线程同时调用 allocate，如果不加保护，两个线程可能拿到同一个车位。上面的代码用 synchronized 把“取出 + 占用”变成一个原子操作：pollFirst 取出即意味着别人再也拿不到。

可以和面试官讨论的升级路径：

• 全局锁：最简单。停车场的进出频率是每秒个位数，几乎不可能成为瓶颈。这是推荐的默认答案。
• 按尺寸分锁：每个池一把锁；跨尺寸尝试时一次只持有一把锁，避免死锁。
• ConcurrentSkipListSet：它的 pollFirst 本身是原子的，可以去掉外层锁。

主动说出“写入频率很低，全局锁足够，先保证正确”，比上来就堆无锁结构更能体现判断力。

另外，unpark 必须幂等：同一张票被重复提交（出口重试、两个出口同时扫同一张票）时，车位不能被放回池子两次。否则第二次 release 可能发生在车位已经被别的车占用之后，把一个有车的车位放回空闲池，下一辆车又被分到这里。

代码里靠 ConcurrentHashMap.remove 的返回值判断：remove 是原子的，同一张票只有一个线程能拿到非 null，也只有它会去 release 车位；其他线程拿到 null，按“票不存在或已结算”处理。如果票据表不是并发容器，就要把“删票 + 放回车位”放在同一把锁下。

扩展讨论

• 空位显示屏：观察者模式，SpotAllocator 在分配和释放时发事件，各层显示屏订阅。
• 电动车充电位：新增一个维度 Feature，空闲池的键从 Size 变成 (Size, Feature)。
• 预约：引入 Reservation，分配时先预留；超时自动释放回池。
• 换分配策略：比如“同一层集中停放”，换一个 SpotAllocator 实现，ParkingLot 不变。

常见失分点

• 用继承表达车型，结果每个子类只重写了一个返回尺寸的方法。
• 找车位用多重循环，且完全没考虑并发。
• 计费用浮点数，或者忘了“不足一小时按一小时”。
• 出场时没处理“票号不存在”和“重复出场”。