- 正确答案：实现一个线程安全的URL计数器，需要支持高并发下的URL访问次数累加（写操作）、实时统计热门URL（基于访问频次排序），并能快速返回访问量最高的若干个URL。该系统应使用读写锁保证并发安全性，底层用哈希表（map）存储URL到计数的映射，同时维护一个最大堆来高效获取Top K热门URL。 - 解答思路： 1. 明确需求：多个线程可能同时访问和更新URL计数，因此必须线程安全。 2. 核心数据结构选择： - 使用 map 存储每个 URL 的访问次数，提供O(1)的查找与更新。 - 使用最大堆（priority_queue 或 heap 结构）按访问次数排序，用于提取最热URL。 - 使用读写锁（如C++中的shared_mutex或Java中的ReentrantReadWriteLock）控制对共享资源的并发访问：读多写少场景下，允许多个线程同时读取热门列表，但写入计数或重建堆时独占访问。 3. 注意点：不能每次查询都重新建堆，否则性能差；可采用懒更新策略，在读取时判断是否需要重建堆。 4. 实现关键函数：incrementUrl(string url)，getTopK(int k) - 深度知识讲解： 1. **线程安全与读写锁原理**：读写锁允许多个线程同时读取共享资源，但在写入时互斥。适用于“读多写少”的场景。例如，URL计数器中 incrementUrl 是写操作，getTopK 是读操作，且 getTopK 调用频率远高于 incrementUrl。若使用互斥锁（mutex），则所有操作串行化，吞吐量低。而读写锁允许并发读，显著提升性能。底层实现通常基于条件变量+引用计数：多个读者可以同时持有共享锁；当有写者到来时，阻塞后续读者，等待当前读者退出后由写者独占。 2. **哈希表（map）的选择**： - C++中推荐 unordered_map + shared_mutex - Java中可用 ConcurrentHashMap，但注意其不支持复合操作原子性（如“读-改-写”仍需额外同步） - 哈希冲突处理：链地址法 or 开放寻址法，影响性能尤其在高并发插入时 3. **最大堆的设计考量**：最大堆适合动态维护Top K元素。但由于URL计数会不断变化，无法直接维护一个始终有序的最大堆（因为计数增加后原位置不再正确）。因此常见做法是： - 每次调用 getTopK 时，从 map 中提取所有数据构造临时最大堆（适合小规模数据集） - 或维护一个优先队列缓存热点数据，并设置失效机制（如标记脏状态）更优方案：懒重建 + 脏标记 - 只有当 incrementUrl 发生时标记“堆已过期” - getTopK 被调用时，若发现过期则重建堆并清除标记 - 减少频繁建堆开销 4. **时间复杂度分析**： - incrementUrl: O(1) 哈希更新 + 写锁临界区 - getTopK: O(n + k log n)，其中n为不同URL总数，k为返回数量（构建堆O(n)，弹出k次O(k log n)） - 空间复杂度：O(n) 5. **扩展优化方向**： - 使用LFU缓存思想：只保留最近活跃的URL - 使用分段锁降低锁粒度（比如按URL哈希分片） - 使用无锁数据结构（如atomic、CAS）实现更高并发（进阶难度） - 定时刷新Top K，避免实时查询压力 - 代码示例（C++风格伪代码，含注释）： ``` #include #include #include #include #include #include class ThreadSafeUrlCounter { private: // 存储URL -> 访问次数 std::unordered_map urlCountMap; // 最大堆节点：(count, url) using HeapNode = std::pair; // 最大堆，按访问次数排序 mutable std::vector maxHeap; // 脏标记：表示自上次增量后堆未更新 mutable bool heapDirty; // 读写锁：保护map和heap mutable std::shared_timed_mutex rwMutex; // 私有方法：重建最大堆（必须持有写锁或已在写上下文中） void rebuildHeap() const { maxHeap.clear(); for (const auto& entry : urlCountMap) { maxHeap.push_back({entry.second, entry.first}); } // 构建堆 O(n) std::make_heap(maxHeap.begin(), maxHeap.end(), [](const HeapNode& a, const HeapNode& b) { return a.first < b.first; // 最大堆 }); heapDirty = false; } public: ThreadSafeUrlCounter() : heapDirty(true) {} // 增加指定URL的访问次数 void incrementUrl(const std::string& url) { std::unique_lock lock(rwMutex); // 写锁 urlCountMap[url]++; heapDirty = true; // 标记堆需要重建 } // 获取前k个最热门的URL std::vector getTopK(int k) const { std::shared_lock lock(rwMutex); // 读锁 // 如果堆脏了，则需要重建（注意：这里要升级为写锁？不行！所以先释放读锁再重获写锁） if (heapDirty) { // 释放读锁，申请写锁进行重建 lock.unlock(); std::unique_lock writeLock(rwMutex); // 双重检查避免重复重建 if (heapDirty) { rebuildHeap(); } lock = std::shared_lock(rwMutex); // 重新获取读锁 } // 复制堆以便提取Top K std::vector tempHeap = maxHeap; std::vector result; result.reserve(k); // 弹出前k个元素 for (int i = 0; i < k && !tempHeap.empty(); ++i) { std::pop_heap(tempHeap.begin(), tempHeap.end(), [](const HeapNode& a, const HeapNode& b) { return a.first < b.first; }); result.push_back(tempHeap.back().second); tempHeap.pop_back(); } return result; } // 获取某个URL的当前计数 int getCount(const std::string& url) const { std::shared_lock lock(rwMutex); auto it = urlCountMap.find(url); return it != urlCountMap.end() ? it->second : 0; } }; ``` - 关键细节说明： 1. `mutable`关键字允许在const成员函数中修改heapDirty和maxHeap，因为getTopK是const但可能触发重建。 2. 读写锁使用shared_timed_mutex配合shared_lock（读）和unique_lock（写）。 3. 重建堆的操作不能在读锁中完成，因此采用了“检测→释放读锁→拿写锁→双重检查→重建”的模式，确保线程安全。 4. 临时复制堆是为了避免在查询过程中干扰全局堆结构。 - 面试加分点： - 提到“懒加载”和“脏标记”优化 - 分析不同锁策略的性能差异 - 能指出ConcurrentHashMap在Java中也不能完全替代同步块 - 提出进一步优化如滑动窗口计数、布隆过滤器防恶意刷URL等总结：本题综合考察多线程编程、数据结构设计与性能权衡能力，重点在于理解读写锁的应用场景以及如何在动态变化的数据上维护有序视图。

虎牙一面凉经

全站热榜

创作者周榜