Instagram抽奖场景高效ADT与数据结构设计咨询

你初始的HashMap+动态数组思路方向是对的，核心问题出在「删除用户时需要遍历数组定位所有对应条目」，只要补充位置映射、懒删除、尾元素补位三个小设计，就能让addEntry、withdrawUser、drawWinner三个方法全部实现均摊O(1)时间复杂度，同时严格满足概率公平性要求。

核心数据结构定义 #

不需要复杂的高级结构，三个基础容器加两个计数器即可：

• countMap: HashMap<String, Integer>：键为用户名，值为该用户当前持有的有效抽奖条目数，用户被抽中或主动退赛时直接修改该值即可，不需要操作数组
• entryList: ArrayList<String>：存储所有抽奖条目，允许存在已失效的冗余条目，所有新条目统一追加到列表尾部
• posMap: HashMap<String, HashSet<Integer>>：键为用户名，值为该用户所有条目在entryList中对应的下标集合，用于快速定位条目位置
• validTotal: Integer：全局计数器，实时记录当前抽奖池内的有效条目总数
• validSize: Integer：动态数组的逻辑有效长度，初始值为0，用于跳过懒删除留下的冗余条目

三个核心方法的具体实现 #

1. addEntry(String username) #

全程无遍历，自动适配单用户最多50次参赛的规则：

1. 先做规则校验：如果countMap中该用户的条目数已经等于50，直接返回，拒绝新增
2. 将用户名追加到entryList尾部，对应下标为idx = entryList.size() - 1
3. 更新countMap：该用户的条目数+1
4. 更新posMap：将idx加入该用户对应的下标集合
5. validTotal和validSize各+1

时间复杂度O(1)：数组尾插、哈希表插入均为常数级操作。

2. withdrawUser(String username) #

直接作废用户所有资格，完全不需要遍历数组删除对应条目：

1. 如果countMap中不存在该用户，或对应条目数为0，直接返回
2. 读取该用户当前有效条目数cnt = countMap.get(username)
3. validTotal -= cnt，直接将countMap中该用户的条目数置为0
4. 清空posMap中该用户对应的下标集合（可选，用于节省内存，不影响核心逻辑）

时间复杂度O(1)：仅修改哈希表中的计数值，跳过了数组遍历删除的高成本步骤，冗余条目交给后续抽奖流程的补位逻辑清理即可。

3. drawWinner() #

严格保证抽中概率和有效条目数成正比，无全量遍历开销：

1. 如果validTotal == 0，直接返回空（无有效参赛用户）
2. 生成[0, validSize - 1]区间内的随机整数randIdx
3. 从randIdx位置开始做有效性校验+补位清理：
   • 如果当前位置的用户名在countMap中的有效条目数为0，说明是之前作废用户留下的失效条目：将entryList中validSize - 1位置的有效元素移动到当前位置，同步更新posMap中该有效元素对应的下标值，随后validSize -= 1，重复校验当前位置
   • 如果当前位置的用户名为有效用户，停止校验，该用户即为中奖者
4. 调用withdrawUser(中奖用户名)作废该用户所有参赛资格，返回中奖用户名

时间复杂度均摊O(1)：每个失效条目只会被补位清理一次，不会被重复访问，所有操作的总开销和总参赛条目数线性相关，均摊到单次抽奖操作即为常数级。
概率正确性说明：有效段内的所有条目权重完全相等，随机取下标时每个有效条目被抽中的概率一致，因此任意用户的中奖概率严格等于「自身有效条目数/全局有效条目总数」，完全符合规则要求。

方案优势 #

相比最初的设计，这个方案没有增加量级上的空间开销，只是把删除操作的O(n)遍历成本，通过懒删除延后到了抽奖时的补位步骤，从根本上避免了最坏情况的线性时间开销，哪怕单场活动参赛条目达到百万级，三个操作的响应延迟也能稳定在常数级。

内容的提问来源于stack exchange，提问作者Hideenu