data-structures - 具有复合值和快速搜索值元素的集合

Question

我正在寻找一种类似于集合的数据结构，该集合存储由 4 个整数组成的复合值：i1, i2, i3, i4. 这种数据结构应该有快速的查找时间，但它也应该允许快速删除具有特定 i3 和 i4 的成员。所以delete_a(x)应该删除所有成员，i3 = x并且delete_b(x)应该删除所有成员i4 = x。最关键的是成员查找操作，所以如果可能的话，我希望它是 O(1)。i1、i2、i3和的值i4相当大，所以我不能使用 4 维数组，因为它会占用太多内存。我想也许哈希表和辅助列表的某种组合可以解决这个问题。

Answer 1

如果你想要绝对速度，同时保持一些内存效率，我会这样做：

HashMap_a:
  Key: i3
  Value: List of Hash(i1,i2,i3,i4)
HashMap_b:
  Key: i4
  Value: List of Hash(i1,i2,i3,i4)
HashMap:
  Key: Hash(i1,i2,i3,i4)
  Value: (i1,i2,i3,i4)

delete_a只是HashMap_a从 HashMap 中获取列表并从列表中删除键在列表中的元素的问题。同样对于delete_b
查找是 O(1) 从HashMap