多键DataStructure

Question

我正在寻找一种数据结构，我可以使用多个键进行搜索。容易用一个例子解释：

var myDataStructure = new MultiKeyDataStructure<int, string, MyType>(); 
myDataStructure.Add(1, "some string 1", new MyType()); 
myDataStructure.Add(2, "some string 2", new MyType()); 

var myType = new MyType(); 
myDataStructure.Add(3, "some string 3", myType); 

Tuple<string, MyType> t1 = myDataStructure[1]; 
Tuple<int, MyType> t2 = myDataStructure["some string 1"]; 
Tuple<int, string> t3 = myDataStructure[myType]; 

是这样的可能，如果是这样，有一个已经存在做什么吗？你将如何实现把所有东西都当作一个键来处理，并通过搜索它们来返回所有相关的键？

理想情况下，你也将被允许使用的参数的任何数量和/或类型：

var myDataStructure = new MultiKeyDataStructure<int, string, Foo, Bar>(); 

Answer 1

所以，这里有一个可以用于三个键的键。您可以按照列出的模式为4,5,6等键制作一个。这将是很多代码，但不是一个特别困难的任务（只是单调乏味）。

请注意，由于密钥的每个部分都有一个字典，因此它会占用相当多的内存;这就是您为任何关键的事实访问灵活性付出的代价。

public class MultiKeyDictionary<T1, T2, T3> 
{ 
    private Dictionary<T1, Tuple<T1, T2, T3>> firstLookup = new Dictionary<T1, Tuple<T1, T2, T3>>(); 
    private Dictionary<T2, Tuple<T1, T2, T3>> secondLookup = new Dictionary<T2, Tuple<T1, T2, T3>>(); 
    private Dictionary<T3, Tuple<T1, T2, T3>> thirdLookup = new Dictionary<T3, Tuple<T1, T2, T3>>(); 

    public void Add(Tuple<T1, T2, T3> values) 
    { 
     if (!firstLookup.ContainsKey(values.Item1) && 
      !secondLookup.ContainsKey(values.Item2) && 
      !thirdLookup.ContainsKey(values.Item3)) 
     { 
      firstLookup.Add(values.Item1, values); 
      secondLookup.Add(values.Item2, values); 
      thirdLookup.Add(values.Item3, values); 
     } 
     else 
     { 
      //throw an exeption or something. 
     } 
    } 

    public Tuple<T1, T2, T3> GetFirst(T1 key) 
    { 
     return firstLookup[key]; 
    } 

    public Tuple<T1, T2, T3> GetSecond(T2 key) 
    { 
     return secondLookup[key]; 
    } 

    public Tuple<T1, T2, T3> GetThird(T3 key) 
    { 
     return thirdLookup[key]; 
    } 

    public void RemoveFirst(T1 key) 
    { 
     var values = GetFirst(key); 

     firstLookup.Remove(values.Item1); 
     secondLookup.Remove(values.Item2); 
     thirdLookup.Remove(values.Item3); 
    } 

    public void RemoveSecond(T2 key) 
    { 
     var values = GetSecond(key); 

     firstLookup.Remove(values.Item1); 
     secondLookup.Remove(values.Item2); 
     thirdLookup.Remove(values.Item3); 
    } 

    public void RemoveThird(T3 key) 
    { 
     var values = GetThird(key); 

     firstLookup.Remove(values.Item1); 
     secondLookup.Remove(values.Item2); 
     thirdLookup.Remove(values.Item3); 
    } 
} 

下面是一个完全不同的方法。不是为每个键填充查找，而是将所有值存储在单个集合中，并执行线性搜索以查找给定键的项目。它将有O（n）搜索/删除时间，但O（1）添加。以前的实现有O（1）添加，删除和搜索，但占用更多的内存来完成它。

public class MultiKeyDictionary2<T1, T2, T3> 
{ 
    private HashSet<Tuple<T1, T2, T3>> lookup = new HashSet<Tuple<T1, T2, T3>>(); 
    private HashSet<T1> firstKeys = new HashSet<T1>(); 
    private HashSet<T2> secondKeys = new HashSet<T2>(); 
    private HashSet<T3> thirdKeys = new HashSet<T3>(); 

    public void Add(Tuple<T1, T2, T3> values) 
    { 
     if (lookup.Any(multiKey => object.Equals(multiKey.Item1, values.Item1) || 
      object.Equals(multiKey.Item2, values.Item2) || 
      object.Equals(multiKey.Item3, values.Item3))) 
     { 
      //throw an exception or something 
     } 
     else 
     { 
      lookup.Add(values); 
     } 
    } 

    public Tuple<T1, T2, T3> GetFirst(T1 key) 
    { 
     return lookup.FirstOrDefault(values => object.Equals(values.Item1, key)); 
    } 

    public Tuple<T1, T2, T3> GetSecond(T2 key) 
    { 
     return lookup.FirstOrDefault(values => object.Equals(values.Item2, key)); 
    } 

    public Tuple<T1, T2, T3> GetThird(T3 key) 
    { 
     return lookup.FirstOrDefault(values => object.Equals(values.Item3, key)); 
    } 

    public void RemoveFirst(T1 key) 
    { 
     var values = GetFirst(key); 
     if (values != null) 
      lookup.Remove(values); 
    } 

    public void RemoveSecond(T2 key) 
    { 
     var values = GetSecond(key); 
     if (values != null) 
      lookup.Remove(values); 
    } 

    public void RemoveThird(T3 key) 
    { 
     var values = GetThird(key); 
     if (values != null) 
      lookup.Remove(values); 
    } 
} 

Answer 2

System.Tuple与使用它作为牢记字典键添加。 用法：

var dict = new Dictionary<Tuple<string, int>, DateTime>(); 
dict.Add(Tuple.Create("Louis", 14), new DateTime(1638, 9, 5)); 

虽然元组的语法很麻烦，静态工厂方法花费在创建网站的痛苦。

Answer 3

最接近的东西可能是HashSet<Tuple<int, string, MyType>>。 HashSets自动检查重复项，并且Tuple检查它是否等价。

class MultiKey<T1, T2, T3> : HashSet<Tuple<T1, T2, T3>> 
{ 
    public bool Add(T1 t1, T2 t2, T3 t3) 
    { 
     return this.Add(Tuple.Create(t1, t2, t3)); 
    } 
    public T1 Get(T2 t2, T3 t3) 
    { 
     var match = this.SingleOrDefault(x => x.Item2.Equals(t2) && x.Item3.Equals(t3)); 
     if (match == null) return default(T1); 
     else return match.Item1; 
    } 
    public T2 Get(T1 t1, T3 t3) 
    { 
     var match = this.SingleOrDefault(x => x.Item1.Equals(t1) && x.Item3.Equals(t3)); 
     if (match == null) return default(T2); 
     else return match.Item2; 
    } 
    public T3 Get(T1 t1, T2 t2) 
    { 
     var match = this.SingleOrDefault(x => x.Item1.Equals(t1) && x.Item2.Equals(t2)); 
     if (match == null) return default(T3); 
     else return match.Item3; 
    } 
} 

用法：

key.Add(1, "Foo", new MyType("foo")); 
key.Add(2, "Bar", new MyType("bar")); 
key.Add(2, "Bar", new MyType("bar")); // Does not add, because it already exists. 
var key1 = key.Get("Bar", new Foo("bar")); // Returns 2 
var defaultKey = key.Get("Bar", new Foo("foo")); // Returns 0, the default value for an int 
var key2 = key.Get(1, new Foo("foo")); // returns "Foo" 

你需要确保MyType比较了它的价值相等，如果你有很多的new的使用它。否则，创建一个新的将保证一个独特的价值。

Answer 4

当我遇到这样的情况时，我只是使用两个字典，而不是试图想出一些新的数据结构。每个字典都有映射到该值的可能键之一。

如果你真的想把它抽象出来，你总是可以创建一个内部使用两个或多个字典的类，具体取决于你需要多少种不同类型的键。

Answer 5

既然你说你想要编译时类型安全，有许多事情你必须放弃：

1. 有任何数量的参数的能力（C＃不具有可变参数仿制药）
2. 具有相同类型的多个按键的能力（编译器会抱怨不明确的重载）

这两个限制，可以通过使用基于反射的方法来解决，但你会失去编译时类型安全。

因此，这是你可以使用的解决方案，根据您的约束（只有当所有的泛型类型是不同的作品！）

class TripleKeyDictionnary<TKey1, TKey2, TKey3> 
{ 
    public Tuple<TKey2, TKey3> this[TKey1 key] 
    { 
     get 
     { 
      return _key1Lookup[key]; 
     } 
    } 

    public Tuple<TKey1, TKey3> this[TKey2 key] 
    { 
     get 
     { 
      return _key2Lookup[key]; 
     } 
    } 

    public Tuple<TKey1, TKey2> this[TKey3 key] 
    { 
     get 
     { 
      return _key3Lookup[key]; 
     } 
    } 

    private Dictionary<TKey1, Tuple<TKey2, TKey3>> _key1Lookup = new Dictionary<TKey1, Tuple<TKey2, TKey3>>(); 
    private Dictionary<TKey2, Tuple<TKey1, TKey3>> _key2Lookup = new Dictionary<TKey2, Tuple<TKey1, TKey3>>(); 
    private Dictionary<TKey3, Tuple<TKey1, TKey2>> _key3Lookup = new Dictionary<TKey3, Tuple<TKey1, TKey2>>(); 

    public void Add(TKey1 key1, TKey2 key2, TKey3 key3) 
    { 
     _key1Lookup.Add(key1, Tuple.Create(key2, key3)); 
     _key2Lookup.Add(key2, Tuple.Create(key1, key3)); 
     _key3Lookup.Add(key3, Tuple.Create(key1, key2)); 
    } 
} 

Answer 6

首先，遗憾的是没有什么内置的，所以你必须实现手动。

这里的问题是，你不能有泛型类型定义，即数目不详的一类不存在这样的事：

class MultiKeyDictionary<T1, ...> 
{} 

所以，要么你可以决定执行某些情况下（ 2键，3键等，使用类似于Tuple<>实施的方法），或者你应该放弃类型安全。

如果你决定对于第一种方法，你应该可以做这样的事情（例如用3个键）：

class ThreeKeysDict<T1,T2,T3> 
{ 
    var dict1 = new Dictionary<T1,Tuple<T2,T3>>(); 
    var dict2 = new Dictionary<T2,Tuple<T1,T3>>(); 
    var dict3 = new Dictionary<T3,Tuple<T1,T2>>(); 
    public void Add(T1 key1,T2 key2, T3 key3) 
    { 
     dict1.Add(key1,Tuple.Create(key2,key3)); 
     dict2.Add(key2,Tuple.Create(key1,key3)); 
     dict3.Add(key3,Tuple.Create(key1,key2)); 
    } 
    public Tuple<T2,T3> GetByKey1(T1 key1) 
    { 
     return dict1[key1]; 
    } 
    public Tuple<T1,T3> GetByKey2(T2 key2) 
    { 
     return dict2[key2]; 
    } 
    public Tuple<T1,T2> GetByKey3(T3 key3) 
    { 
     return dict3[key3]; 
    } 
} 

非通用版本将是这样的：

class MultiKeyDict 
{ 
    Dictionary<object, object[]>[] indexesByKey; 
    public MultiKeyDict(int nKeys) 
    { 
     indexesByKey = new Dictionary<object, object[]>[nKeys]; 
    } 
    public void Add(params object[] values) 
    { 
     if (values.Length != indexesByKey.Length) 
      throw new ArgumentException("Wrong number of arguments given"); 
     var objects = values.ToArray(); 
     for (int i = 0; i < indexesByKey.Length; i++) 
      this.indexesByKey[i].Add(values[i], objects); 
    } 
    public object[] Get(int keyNum, object key) 
    { 
     return this.indexesByKey[keyNum][key]; 
    } 
} 

如果不同密钥的数量增加（因为它们为每个密钥采用一个字典），这两种方法都使用大量内存。

---

免责声明：

代码的片段没有经过测试和缺乏空的输入/输出超范围检查等
他们只是给你的总体思路。

Answer 7

我不确定是否存在任何这样的数据结构，但可以创建一个。

假设密钥/副密钥将是唯一的

以下是MultiKeyDictionary（使用2本内部字典，一个用于键（如object），以及一个用于值）。

public class MultiKeyDictionary<TValue> 
{ 
    private Dictionary<Guid, TValue> values; 
    private Dictionary<Object, Guid> keys; 

    public MultiKeyDictionary() 
    { 
     keys = new Dictionary<Object,Guid>(); 
     values = new Dictionary<Guid,TValue>(); 
    } 
    public IEnumerable<Object> Keys 
    { 
     get { return keys.Keys.AsEnumerable();} // May group according to values here 
    } 

    public IEnumerable<TValue> Values 
    { 
     get { return values.Values;} 
    } 

    public TValue this[object key] 
    { 
     get 
     { 
      if (keys.ContainsKey(key)) 
      { 
       var internalKey = keys[key]; 
       return values[internalKey]; 
      } 
      throw new KeyNotFoundException(); 
     } 
    } 


    public void Add(TValue value,object key1, params object[] keys) // key1 to force minimum 1 key 
    { 
     Add(key1 , value); 
     foreach(var key in keys) 
     { 
     Add (key, value); 
     } 
    } 

    private void Add(Object key, TValue value) 
    { 
     var internalKey = Guid.NewGuid(); 
     keys.Add(key, internalKey); 
     values.Add(internalKey, value);  
    } 
} 

它可以作为

MultiKeyDictionary<string> dict = new MultiKeyDictionary<string>(); 
dict.Add("Hello" , 1,2,3,"StringKey"); // First item is value, remaining all are keys 
Console.WriteLine(dict[1]); // Note 1 is key and not intex 
Console.WriteLine(dict[2]); // Note 2 is key and not index 
Console.WriteLine(dict["StringKey"]); 

Answer 8

如何

class MultiKeyLookup<A, B, C> : IEnumerable<Tuple<A, B, C>> 
{ 
    private readonly ILookup<A, Tuple<B, C>> a; 
    private readonly ILookup<B, Tuple<A, C>> b; 
    private readonly ILookup<C, Tuple<A, B>> c; 
    private readonly IEnumerable<Tuple<A, B, C>> order; 

    public MultiKeyLookup(IEnumerable<Tuple<A, B, C>> source) 
    { 
     this.order = source.ToList(); 
     this.a = this.order.ToLookup(
      o => o.Item1, 
      o => new Tuple<B, C>(o.Item2, o.Item3)); 
     this.b = this.order.ToLookup(
      o => o.Item2, 
      o => new Tuple<A, C>(o.Item1, o.Item3)); 
     this.c = this.order.ToLookup(
      o => o.Item3, 
      o => new Tuple<A, B>(o.Item1, o.Item2)); 
    } 

    public ILookup<A, Tuple<B, C>> Item1 
    { 
     get 
     { 
      return this.a 
     } 
    } 

    public ILookup<B, Tuple<A, C>> Item2 
    { 
     get 
     { 
      return this.b 
     } 
    } 

    public ILookup<C, Tuple<A, B>> Item3 
    { 
     get 
     { 
      return this.c 
     } 
    } 

    public IEnumerator<Tuple<A, B, C>> GetEnumerator() 
    { 
     this.order.GetEnumerator(); 
    } 

    public IEnumerator IEnumerable.GetEnumerator() 
    { 
     this.order.GetEnumerator(); 
    } 
} 

，你会使用像，

var multiKeyLookup = new MultiKeyLookup(
    new[] { 
     Tuple.Create(1, "some string 1", new MyType()), 
     Tuple.Create(2, "some string 2", new MyType())}); 

var intMatches = multiKeyLookup.Item1[1]; 
var stringMatches = multiKeyLookup.Item2["some string 1"]; 
var typeMatches = multiKeyLookup.Item3[myType];