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

Question

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

我有一张查询表.有点像

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

因此,如果有人想要"Thing 1"或"Thing 2",他们会传递0或1.但是他们也可以传递其他内容.我有256种这类东西,其中200种是保留的.

那么最有效的想法是什么呢？

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

我对此解决方案的一个问题是所有"保留"值.我不想创建那些冗余的"保留"值.或者我可以对所有"保留"的所有地方都有一个if语句,但它们现在可能只有2-3,可能是2-3,40-55以及字节中的所有不同位置.这个if语句会变得非常快速

• 我想的另一个选择是switch语句.而且我将获得所有50个已知值并且将通过默认值保留值.

我想知道这是否比创建一个字符串数组或字典更多的处理,只是返回适当的值.

• 别的什么？还有另一种方法可以考虑吗？

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

Answer 2

在 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如果键被保留则返回 null，如果它不在表中则抛出异常——但至少现在你可以在Table.Values不过滤魔法值的情况下迭代。