如何覆蓋HashSet的等於和GetHash

Question

我有一個HashSet<int[]> foo其中int []代表平面中某個點的座標。位置0處的值代表x，位置1處的值代表和。我想覆蓋Equals和GetHashCode方法，如果它的內部值等於給定值，就可以移除一個元素（該點表示爲大小爲2的數組）。

已經嘗試過：

public override int GetHashCode(){ 
    return this.GetHashCode(); 
} 

public override bool Equals(object obj){ 
    if (obj == null || ! (obj is int[])) 
    return false; 

    HashSet<int[]> item = obj as HashSet<int[]>; 

    return item == this; 
} 

在我的課堂迷宮。

在此先感謝。

編輯

我找到了一種方法來做到這一點

class SameHash : EqualityComparer<int[]> 
{ 
    public override bool Equals(int[] i1, int[] i2) 
    { 
     return i1[0] == i2[0] && i1[1] == i2[1]; 
    } 


    public override int GetHashCode(int[] i) 
    { 
     return base.GetHashCode(); 
    } 
} 

Answer 1

的唯一途徑，我發現它可能是通過創建一個類MyPair而不是使用數組（INT []）喜歡你沒有。請注意，我在GetHashCode（）函數中使用了X * 10000 + Y，但您可以更改常量值以便爲每個項目獲取更好的HashCode，或者您可以創建自己的HashCode。我只是提供了一個簡單的例子，因爲當X和Y的邊界相對較小（小於Int.MaxValue的根）時，可以使用不同的hashCode。 在這裏，你有工作代碼：

using System; 
using System.Collections.Generic; 
using System.Linq; 

namespace hash 
{ 

    public class MyPair 
    { 
     public int X { get; set; } 
     public int Y { get; set; } 

     public override int GetHashCode() 
     { 
      return X * 10000 + Y; 
     } 

     public override bool Equals(object obj) 
     { 
      MyPair other = obj as MyPair; 
      return X == other.X && Y == other.Y; 
     } 
    } 

    class Program 
    { 

     static void Main(string[] args) 
     { 
      HashSet<MyPair> hash = new HashSet<MyPair>(); 
      MyPair one = new MyPair { X = 10, Y = 2 }; 
      MyPair two = new MyPair { X = 1, Y = 24 }; 
      MyPair three = new MyPair { X = 111, Y = 266 }; 
      MyPair copyOfOne = new MyPair { X = 10, Y = 2 }; 
      Console.WriteLine(hash.Add(one)); 
      Console.WriteLine(hash.Add(two)); 
      Console.WriteLine(hash.Add(three)); 
      Console.WriteLine(hash.Add(copyOfOne)); 
     } 

    } 
} 

Answer 2

它可能看起來像你解決你問什麼，但有一些重要的是應該指出的。當您實施EqualityComparer<int[]>時，您將GetHashCode(int[] i)編碼爲return base.GetHashCode();，即使它工作正常也不正確。我花時間爲您提供了以下代碼，以便您查看實施結果，並且我還爲您提供了可能的解決方案。 將此代碼複製並在控制檯項目中運行。註釋您的代碼行，取消註釋下面的行並重新運行它。你會看到不同之處！ 總結，當您返回base.GetHashCode()時，您將爲每個項目返回相同的散列碼。這會導致哈希集合內的所有插入衝突以行爲的速度降低，如果您使用的是List<int[]>，並且您在插入元素之前詢問它是否包含元素。這就是爲什麼你會看到，通過使用我提供的功能和我產生的數字範圍，你將能夠在不到1秒內插入多達一百萬次。然而，使用你的，不管範圍，它在1萬次插入中花費1秒。發生這種情況是因爲對於所有n個插入，都存在衝突，並且當HashSet和偶數分佈Hash函數的期望值爲O（n）時，所產生的時間複雜度爲O（n^2）。 查看結果：

using System; 
using System.Collections.Generic; 
using System.Diagnostics; 
using System.Linq; 

namespace hashExample 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      List<int[]> points = new List<int[]>(); 
      Random random = new Random(); 
      int toInsert = 20000; 
      for (int i = 0; i < toInsert; i++) 
      { 
       int x = random.Next(1000); 
       int y = random.Next(1000); 
       points.Add(new int[]{ x,y }); 
      } 
      HashSet<int[]> set = new HashSet<int[]>(new SameHash()); 
      Stopwatch clock = new Stopwatch(); 
      clock.Start(); 
      foreach (var item in points) 
      { 
       set.Add(item); 
      } 
      clock.Stop(); 
      Console.WriteLine("Elements inserted: " + set.Count + "/" + toInsert); 
      Console.WriteLine("Time taken: " + clock.ElapsedMilliseconds); 
     } 

     public class SameHash : EqualityComparer<int[]> 
     { 
      public override bool Equals(int[] p1, int[] p2) 
      { 
       return p1[0] == p2[0] && p1[1] == p2[1]; 
      } 
      public override int GetHashCode(int[] i) 
      { 
       return base.GetHashCode(); 
       //return i[0] * 10000 + i[1]; 
       //Notice that this is a very basic implementation of a HashCode function 
      } 
     }  
    } 
}