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

"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."

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

在C#中查找整数值最快的方法是使用数组。如果您试图一次进行成千上万次的查找,那么这可能比使用字典更好。在大多数情况下,这是过分的;您更可能需要优化开发人员时间而不是处理器时间。

如果保留键不仅仅是不在查找表中的所有键(即,如果键的查找可以返回找到的值、未找到状态或保留状态),则需要将保留键保存在某个位置。将它们保存为具有魔法值的字典条目(例如,保留值为null的任何字典条目的键)是可以的,除非您编写代码,在不过滤字典条目的情况下对其进行迭代。

解决这个问题的一种方法是使用单独的 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];
   }
}

您会注意到,这仍然存在神奇的价值问题- Lookup Table.Values 没有过滤魔法值。

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

如果您有很多保留(当前未使用)值,或者如果整数值的范围非常大,那么我将使用通用字典(dictionary):

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

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

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

内置的 Dictionary 对象(最好是一个通用字典)将是实现这一点的理想选择,并且专门设计用于快速/高效地检索与键相关的值。

从链接的MSDN文章:

使用某个值的键检索该值是非常困难的 字典<(属于<(TKey,TValue>)>) 类作为哈希表实现。

就您的“保留”键而言,如果我们只讨论几百个键/值,我根本不会担心这一点。只有当您达到数十个,甚至数十万个“保留”键/值时,您才会希望实现更高效的功能。

在这些情况下,最有效的存储容器可能是 Sparse Matrix .

我不太确定我是否正确理解了你的问题。您有一个字符串集合。每个字符串都与一个索引相关联。使用者请求提供一个索引,您返回相应的字符串,除非索引是 含蓄的 . 对吗?

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

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

不管怎样,如果你能澄清你的问题,你可能会得到更好的答案。

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

如果需要的话,可以使用第二本字典来进行反向查找

将所有值加载到

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

您的问题似乎暗示查询键是一个整数。因为您最多有256个项目,所以查询键的范围是0..255,对吗?如果是这样的话,只需要拥有一个256个字符串的字符串数组,并使用该键作为数组的索引。

如果查询键是字符串值,那么它更像是一个真正的查找表。使用Dictionary对象很简单,但如果您想要获得一组只有50个左右的实际答案的原始速度,则使用自己动手的方法(如二进制搜索或trie)可能会更快。如果使用二进制搜索,由于项目数很小,可以展开它。

项目列表多久更改一次?如果它很少更改,则可以通过生成代码来执行搜索来获得更快的速度,然后可以编译和执行代码来执行每个查询。

另一方面,我假设您已经通过分析或验证证明了此查找是您的瓶颈 taking stackshots 你的瓶颈,所以你可以做的事情是最容易编码。