什么是最适合这个内存查找表的数据结构？

Question

我需要在我的一个类中将查找表作为实例成员进行存储。该表将在对象构造时初始化。每个“行”将有3个“列”：

StringKey (e.g., "car")
EnumKey (e.g., LookupKeys.Car)
Value (e.g, "Ths is a car.")

我希望选择最适合按StringKey或EnumKey进行查找的数据结构，以获得最佳性能。

对于同一个字典值有两个键有点尴尬。我以前从未遇到过这种情况，所以想知道这种情况的常规做法是什么。

我可以使用Key/Value/Value结构而不是Key/Key/Value结构，但我想知道这样做会对性能产生什么影响。

我的想法是否正确？

- vg1890

Answer 1

嗯... " 错误 " 是一个严厉的说法。我认为这是因为最常见的字典是 " 单个键对应值 "，并且大量的工作都用于为此提供高效的数据结构 ( 映射 ) ，因此通常最好只使用其中的两个，如果可能的话，共享值的内存。

- unwind

Answer 2

你有两个哈希映射表。

• 一个是从StringKey到value的映射。

• 一个是从EnumKey到value的映射。

你不必复制所有Value实例，这些对象可以在两个哈希映射表之间共享。

如果有很多项，你可能需要使用两个树映射表而不是两个哈希映射表。但基本原则（“共享Values”）适用于两种结构。一个Values集合，两个映射表。

- S.Lott

---

好的 - 所以在我的例子中，“value instances”只是字符串。我将创建2个字典（一个使用StringKey，一个使用EnumKey），它们的值包含相同的字符串引用变量。听起来没问题吗？ - Rob Sobers

没错，在Python中就是这样。在Java中，有一个string.intern()函数可以确保所有intern()的字符串都被减少到一个公共字符串池中，消除了一些可能的冗余。 - S.Lott

我正在使用C#...你知道当我将字符串添加到每个字典中时，.NET是否会复制它？ - Rob Sobers

为每个字典添加一个引用。字符串只存在一次。对于一个字符串有多个引用。 - S.Lott

明白了。字典会获得对字符串的自己的引用，但它们都指向同一个字符串对象。string s = "joe"; dct1.Add("key", s); -- 即使传递的参数被称为s，dct1.Add也会获得对"joe"的自己的引用。谢谢！ - Rob Sobers

Answer 3

真的有必要用两种类型的键输入相同的结构吗？如果内存不是问题，你可能不需要自己重新构建一个复杂的数据结构。你可以对查找表进行某种封装，这样你就真的有了两个查找表。你可以使用这个封装结构来模拟能够从“相同”结构中使用任一类型的键提取值。

或者

如果有一种方法可以将枚举值和字符串键进行映射，你可以选择这种方式，只使用一种类型的查找表。

- Brad Barker

Answer 4

LINQ的ILookup(TKey, TElement)接口可能会有所帮助。假设您的字典类似于：

Dictionary<carKey, carValue> cars;

你可以使用：

ILookUp<carValue, carKey> lookup = cars.ToLookup(x => x.Value, x => x.Key);

（...实际上我认为我可能稍微误读了问题 - 但是 ILookUp 可能仍然适合，但键/值集可能需要是键和枚举。）

- Joan Miro

Answer 5

如果每个值都保证可以通过两种类型的键访问，另一个想法是将一种类型的键转换为另一种类型。例如：

public Value getValue(String key)
{
    dictionary.get(key); // normal way
}

public Value getValue(Enum enumKey)
{
    String realKey = toKey(enumKey);
    getValue(realKey); // use String key
}

您可以让枚举实现一个toKey()方法，以返回它们的字符串键，或者可能有另一个字典将枚举值映射到字符串对应项。

- Outlaw Programmer