业务需求的数据结构建议

Question

我的记录结构如下(名称、选择StartNum EndNum空缺)

Name,Option,StartNum,EndNum构成结构/表的复合键。因此，对于给定的这些组合，将只有一个空缺记录。

<标题>示例记录

ABC, X, 2, 14日1
正面X 3 8 0
时,Y, 1, 12日2
小块土地,X, 12、13、17

可能有:

1. 250 - 300名

2. 每个名称20 - 30选择

3. 每个选项1-45 StartNum

4. 对于每个StartNum1 - 14 EndNum

5. 对于上述条目的每个组合，只有一个空缺条目。

所以最多可以有5,670,000(300*30*45*14)个条目

支持快速操作

1. 搜索复合键即(Name+Option+StartNum+EndNum)并获取它的空缺记录值
2. 对于给定的名称，选项和数字，搜索并删除具有给定名称，选项和StartNum<=Number<=EndNum的记录

谁能建议适当的数据结构，我的上述要求。数据结构构建操作可能会很慢，因为它是离线完成的，但是上面提到的两个操作应该非常非常快。

谢谢,
哈瑞

Answer 1

我将基于元组(Name, Option)创建一个哈希映射。对于这两者的每一种组合，都可以有一个简单的列表，按(StartNum, EndNum)排序。插入到这个列表中需要O(N)的大小，但是你知道这个大小是非常小的。另一个选择是一些平衡二叉搜索树或跳跃表。

如果你有一个好的散列(这应该不难，标准的散列应该可以工作)，检索的时间复杂度将是O(1 + log(|StartNum| * |EndNum|))。

按2进行搜索时。，检查所有具有StartNum <= Number的值是否与EndNum匹配

Answer 2

散列映射应该很好地满足您的目的。您只需要弄清楚如何为组合键创建一个好的散列。如果您已经为各个项目设置了散列，那么您可以使用一个简单的异或将它们组合起来。