代码之家  ›  专栏  ›  技术社区  ›  AaronLS

组合键字典

  •  73
  • AaronLS  · 技术社区  · 15 年前

    我有一些物品在清单上,比如说 List<MyClass> MyClass有几个属性。我想基于MyClass的3个属性创建列表的索引。在这种情况下,2个属性是int的,一个属性是datetime。

    基本上,我希望能够做如下的事情:

    Dictionary< CompositeKey , MyClass > MyClassListIndex = Dictionary< CompositeKey , MyClass >();
    //Populate dictionary with items from the List<MyClass> MyClassList
    MyClass aMyClass = Dicitonary[(keyTripletHere)];
    

    我有时会在一个列表上创建多个字典,以索引它所持有的类的不同属性。不过,我不知道如何最好地处理组合键。我考虑对这三个值进行校验和,但这会带来碰撞的风险。

    9 回复  |  直到 8 年前
        1
  •  92
  •   Eldritch Conundrum    8 年前

    你应该使用元组。它们等价于compositekey类,但是equals()和gethashcode()已经为您实现。

    var myClassIndex = new Dictionary<Tuple<int, bool, string>, MyClass>();
    //Populate dictionary with items from the List<MyClass> MyClassList
    foreach (var myObj in myClassList)
        myClassIndex.Add(Tuple.Create(myObj.MyInt, myObj.MyBool, myObj.MyString), myObj);
    MyClass myObj = myClassIndex[Tuple.Create(4, true, "t")];
    

    或使用System.Linq

    var myClassIndex = myClassList.ToDictionary(myObj => Tuple.Create(myObj.MyInt, myObj.MyBool, myObj.MyString));
    MyClass myObj = myClassIndex[Tuple.Create(4, true, "t")];
    

    除非需要自定义哈希的计算,否则使用元组更简单。

    如果您希望在复合键中包含许多属性,则元组类型名称可能会变得相当长,但您可以通过创建从元组派生的类来缩短名称。


    ** 2017编辑 **

    有一个新的选择,从C 7开始: 值元组 . 想法相同,但语法不同,更轻:

    类型 Tuple<int, bool, string> 变成 (int, bool, string) 和价值 Tuple.Create(4, true, "t") 变成 (4, true, "t") .

    对于值元组,也可以命名元素。请注意,性能略有不同,因此如果它们对您很重要,您可能需要进行一些基准测试。

        2
  •  21
  •   Jon Allen E. Scharfenberg    9 年前

    我能想到的最好方法是创建一个复合键结构和 确保 要重写getHashCode()和equals()方法,以确保使用集合时的速度和准确性,请执行以下操作:

    class Program
    {
        static void Main(string[] args)
        {
            DateTime firstTimestamp = DateTime.Now;
            DateTime secondTimestamp = firstTimestamp.AddDays(1);
    
            /* begin composite key dictionary populate */
            Dictionary<CompositeKey, string> compositeKeyDictionary = new Dictionary<CompositeKey, string>();
    
            CompositeKey compositeKey1 = new CompositeKey();
            compositeKey1.Int1 = 11;
            compositeKey1.Int2 = 304;
            compositeKey1.DateTime = firstTimestamp;
    
            compositeKeyDictionary[compositeKey1] = "FirstObject";
    
            CompositeKey compositeKey2 = new CompositeKey();
            compositeKey2.Int1 = 12;
            compositeKey2.Int2 = 9852;
            compositeKey2.DateTime = secondTimestamp;
    
            compositeKeyDictionary[compositeKey2] = "SecondObject";
            /* end composite key dictionary populate */
    
            /* begin composite key dictionary lookup */
            CompositeKey compositeKeyLookup1 = new CompositeKey();
            compositeKeyLookup1.Int1 = 11;
            compositeKeyLookup1.Int2 = 304;
            compositeKeyLookup1.DateTime = firstTimestamp;
    
            Console.Out.WriteLine(compositeKeyDictionary[compositeKeyLookup1]);
    
            CompositeKey compositeKeyLookup2 = new CompositeKey();
            compositeKeyLookup2.Int1 = 12;
            compositeKeyLookup2.Int2 = 9852;
            compositeKeyLookup2.DateTime = secondTimestamp;
    
            Console.Out.WriteLine(compositeKeyDictionary[compositeKeyLookup2]);
            /* end composite key dictionary lookup */
        }
    
        struct CompositeKey
        {
            public int Int1 { get; set; }
            public int Int2 { get; set; }
            public DateTime DateTime { get; set; }
    
            public override int GetHashCode()
            {
                return Int1.GetHashCode() ^ Int2.GetHashCode() ^ DateTime.GetHashCode();
            }
    
            public override bool Equals(object obj)
            {
                if (obj is CompositeKey)
                {
                    CompositeKey compositeKey = (CompositeKey)obj;
    
                    return ((this.Int1 == compositeKey.Int1) &&
                            (this.Int2 == compositeKey.Int2) &&
                            (this.DateTime == compositeKey.DateTime));
                }
    
                return false;
            }
        }
    }
    

    有关getHashCode()的msdn文章:

    http://msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx

        3
  •  13
  •   Jason Kleban    15 年前

    怎么样 Dictionary<int, Dictionary<int, Dictionary<DateTime, MyClass>>> ?

    这将允许您执行以下操作:

    MyClass item = MyData[8][23923][date];
    
        4
  •  11
  •   kemiller2002    15 年前

    您可以将它们存储在结构中,并将其用作键:

    struct CompositeKey
    {
      public int value1;
      public int value2;
      public DateTime value3;
    }
    

    获取哈希代码的链接: http://msdn.microsoft.com/en-us/library/system.valuetype.gethashcode.aspx

        5
  •  5
  •   Lucian Wischik    8 年前

    既然VS2017/C_7已经出现,最好的答案是使用valuetuple:

    // declare:
    Dictionary<(string, string, int), MyClass) index;
    
    // populate:
    foreach (var m in myClassList) {
      index[(m.Name, m.Path, m.JobId)] = m;
    }
    
    // retrieve:
    var aMyClass = index[("foo", "bar", 15)];
    

    我选择用匿名值元组声明字典 (string, string, int) . 但我可以给他们起名字 (string name, string path, int id) .

    在性能上,新的valuetuple比tuple更快 GetHashCode 但在 Equals . 我认为你需要做完整的端到端的实验来找出哪一个对于你的场景来说是最快的。但是,ValueTuple的端到端的良好性和语言语法使它胜出。

    // Perf from https://gist.github.com/ljw1004/61bc96700d0b03c17cf83dbb51437a69
    //
    //              Tuple ValueTuple KeyValuePair
    //  Allocation:  160   100        110
    //    Argument:   75    80         80    
    //      Return:   75   210        210
    //        Load:  160   170        320
    // GetHashCode:  820   420       2700
    //      Equals:  280   470       6800
    
        6
  •  4
  •   Dan Tao    15 年前

    立刻想到两种方法:

    1. 按照凯文的建议去做,写一个结构作为你的钥匙。确保使此结构实现 IEquatable<TKey> 并覆盖其 Equals GetHashCode 方法*。

    2. 编写一个在内部使用嵌套字典的类。类似: TripleKeyDictionary<TKey1, TKey2, TKey3, TValue> …此类的内部成员的类型为 Dictionary<TKey1, Dictionary<TKey2, Dictionary<TKey3, TValue>>> ,并将公开诸如 this[TKey1 k1, TKey2 k2, TKey3 k3] , ContainsKeys(TKey1 k1, TKey2 k2, TKey3 k3) 等。

    *关于是否重写 等于 方法是必要的:虽然 等于 结构的方法在默认情况下比较每个成员的值,它是通过使用反射来实现的,反射本身就需要性能成本,因此 一个非常合适的实现,用于在字典中用作键(在我看来,无论如何)。根据有关 ValueType.Equals :

    默认实现 Equals方法使用反射 比较的相应字段 obj和这个实例。重写 特定类型的Equals方法 提高方法的性能 更紧密地代表了这个概念 类型的相等。

        7
  •  3
  •   paparazzo    11 年前

    如果键是类的一部分,则使用keyedcollection。
    它是一个字典,其中键是从对象派生的。
    封面下面是字典
    不必在键和值中重复键。
    为什么冒险呢?钥匙和价值不一样。
    不必在内存中复制相同的信息。

    KeyedCollection Class

    用于公开复合键的索引器

        using System.Collections.ObjectModel;
    
        namespace IntIntKeyedCollection
        {
            class Program
            {
                static void Main(string[] args)
                {
                    Int32Int32DateO iid1 = new Int32Int32DateO(0, 1, new DateTime(2007, 6, 1, 8, 30, 52));
                    Int32Int32DateO iid2 = new Int32Int32DateO(0, 1, new DateTime(2007, 6, 1, 8, 30, 52));
                    if (iid1 == iid2) Console.WriteLine("same");
                    if (iid1.Equals(iid2)) Console.WriteLine("equals");
                    // that are equal but not the same I don't override = so I have both features
    
                    Int32Int32DateCollection int32Int32DateCollection = new Int32Int32DateCollection();
                    // dont't have to repeat the key like Dictionary
                    int32Int32DateCollection.Add(new Int32Int32DateO(0, 0, new DateTime(2008, 5, 1, 8, 30, 52)));
                    int32Int32DateCollection.Add(new Int32Int32DateO(0, 1, new DateTime(2008, 6, 1, 8, 30, 52)));
                    int32Int32DateCollection.Add(iid1);
                    //this would thow a duplicate key error
                    //int32Int32DateCollection.Add(iid2);
                    //this would thow a duplicate key error
                    //int32Int32DateCollection.Add(new Int32Int32DateO(0, 1, new DateTime(2008, 6, 1, 8, 30, 52)));
                    Console.WriteLine("count");
                    Console.WriteLine(int32Int32DateCollection.Count.ToString());
                    // reference by ordinal postion (note the is not the long key)
                    Console.WriteLine("oridinal");
                    Console.WriteLine(int32Int32DateCollection[0].GetHashCode().ToString());
                    // reference by index
                    Console.WriteLine("index");
                    Console.WriteLine(int32Int32DateCollection[0, 1, new DateTime(2008, 6, 1, 8, 30, 52)].GetHashCode().ToString());
                    Console.WriteLine("foreach");
                    foreach (Int32Int32DateO iio in int32Int32DateCollection)
                    {
                        Console.WriteLine(string.Format("HashCode {0} Int1 {1} Int2 {2} DateTime {3}", iio.GetHashCode(), iio.Int1, iio.Int2, iio.Date1));
                    }
                    Console.WriteLine("sorted by date");
                    foreach (Int32Int32DateO iio in int32Int32DateCollection.OrderBy(x => x.Date1).ThenBy(x => x.Int1).ThenBy(x => x.Int2))
                    {
                        Console.WriteLine(string.Format("HashCode {0} Int1 {1} Int2 {2} DateTime {3}", iio.GetHashCode(), iio.Int1, iio.Int2, iio.Date1));
                    }
                    Console.ReadLine();
                }
                public class Int32Int32DateCollection : KeyedCollection<Int32Int32DateS, Int32Int32DateO>
                {
                    // This parameterless constructor calls the base class constructor 
                    // that specifies a dictionary threshold of 0, so that the internal 
                    // dictionary is created as soon as an item is added to the  
                    // collection. 
                    // 
                    public Int32Int32DateCollection() : base(null, 0) { }
    
                    // This is the only method that absolutely must be overridden, 
                    // because without it the KeyedCollection cannot extract the 
                    // keys from the items.  
                    // 
                    protected override Int32Int32DateS GetKeyForItem(Int32Int32DateO item)
                    {
                        // In this example, the key is the part number. 
                        return item.Int32Int32Date;
                    }
    
                    //  indexer 
                    public Int32Int32DateO this[Int32 Int1, Int32 Int2, DateTime Date1]
                    {
                        get { return this[new Int32Int32DateS(Int1, Int2, Date1)]; }
                    }
                }
    
                public struct Int32Int32DateS
                {   // required as KeyCollection Key must be a single item
                    // but you don't really need to interact with Int32Int32DateS directly
                    public readonly Int32 Int1, Int2;
                    public readonly DateTime Date1;
                    public Int32Int32DateS(Int32 int1, Int32 int2, DateTime date1)
                    { this.Int1 = int1; this.Int2 = int2; this.Date1 = date1; }
                }
                public class Int32Int32DateO : Object
                {
                    // implement other properties
                    public Int32Int32DateS Int32Int32Date { get; private set; }
                    public Int32 Int1 { get { return Int32Int32Date.Int1; } }
                    public Int32 Int2 { get { return Int32Int32Date.Int2; } }
                    public DateTime Date1 { get { return Int32Int32Date.Date1; } }
    
                    public override bool Equals(Object obj)
                    {
                        //Check for null and compare run-time types.
                        if (obj == null || !(obj is Int32Int32DateO)) return false;
                        Int32Int32DateO item = (Int32Int32DateO)obj;
                        return (this.Int32Int32Date.Int1 == item.Int32Int32Date.Int1 &&
                                this.Int32Int32Date.Int2 == item.Int32Int32Date.Int2 &&
                                this.Int32Int32Date.Date1 == item.Int32Int32Date.Date1);
                    }
                    public override int GetHashCode()
                    {
                        return (((Int64)Int32Int32Date.Int1 << 32) + Int32Int32Date.Int2).GetHashCode() ^ Int32Int32Date.GetHashCode();
                    }
                    public Int32Int32DateO(Int32 Int1, Int32 Int2, DateTime Date1)
                    {
                        Int32Int32DateS int32Int32Date = new Int32Int32DateS(Int1, Int2, Date1);
                        this.Int32Int32Date = int32Int32Date;
                    }
                }
            }
        }
    

    对于使用值类型fpr,Microsoft特别推荐使用该键。

    ValueType.GetHashCode

    从技术上讲,tuple不是值类型,但具有相同的症状(哈希冲突),不适合作为键的候选者。

        8
  •  2
  •   Michael Logutov    10 年前

    我可以推荐一个替代方案吗?匿名对象。我们在groupby-linq方法中使用多个键也是一样的。

    var dictionary = new Dictionary<object, string> ();
    dictionary[new { a = 1, b = 2 }] = "value";
    

    这可能看起来很奇怪,但我已经将tuple.gethashcode和new a=1,b=2.gethashcode方法作为基准,匿名对象在我的.NET 4.5.1计算机上获胜:

    对象-891732 ms,在1000个周期内调用10000次

    tuple-7384475 ms,用于1000个周期内的10000次呼叫

        9
  •  0
  •   Hans Olsson    15 年前

    另一个解决方案是存储到目前为止生成的所有键的列表,当生成一个新对象时,生成它的哈希代码(就像一个起点),检查它是否已经在列表中,如果已经在列表中,然后向它添加一些随机值等,直到获得一个唯一的键,然后将该键存储在对象中。在列表中,并始终将其作为键返回。