我面临着以一种我以前从未解决过的方式处理 ID 的问题。我认为对此没有什么惊人的解决方案,但我想我不妨问问。
我有一个对象的哈希表。
每个都由一个 id 标识,为了演示,它是一个数字。虽然它实际上是一个 GUID。
对象的数量是无限的,并且为了这个数十亿规模的练习。
应用程序逻辑定义了 ID 组之间存在转换。例如,{4, 7, 12}
可以将 ID 组定义为转换为{5, 16}
. 每个 ID 都可以出现在任意数量的分组翻译中。分组翻译中的一个组可以翻译成多个其他组,但每个组都是其自身的翻译规则,独立于其他组。分组翻译中的组可以包含从 1 个 ID 到数万个 ID。不允许空组。喜欢{3} => {3}
或{5, 17} => {5, 17}
允许自行翻译。ID 或组之间没有数学或其他可计算的关系,它们是任意定义的。
我正在寻找可以执行翻译的数据结构和/或搜索算法。查询组进行翻译的速度至关重要,必须为 O(1) 或非常接近。
从索引中添加或删除翻译可以在计划的维护会话中执行,并且不必非常快,尽管它必须足够快才能在最多 20%-30% 的停机时间下实际执行。
为了讨论,内存使用无关紧要。假设存储 ID 哈希表所需的相同规模的存储空间可用多次。
欢迎已知的算法、想法、建议、证明这是不可能的。