2013-01-11 64 views
9

我正在尋找一種數據結構,我可以使用多個鍵進行搜索。容易用一個例子解釋:多鍵DataStructure

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>(); 
+4

那麼將't3'包含在你的情況?你的'MyType'對象不是唯一的,所以有三個匹配的對象。 – Servy

+0

幾個字典,你添加相同的一組值? –

+0

就我而言,你不能爲類型參數做一個參數陣列 – Jodrell

回答

5

所以,這裏有一個可以用於三個鍵的鍵。您可以按照列出的模式爲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); 
    } 
} 
+0

哈,我只是想發佈我的答案,這幾乎是相同的! –

+0

是的。我等了一會兒,看看是否有更好的選擇出現,但經過5次不正確的回答,似乎得到的東西很難看,但至少在板子上工作是值得的。 – Servy

+0

@Agent_L是的,編輯。 – Servy

-2

System.Tuple與使用它作爲牢記字典鍵添加。 用法:

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

雖然元組的語法很麻煩,靜態工廠方法花費在創建網站的痛苦。

+0

我有同樣的想法,但後來我意識到OP需要查找任何關鍵給其他兩個... – Bobson

+0

似乎我有點匆忙... –

0

最接近的東西可能是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的使用它。否則,創建一個新的將保證一個獨特的價值。

+0

'應該有可能寫一個類繼承並添加了檢索給定兩個其他鍵的鍵的功能。「嗯,鑑於這是真正的問題,在這裏你應該提供更多的答案。你認爲這可能不是一個真正的答案。你會怎麼做? – Servy

+0

@Servy - 這是一個開始。它指向一個可能有所幫助的數據結構。不過,我會努力擴展它。 – Bobson

+0

我可以告訴你,沒有辦法通過它所擁有的類型的任意屬性來搜索'HashSet'。你需要選擇IEqualityComparer所基於的一個*就是這樣。所以不,不可能使用你所描述的佈局。如果是,那麼證明它;沒有這個答案就沒用了。 – Servy

1

當我遇到這樣的情況時,我只是使用兩個字典,而不是試圖想出一些新的數據結構。每個字典都有映射到該值的可能鍵之一。

如果你真的想把它抽象出來,你總是可以創建一個內部使用兩個或多個字典的類,具體取決於你需要多少種不同類型的鍵。

2

既然你說你想要編譯時類型安全,有許多事情你必須放棄:

  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)); 
    } 
} 
2

首先,遺憾的是沒有什麼內置的,所以你必須實現手動。

這裏的問題是,你不能有泛型類型定義,即數目不詳的一類不存在這樣的事:

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]; 
    } 
} 

如果不同密鑰的數量增加(因爲它們爲每個密鑰採用一個字典),這兩種方法都使用大量內存。


免責聲明:

代碼的片段沒有經過測試和缺乏空的輸入/輸出超範圍檢查等
他們只是給你的總體思路。

0

我不確定是否存在任何這樣的數據結構,但可以創建一個。

假設密鑰/副密鑰將是唯一的

以下是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"]); 
0

如何

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];