Cider面试：本地实现一个CRUD订单系统，能实时计算最高最低平均价格，线程安全，复杂度尽可能低？

你可以使用 `ConcurrentHashMap` 存储订单，并使用 `AtomicLong` 和 `AtomicReference` 来维护最高、最低和平均价格，以确保线程安全，同时保持较低的复杂度。 ### 设计思路： 1. **使用 `ConcurrentHashMap<Long, Order>` 存储订单**，支持高并发 CRUD 操作。 2. **使用 `AtomicLong` 维护订单总数和价格总和**，便于计算平均值。 3. **使用 `AtomicReference<Order>` 维护最高和最低价格订单**，利用 `compareAndSet` 进行原子更新。 4. **读写分离**：增删改时更新统计数据，查询时直接返回缓存值，提高效率。 ### 代码实现： ```java import java.util.concurrent.ConcurrentHashMap; import java.util.concurrent.atomic.AtomicLong; import java.util.concurrent.atomic.AtomicReference; class Order { long id; double price; Order(long id, double price) { this.id = id; this.price = price; } } public class OrderSystem { private final ConcurrentHashMap<Long, Order> orders = new ConcurrentHashMap<>(); private final AtomicLong totalPrice = new AtomicLong(0); private final AtomicLong totalOrders = new AtomicLong(0); private final AtomicReference<Order> maxOrder = new AtomicReference<>(null); private final AtomicReference<Order> minOrder = new AtomicReference<>(null); // 创建订单 public void createOrder(long id, double price) { Order newOrder = new Order(id, price); if (orders.putIfAbsent(id, newOrder) == null) { totalPrice.addAndGet((long) price); totalOrders.incrementAndGet(); updateMaxMin(newOrder, true); } } // 更新订单 public void updateOrder(long id, double newPrice) { orders.computeIfPresent(id, (key, oldOrder) -> { totalPrice.addAndGet((long) (newPrice - oldOrder.price)); updateMaxMin(oldOrder, false); Order updatedOrder = new Order(id, newPrice); updateMaxMin(updatedOrder, true); return updatedOrder; }); } // 删除订单 public void deleteOrder(long id) { Order removedOrder = orders.remove(id); if (removedOrder != null) { totalPrice.addAndGet((long) -removedOrder.price); totalOrders.decrementAndGet(); updateMaxMin(removedOrder, false); } } // 获取最高价格订单 public Order getMaxOrder() { return maxOrder.get(); } // 获取最低价格订单 public Order getMinOrder() { return minOrder.get(); } // 获取平均价格 public double getAveragePrice() { long count = totalOrders.get(); return count == 0 ? 0 : (double) totalPrice.get() / count; } // 更新最高/最低价格订单 private void updateMaxMin(Order order, boolean isAdd) { if (isAdd) { maxOrder.accumulateAndGet(order, (current, newO) -> current == null || newO.price > current.price ? newO : current); minOrder.accumulateAndGet(order, (current, newO) -> current == null || newO.price < current.price ? newO : current); } else { if (maxOrder.get() == order || minOrder.get() == order) { recalculateMaxMin(); } } } // 重新计算最高/最低价格 private void recalculateMaxMin() { Order newMax = null, newMin = null; for (Order order : orders.values()) { if (newMax == null || order.price > newMax.price) newMax = order; if (newMin == null || order.price < newMin.price) newMin = order; } maxOrder.set(newMax); minOrder.set(newMin); } public static void main(String[] args) { OrderSystem orderSystem = new OrderSystem(); orderSystem.createOrder(1, 100); orderSystem.createOrder(2, 200); orderSystem.createOrder(3, 50); System.out.println("最高价: " + orderSystem.getMaxOrder().price); System.out.println("最低价: " + orderSystem.getMinOrder().price); System.out.println("平均价: " + orderSystem.getAveragePrice()); orderSystem.updateOrder(2, 30); System.out.println("更新后最高价: " + orderSystem.getMaxOrder().price); System.out.println("更新后最低价: " + orderSystem.getMinOrder().price); System.out.println("更新后平均价: " + orderSystem.getAveragePrice()); orderSystem.deleteOrder(1); System.out.println("删除后最高价: " + orderSystem.getMaxOrder().price); System.out.println("删除后最低价: " + orderSystem.getMinOrder().price); System.out.println("删除后平均价: " + orderSystem.getAveragePrice()); } } ``` ### 复杂度分析： - **创建订单 `O(1)`**：`putIfAbsent` 操作为 `O(1)`，更新 `AtomicLong` 也为 `O(1)`。 - **更新订单 `O(1)`**：`computeIfPresent` 是 `O(1)`，涉及 `AtomicLong` 和 `AtomicReference` 也是 `O(1)`。 - **删除订单 `O(1) ~ O(N)`**： - 删除后如果最高/最低价格没变化，`O(1)`。 - 若需要重算最高/最低价格，则 `O(N)`（遍历 `orders`）。 ### 优势： 1. **高并发支持**：使用 `ConcurrentHashMap` 和 `Atomic` 变量，线程安全。 2. **高效计算**： - 维护 `AtomicLong` 避免每次查询时重新计算总价，提高性能。 - `AtomicReference` 维护最高/最低价格，减少遍历次数。 3. **低复杂度**：大多数操作都是 `O(1)`，只有删除最高/最低订单时可能退化到 `O(N)`。 这套方案在保证线程安全的同时，实现了高效的 CRUD 操作和实时价格计算。