哈希算法题目：设计一个支持动态顺序统计的哈希结构

题目描述
设计一个名为 OrderStatisticsHash 的哈希结构，支持以下操作，并保证所有操作的平均时间复杂度为 O(1)：

1. insert(key, priority)：插入一个具有唯一 key 和整数 priority 的元素。如果 key 已存在，则更新其优先级。
2. delete(key)：删除指定 key 的元素。
3. get_rank(key)：返回指定 key 的元素在按优先级升序排序的顺序中的排名（从 1 开始）。例如，优先级最小的元素排名为 1。
4. get_key_by_rank(k)：返回排名为 k 的元素的 key。

要求：

• 所有键是唯一的，但优先级可以重复。
• 优先级可以在插入后通过 insert 操作更新（视为先删除旧优先级，再插入新优先级）。
• 需要高效支持动态插入、删除和顺序统计查询。

解题思路
这是一个结合哈希表和顺序统计的数据结构问题。

• 哈希表（字典）能提供 O(1) 的键值查找，但无法直接维护顺序。
• 平衡二叉搜索树（如 AVL 树、红黑树）能维护有序性，并支持顺序统计（如果节点额外存储子树大小），但查找是 O(log n)。
• 我们需要将哈希表的快速查找和平衡树的顺序统计结合，同时保证 O(1) 的平均操作时间。

关键想法：
我们可以使用哈希表 + 动态数组 + 另一个哈希表的组合：

1. key_to_index：哈希表，映射键 key 到动态数组中的索引位置。
2. array：动态数组，存储 (key, priority) 对，但不显式排序，而是通过桶排序思想结合哈希来间接维护顺序。
3. priority_to_keys：哈希表，映射优先级值到一个存储该优先级下所有键的列表（或集合）。
4. counts：哈希表，映射优先级到具有该优先级的元素数量，用于快速计算排名。

但这样 get_rank 和 get_key_by_rank 会需要扫描优先级范围，最坏 O(P)（P 是不同优先级数量），并非 O(1)。

更优思路：
我们可以借鉴索引顺序访问方法，但保持 O(1) 需要更巧妙的平衡。实际上，在普通计算机模型下，不可能同时满足所有操作严格 O(1)（因为顺序统计本身至少需要 O(log n) 的信息维护）。但题目允许“平均 O(1)”，我们可以通过分桶+哈希近似实现。

设计步骤

步骤1：数据结构设计

• 将优先级范围划分成若干个桶（bucket），每个桶覆盖一段连续的优先级值。
• 每个桶内使用哈希表存储该桶内所有键，并且桶内元素不需要排序，因为桶之间是按优先级范围有序的。
• 另外维护：
  • key_to_bucket_and_priority：哈希表，键 key -> (桶索引, 优先级)。
  • bucket_size：数组，记录每个桶中元素个数。
  • bucket_priority_range：每个桶的优先级范围是固定的，比如桶 i 存储优先级在 [i * B, (i+1)*B - 1] 的元素，B 是桶大小（一个设计参数）。

步骤2：操作设计

1. insert(key, priority)：

   • 如果 key 已存在，先执行 delete(key) 删除旧记录。
   • 计算桶索引：bucket_id = priority // B。
   • 在 key_to_bucket_and_priority[key] 中记录 (bucket_id, priority)。
   • 将 key 添加到桶 bucket_id 的哈希集合中。
   • 增加 bucket_size[bucket_id]。

2. delete(key)：

   • 从 key_to_bucket_and_priority 获取该键的桶索引和优先级。
   • 从该桶的哈希集合中删除 key。
   • 减少 bucket_size[bucket_id]。
   • 从 key_to_bucket_and_priority 删除该键。

3. get_rank(key)：

   • 从 key_to_bucket_and_priority 获取该键的桶索引 b 和优先级 p。
   • 排名 = 所有优先级小于 p 的元素数量 + 在桶 b 中优先级小于 p 的元素数量 + 1。
   • 计算第一部分：遍历桶 0 到 b-1，累加 bucket_size[i]，这是 O(桶数量)，但如果我们保持桶数量大约为 √M（M 是可能优先级范围），则是 O(√M)。
   • 计算第二部分：在桶 b 中，我们需要找出优先级严格小于 p 的键的数量。这需要对桶内所有元素遍历一次，桶内平均大小是 O(n/桶数量)，如果桶数量 ~ √n，则这部分是 O(√n)。
   • 为了优化到平均 O(1)，我们可以让每个桶内部再按优先级分组（二级桶），或者使用桶内维护有序链表+哈希，但那样会增加更新开销。

步骤3：优化到平均 O(1)

• 桶大小 B 取为常数，比如 B=1000。
• 这样，桶数量 = 优先级范围 / B，但优先级范围可能很大。
• 我们使用动态桶：只有非空桶才分配内存，用哈希表映射桶索引到桶内结构。
• 桶内结构：用动态数组存储该桶内所有元素的 (key, priority)，并按优先级排序。
• 为了在桶内快速插入/删除，我们可以用哈希表 key -> 在数组中的索引，然后数组用“交换到末尾再删除”技巧实现 O(1) 删除，但插入时需要保持有序，所以插入是 O(桶大小)。
• 桶大小是常数 B，所以桶内操作是 O(B)=O(1)。

具体结构：

• bucket_dict：哈希表，桶索引 -> 桶对象。
• 桶对象包含：
  • keys_priorities：动态数组，按优先级升序存储 (key, priority)。
  • key_to_pos：哈希表，键 -> 在 keys_priorities 中的索引。
• 全局 key_to_bucket：键 -> 桶索引。

步骤4：操作实现

insert(key, priority)：

1. 如果键存在，调用 delete(key)。
2. 计算桶索引 b = priority // B。
3. 如果桶 b 不存在，创建新桶（空数组和空哈希表）。
4. 在桶 b 的 keys_priorities 中找到插入位置（因为数组有序），插入新元素。更新 key_to_pos。
5. 更新 key_to_bucket[key] = b。

桶内插入需要移动元素，但桶大小 ≤ B 是常数，所以是 O(B)=O(1)。

delete(key)：

1. 从 key_to_bucket 获取桶索引 b。
2. 从桶 b 的 key_to_pos 获取位置 pos。
3. 将 keys_priorities[pos] 与最后一个元素交换，更新 key_to_pos 中原来最后一个元素的索引。
4. 删除最后一个元素，删除 key_to_pos[key]。
5. 如果桶变空，可选删除该桶。
6. 删除 key_to_bucket[key]。

桶内删除是 O(1)。

get_rank(key)：

1. 获取桶索引 b 和优先级 p。
2. 排名 = 所有桶索引小于 b 的元素总数 + 在桶 b 中优先级小于 p 的元素数量 + 1。
3. 第一部分：我们可以维护一个前缀和数组 prefix_count，其中 prefix_count[i] 表示所有桶索引小于 i 的元素总数。但桶索引是动态的，需要动态更新前缀和。
4. 为了 O(1) 查询，我们可以用树状数组（Fenwick Tree） 来维护每个桶索引处的元素数量，这样可以在 O(log M) 时间内计算前缀和，其中 M 是桶索引范围。但 M 可能很大。
5. 改进：因为桶大小固定为 B，桶索引是 priority // B，我们可以用数组 bucket_size 直接存储每个桶的元素数，但桶索引可能很大。
6. 实际我们可以用哈希表 bucket_index_to_size 存储每个非空桶的大小，然后计算前缀和需要遍历所有非空桶，最坏 O(桶数量)。
7. 为了使 get_rank 平均 O(1)，我们可以让 get_rank 不常用，或者接受 O(桶数量) 的时间，桶数量平均是 n/B，如果 B 选为 √n，则是 O(√n)。

步骤5：真正的 O(1) 平均方案

• 使用双层哈希：
  • 第一层：优先级除以 B 得到桶索引。
  • 第二层：桶内，优先级对 B 取模得到桶内子桶索引。
  • 这样，每个子桶内优先级相同，因此 get_rank 只需要计算：前面所有桶元素总数 + 前面子桶元素总数 + 1。
• 维护：
  • bucket_size[b]：桶 b 的元素数。
  • sub_bucket_count[b][r]：桶 b 中模值 r 的元素数。
• 然后 get_rank(key)：
  • 桶 b，优先级 p，模值 r = p % B。
  • 排名 = sum(bucket_size[0..b-1]) + sum(sub_bucket_count[b][0..r-1]) + 1。
• 前缀和可以预先计算并维护：
  • bucket_prefix：桶大小的前缀和数组，桶索引最多可能为 (max_priority // B) + 1，但可以动态扩展。
  • sub_bucket_prefix[b]：桶 b 内子桶计数的前缀和数组。
• 每次插入/删除时更新相关桶和子桶的计数，并更新前缀和。
• 前缀和更新如果使用差分+树状数组，可以 O(log M) 更新，但这里桶索引和子桶索引数量都是常数范围（如果优先级范围有限），我们可以直接更新所有受影响的前缀和，最坏 O(桶数量)。
• 但通过巧妙设计，我们可以让 B 约等于 √(优先级范围)，桶数量 √M，子桶数量 B=√M，这样每次更新需要更新 O(√M) 个前缀和，不是 O(1)。

最终简化可行方案
如果优先级范围不大（比如 0 到 10^5），我们可以直接用一个大数组 priority_count[priority] 记录每个优先级的元素数量，再用哈希表 key_to_priority 记录键的优先级。

• get_rank(key)：计算优先级小于 p 的元素总数，即前缀和查询，用树状数组维护 priority_count 的前缀和，O(log M)。
• get_key_by_rank(k)：需要在树状数组上二分查找，找到最小的优先级使得前缀和 ≥ k，然后在该优先级的键集合中任取一个键。
• 插入/删除时更新树状数组和 priority_count。
• 每个优先级可能有多个键，用哈希集合存储。

这样，所有操作 O(log M)，如果 M 是常数范围，则可视为 O(1)。

总结
本题的核心挑战是在哈希表的基础上支持顺序统计。

• 纯哈希表无法维护顺序。
• 平衡树可以 O(log n) 支持所有操作，但题目要求平均 O(1)。
• 通过分桶+前缀和，可以近似达到平均 O(1)，但需要根据优先级范围权衡桶大小。
• 如果优先级范围有限，直接用树状数组+哈希是最清晰的实现，操作 O(log M)，M 是优先级范围，可视为常数。

代码框架（Python 伪代码）

class OrderStatisticsHash:
    def __init__(self, max_priority=10**5):
        self.M = max_priority
        self.key_to_priority = {}
        self.priority_to_keys = [set() for _ in range(self.M+1)]
        self.BIT = [0]*(self.M+2)  # 树状数组，索引从1开始
    
    def _update_bit(self, idx, delta):
        while idx <= self.M+1:
            self.BIT[idx] += delta
            idx += idx & -idx
    
    def _prefix_sum(self, idx):
        s = 0
        while idx > 0:
            s += self.BIT[idx]
            idx -= idx & -idx
        return s
    
    def insert(self, key, priority):
        if key in self.key_to_priority:
            self.delete(key)
        self.key_to_priority[key] = priority
        self.priority_to_keys[priority].add(key)
        self._update_bit(priority+1, 1)  # 树状数组索引从1开始
    
    def delete(self, key):
        priority = self.key_to_priority[key]
        del self.key_to_priority[key]
        self.priority_to_keys[priority].remove(key)
        self._update_bit(priority+1, -1)
    
    def get_rank(self, key):
        priority = self.key_to_priority[key]
        return self._prefix_sum(priority) + 1  # 小于 priority 的数量 + 1
    
    def get_key_by_rank(self, k):
        # 二分查找树状数组找到前缀和 >= k 的最小优先级
        lo, hi = 1, self.M+1
        while lo < hi:
            mid = (lo+hi)//2
            if self._prefix_sum(mid) >= k:
                hi = mid
            else:
                lo = mid+1
        if lo > self.M+1:
            return None
        priority = lo-1
        if not self.priority_to_keys[priority]:
            return None
        return next(iter(self.priority_to_keys[priority]))

复杂度：

• 插入、删除：O(log M)。
• 查询排名、按排名取键：O(log M)。
• 若 M 固定，则视为 O(1)。

这样我们就设计了一个支持动态顺序统计的哈希结构，核心在于用树状数组维护优先级计数，用哈希表维护键到优先级的映射，用数组+集合存储同一优先级的键，从而在有限优先级范围内实现高效操作。