algorithm - 什么是存储支持添加、删除元组和比较(在 a 或 b 上)的 2 元组 (a, b) 的最佳数据结构)

Question

所以这是我的问题。我想存储 2 元组 (key, val) 并想执行以下操作:

• 键是字符串，值是整数
  
• 多个键可以有相同的值
• 添加新元组
  
• 用新值更新任何键(任何新值或更新值大于前一个值，如时间戳)
  
• 获取所有值小于或大于给定值的键
  
• 删除元组。

哈希似乎是更新键值的明显选择，但通过值查找将花费更长的时间 (O(n))。另一种选择是键值交换的平衡二叉搜索树。所以现在通过值查找将很快(O(lg(n)))但更新键将花费(O(n))。那么有没有什么数据结构可以用来解决这些问题呢？

谢谢。

Answer 1

我会使用 2 个数据结构，一个从键到值的哈希表和一个按值排序然后按键排序的搜索树。插入时，将对插入到两个结构中，当按键删除时，从哈希中查找值，然后从树中删除对。更新基本上就是delete+insert。插入、删除和更新是 O(log n)。为了获取所有小于值的键，在搜索树中查找值并向后迭代。这是 O(log n + k)。

好的哈希表和搜索树实现的选择在很大程度上取决于您的数据和操作的特定分布。也就是说，两者的良好通用实现应该就足够了。