在 C# 中进行查找表的最有效方法是什么

What is the most efficient way to do look-up table in C#

提问by Maestro1024

What is the most efficient way to do look-up table in C#

在 C# 中进行查找表的最有效方法是什么

I have a look-up table. Sort of like

我有一个查找表。有点像

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

So if someone wants "Thing 1" or "Thing 2" they pass in 0 or 1. But they may pass in something else also. I have 256 of these type of things and maybe 200 of them are reserved.

因此，如果有人想要“事物 1”或“事物 2”，他们会传入 0 或 1。但他们也可能会传入其他内容。我有 256 件这样的东西，其中可能有 200 件是保留的。

So what is the most efficient want to set this up?

那么什么是最有效的设置呢？

• A string Array or dictionary variable that gets all of the values. And then take the integer and return the value at that place.

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

One problem I have with this solution is all of the "Reserved" values. I don't want to create those redundant "reserved" values. Or else I can have an if statement against all of the various places that are "reserved" but they might now be just 2-3, might be 2-3, 40-55 and all different places in the byte. This if statement would get unruly quick

我在此解决方案中遇到的一个问题是所有“保留”值。我不想创建那些多余的“保留”值。否则，我可以对所有“保留”的各个位置进行 if 语句，但它们现在可能只是 2-3，可能是 2-3、40-55 以及字节中的所有不同位置。这个 if 语句会很快变得不守规矩

• My other option that I was thinking was a switch statement. And I would have all of the 50ish known values and would fall through through and default for the reserved values.

• 我正在考虑的另一个选项是 switch 语句。而且我将拥有所有 50 左右的已知值，并且会失败并默认保留值。

I am wondering if this is a lot more processing than creating a string array or dictionary and just returning the appropriate value.

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

• Something else? Is there another way to consider?

• 还有什么？有没有其他方法可以考虑？

采纳答案by Jonas Elfstr?m

"Retrieving a value by using its key is very fast, close to O(1), because the Dictionary(TKey, TValue) class is implemented as a hash table."

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

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

回答by M4N

If you have lots of reserved (currently unused) values or if the range of the integer values can get very big, then I would use a generic dictionary (Dictionary):

如果您有很多保留的（当前未使用的）值，或者整数值的范围可能变得很大，那么我将使用通用字典（Dictionary）：

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

Otherwise, if you have a fixed number of values and only few of the are currently unused, then I'd use a string array (string[200]) and set/leave the reserved entries to null.

否则，如果您有固定数量的值并且只有少数当前未使用，那么我将使用字符串数组 (string[200]) 并将保留条目设置/保留为空。

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

回答by CraigTP

The in-built Dictionaryobject (preferably a generic dictionary) would be ideal for this, and is specifically designed for fast/efficient retrieval of the values relating to the keys.

内置的Dictionary对象（最好是通用字典）将是理想的选择，并且专门设计用于快速/高效地检索与键相关的值。

From the linked MSDN article:

来自链接的 MSDN 文章：

Retrieving a value by using its key is very fast, close to O(1), because the Dictionary<(Of <(TKey, TValue>)>) class is implemented as a hash table.

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

As far as your "reserved" keys go, I wouldn't worry about that at all if we're only talking about a few hundred keys/values. It's only when you reach tens, maybe hundreds of thousands of "reserved" keys/values that you'll want to implement something more efficient.

就您的“保留”键而言，如果我们只讨论几百个键/值，我根本不会担心。只有当您达到数十个甚至数十万个“保留”键/值时，您才会想要实现更有效的东西。

In those cases, probably the most efficient storage container then would be an implementation of a Sparse Matrix.

在这些情况下，最有效的存储容器可能是Sparse Matrix的实现。

回答by Serge Wautier

I'm not quite sure I understand your problem correctly. You have a collection of strings. Each string is associated to an index. The consumer requests gives an index and you return the corresponding string, unless the index is reserved. Right?

我不太确定我是否正确理解您的问题。你有一个字符串的集合。每个字符串都与一个索引相关联。消费者请求给出一个索引，你返回相应的字符串，除非索引是reserved。对？

Can't you simple set reserved items as null in the array.

您不能简单地将数组中的保留项设置为 null。

If not, using a dictionary that doesn't contain the reserved items seems a reasonable solution.

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

Anyway, you'll probably get better answers if you clarify your problem.

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

回答by Manu

Load all your values into

将所有值加载到

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

And use this for retrieval:

并将其用于检索：

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");
}

回答by AutomatedTester

I would use a Dictionary to do the lookups. This is the most efficient way to do look ups by far. Using a string will run somewhere in the region of O(n) to find the object.

我会使用字典来进行查找。这是迄今为止最有效的查找方式。使用字符串将在 O(n) 区域的某处运行以查找对象。

It might be useful to have a 2nd Dictionary to all you to do a reverse lookup if its needed

如果需要，为所有人提供第二个字典进行反向查找可能会很有用

回答by Corey Coogan

Checkout the HybridDictionary. It automatically adjusts it's underlying storage mechanism based on size to get the greatest efficiency.

查看 HybridDictionary。它会根据大小自动调整其底层存储机制，以获得最大的效率。

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

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

回答by Robert Rossney

The absolute fastest way to do lookups of integer values in C# is with an array. This will be preferable to using a dictionary, maybe, if you are trying to do tens of thousands of lookups at a time. For most purposes, this is overkill; it's more likely that you need to optimize developer time than processor time.

在 C# 中查找整数值的绝对最快方法是使用数组。如果您尝试一次进行数万次查找，这可能比使用字典更可取。对于大多数目的，这是矫枉过正；与处理器时间相比，您更有可能需要优化开发人员时间。

If the reserved keys are not simply all keys that aren't in the lookup table (i.e. if a lookup for a key can return the found value, a not-found status, or a reserved status), you'll need to save the reserved keys somewhere. Saving them as dictionary entries with magic values (e.g. the key of any dictionary entry whose value is null is reserved) is OK unless you write code that iterates over the dictionary's entries without filtering them.

如果保留键不是所有不在查找表中的键（即，如果对键的查找可以返回找到的值、未找到的状态或保留的状态），则需要保存某处保留的密钥。将它们保存为具有魔法值的字典条目（例如，保留值为 null 的任何字典条目的键）是可以的，除非您编写代码来遍历字典条目而不对其进行过滤。

A way to solve that problem is to use a separate HashSet<int>to store the reserved keys, and maybe bake the whole thing into a class, e.g.:

解决这个问题的一种方法是使用一个单独的HashSet<int>来存储保留的键，并且可能将整个事物烘焙到一个类中，例如：

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];
   }
}

You'll note that this still has the magic-value issue - Lookupreturns null if the key is reserved, and throws an exception if it's not in the table - but at least now you can iterate over Table.Valueswithout filtering magic values.

您会注意到这仍然存在魔法值问题——Lookup如果键被保留则返回 null，如果它不在表中则抛出异常——但至少现在你可以在Table.Values不过滤魔法值的情况下迭代。

回答by Mike Dunlavey

Your question seems to imply that the query key is an integer. Since you have at most 256 items, then the query key is in the range 0..255, right? If so, just have a string array of 256 strings, and use the key as an index into the array.

您的问题似乎暗示查询键是一个整数。既然您最多有 256 个项目，那么查询键在 0..255 范围内，对吗？如果是这样，只需有一个包含 256 个字符串的字符串数组，并将键用作数组的索引。

If your query key is a string value, then it's more like a real lookup table. Using a Dictionary object is simple, but if you're after raw speed for a set of as few as 50 or so actual answers, a do-it-yourself approach such as binary search, or a trie, could be quicker. If you use binary search, since the number of items is so small, you could unroll it.

如果您的查询键是字符串值，那么它更像是一个真正的查找表。使用 Dictionary 对象很简单，但是如果您对一组少至 50 个左右的实际答案追求原始速度，那么自己动手的方法（例如二分搜索或 trie）可能会更快。如果您使用二分搜索，由于项目数量很少，您可以展开它。

How often does the list of items change? If it only changes very seldom, you can get even better speed by generating code to do the search, which you can then compile and execute to do each query.

项目列表多久更改一次？如果它只是很少改变，您可以通过生成代码来执行搜索来获得更快的速度，然后您可以编译并执行这些代码来执行每个查询。

On the other hand, I assume you've proven that this lookup is your bottleneck, either by profiling or taking stackshots. If less than 10% of time-when-slow is spent in this query, then it is notyour bottleneck so you may as well do the thing that is easiest to code.

另一方面，我假设您已经通过分析或获取 stackshots证明了此查找是您的瓶颈。如果在这个查询中花费的 time-when-slow 少于 10%，那么这不是你的瓶颈，所以你最好做最容易编码的事情。