哈希算法题目：设计推特

题目描述
设计一个简化版的推特(Twitter)，支持以下功能：

1. postTweet(userId, tweetId): 用户发布一条推文
2. getNewsFeed(userId): 获取用户最近10条推文，包括自己发的和关注的人发的，按时间倒序排列
3. follow(followerId, followeeId): 关注一个用户
4. unfollow(followerId, followeeId): 取消关注一个用户

解题思路分析
这个问题的核心在于如何高效管理用户关系和推文流。我们需要：

• 存储每个用户的关注列表
• 存储每个用户发布的推文
• 合并多个用户的推文流并按时间排序

详细解题步骤

步骤1：数据结构设计
我们需要两个核心数据结构：

1. 关注关系表：使用哈希表存储每个用户关注的用户集合
2. 推文存储：每个用户的推文用链表存储，包含推文ID和时间戳

class Twitter:
    def __init__(self):
        self.timestamp = 0  # 全局时间戳
        self.user_follows = {}  # userId -> set[followeeId]
        self.user_tweets = {}   # userId -> list[(timestamp, tweetId)]

步骤2：用户初始化处理
在操作前确保用户数据已初始化：

def _init_user(self, userId):
    if userId not in self.user_follows:
        self.user_follows[userId] = set([userId])  # 默认关注自己
    if userId not in self.user_tweets:
        self.user_tweets[userId] = []

步骤3：实现发布推文功能
发布推文时更新时间戳并存储：

def postTweet(self, userId, tweetId):
    self._init_user(userId)
    self.timestamp += 1
    self.user_tweets[userId].append((self.timestamp, tweetId))

步骤4：实现关注/取消关注功能
管理用户的关注关系：

def follow(self, followerId, followeeId):
    self._init_user(followerId)
    self._init_user(followeeId)
    self.user_follows[followerId].add(followeeId)

def unfollow(self, followerId, followeeId):
    if followerId in self.user_follows and followeeId in self.user_follows[followerId]:
        self.user_follows[followerId].remove(followeeId)

步骤5：实现获取新闻推送功能
这是最复杂的功能，需要合并多个时间线：

def getNewsFeed(self, userId):
    if userId not in self.user_follows:
        return []
    
    # 获取所有关注用户的推文
    all_tweets = []
    for followeeId in self.user_follows[userId]:
        if followeeId in self.user_tweets:
            all_tweets.extend(self.user_tweets[followeeId])
    
    # 按时间戳降序排序
    all_tweets.sort(reverse=True)
    
    # 返回最新的10条
    return [tweetId for _, tweetId in all_tweets[:10]]

步骤6：优化方案（使用堆排序）
当推文数量很大时，可以使用最小堆优化：

import heapq

def getNewsFeed_optimized(self, userId):
    if userId not in self.user_follows:
        return []
    
    heap = []
    for followeeId in self.user_follows[userId]:
        if followeeId in self.user_tweets:
            tweets = self.user_tweets[followeeId]
            if tweets:
                # 推文已按时间顺序存储，取最后一条（最新的）
                idx = len(tweets) - 1
                timestamp, tweetId = tweets[idx]
                heapq.heappush(heap, (-timestamp, tweetId, followeeId, idx - 1))
    
    # 从堆中取出前10条
    result = []
    while heap and len(result) < 10:
        neg_timestamp, tweetId, followeeId, idx = heapq.heappop(heap)
        result.append(tweetId)
        if idx >= 0:
            next_timestamp, next_tweetId = self.user_tweets[followeeId][idx]
            heapq.heappush(heap, (-next_timestamp, next_tweetId, followeeId, idx - 1))
    
    return result

关键要点总结

1. 哈希表用于快速查找用户关系和推文历史
2. 时间戳确保推文按时间顺序排列
3. 多路归并或堆排序用于高效合并多个时间线
4. 用户默认关注自己，简化逻辑处理

这种设计平衡了各项操作的时间复杂度，发布推文O(1)，关注/取消关注O(1)，获取推送O(n log k)其中k是关注人数。