c# - 集合中的多索引，搜索时间为 O(1)

Question

假设我想制作一个具有 10 个属性的 Class 集合，该集合包含大约 1000 万个项目。

现在我想通过类的任何属性以 O(1) 时间复杂度或接近 O(1) 来搜索这个集合。（不仅仅是一个属性，即 ID 或名称）

如果我通过 LINQ 查询使用 List 而不是它，它将需要 O(n) 时间复杂度，所以它不能被使用。

C# 有字典，只能由一种键类型索引。所以也不能用。

作为一种解决方案，我可以为每个属性创建 10 个字典索引，但此解决方案将需要大量内存，因为它有 1000 万个项目。所以这将是不可行的。

PS我只想要内存解决方案（无数据库），并且可以通过类的任何单个属性搜索集合（例如 MyCollection[2] 或 MyCollection["John"] 或 MyCollection["12/12/2013"] 等）并且搜索时间必须接近 O(1)。

那么我该如何实现这种数据结构呢？

score 2 · Accepted Answer

你不能。您需要在内存或时间之间进行权衡。要么创建 10 个不同的索引（即 10 个内部字典）以获得 O(1) 查找时间，要么进行线性搜索以防止内存占用增加。

这些是你的选择。没有什么灵丹妙药可以让你两全其美。

1 回答 1