唯一的键值对集合

Question

是否有任何结构允许这两种操作：

• collection.TryGetValue(TKey, out TValue)
• collection.TryGetKey(TValue, out TKey)

在比O(n(更好的时间？

我的问题：

我基本上需要能够非常快速地检索键的值或值的键，而无需复制内存(因此两个字典是毫无疑问的(。

非常重要的注意事项：所有键都是唯一的，所有值都是唯一的。有了这些信息，我觉得应该有可能在比 O(1( 代表 .TryGetValue 和 O(n( 代表.TryGetKey更好的时间内完成这项任务。

编辑：

就我而言，我在strings和ints之间有一个映射。有 ~650,000 个文本及其 ID 的键值对。所以我基本上想获取具有特定 ID 的字符串，但也要获取某个字符串的 ID。

Answer 1

要比O(n(更好，您需要使用第二本字典。但是，正如您提到的，您正在使用结构，并且担心具有结构副本的第二个字典的内存使用情况。

解决此问题的一种方法是将结构值装箱在对象中，然后在两个字典中共享盒装对象。如果您使用继承自DictionaryBase这实际上很容易实现。

public sealed class TwoWayDictionary<TKey, TValue> : DictionaryBase
{
    Hashtable reverseLookup = new Hashtable();
    public void Add(TKey key, TValue value)
    {
        this.Dictionary.Add(key, value);
    }
    public void Remove(TKey key)
    {
        this.Dictionary.Remove(key);
    }
    public bool TryGetValue(TKey key, out TValue value)
    {
        object lookup = Dictionary[key];
        if (lookup == null)
        {
            value = default(TValue);
            return false;
        }
        else
        {
            value = (TValue)lookup;
            return true;
        }
    }
    public bool TryGetKey(TValue value, out TKey key)
    {
        object lookup = reverseLookup[value];
        if (lookup == null)
        {
            key = default(TKey);
            return false;
        }
        else
        {
            key = (TKey)lookup;
            return true;
        }
    }
    //If OnInsertComplete or OnSetComplete raises a exception DictionaryBase will 
    // roll back the operation it completed.
    protected override void OnInsertComplete(object key, object value)
    {
        reverseLookup.Add(value, key);
    }
    protected override void OnSetComplete(object key, object oldValue, object newValue)
    {
        if(reverseLookup.Contains(newValue))
            throw new InvalidOperationException("Duplicate value");
        if(oldValue != null)
            reverseLookup.Remove(oldValue);
        reverseLookup[newValue] = key;
    }
    protected override void OnRemoveComplete(object key, object value)
    {
        reverseLookup.Remove(value);
    }
}

Dictionary 和 reverseLookup 字典将共享相同的引用，因此与使用两个具有大型结构的强类型字典相比，它的内存占用量更小。

如果不编写一个完整的Dictionary<TKey, TValue>实现，该实现使用两个内部存储桶集合来存储键和值，并使用两个链表来存储存储桶的链，我认为您不会获得更好的结果。

Answer 2

你可以为key编写一些包装器，它应该包含键和链接到value包装器和包装器，value包装器应该包含值并链接到key包装器。并使用两种不同的HashSet。
在这种情况下，您可以避免内存重复。您只需要额外的内存来链接。

Answer 3

你可以做这样的事情;

Dictionary<string, string> types = new Dictionary<string, string>()
            {
                        {"1", "one"},
                        {"2", "two"},
                        {"3", "three"}
            };
            var myValue = types.FirstOrDefault(x => x.Value == "one").Key;