logo标签列表

C#中的双向字典/双向映射？

c#.netdictionary
135

我希望以以下方式在字典中存储单词：

通过单词获取单词代码: dict["SomeWord"] -> 123，通过单词代码获取单词： dict[123] -> "SomeWord"

这可行吗？当然，一种实现方式是使用两个字典：Dictionary<string,int> 和 Dictionary<int,string>，但是否存在其他的方式？

2
截至.NET 4，没有标准数据类型可以提供O(1)的双向访问...据我所知 :) - user166390
请注意，双向映射（关键字？）会施加额外的限制，除非是多重双向映射... - user166390
2
双向词典，C#中的双向1对1词典 - user166390
15个回答
138

我写了几个快速类，可以让你做想要的事情。你可能需要通过添加更多功能来扩展它，但这是一个很好的起点。

代码的使用方式如下：

var map = new Map<int, string>();

map.Add(42, "Hello");

Console.WriteLine(map.Forward[42]);
// Outputs "Hello"

Console.WriteLine(map.Reverse["Hello"]);
//Outputs 42

以下是定义：

public class Map<T1, T2>
{
    private Dictionary<T1, T2> _forward = new Dictionary<T1, T2>();
    private Dictionary<T2, T1> _reverse = new Dictionary<T2, T1>();

    public Map()
    {
        this.Forward = new Indexer<T1, T2>(_forward);
        this.Reverse = new Indexer<T2, T1>(_reverse);
    }

    public class Indexer<T3, T4>
    {
        private Dictionary<T3, T4> _dictionary;
        public Indexer(Dictionary<T3, T4> dictionary)
        {
            _dictionary = dictionary;
        }
        public T4 this[T3 index]
        {
            get { return _dictionary[index]; }
            set { _dictionary[index] = value; }
        }
    }

    public void Add(T1 t1, T2 t2)
    {
        _forward.Add(t1, t2);
        _reverse.Add(t2, t1);
    }

    public Indexer<T1, T2> Forward { get; private set; }
    public Indexer<T2, T1> Reverse { get; private set; }
}
3
@Pedro77 - 我只是开玩笑地建议我的课堂是新的“地图”解决方案。 - Enigmativity
16
这段代码在出现异常时无法保持类的不变性。虽然 _forward.Add 可能成功，但 _reverse.Add 可能失败，导致你只添加了一半的键值对。 - user743382
5
就像我之前所说的一样，这是一个匆忙组织的课程。 - Enigmativity
4
类不变式是类的属性，对于所有有效的实例，它必须始终为真。使用该类的所有代码可以假定其为真，并且使用该类的所有代码都必须保持不变。在这里，一个有用的类不变式是“对于_forward中的每个(k,v)对，都存在一个相应的(v,k)对在_reverse中”，调用代码肯定会依赖于此。我简要说明了这个类中的方法如何导致违反这个不变式。 - user743382
4
@AaA并没有修改Forward字典属性本身（该属性有private set;），而是通过Indexer类的索引器属性来修改该字典中的值，进而将其传递给字典。public T4 this[T3 index] { get { return _dictionary[index]; } set { _dictionary[index] = value; } } 这样就破坏了正向/反向查找。 - Jeroen van Langen
显示剩余15条评论
49

遗憾的是，你需要两个字典，一个用于每个方向。不过，你可以使用LINQ轻松获取反向字典：

很抱歉，您需要两个字典，一个用于正向，另一个用于反向。不过，您可以使用LINQ轻松地获取反向字典：

Dictionary<T1, T2> dict = new Dictionary<T1, T2>();
Dictionary<T2, T1> dictInverse = dict.ToDictionary((i) => i.Value, (i) => i.Key);
1
虽然方便，但如果您经常访问逆字典，则性能不佳。每次需要时即时创建新字典的成本很高。 - Tom Bogle
@TomBogle 只是一个小细节：如果字典不会改变，那么访问它实际上不会更昂贵。我们需要在每次修改字典时更新/重新生成dictInverse，这将是昂贵的部分。 - Dani Barca Casafont
16

在Enigmativity代码的基础上进行了扩展，添加了初始化和Contains方法。

public class Map<T1, T2> : IEnumerable<KeyValuePair<T1, T2>>
{
    private readonly Dictionary<T1, T2> _forward = new Dictionary<T1, T2>();
    private readonly Dictionary<T2, T1> _reverse = new Dictionary<T2, T1>();

    public Map()
    {
        Forward = new Indexer<T1, T2>(_forward);
        Reverse = new Indexer<T2, T1>(_reverse);
    }

    public Indexer<T1, T2> Forward { get; private set; }
    public Indexer<T2, T1> Reverse { get; private set; }

    public void Add(T1 t1, T2 t2)
    {
        _forward.Add(t1, t2);
        _reverse.Add(t2, t1);
    }

    public void Remove(T1 t1)
    {
        T2 revKey = Forward[t1];
        _forward.Remove(t1);
        _reverse.Remove(revKey);
    }
    
    public void Remove(T2 t2)
    {
        T1 forwardKey = Reverse[t2];
        _reverse.Remove(t2);
        _forward.Remove(forwardKey);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    public IEnumerator<KeyValuePair<T1, T2>> GetEnumerator()
    {
        return _forward.GetEnumerator();
    }

    public class Indexer<T3, T4>
    {
        private readonly Dictionary<T3, T4> _dictionary;

        public Indexer(Dictionary<T3, T4> dictionary)
        {
            _dictionary = dictionary;
        }

        public T4 this[T3 index]
        {
            get { return _dictionary[index]; }
            set { _dictionary[index] = value; }
        }

        public bool Contains(T3 key)
        {
            return _dictionary.ContainsKey(key);
        }
    }
}

这里有一个使用案例，检查有效的括号

public static class ValidParenthesisExt
{
    private static readonly Map<char, char>
        _parenthesis = new Map<char, char>
        {
            {'(', ')'},
            {'{', '}'},
            {'[', ']'}
        };

    public static bool IsValidParenthesis(this string input)
    {
        var stack = new Stack<char>();
        foreach (var c in input)
        {
            if (_parenthesis.Forward.Contains(c))
                stack.Push(c);
            else
            {
                if (stack.Count == 0) return false;
                if (_parenthesis.Reverse[c] != stack.Pop())
                    return false;
            }
        }
        return stack.Count == 0;
    }
}
{ get { return _dictionary[index]; } set { _dictionary[index] = value; } }``` 由于这段代码，字典可以指向键值对之外的值。 - Aditya Nadig
var parent = parentMap.Reverse[pair.Key]; parentMap.Forward[parent] = <某个值>; - Aditya Nadig
10
您可以像其他人所说的那样使用两个字典，但请注意，如果 TKey 和 TValue 都是相同类型（并且它们的运行时值域已知为不相交），则您只需为每个键/值配对创建两个条目，就可以使用同一个字典：

dict["SomeWord"]= "123" 和 dict["123"]="SomeWord"

这样一来，单个字典就可以用于任何类型的查找。

3
是的，这种方法在问题中得到了承认 :) - user166390
4
这忽略了“键”和“值”中可能存在相同值的可能性。因此，在这个解决方案中会产生冲突。 - user1028741
1
@user1028741 同意，尽管从例子中看来，他们的意思是“不同类型”，而不是“相同类型”。 - Hutch
这可能导致未来重构代码时出现意外结果，例如左右两侧开始重叠。而且它几乎不会对性能产生任何影响。 - Vinigas
7

算了，我也来加入这个讨论：

public class BijectiveDictionary<TKey, TValue> 
{
    private EqualityComparer<TKey> _keyComparer;
    private Dictionary<TKey, ISet<TValue>> _forwardLookup;
    private EqualityComparer<TValue> _valueComparer;
    private Dictionary<TValue, ISet<TKey>> _reverseLookup;             

    public BijectiveDictionary()
        : this(EqualityComparer<TKey>.Default, EqualityComparer<TValue>.Default)
    {
    }

    public BijectiveDictionary(EqualityComparer<TKey> keyComparer, EqualityComparer<TValue> valueComparer)
        : this(0, EqualityComparer<TKey>.Default, EqualityComparer<TValue>.Default)
    {
    }

    public BijectiveDictionary(int capacity, EqualityComparer<TKey> keyComparer, EqualityComparer<TValue> valueComparer)
    {
        _keyComparer = keyComparer;
        _forwardLookup = new Dictionary<TKey, ISet<TValue>>(capacity, keyComparer);            
        _valueComparer = valueComparer;
        _reverseLookup = new Dictionary<TValue, ISet<TKey>>(capacity, valueComparer);            
    }

    public void Add(TKey key, TValue value)
    {
        AddForward(key, value);
        AddReverse(key, value);
    }

    public void AddForward(TKey key, TValue value)
    {
        ISet<TValue> values;
        if (!_forwardLookup.TryGetValue(key, out values))
        {
            values = new HashSet<TValue>(_valueComparer);
            _forwardLookup.Add(key, values);
        }
        values.Add(value);
    }

    public void AddReverse(TKey key, TValue value) 
    {
        ISet<TKey> keys;
        if (!_reverseLookup.TryGetValue(value, out keys))
        {
            keys = new HashSet<TKey>(_keyComparer);
            _reverseLookup.Add(value, keys);
        }
        keys.Add(key);
    }

    public bool TryGetReverse(TValue value, out ISet<TKey> keys)
    {
        return _reverseLookup.TryGetValue(value, out keys);
    }

    public ISet<TKey> GetReverse(TValue value)
    {
        ISet<TKey> keys;
        TryGetReverse(value, out keys);
        return keys;
    }

    public bool ContainsForward(TKey key)
    {
        return _forwardLookup.ContainsKey(key);
    }

    public bool TryGetForward(TKey key, out ISet<TValue> values)
    {
        return _forwardLookup.TryGetValue(key, out values);
    }

    public ISet<TValue> GetForward(TKey key)
    {
        ISet<TValue> values;
        TryGetForward(key, out values);
        return values;
    }

    public bool ContainsReverse(TValue value)
    {
        return _reverseLookup.ContainsKey(value);
    }

    public void Clear()
    {
        _forwardLookup.Clear();
        _reverseLookup.Clear();
    }
}

在其中添加一些数据：

var lookup = new BijectiveDictionary<int, int>();

lookup.Add(1, 2);
lookup.Add(1, 3);
lookup.Add(1, 4);
lookup.Add(1, 5);

lookup.Add(6, 2);
lookup.Add(6, 8);
lookup.Add(6, 9);
lookup.Add(6, 10);

然后进行查找：

lookup[2] --> 1, 6
lookup[3] --> 1
lookup[8] --> 6
1
我喜欢它支持1:N。 - Sebastian
@Sebastian，你可以添加IEnumerable<KeyValuePair<TKey, TValue>>。 - Ostati
6
6

您可以使用这个扩展方法，虽然它使用枚举，因此对于大数据集可能不太高效。如果您担心效率问题，则需要两个字典。如果您想将这两个字典封装到一个类中，请参见这个问题的已接受答案：C#中的双向1对1字典

public static class IDictionaryExtensions
{
    public static TKey FindKeyByValue<TKey, TValue>(this IDictionary<TKey, TValue> dictionary, TValue value)
    {
        if (dictionary == null)
            throw new ArgumentNullException("dictionary");

        foreach (KeyValuePair<TKey, TValue> pair in dictionary)
            if (value.Equals(pair.Value)) return pair.Key;

        throw new Exception("the value is not found in the dictionary");
    }
}
9
虽然这是一个双向字典，获取值的操作是一个O(n)的操作，而不是应该是一个O(1)的操作。对于小数据集来说可能并不重要，但是在处理大数据集时可能会导致性能问题。在空间性能方面的最佳答案是使用两个反转数据的字典。 - Tom
1
@TomA 我完全同意Tom的观点，唯一需要真正的双向字典的情况是当你有100K、1M+条目时，扫描它实际上是不必要的。 - Chris Marisic
我喜欢这个解决方案适用于我的情况（小字典大小），因为我仍然可以使用集合初始化程序。我认为在被接受的答案中，Map<A,B>不能在集合初始化程序中使用。 - CVertex
1
@ChrisMarisic，这似乎是一个奇怪的宣言。如果这个查找在一个紧密的循环中被调用，我敢打赌，即使有不到500个条目，你也会感到痛苦。这还取决于比较测试的成本。我认为像你的评论这样的笼统陈述并没有什么帮助。 - Lee Campbell
@LeeCampbell，我的概括性陈述是基于实际现实的经验，即可衡量和分析的现实。如果你想将某些复杂类型用作字典的键，那是你的问题，而不是我的问题。 - Chris Marisic
@CVertex 您可以在Map类中包含一个构造函数，它接受一个IDictionary<A, B>，这样您就只需要最小的重载来继续使用集合初始化程序 (new Map <int, string>(new Dictionary<int, string> { ... });. 有点丑，但只有一点 (; - Sebastian Werk
4

这是Xavier John答案的修改版，增加了一个额外的构造函数来接受前向和后向比较器。例如，这将支持不区分大小写的键。如果需要，可以添加更多的构造函数来将其他参数传递给前向和后向字典构造函数。

public class Map<T1, T2> : IEnumerable<KeyValuePair<T1, T2>>
{
    private readonly Dictionary<T1, T2> _forward;
    private readonly Dictionary<T2, T1> _reverse;

    /// <summary>
    /// Constructor that uses the default comparers for the keys in each direction.
    /// </summary>
    public Map()
        : this(null, null)
    {
    }

    /// <summary>
    /// Constructor that defines the comparers to use when comparing keys in each direction.
    /// </summary>
    /// <param name="t1Comparer">Comparer for the keys of type T1.</param>
    /// <param name="t2Comparer">Comparer for the keys of type T2.</param>
    /// <remarks>Pass null to use the default comparer.</remarks>
    public Map(IEqualityComparer<T1> t1Comparer, IEqualityComparer<T2> t2Comparer)
    {
        _forward = new Dictionary<T1, T2>(t1Comparer);
        _reverse = new Dictionary<T2, T1>(t2Comparer);
        Forward = new Indexer<T1, T2>(_forward);
        Reverse = new Indexer<T2, T1>(_reverse);
    }

    // Remainder is the same as Xavier John's answer:
    // https://dev59.com/t2gu5IYBdhLWcg3w8Lav#41907561
    ...
}

一个不区分大小写的键的使用示例：

Map<int, string> categories = 
new Map<int, string>(null, StringComparer.CurrentCultureIgnoreCase)
{
    { 1, "Bedroom Furniture" },
    { 2, "Dining Furniture" },
    { 3, "Outdoor Furniture" }, 
    { 4, "Kitchen Appliances" }
};

int categoryId = 3;
Console.WriteLine("Description for category ID {0}: '{1}'", 
    categoryId, categories.Forward[categoryId]);

string categoryDescription = "DINING FURNITURE";
Console.WriteLine("Category ID for description '{0}': {1}", 
    categoryDescription, categories.Reverse[categoryDescription]);

categoryDescription = "outdoor furniture";
Console.WriteLine("Category ID for description '{0}': {1}", 
    categoryDescription, categories.Reverse[categoryDescription]);

// Results:
/*
Description for category ID 3: 'Outdoor Furniture'
Category ID for description 'DINING FURNITURE': 2
Category ID for description 'outdoor furniture': 3
*/
2

这是我的代码。除了种子构造函数之外，一切都是O(1)。

using System.Collections.Generic;
using System.Linq;

public class TwoWayDictionary<T1, T2>
{
    Dictionary<T1, T2> _Forwards = new Dictionary<T1, T2>();
    Dictionary<T2, T1> _Backwards = new Dictionary<T2, T1>();

    public IReadOnlyDictionary<T1, T2> Forwards => _Forwards;
    public IReadOnlyDictionary<T2, T1> Backwards => _Backwards;

    public IEnumerable<T1> Set1 => Forwards.Keys;
    public IEnumerable<T2> Set2 => Backwards.Keys;


    public TwoWayDictionary()
    {
        _Forwards = new Dictionary<T1, T2>();
        _Backwards = new Dictionary<T2, T1>();
    }

    public TwoWayDictionary(int capacity)
    {
        _Forwards = new Dictionary<T1, T2>(capacity);
        _Backwards = new Dictionary<T2, T1>(capacity);
    }

    public TwoWayDictionary(Dictionary<T1, T2> initial)
    {
        _Forwards = initial;
        _Backwards = initial.ToDictionary(kvp => kvp.Value, kvp => kvp.Key);
    }

    public TwoWayDictionary(Dictionary<T2, T1> initial)
    {
        _Backwards = initial;
        _Forwards = initial.ToDictionary(kvp => kvp.Value, kvp => kvp.Key);
    }


    public T1 this[T2 index]
    {
        get => _Backwards[index];
        set
        {
            if (_Backwards.TryGetValue(index, out var removeThis))
                _Forwards.Remove(removeThis);

            _Backwards[index] = value;
            _Forwards[value] = index;
        }
    }

    public T2 this[T1 index]
    {
        get => _Forwards[index];
        set
        {
            if (_Forwards.TryGetValue(index, out var removeThis))
                _Backwards.Remove(removeThis);

            _Forwards[index] = value;
            _Backwards[value] = index;
        }
    }

    public int Count => _Forwards.Count;

    public bool Contains(T1 item) => _Forwards.ContainsKey(item);
    public bool Contains(T2 item) => _Backwards.ContainsKey(item);

    public bool Remove(T1 item)
    {
        if (!this.Contains(item))
            return false;

        var t2 = _Forwards[item];

        _Backwards.Remove(t2);
        _Forwards.Remove(item);

        return true;
    }

    public bool Remove(T2 item)
    {
        if (!this.Contains(item))
            return false;

        var t1 = _Backwards[item];

        _Forwards.Remove(t1);
        _Backwards.Remove(item);

        return true;
    }

    public void Clear()
    {
        _Forwards.Clear();
        _Backwards.Clear();
    }
}
1
我想知道如果你传递一个已经存在的字典给构造函数，其中键和值类型相同，它会如何表现。它将如何解决使用向后还是向前的方式？ - Colm Bhandal
1
error CS0121: The call is ambiguous between the following methods or properties: 'TwoWayDictionary<T1, T2>.TwoWayDictionary(Dictionary<T1, T2>)' and 'TwoWayDictionary<T1, T2>.TwoWayDictionary(Dictionary<T2, T1>)' - Graham
1

这是一个老问题，但我想添加两个扩展方法，以防有人发现它有用。第二个不太有用，但如果需要支持一对一的字典，则它提供了一个起点。

    public static Dictionary<VALUE,KEY> Inverse<KEY,VALUE>(this Dictionary<KEY,VALUE> dictionary)
    {
        if (dictionary==null || dictionary.Count == 0) { return null; }

        var result = new Dictionary<VALUE, KEY>(dictionary.Count);

        foreach(KeyValuePair<KEY,VALUE> entry in dictionary)
        {
            result.Add(entry.Value, entry.Key);
        }

        return result;
    }

    public static Dictionary<VALUE, KEY> SafeInverse<KEY, VALUE>(this Dictionary<KEY, VALUE> dictionary)
    {
        if (dictionary == null || dictionary.Count == 0) { return null; }

        var result = new Dictionary<VALUE, KEY>(dictionary.Count);

        foreach (KeyValuePair<KEY, VALUE> entry in dictionary)
        {
            if (result.ContainsKey(entry.Value)) { continue; }

            result.Add(entry.Value, entry.Key);
        }

        return result;
    }
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接