在C#中，最高效的查找表方法是什么？

Question

如何在C＃中实现最有效的查找表？

我有一个查找表。类似于：

0 "Thing 1"
1 "Thing 2"
2 "Reserved"
3 "Reserved"
4 "Reserved"
5 "Not a Thing"

如果有人想要“物品1”或“物品2”，则传入0或1。但他们也可能传入其他内容。 我有256个这样的东西，其中大约有200个是保留的。

那么最有效的设置方式是什么？

一个字符串数组或字典变量获取所有值。然后取整数并返回该位置处的值。

我对此解决方案有一个问题，即所有“保留”值都会产生冗余。否则，我可以针对所有“保留”的各种位置设置if语句，但它们可能只是2-3个，也可能是2-3个、40-55个和字节中的所有不同位置。这个if语句很快就会变得难以管理。

我的另一个选择是switch语句。我将拥有所有50多个已知值，并会通过并为保留值设置默认值。

我想知道这是否比创建字符串数组或字典并返回适当的值要耗费更多的处理时间。

还有其他方法吗？有其他考虑方式吗？

- Maestro1024

---

你想要做什么，性能差异为什么如此重要？ - Paco

Answer 1

"通过使用其键检索值非常快，接近O(1)，因为Dictionary(TKey, TValue)类是实现为哈希表的。"

var things = new Dictionary<int, string>();
things[0]="Thing 1";
things[1]="Thing 2";
things[4711]="Carmen Sandiego";

- Jonas Elfström

---

O(1)并不代表算法一定快，它只是意味着执行时间是恒定的。一个O(N)的算法可能会更快。这是一个常见的误解。 - 0b101010

但这不是下注的方式。不过，如果性能如此重要，请测试您的确切场景。 - PRMan

Answer 2

在C#中进行整数值查找的绝对最快方法是使用数组。如果您要一次性进行成千上万次的查找，那么这将优于使用字典。对于大多数情况来说，这是过度设计；更有可能的是您需要优化开发人员的时间而不是处理器时间。

如果保留的键不仅仅是不在查找表中的所有键（例如，如果针对关键字的查找可以返回找到的值、未找到状态或保留状态），则需要将保留的键保存在某个地方。将其保存为具有魔术值的字典条目（例如，其值为null的任何字典条目的键都是保留的）是可以的，除非您编写了遍历字典条目而没有对其进行筛选的代码。

解决该问题的方法是使用单独的 HashSet 来存储保留的键，也许将整个内容制作成一个类，如下所示：

public class LookupTable
{
   public readonly Dictionary<int, string> Table { get; }
   public readonly HashSet<int> ReservedKeys { get; }

   public LookupTable()
   {
      Table = new Dictionary<int, string>();
      ReservedKeys = new HashSet<int>();
   }

   public string Lookup(int key)
   {
      return (ReservedKeys.Contains(key))
         ? null
         : Table[key];
   }
}

注意，这种方法仍然存在魔法值的问题 - 如果键是保留的，则Lookup返回null；如果不在表中，则会抛出异常 - 但至少现在你可以遍历Table.Values而无需筛选魔法值。

- Robert Rossney

---

这不是真的。虽然数组访问和迭代可能很快，但如果您可以直接比较两个元素并且a > b > c --> a > c成立，则加权树更快。 - FalcoGer

Answer 3

如果您有很多保留的（当前未使用的）值，或者整数值的范围可能非常大，则建议使用通用字典（Dictionary）：

var myDictionary = new Dictionary<int, string>();
myDictionary.Add(0, "Value 1");
myDictionary.Add(200, "Another value");
// and so on

否则，如果你有一定数量的值且只有少量未被使用，那么我建议使用字符串数组（string[200]），并将保留的条目设置/保留为空。

var myArray = new string[200];
myArray[0] = "Value 1";
myArray[2] = "Another value";
//myArray[1] is null

- M4N

Answer 4

了解一下HybridDictionary。它会根据大小自动调整其底层存储机制，以获得最大效率。

http://msdn.microsoft.com/en-us/library/system.collections.specialized.hybriddictionary.aspx

- Corey Coogan

---

HybridDictionary 不是强类型 / 泛型的 (集合中的所有内容都存储为对象)，这可能会导致大量的类型转换（除非您创建一个包装器来处理它）。 - M4N

非常酷的类，我之前不知道。MSDN指出，“当字典中元素数量未知时推荐使用该类”。看起来Maestro1024知道元素数量，所以我猜Maestro1024应该在Hashtable和ListDictionary之间进行选择。 - Eddie

Answer 5

将所有的值加载进来

var dic = new Dictionary<int, string>();

并使用此进行检索：

string GetDescription(int val)
{
     if(0 <= val && val < 256)
        if(!dic.Contains(val))
           return "Reserved";
        return dic[val];
    throw new ApplicationException("Value must be between 0 and 255");
}

- Manu

---

你应该使用dic.TryGetValue而不是dic.Contains，因为它更高效。 - gimlichael

Answer 6

内置的字典对象（最好是通用字典）非常适合此类问题，并且专门设计用于快速/高效地检索与键相关的值。

从链接的MSDN文章中可以看到：

通过使用其键检索值非常快，接近O（1），因为Dictionary<(Of <(TKey, TValue>)>)类实现为哈希表。

至于您的“保留”键，如果我们只谈论几百个键/值，那么我不会担心这个问题。只有当您达到数万甚至数十万个“保留”键/值时，您才需要实现更有效的方法。

在这些情况下，可能最有效的存储容器是稀疏矩阵的实现。

- CraigTP

Answer 7

我不太确定我正确理解了你的问题。你有一组字符串，每个字符串都与一个索引相关联。消费者请求给出一个索引，然后你返回相应的字符串，除非该索引是保留的。对吗？

如果可以的话，你可以将保留项简单地设置为数组中的null。

如果不行，使用一个不包含保留项的字典似乎是一个合理的解决方案。

无论如何，如果你能澄清你的问题，你可能会得到更好的答案。

- Serge Wautier

Answer 8

我会使用字典来进行查找。这是迄今为止最有效的查找方法。使用字符串查找对象的运行时间大约为O(n)。

如果需要，建立第二个字典进行逆向查找可能非常有用。

- AutomatedTester

Answer 9

你的问题似乎意味着查询键是一个整数。由于你最多只有256个项目，那么查询键在0..255范围内，对吗？如果是这样，只需使用包含256个字符串的字符串数组，并将键用作数组中的索引。

如果你的查询键是一个字符串值，那么它更像是一个真正的查找表。使用Dictionary对象很简单，但如果你想要获得一组少至50个实际答案的原始速度，那么自己编写二分查找或trie等方法可能更快。如果你使用二分查找，由于项目数量非常少，你可以展开它。

列表项有多经常更改？如果它只更改得非常少，你甚至可以通过生成代码来执行搜索，然后编译并执行每个查询来获得更好的速度。

另一方面，我假设您已经通过分析或 堆栈跟踪 证明了此查找是您的瓶颈。如果慢时所需时间少于10％用于此查询，则它 不是 您的瓶颈，因此您可以随便编写最容易的代码。

- Mike Dunlavey