c# - 如何优化每个不同值具有多个键的字典？

Question

我有一组相对较大的数据，它们非常自然地适合 C# 的字典对象。目前，我有 102400 个键值对，它们在程序启动时半动态生成。我的问题是我必须尽快运行大量查找操作。

根据This Page查找速度直接受字典中键值对数量的影响。我的数据有点奇怪，因为大量不同的键导致相同的值。事实上，我只有 4900 个不同的值...这意味着每个不同的值平均有 20 个键值对。

我的第一直觉是将键交换为值(因为我只关心数据中的不同值)，然后将列表或数组中的旧键作为新值。这将我的字典大小从 102400 个键值对减少到 4900 个，但我看不到任何方法可以有效地在所有列表中搜索特定值来获取键。

我知道当我切换键和值时，我的描述可能有点难以理解，因此我添加了一个数据模型来向您展示我的意思:

旧方法:

Key   Value
---   -----
1     1
2     2
3     3
4     1
5     3
6     2
7     2
8     1
9     3
10    2
11    3
12    1

新结构:

Key   Value
---   -----
1     {1,4,8,12}
2     {2,6,7,10}
3     {3,9,5,11}

在我的程序中，我将得到“11”，我需要返回“3”。第一个结构是一个简单的查找，但是是一个巨大的列表，这似乎会减慢速度......第二个结构增加了很多逻辑开销来跟踪我正在寻找的值列表，我只看到了减少尝试实现它的速度。

我是不是找错树了？我应该接受较大列表的速度，还是有其他方法可以存储数据以提高查找速度？

Answer 1

如果所有键都是不同且连续的，那么您应该考虑一个简单的数组；如果键不连续，则为 HashMap 类型的结构(如果不连续)。如果散列函数很好的话，这将接近 O(1)，并且如果它们都是整数，则不会占用太多空间。

即使如此，对于 102400 个元素，二叉树查找每次查找最多需要 log2(102400) 次操作，即 16.64 次操作，速度并不慢。