Câu hỏi Tại sao điều quan trọng là phải ghi đè GetHashCode khi phương thức Equals bị ghi đè?


Cho lớp sau

public class Foo
{
    public int FooId { get; set; }
    public string FooName { get; set; }

    public override bool Equals(object obj)
    {
        Foo fooItem = obj as Foo;

        return fooItem.FooId == this.FooId;
    }

    public override int GetHashCode()
    {
        // Which is preferred?

        return base.GetHashCode();

        //return this.FooId.GetHashCode();
    }
}

Tôi đã ghi đè Equals phương pháp vì Foo đại diện cho một hàng cho Fooổn định. Đó là phương pháp ưa thích để ghi đè GetHashCode?

Tại sao điều quan trọng là ghi đè GetHashCode?


1167
2017-12-16 13:41


gốc


Điều quan trọng là thực hiện cả hai bằng và gethashcode, do va chạm, đặc biệt trong khi sử dụng từ điển. nếu hai đối tượng trả về cùng một hashcode, chúng sẽ được chèn vào từ điển với chuỗi. Trong khi truy cập mục bằng phương thức được sử dụng. - DarthVader


Các câu trả lời:


Có, điều quan trọng là nếu mặt hàng của bạn sẽ được sử dụng như một chìa khóa trong từ điển, hoặc HashSet<T>, vv - vì điều này được sử dụng (trong trường hợp không có tùy chỉnh IEqualityComparer<T>) để nhóm các mục vào nhóm. Nếu mã băm cho hai mục không khớp, chúng có thể không bao giờ được coi là bình đẳng (Equals sẽ không bao giờ được gọi).

Các GetHashCode() phương pháp nên phản ánh Equals logic; các quy tắc là:

  • nếu hai điều bình đẳng (Equals(...) == true) sau đo họ phải trả lại cùng một giá trị cho GetHashCode()
  • nếu GetHashCode() bằng nhau, nó là không phải cần thiết cho họ giống nhau; đây là một va chạm, và Equals sẽ được gọi để xem nó có thực sự bình đẳng hay không.

Trong trường hợp này, nó trông giống như "return FooId;"là phù hợp GetHashCode() thực hiện. Nếu bạn đang thử nghiệm nhiều thuộc tính, việc kết hợp chúng bằng mã như dưới đây là phổ biến, để giảm va chạm chéo (tức là new Foo(3,5) có một mã băm khác nhau để new Foo(5,3)):

int hash = 13;
hash = (hash * 7) + field1.GetHashCode();
hash = (hash * 7) + field2.GetHashCode();
...
return hash;

Oh - để thuận tiện, bạn cũng có thể cân nhắc việc cung cấp == và != toán tử khi ghi đè Equals và GetHashCode.


Một minh chứng về những gì xảy ra khi bạn nhận được sai lầm này là đây.


1101
2017-12-16 13:47



Tôi có thể hỏi ahy là bạn nhân với các yếu tố như vậy? - Leandro López
Trên thực tế, tôi có thể có thể mất một trong số họ; vấn đề là cố gắng giảm thiểu số va chạm - để đối tượng {1,0,0} có giá trị băm khác nhau {0,1,0} và {0,0,1} (nếu bạn hiểu ý tôi ), - Marc Gravell♦
Tôi đã chỉnh sửa các con số để làm cho nó rõ ràng hơn (và thêm một hạt giống). Một số mã sử dụng các số khác nhau - ví dụ trình biên dịch C # (cho các kiểu ẩn danh) sử dụng một hạt giống 0x51ed270b và một hệ số là -1521134295. - Marc Gravell♦
@Leandro López: Thông thường các yếu tố được chọn là số nguyên tố vì nó làm cho số lượng va chạm nhỏ hơn. - Andrei Rînea
"Ồ - để thuận tiện, bạn cũng có thể xem xét việc cung cấp các toán tử == và! = Khi ghi đè Equals và GethashCode.": Microsoft không khuyến khích thực thi toán tử == cho các đối tượng không thay đổi - msdn.microsoft.com/en-us/library/ms173147.aspx - "Không phải là một ý tưởng hay để ghi đè toán tử == ở các loại không thay đổi". - antiduh


Nó thực sự rất khó thực hiện GetHashCode() một cách chính xác bởi vì, ngoài các quy tắc mà Marc đã đề cập, mã băm không nên thay đổi trong suốt thời gian tồn tại của một đối tượng. Do đó, các trường được sử dụng để tính toán mã băm phải không thay đổi.

Cuối cùng tôi đã tìm thấy một giải pháp cho vấn đề này khi tôi đang làm việc với NHibernate. Cách tiếp cận của tôi là tính toán mã băm từ ID của đối tượng. ID chỉ có thể được đặt mặc dù hàm tạo nên nếu bạn muốn thay đổi ID, điều này rất khó xảy ra, bạn phải tạo một đối tượng mới có ID mới và do đó là mã băm mới. Cách tiếp cận này hoạt động tốt nhất với GUID vì bạn có thể cung cấp một hàm tạo parameterless để tạo ngẫu nhiên một ID.


115
2017-12-21 12:39



@vanja. Tôi tin rằng nó phải làm với: nếu bạn thêm đối tượng vào một từ điển và sau đó thay đổi id của đối tượng, khi tìm nạp sau, bạn sẽ sử dụng một băm khác để lấy nó để bạn sẽ không bao giờ lấy nó từ từ điển. - ANeves
Tài liệu của Microsoft về hàm GetHashCode () không có nghĩa là các trạng thái cũng không ngụ ý rằng băm đối tượng phải duy trì tính nhất quán trong suốt thời gian tồn tại của nó. Trong thực tế, nó giải thích cụ thể một trường hợp được phép mà trong đó nó có thể không phải: "Phương thức GetHashCode cho một đối tượng phải luôn trả về cùng một mã băm miễn là không có sửa đổi đối với trạng thái đối tượng xác định giá trị trả về của phương thức Equals của đối tượng." - PeterAllenWebb
"mã băm không nên thay đổi trong suốt thời gian tồn tại của một đối tượng" - điều đó không đúng. - zgnilec
Một cách tốt hơn để nói nó là "mã băm (cũng không phải là sự evaulation bằng) nên thay đổi trong khoảng thời gian đối tượng được sử dụng như một chìa khóa cho một bộ sưu tập" Vì vậy, nếu bạn thêm đối tượng vào một từ điển như một khóa, bạn phải đảm bảo rằng GetHashCode và Equals sẽ không thay đổi đầu ra của chúng cho một đầu vào cho trước cho đến khi bạn loại bỏ đối tượng khỏi từ điển. - Scott Chamberlain
@ScottChamberlain Tôi nghĩ rằng bạn quên KHÔNG trong bình luận của bạn, nó phải là: "mã băm (cũng không phải evaulation bằng) không nên thay đổi trong thời gian đối tượng được sử dụng như một chìa khóa cho một bộ sưu tập". Đúng? - Stan Prokop


Bằng cách ghi đè Bằng bạn về cơ bản nói rằng bạn là người hiểu rõ hơn về cách so sánh hai trường hợp của một kiểu nhất định, vì vậy bạn có thể là ứng cử viên tốt nhất để cung cấp mã băm tốt nhất.

Đây là một ví dụ về cách ReSharper viết một hàm GetHashCode () cho bạn:

public override int GetHashCode()
{
    unchecked
    {
        var result = 0;
        result = (result * 397) ^ m_someVar1;
        result = (result * 397) ^ m_someVar2;
        result = (result * 397) ^ m_someVar3;
        result = (result * 397) ^ m_someVar4;
        return result;
    }
}

Như bạn có thể thấy nó chỉ cố gắng đoán mã băm tốt dựa trên tất cả các trường trong lớp, nhưng vì bạn biết phạm vi giá trị hoặc miền của đối tượng của bạn, bạn vẫn có thể cung cấp mã băm tốt hơn.


41
2017-12-16 13:48



Sẽ không phải lúc nào cũng trả về số không? Có lẽ nên khởi tạo kết quả 1! Cũng cần thêm một vài dấu chấm phẩy. - Sam Mackrill
Bạn có biết những gì các nhà điều hành XOR (^) không? - Stephen Drew
Như tôi đã nói, đây là những gì R # viết cho bạn (ít nhất đó là những gì nó đã làm trở lại trong năm 2008) khi được yêu cầu. Rõ ràng, đoạn mã này được dự định sẽ được chỉnh sửa bởi lập trình viên theo một cách nào đó. Đối với các dấu chấm phẩy bị mất ... vâng, có vẻ như tôi đã bỏ chúng ra khi tôi sao chép-dán mã từ một vùng chọn trong Visual Studio. Tôi cũng nghĩ mọi người sẽ tìm ra cả hai. - Trap
@SamMackrill Tôi đã thêm vào các dấu chấm phẩy bị thiếu. - Matthew Murdoch
@SamMackrill Không, nó sẽ không luôn trả về 0. 0 ^ a = a, vì thế 0 ^ m_someVar1 = m_someVar1. Anh ta cũng có thể đặt giá trị ban đầu của result đến m_someVar1. - Millie Smith


Xin đừng quên kiểm tra thông số obj chống lại null khi ghi đè Equals(). Và cũng so sánh các loại.

public override bool Equals(object obj)
{
    if (obj == null || GetType() != obj.GetType())
        return false;

    Foo fooItem = obj as Foo;

    return fooItem.FooId == this.FooId;
}

Lý giải cho vấn đề này là: Equals phải trả về false khi so sánh với null. Xem thêm http://msdn.microsoft.com/en-us/library/bsc2ak47.aspx


32
2017-11-17 07:46



Việc kiểm tra kiểu này sẽ không thành công trong trường hợp một lớp con đề cập đến phương thức đẳng cấp giống như là một phần của so sánh riêng của nó (tức là base.Equals (obj)) - nên sử dụng thay vào đó - sweetfa
@sweetfa: Nó phụ thuộc vào cách thức phương thức Equals của lớp con được thực thi. Nó cũng có thể gọi base.Equals ((BaseType) obj)) sẽ hoạt động tốt. - huha
Không, nó sẽ không: msdn.microsoft.com/en-us/library/system.object.gettype.aspx. Và bên cạnh đó, việc thực hiện một phương pháp không nên thất bại hoặc thành công tùy thuộc vào cách nó được gọi. Nếu kiểu thời gian chạy của một đối tượng là một lớp con của một số baseclass thì Equals () của baseclass sẽ trả về true nếu obj thực sự là bằng this không có vấn đề như thế nào Equals () của baseclass được gọi là. - Jupiter
Di chuyển fooItem trên cùng và sau đó kiểm tra nó cho null sẽ thực hiện tốt hơn trong trường hợp của null hoặc một loại sai. - IllidanS4
@ 40Alpha Vâng, vâng, sau đó obj as Foo sẽ không hợp lệ. - IllidanS4


Làm thế nào về:

public override int GetHashCode()
{
    return string.Format("{0}_{1}_{2}", prop1, prop2, prop3).GetHashCode();
}

Giả sử hiệu suất không phải là một vấn đề :)


23
2017-11-25 00:48



erm - nhưng bạn đang trả về một chuỗi cho một phương thức dựa trên int; _0 - jim tollan
Không, anh ta gọi GetHashCode () từ đối tượng String, trả về một int. - Richard Clayton
Tôi không mong đợi điều này được nhanh như tôi muốn, không chỉ cho các môn thể thao liên quan đến các loại giá trị, mà còn cho hiệu suất của string.Format. Một người khác geeky tôi đã thấy là new { prop1, prop2, prop3 }.GetHashCode(). Cant bình luận mặc dù cái nào sẽ chậm hơn giữa hai cái này. Đừng lạm dụng các công cụ. - nawfal
Điều này sẽ trả về giá trị đúng cho { prop1="_X", prop2="Y", prop3="Z" } và { prop1="", prop2="X_Y", prop3="Z_" }. Có thể bạn không muốn điều đó. - voetsjoeba
Đúng, bạn luôn có thể thay thế biểu tượng gạch dưới bằng một thứ gì đó không phổ biến (ví dụ:,, ▲, ►, ◄,, ☻) và hy vọng người dùng của bạn sẽ không sử dụng những biểu tượng này ... :) - Ludmil Tinkov


Đó là vì khung công tác yêu cầu hai đối tượng giống nhau phải có cùng mã băm. Nếu bạn ghi đè phương thức equals để so sánh đặc biệt hai đối tượng và hai đối tượng được coi là giống nhau bởi phương thức, thì mã băm của hai đối tượng cũng phải giống nhau. (Từ điển và Hashtables dựa trên nguyên tắc này).


9
2017-12-16 13:48





Chỉ cần thêm vào các câu trả lời ở trên:

Nếu bạn không ghi đè Equals thì hành vi mặc định là tham chiếu của các đối tượng được so sánh. Điều tương tự cũng áp dụng cho hashcode - implmentation mặc định thường dựa trên địa chỉ bộ nhớ của tham chiếu. Bởi vì bạn đã ghi đè Bằng nó có nghĩa là hành vi chính xác là so sánh bất cứ điều gì bạn đã thực hiện trên Equals và không phải là các tham chiếu, vì vậy bạn nên làm tương tự cho hashcode.

Khách hàng của lớp của bạn sẽ mong đợi hashcode có logic tương tự với phương thức equals, ví dụ phương thức linq sử dụng IEqualityComparer đầu tiên so sánh hashcodes và chỉ khi chúng bằng nhau, chúng sẽ so sánh phương thức Equals () có thể đắt hơn để chạy, nếu chúng ta không triển khai hashcode, đối tượng bằng nhau có lẽ sẽ có các mã băm khác nhau (vì chúng có địa chỉ bộ nhớ khác nhau) và sẽ được xác định sai như nhau (Equals () thậm chí sẽ không trúng).

Ngoài ra, ngoại trừ vấn đề mà bạn không thể tìm thấy đối tượng của bạn nếu bạn sử dụng nó trong từ điển (vì nó được chèn bởi một hashcode và khi bạn tìm nó, hashcode mặc định có thể sẽ khác nhau và một lần nữa là Equals () thậm chí sẽ không được gọi, như Marc Gravell giải thích trong câu trả lời của mình, bạn cũng giới thiệu một sự vi phạm từ điển hoặc khái niệm băm mà không nên cho phép các khóa giống nhau - bạn đã tuyên bố rằng những đối tượng này về cơ bản giống nhau khi bạn overrode Equals vì vậy bạn không muốn cả hai đối tượng này là các khóa khác nhau trên một cấu trúc dữ liệu giả sử có một khóa duy nhất. Nhưng vì chúng có một hashcode khác nhau, khóa "giống nhau" sẽ được chèn vào như một khóa khác.


8
2017-11-12 13:48





Chúng tôi có hai vấn đề để đối phó với.

  1. Bạn không thể cung cấp một hợp lý GetHashCode() nếu có trường nào trong đối tượng có thể được thay đổi. Thường thì một đối tượng sẽ KHÔNG BAO GIỜ được sử dụng trong một bộ sưu tập phụ thuộc vào GetHashCode(). Vì vậy, chi phí của thực hiện GetHashCode() thường không đáng, hoặc không khả thi.

  2. Nếu ai đó đặt đối tượng của bạn vào bộ sưu tập có cuộc gọi GetHashCode() và bạn đã ghi đè Equals() mà không cần phải làm GetHashCode() cư xử đúng cách, người đó có thể dành hàng ngày theo dõi vấn đề.

Vì vậy, theo mặc định tôi làm.

public class Foo
{
    public int FooId { get; set; }
    public string FooName { get; set; }

    public override bool Equals(object obj)
    {
        Foo fooItem = obj as Foo;

        return fooItem.FooId == this.FooId;
    }

    public override int GetHashCode()
    {
        // Some comment to explain if there is a real problem with providing GetHashCode() 
        // or if I just don't see a need for it for the given class
        throw new Exception("Sorry I don't know what GetHashCode should do for this class");
    }
}

7
2017-11-19 10:17



Ném ngoại lệ từ GetHashCode là vi phạm hợp đồng Object. Không có khó khăn khi xác định GetHashCode chức năng như vậy mà bất kỳ hai đối tượng được bằng nhau trả về cùng một mã băm; return 24601; và return 8675309; cả hai đều có thể triển khai hợp lệ GetHashCode. Hiệu suất của Dictionary sẽ chỉ được phong nha khi số lượng các mục là nhỏ, và sẽ nhận được rất xấu nếu số lượng các mục được lớn, nhưng nó sẽ làm việc một cách chính xác trong mọi trường hợp. - supercat
@supercat, Không thể triển khai GetHashCode theo cách hợp lý nếu các trường xác định trong đối tượng có thể thay đổi, vì mã băm không bao giờ thay đổi. Làm những gì bạn nói có thể khiến ai đó phải mất nhiều ngày theo dõi vấn đề hiệu suất, sau đó nhiều tuần trên một hệ thống lớn thiết kế lại để loại bỏ việc sử dụng các từ điển. - Ian Ringrose
Tôi đã từng làm một cái gì đó như thế này cho tất cả các lớp mà tôi đã định nghĩa cần Equals (), và tôi hoàn toàn chắc chắn rằng tôi sẽ không bao giờ sử dụng đối tượng đó làm khóa trong bộ sưu tập. Sau đó, một ngày một chương trình mà tôi đã sử dụng một đối tượng như thế là đầu vào cho một điều khiển DevExpress XtraGrid bị rơi. Nó chỉ ra XtraGrid, sau lưng tôi, đã tạo ra một HashTable hoặc một cái gì đó dựa trên các đối tượng của tôi. Tôi đã có một cuộc tranh luận nhỏ với DevExpress ủng hộ mọi người về điều này. Tôi nói nó không phải là thông minh mà họ dựa trên chức năng của thành phần và độ tin cậy của họ trên một khách hàng chưa biết thực hiện một phương pháp tối nghĩa. - RenniePet
Những người DevExpress khá rùng rợn, về cơ bản nói rằng tôi phải là một thằng ngốc để ném một ngoại lệ trong một phương thức GetHashCode (). Tôi vẫn nghĩ rằng họ nên tìm một phương pháp thay thế để làm những gì họ đang làm - tôi nhớ Marc Gravell về một chủ đề khác mô tả cách ông xây dựng một từ điển các đối tượng tùy ý mà không bị lệ thuộc vào GetHashCode () - không thể nhớ lại Tuy nhiên. - RenniePet
@RenniePet, phải tốt hơn có một lòng vì ném một ngoại lệ, sau đó có một rất khó để tìm lỗi do thực hiện không hợp lệ. - Ian Ringrose


Mã băm được sử dụng cho các bộ sưu tập dựa trên băm như Từ điển, Hashtable, HashSet vv Mục đích của mã này là để sắp xếp trước một cách nhanh chóng đối tượng cụ thể bằng cách đặt nó vào nhóm cụ thể (nhóm). Việc sắp xếp trước này giúp rất nhiều trong việc tìm kiếm đối tượng này khi bạn cần lấy lại nó từ bộ sưu tập băm vì mã phải tìm kiếm đối tượng của bạn chỉ trong một thùng thay vì trong tất cả các đối tượng mà nó chứa. Việc phân phối mã băm tốt hơn (tính duy nhất tốt hơn) việc truy xuất nhanh hơn. Trong tình huống lý tưởng mà mỗi đối tượng có một mã băm duy nhất, việc tìm kiếm nó là một hoạt động O (1). Trong hầu hết các trường hợp, nó tiếp cận O (1).


5
2018-02-21 11:36





Nó không nhất thiết quan trọng; nó phụ thuộc vào kích thước của bộ sưu tập của bạn và yêu cầu hiệu suất của bạn và liệu lớp học của bạn sẽ được sử dụng trong thư viện nơi bạn có thể không biết yêu cầu về hiệu suất. Tôi thường biết kích thước bộ sưu tập của mình không quá lớn và thời gian của tôi có giá trị hơn một vài phần nghìn giây hiệu suất đạt được bằng cách tạo mã băm hoàn hảo; vì vậy (để loại bỏ các cảnh báo gây phiền nhiễu bởi trình biên dịch), tôi chỉ cần sử dụng:

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

(Tất nhiên tôi cũng có thể sử dụng #pragma để tắt cảnh báo nhưng tôi thích cách này.)

Khi bạn ở vị trí mà bạn làm cần hiệu suất hơn tất cả các vấn đề được đề cập bởi những người khác ở đây áp dụng, tất nhiên. Quan trọng nhất - nếu không bạn sẽ nhận được kết quả sai khi truy xuất các mục từ bộ băm hoặc từ điển: mã băm không được thay đổi theo thời gian sống của đối tượng (chính xác hơn, trong suốt thời gian khi mã băm là cần thiết, chẳng hạn như khi đang là một từ khóa trong từ điển): ví dụ, sau đây là sai vì Value là public và do đó có thể được thay đổi bên ngoài vào lớp trong suốt thời gian tồn tại của ví dụ, vì vậy bạn không được sử dụng nó làm cơ sở cho mã băm:


   class A
   {
      public int Value;

      public override int GetHashCode()
      {
         return Value.GetHashCode(); //WRONG! Value is not constant during the instance's life time
      }
   }    

Mặt khác, nếu không thể thay đổi giá trị, bạn có thể sử dụng:


   class A
   {
      public readonly int Value;

      public override int GetHashCode()
      {
         return Value.GetHashCode(); //OK  Value is read-only and can't be changed during the instance's life time
      }
   }


3
2018-06-26 23:21



Đã bỏ phiếu. Điều này là sai. Ngay cả trạng thái của Microsoft trong MSDN (msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx) giá trị của GetHashCode PHẢI thay đổi khi trạng thái của đối tượng thay đổi theo cách có thể ảnh hưởng đến giá trị trả về của một cuộc gọi đến Equals (), và thậm chí trong ví dụ của nó nó cũng cho thấy việc triển khai GetHashCode hoàn toàn phụ thuộc vào các giá trị có thể thay đổi công khai. - Sebastian P.R. Gingter
Sebastian, tôi không đồng ý: Nếu bạn thêm một đối tượng vào một bộ sưu tập sử dụng mã băm, nó sẽ được đưa vào thùng rác phụ thuộc vào mã băm. Nếu bây giờ bạn thay đổi mã băm, bạn sẽ không tìm thấy đối tượng một lần nữa trong bộ sưu tập vì thùng rác sẽ được tìm kiếm. Đây là, trên thực tế, một cái gì đó đã xảy ra trong mã của chúng tôi và đó là lý do tại sao tôi thấy nó cần thiết để chỉ ra điều đó. - ILoveFortran
Sebastian, Ngoài ra, tôi không thể nhìn thấy một tuyên bố trong liên kết (msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx) GetHashCode () phải thay đổi. Ngược lại - nó không được thay đổi miễn là Equals trả về cùng một giá trị cho cùng một đối số: "Phương thức GetHashCode cho một đối tượng phải trả về cùng một mã băm miễn là không có sửa đổi đối tượng trạng thái xác định giá trị trả về của phương thức Equals của đối tượng. "Câu lệnh này không ngụ ý ngược lại, rằng nó phải thay đổi nếu giá trị trả về bằng với các thay đổi. - ILoveFortran
@ILoveFortran, tôi không nghĩ rằng những gì bạn đang nói là chính xác. Bài viết MSDN nêu rõ: "Mã băm không phải là giá trị vĩnh viễn. Vì lý do này: 1) Không tuần tự hóa các giá trị mã băm hoặc lưu trữ chúng trong cơ sở dữ liệu. 2) Không sử dụng mã băm làm khóa để lấy đối tượng từ bộ sưu tập có khóa. 3 ... 4 ... ", tức là, thay đổi HasCode trong suốt thời gian tồn tại của đối tượng và mã của bạn cần phải biết điều đó. Nếu bạn muốn làm cho mỗi đối tượng duy nhất với một định danh mà không bao giờ thay đổi trong cuộc đời của nó, bạn nên sử dụng cái gì khác. - Joao Coelho
@ Jaao, bạn đang bối rối phía khách hàng / người tiêu dùng của hợp đồng với nhà sản xuất / người triển khai. Tôi đang nói về trách nhiệm của người thực hiện, người ghi đè GetHashCode (). Bạn đang nói về người tiêu dùng, người đang sử dụng giá trị. - ILoveFortran


Đó là sự hiểu biết của tôi rằng GetHashCode gốc () trả về địa chỉ bộ nhớ của đối tượng, do đó, điều cần thiết là ghi đè lên nó nếu bạn muốn so sánh hai đối tượng khác nhau.

CHỈNH SỬA: Điều đó không chính xác, phương thức GetHashCode () ban đầu không thể đảm bảo sự bình đẳng của 2 giá trị. Mặc dù các đối tượng bằng nhau trả lại cùng một mã băm.


0
2017-10-07 17:06