兩個關鍵元組的列表或字典

我有一組雙鍵字符串{（a1，b1），（a2，b2），（a3，b3），...}。在我的場景（a1，b1）==（b1，a1）中，所以a（a1，b1）或（b1，a1）組合應該只是我的集合的一部分。兩個關鍵元組的列表或字典

在C＃應用程序，我需要能夠：

添加的這些新的對（A，B）元組
高效（即快速）檢查，如果一對（A1，B1 ）或（b1，a1）已經在我的表格中。

你將如何實現這樣的事情，用字典[Tuple [K1，K2]]或其他？如果使用字典，有什麼辦法可以讓它考慮（K1，K2）與（K2，K1）相同，所以我不必添加這兩種組合？或者可能加入（K1，K2）和（K2，K1）是要走的路？

謝謝。

來源

2013-03-24 pbz

顯然我不能鍵入LT或GT的人物，他們沒有得到逃脫，所以我代替那些括號/圓括號 – pbz 2013-03-24 19:27:25

你有什麼需要用一套呢？例如，您想如何查看價值？ – 2013-03-24 19:28:13

@JonSkeet我只需要快速檢查（a1，b1）和（b1，a1）是否已經在集合中。我正在處理大量的這些事情，所以它需要很快。謝謝。 – pbz 2013-03-24 19:29:51

創建一個存儲類，公開Add（a，b）和類似的函數。內部存儲器可以是HashSet<T>，其中T是適合的字符串元組鍵。這個Key和comparer唯一重要的是使用對稱的散列和相等函數，即（a，b）等於（b，a），因此散列（a，b）==散列（b，a ）。

正如前面指出的，許多散列函數都有這個屬性，例如散列值的和和。我選擇不使用xor，因爲它意味着所有的對等字符串都會有散列零，如果可能的話，可能會導致低效率的查找。

下面的實現假設所有的字符串都是非空的，但沒有錯誤檢查。

public class Storage 
{ 
    private HashSet<Key> set; 

    public Storage() 
    { 
     set = new HashSet<Key>(new Key.Comparer()); 
    } 

    public void Add(string a, string b) 
    { 
     set.Add(new Key{A=a, B=b}); 
    } 

    public bool Contains(string a, string b) 
    { 
     return set.Contains(new Key{A=a, B=b}); 
    } 

    internal class Key 
    { 
     internal String A { get; set; } 
     internal String B { get; set; } 
     internal class Comparer : IEqualityComparer<Key> 
     { 
      public bool Equals(Key x, Key y) 
      { 
      return (x.A == y.A && x.B == y.B) || (x.A == y.B && x.B == y.A); 
      } 
      public int GetHashCode(Key k) 
      { 
      int aHash = k.A.GetHashCode(); 
      int bHash = k.B.GetHashCode(); 
      // Hash for (x,y) same as hash for (y,x) 
      if (aHash > bHash) 
       return bHash * 37 + aHash; 
      return aHash * 37 + bHash; 
      } 
     } 
    } 

}

來源

2013-03-24 19:47:16

爲什麼使用* 37？ – pbz 2013-03-24 19:50:57

一種總是將哈希合併爲「a * prime_number + b」的舊習慣。當組合哈希代碼以避免衝突時，這是通常的簡單模式，但我現在實際上並不確定在做這樣的對稱散列時它是否是嚴格必要的，現在我想到了它。它可能會造成a，b之間的不對稱，如果我只將哈希值相加，那麼它就不會存在。有人可以在這裏填寫，其後期... – 2013-03-24 19:56:25

當aHash和bHash是哈希值時，爲什麼不簡單地將它們異或？那會不好？ – 2013-03-24 23:20:32

這是功課嗎？這看起來像是一本書的問題。

定義類Key定義了相等和散列運算符和方法。（這意味着你應該定義方法Equals，運算符==，方法GetHashCode，如果編譯器需要它們可能還有其他方法）。
使用HashSet<Key>。

來源

2013-03-24 19:27:46

不，不是一個家庭作業問題......我只是試圖以非模糊的方式解釋。 – pbz 2013-03-24 19:28:42

但是，如果我重寫Equals方法，是不是減慢了在列表中找到項目的速度？這是否不符合快速訪問的目的？謝謝。 – pbz 2013-03-24 19:32:00

我們幾乎不可能在這裏談論減速 - 因爲您只需要一種方法來比較兩個鍵。如果您沒有提供比較密鑰的方法，則無法使用。 – 2013-03-24 23:19:17

製作一個自定義類，實現IEquatable（並確保正確覆蓋GetHashCode）。然後，您可以在HashSet<T>中使用它，並且這兩對可以自動「平等」。

來源

2013-03-24 19:31:02

而且這將正確地「索引」項目？我試圖阻止「掃描」，即爲每個項目檢查調用「等於」。 – pbz 2013-03-24 19:33:20

@pbz：只要你有一個明智的哈希碼，那應該沒問題。 – 2013-03-24 19:34:45

GetHashCode應該是什麼樣子？ key1 + key2或key2 + key1？ – pbz 2013-03-24 19:34:55

我會使用一個字典，其中的密鑰由接受2個字符串的函數生成，並像這樣生成哈希：比較兩個字符串，構建一個由「較小」字符串+分隔符+「較大」串。這種順序無關緊要。一個類似的「等於」操作符也可以被實現。

來源

2013-03-24 19:33:38

小於string1 pbz 2013-03-24 19:42:50

是的，使用String.Compare（str1，str2） – 2013-03-24 19:51:59

兩個關鍵元組的列表或字典

回答

相關問題