[C#]实现双字典的最有效方法 [英] [C#] Most efficient way to implement dual-Dictionary

问题描述

我猜想.NET Framework中没有这样的数据结构吗?该怎么办?两个字典还是两个哈希表?你会推荐什么.总的来说，我需要Map ，它可以有效地按值和按值查找键(匹配是在连接ID与客户端ID之间进行的匹配，因此这对我们中的数学家来说是一项内在的功能. .)

I guess that there isn''t such a data structure in the .NET Framework? What should do the trick? Two Dictionaries, or Two Hashtables? What would you recommend. In General, I need something Map<t1,t2>, that can find efficiently both key by value and value by key (The match is between a connection ID to a client ID, so its an injective function for the mathematicians among us...)

推荐答案

是的，最简单的实现方法是两个字典:System.Collections.Generic.Dictionary<ConnectionId, ClientId>和System.Collections.Generic.Dictionary<ClientId, ConnectionId>(假设您的两种ID类型不同)，参见 http://msdn.microsoft.com/en-us/library/xfhwa508.aspx [ ^ ].

当然，将它们封装在一个类中并使字典本身不可访问，仅公开通过两个键在Add，Remove，Get，TryGet两个字典字段上实现的方法，等等. >
当然，这种方法仅对单打功能有效，因为字典通过键保留唯一性，并且您需要在两个方向上通过键进行搜索.

您将拥有针对大集合的O(1)搜索算法，该算法足够有效:-)也许对于这样的双向字典，您也可以实现更好的内存开销，但前提是您是从头开始创建算法的. >

—SA

Yes, the simplest way to achieve that is two dictionaries: System.Collections.Generic.Dictionary<ConnectionId, ClientId> and System.Collections.Generic.Dictionary<ClientId, ConnectionId> (assuming your two type for those IDs are different), see http://msdn.microsoft.com/en-us/library/xfhwa508.aspx[^].

Of course, encapsulate them in one class and make the dictionaries themselves non-accessible, only expose methods implemented on both dictionary fields: Add, Remove, Get, TryGet by both keys, etc.

And of course this approach will be only valid for an injective functions as dictionary preserves uniqueness by a key, and you need search by key in both directions.

You will have search algorithm of O(1) for big collections, which is effective enough :-) Perhaps you also could achieve some better memory overhead for such two-way dictionary, but only if you created the algorithm from scratch.

—SA

28/10/11:进行了较小的编辑，以使内容更清晰，并修复了使List声明成为注释部分的代码示例中缺少的CRLF .
...

我的感觉是SAK明确回答了这个问题，但我会得出一个推论:当我尝试使用这种镜像"对偶字典时，我发现自己在质疑是否可以执行相同的任务(按键或值查找)就像使用具有某些可能的战略附加值的通用列表一样有效:使用两个列表，消除了在镜像"字典中具有重复键的可能错误.

一个示例(从Linq之前的日子开始):

28/10/11: minor edit for clarity, and to fix a missing CRLF in the code sample that made the List declaration part of a comment.
...

My sense is that SAK has definitively answered this question, but I will add a corollary: back when I was experimenting with such ''mirrored'' dual dictionaries, I found myself questioning if the same task (lookup by key or value) could be just as efficiently done using generic Lists with some possible strategic additional value: using two Lists, eliminates the possible errors of having duplicate keys in the ''mirror'' dictionary.

An example (from pre-Linq days):

// note: duplicates used deliberately
List<int> theKeys = new List<int>() { 3, 4, 7, 1, 2, 5, 6, 2 };
//
List<string> theValues = new List<string>() { "three", "four", "seven", "one", "two", "five", "six", "two" };

private string findByKey(int theKey)
{
    return theKeys.Contains(theKey) ? theValues[theKeys.IndexOf(theKey)] : null;
}

private int? findByValue(string theValue)
{
    // note the hack here in order
    // to be able to return null
    // in the case of a 'fail
    int? result = null;

    if (theValues.Contains(theValue)) result = theKeys[theValues.IndexOf(theValue)];

    return result;
}

一个超出范围的值的示例测试(验证是否返回了null):

A sample test for out-of-bounds values (verify nulls are being returned):

string theString = findByKey(77);
int? theInt = findByValue("magic");

现在我们在Linq中感到窒息"荣耀，有一天，我将重新访问该实验，着眼于使用Linq实现select first，last，multiple等.

现在，使用这种解决方案的成本"当然必须包括正确填写镜像"列表.我仍然非常喜欢使用.NET Dictionaries！

Now that we are smothered in Linq''s glory, I will, someday, re-visit this experiment, looking at using Linq to implement select first, last, multiples, etc.

Now the "cost" of using this type of solution, of course, has to include filling the ''mirrored'' Lists properly. I still really enjoy messing around with .NET Dictionaries !

这篇关于[C#]实现双字典的最有效方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！