c# - 独特的键值对集合

Question

是否有任何结构允许BOTH这些操作:

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

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

我的问题:

我基本上需要能够非常快地检索键的值或值的键，而不会复制内存(所以两个字典是不可能的)。

非常重要的注意事项:所有的键都是唯一的，所有的值也是唯一的。有了这些信息，我感觉应该可以在比 .TryGetValue 的 O(1) 和 的 O(n) 更短的时间内完成此任务。 TryGetKey.

编辑:

在我的例子中，我有一个 strings 和 ints 之间的映射。文本及其 ID 大约有 650,000 个键值对。所以我基本上想获得具有特定 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>使用两个内部存储桶集合存储键和值，并使用两个链表存储存储桶链的实现，我认为您不会获得更好的结果。