**问题示例建议**： 1. 如何使用 Set 数据结构实现用户关注与取消关注功能？ 2. 使用 Set 实现“共同关注”功能的底层原理是什么？时间复杂度如何？ 3. 为什么在关注系统中使用 Set 而不是 List 或 Array？ 4. 如果有上亿用户，关注系统如何优化存储和查询效率？ 5. Set 在 Java 中有哪些实现类？各自适用场景是什么？ --- ### 示例面试题： **请设计一个简单的用户关注系统，支持以下操作：** - 关注某个用户 - 取消关注某个用户 - 查询某用户是否已关注另一个用户 - 获取两个用户的共同关注列表 --- ### 正确答案：我们可以使用 Set 数据结构来实现每个用户所关注的用户集合。例如，使用一个 Map，其中 key 是用户 ID，value 是该用户关注的所有用户 ID 的 Set。 --- ### 解答思路： 1. **数据结构选择**： - 每个用户的关注列表用 Set 存储，因为 Set 支持 O(1) 时间复杂度的插入、删除和查找操作。 - 整体结构使用 Map> 来保存所有用户的关注关系。 2. **操作分析**： - 关注：将目标用户加入当前用户的关注集合。 - 取关：从当前用户的关注集合中删除目标用户。 - 是否关注：检查当前用户的关注集合是否包含目标用户。 - 共同关注：取两个用户关注集合的交集。 3. **性能分析**： - 所有基本操作的时间复杂度为 O(1)（Set 的哈希表实现）。 - 共同关注的操作时间复杂度取决于两个集合的大小，若使用 HashSet，则可利用 retainAll 方法高效求交集。 --- ### 深度知识讲解： #### Set 数据结构的底层实现原理： Set 是一种不允许重复元素的集合结构，其常见的实现包括： - **HashSet**：基于 HashMap 实现，元素作为键存储，值为一个固定对象（如 PRESENT）。 - **TreeSet**：基于红黑树实现，支持有序遍历。 - **LinkedHashSet**：继承自 HashSet，内部使用双向链表维护插入顺序或访问顺序。 **HashSet 的实现机制**： - 底层是通过 HashMap 实现的。 - 插入元素时，元素作为 key 插入到 HashMap 中，value 是一个静态对象。 - 因此，HashSet 的查找、插入、删除操作都具有 O(1) 的平均时间复杂度。 #### 哈希冲突解决方式： - 开放寻址法（Open Addressing） - 链地址法（Separate Chaining） Java 中的 HashMap（进而影响 HashSet）采用的是链地址法，在发生哈希冲突时，会将冲突的键值对以链表形式存储在一个桶中。当链表长度超过阈值（默认8），链表会转化为红黑树，提高查找效率。 --- ### 代码示例（Java）： ```java import java.util.*; public class FollowSystem { private Map> followMap; public FollowSystem() { followMap = new HashMap<>(); } // 用户 followerId 关注 followeeId public void follow(int followerId, int followeeId) { followMap.putIfAbsent(followerId, new HashSet<>()); followMap.get(followerId).add(followeeId); } // 用户 followerId 取消关注 followeeId public void unfollow(int followerId, int followeeId) { if (followMap.containsKey(followerId)) { followMap.get(followerId).remove(followeeId); } } // 判断用户 followerId 是否关注了 followeeId public boolean isFollowing(int followerId, int followeeId) { return followMap.containsKey(followerId) && followMap.get(followerId).contains(followeeId); } // 获取两个用户之间的共同关注 public Set getCommonFollowees(int user1Id, int user2Id) { Set set1 = followMap.getOrDefault(user1Id, new HashSet<>()); Set set2 = followMap.getOrDefault(user2Id, new HashSet<>()); Set common = new HashSet<>(set1); common.retainAll(set2); // 取交集 return common; } // 测试用例 public static void main(String[] args) { FollowSystem system = new FollowSystem(); system.follow(1, 2); system.follow(1, 3); system.follow(2, 3); System.out.println("User 1 is following User 2? " + system.isFollowing(1, 2)); // true System.out.println("Common followees of 1 and 2: " + system.getCommonFollowees(1, 2)); // [3] } } ``` --- ### 扩展知识点： #### 1. 大规模系统的优化方向： - 使用 Redis 缓存关注关系，提升读写性能。 - 使用布隆过滤器（Bloom Filter）预判是否关注，减少数据库访问。 - 使用图数据库（如 Neo4j）管理社交网络中的关注关系。 #### 2. Set 和 List 的对比： | 特性 | Set | List | |------------------|-----------------------------|--------------------------| | 是否允许重复 | 否 | 是 | | 是否有序 | 不一定（HashSet无序） | 有序 | | 查找时间复杂度 | O(1) | O(n) | | 应用场景 | 关注/去重/集合运算 | 顺序数据处理 | #### 3. Set 在实际项目中的典型应用： - 社交平台的关注系统 - 文档关键词提取与匹配 - 网络爬虫的 URL 去重 - 用户权限控制（角色权限集合） --- ### 总结：本题考察候选人对 Set 数据结构的理解及在实际系统中的应用能力。重点在于理解 Set 的底层实现（HashMap）、集合操作的效率、以及如何用它构建复杂的业务逻辑。对于校园招聘来说，掌握这些内容不仅能应对基础算法题，也能展示出良好的工程实践能力。

滴滴一面

全站热榜

创作者周榜