Câu hỏi Thuật toán tốt nhất cho System.Object.GetHashCode bị ghi đè là gì?


Trong lưới System.Object.GetHashCode phương pháp được sử dụng ở rất nhiều nơi, trong suốt các thư viện lớp cơ sở .NET. Đặc biệt là khi tìm kiếm các vật phẩm trong một bộ sưu tập nhanh hoặc để xác định sự bình đẳng. Có một thuật toán chuẩn / thực hành tốt nhất về cách triển khai GetHashCode ghi đè cho các lớp tùy chỉnh của tôi vì vậy tôi không làm suy giảm hiệu suất?


1218
2017-11-04 20:53


gốc


Sau khi đọc câu hỏi này và bài viết dưới đây, tôi có thể thực hiện ghi đè GetHashCode. Tôi hy vọng nó sẽ hữu ích cho người khác. Nguyên tắc và quy tắc cho GetHashCode được viết bởi Eric Lippert - rene
"hoặc để xác định bình đẳng": không! Hai đối tượng có cùng mã băm không nhất thiết phải bằng nhau. - Thomas Levesque
@ThomasLevesque Bạn nói đúng, hai đối tượng có cùng mã băm không nhất thiết phải bằng nhau. Nhưng vẫn GetHashCode() được sử dụng trong nhiều triển khai Equals(). Đó là điều tôi muốn nói với câu nói đó. GetHashCode() phía trong Equals() thường được sử dụng làm lối tắt để xác định sự bất bình đẳng, bởi vì nếu hai vật thể có khác nhau mã băm họ phải là đối tượng không bằng nhau và phần còn lại của kiểm tra bình đẳng không phải thực hiện. - bitbonk
@bitbonk Thông thường, cả hai GetHashCode() và Equals() cần phải xem xét tất cả các trường của cả hai đối tượng (Equals phải làm điều này nếu nó hashcodes bằng hoặc không được kiểm tra). Bởi vì điều này, một cuộc gọi đến GetHashCode() phía trong Equals() thường thừa và có thể giảm hiệu suất. Equals() cũng có thể ngắn mạch, làm cho nó nhanh hơn nhiều - tuy nhiên trong một số trường hợp, mã băm có thể được lưu vào bộ nhớ cache, làm cho GetHashCode() kiểm tra nhanh hơn và đáng giá như vậy. Xem câu hỏi này để biết thêm. - NotEnoughData


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


Tôi thường đi với một cái gì đó giống như việc thực hiện được đưa ra trong Josh Bloch của tuyệt vời  Java hiệu quả. Đó là nhanh chóng và tạo ra một hash khá tốt mà không có khả năng gây ra va chạm. Chọn hai số nguyên tố khác nhau, ví dụ: 17 và 23, và làm:

public override int GetHashCode()
{
    unchecked // Overflow is fine, just wrap
    {
        int hash = 17;
        // Suitable nullity checks etc, of course :)
        hash = hash * 23 + field1.GetHashCode();
        hash = hash * 23 + field2.GetHashCode();
        hash = hash * 23 + field3.GetHashCode();
        return hash;
    }
}

Như đã lưu ý trong các nhận xét, bạn có thể thấy tốt hơn là chọn một số nguyên tố lớn để nhân với thay vào đó. Rõ ràng 486187739 là tốt ... và mặc dù hầu hết các ví dụ tôi đã nhìn thấy với số lượng nhỏ có xu hướng sử dụng số nguyên tố, có ít nhất các thuật toán tương tự mà các số nguyên tố thường được sử dụng. Trong không hoàn toàn-FNV ví dụ sau, ví dụ, tôi đã sử dụng các con số có vẻ hoạt động tốt - nhưng giá trị ban đầu không phải là số nguyên tố. (Hằng số nhân  mặc dù. Tôi không biết nó quan trọng như thế nào.)

Điều này là tốt hơn so với thực tế phổ biến của XORing hashcodes vì ​​hai lý do chính. Giả sử chúng ta có một loại với hai int lĩnh vực:

XorHash(x, x) == XorHash(y, y) == 0 for all x, y
XorHash(x, y) == XorHash(y, x) for all x, y

Bằng cách này, các thuật toán trước đó là một trong những hiện đang được sử dụng bởi trình biên dịch C # cho các loại vô danh.

Trang này đưa ra một số tùy chọn. Tôi nghĩ rằng đối với hầu hết các trường hợp ở trên là "đủ tốt" và nó vô cùng dễ dàng để nhớ và nhận được ngay. Các FNV thay thế tương tự đơn giản, nhưng sử dụng các hằng số khác nhau và XOR thay vì ADD như một hoạt động kết hợp. Nó trông một cái gì đó giống như mã bên dưới, nhưng thuật toán FNV bình thường hoạt động trên các byte riêng lẻ, do đó, điều này sẽ yêu cầu sửa đổi để thực hiện một lần lặp trên mỗi byte, thay vì mỗi giá trị băm 32 bit. FNV cũng được thiết kế cho độ dài thay đổi của dữ liệu, trong khi cách chúng tôi đang sử dụng nó ở đây luôn luôn cho cùng một số giá trị trường. Nhận xét về câu trả lời này cho thấy rằng mã ở đây không thực sự hoạt động tốt (trong trường hợp mẫu được kiểm tra) là phương pháp bổ sung ở trên.

// Note: Not quite FNV!
public override int GetHashCode()
{
    unchecked // Overflow is fine, just wrap
    {
        int hash = (int) 2166136261;
        // Suitable nullity checks etc, of course :)
        hash = (hash * 16777619) ^ field1.GetHashCode();
        hash = (hash * 16777619) ^ field2.GetHashCode();
        hash = (hash * 16777619) ^ field3.GetHashCode();
        return hash;
    }
}

Lưu ý rằng một điều cần lưu ý là lý tưởng bạn nên ngăn chặn trạng thái nhạy cảm bình đẳng (và do đó hashcode-nhạy cảm) thay đổi sau khi thêm nó vào một tập hợp phụ thuộc vào mã băm.

Theo tài liệu:

Bạn có thể ghi đè GetHashCode cho các loại tham chiếu không thay đổi được. Nói chung, đối với các loại tham chiếu có thể thay đổi, bạn chỉ nên ghi đè GetHashCode nếu:

  • Bạn có thể tính toán mã băm từ các trường không thể thay đổi được; hoặc là
  • Bạn có thể đảm bảo rằng mã băm của một đối tượng có thể thay đổi không thay đổi trong khi đối tượng được chứa trong một bộ sưu tập dựa trên mã băm của nó.

1362
2017-11-04 20:56



Các thuật toán được mô tả trong cuốn sách bạn đề cập là infact chi tiết hơn một chút nó especailly mô tả phải làm gì cho các loại dữ liệu khác nhau của các lĩnh vực. Ví dụ: đối với các trường sử dụng loại dài (int) (trường ^ f >>> 32) thay vì chỉ cần gọi GetHashcode. Long.GetHashCodes có được triển khai theo cách đó không? - bitbonk
Yup, Int64.GetHashCode thực hiện chính xác điều đó. Trong Java có thể yêu cầu boxing, tất nhiên. Điều đó nhắc tôi - thời gian để thêm liên kết vào sách ... - Jon Skeet
23 không phải là lựa chọn tốt, vì (tính đến .net 3.5 SP1) Dictionary<TKey,TValue> giả định tốt modulo phân phối số nguyên tố nhất định. Và 23 là một trong số đó. Vì vậy, nếu bạn có từ điển với dung lượng 23 chỉ đóng góp cuối cùng cho GetHashCode ảnh hưởng đến hashcode phức hợp. Vì vậy, tôi muốn sử dụng 29 thay vì 23. - CodesInChaos
@CodeInChaos: Chỉ đóng góp cuối cùng ảnh hưởng đến nhóm - vì vậy, có thể, lúc tồi tệ nhất, phải xem xét tất cả 23 các mục nhập trong từ điển. Nó vẫn sẽ kiểm tra mã băm thực tế của mỗi mục, nó sẽ rẻ. Nếu bạn có một từ điển nhỏ, nó không có vấn đề gì nhiều. - Jon Skeet
@ Vajda: Tôi thường sử dụng 0 làm mã băm hiệu quả cho null - không giống như bỏ qua trường. - Jon Skeet


Microsoft đã cung cấp một trình tạo HashCode chung tốt: Chỉ cần sao chép các giá trị thuộc tính / trường của bạn vào một kiểu ẩn danh và băm nó:

new { PropA, PropB, PropC, PropD }.GetHashCode();

Điều này sẽ làm việc cho bất kỳ số lượng tài sản. Nó không sử dụng quyền anh hoặc tài nguyên phụ. Nó chỉ sử dụng các thuật toán đã được thực hiện trong khuôn khổ cho các loại vô danh.


302
2018-01-07 21:38



Có, ẩn danh GetHashCode việc thực hiện rất hiệu quả (BTW giống như câu trả lời của Jon Skeet), nhưng vấn đề duy nhất với giải pháp này là bạn tạo ra một cá thể mới tại bất kỳ GetHashCode gọi điện. Nó có thể là một chút chi phí-ish đặc biệt trong trường hợp truy cập chuyên sâu vào các bộ sưu tập băm lớn ... - digEmAll
Điều này làm việc trong VB w / .NET 4.0, nhưng nhìn qua IL, nó đang sử dụng box cuộc gọi kể từ khi loại sử dụng Generics. Không unboxing, nhưng từ đọc của tôi ở đây, sự hiện diện chỉ của boxing cho thấy điều này có thể là một chút không hiệu quả. Có vẻ như sự lựa chọn duy nhất cho VB, mặc dù, vì nó không tương đương với checked/ 'bỏ chọn'. - Kumba
@ digEmAll Tốt điểm, tôi không nghĩ về chi phí của việc tạo ra một đối tượng mới. Câu trả lời của Jon Skeet là hiệu quả nhất và sẽ không sử dụng quyền anh. (@Kumba Để giải quyết việc bỏ chọn trong VB, chỉ cần sử dụng một Int64 (dài) và cắt ngắn nó sau khi tính toán.) - Rick Love
chỉ có thể nói new { PropA, PropB, PropC, PropD }.GetHashCode() quá - sehe
VB.NET phải sử dụng Key trong việc tạo kiểu ẩn danh: New With {Key PropA}.GetHashCode() Nếu không GetHashCode sẽ không trả về cùng một hashcode cho các đối tượng khác nhau với cùng một thuộc tính 'xác định'. - David Osborne


Đây là trình trợ giúp hashcode của tôi.
Đó là lợi thế là nó sử dụng các đối số kiểu chung và do đó sẽ không gây ra boxing:

public static class HashHelper
{
    public static int GetHashCode<T1, T2>(T1 arg1, T2 arg2)
    {
         unchecked
         {
             return 31 * arg1.GetHashCode() + arg2.GetHashCode();
         }
    }

    public static int GetHashCode<T1, T2, T3>(T1 arg1, T2 arg2, T3 arg3)
    {
        unchecked
        {
            int hash = arg1.GetHashCode();
            hash = 31 * hash + arg2.GetHashCode();
            return 31 * hash + arg3.GetHashCode();
        }
    }

    public static int GetHashCode<T1, T2, T3, T4>(T1 arg1, T2 arg2, T3 arg3, 
        T4 arg4)
    {
        unchecked
        {
            int hash = arg1.GetHashCode();
            hash = 31 * hash + arg2.GetHashCode();
            hash = 31 * hash + arg3.GetHashCode();
            return 31 * hash + arg4.GetHashCode();
        }
    }

    public static int GetHashCode<T>(T[] list)
    {
        unchecked
        {
            int hash = 0;
            foreach (var item in list)
            {
                hash = 31 * hash + item.GetHashCode();
            }
            return hash;
        }
    }

    public static int GetHashCode<T>(IEnumerable<T> list)
    {
        unchecked
        {
            int hash = 0;
            foreach (var item in list)
            {
                hash = 31 * hash + item.GetHashCode();
            }
            return hash;
        }
    }

    /// <summary>
    /// Gets a hashcode for a collection for that the order of items 
    /// does not matter.
    /// So {1, 2, 3} and {3, 2, 1} will get same hash code.
    /// </summary>
    public static int GetHashCodeForOrderNoMatterCollection<T>(
        IEnumerable<T> list)
    {
        unchecked
        {
            int hash = 0;
            int count = 0;
            foreach (var item in list)
            {
                hash += item.GetHashCode();
                count++;
            }
            return 31 * hash + count.GetHashCode();
        }
    }

    /// <summary>
    /// Alternative way to get a hashcode is to use a fluent 
    /// interface like this:<br />
    /// return 0.CombineHashCode(field1).CombineHashCode(field2).
    ///     CombineHashCode(field3);
    /// </summary>
    public static int CombineHashCode<T>(this int hashCode, T arg)
    {
        unchecked
        {
            return 31 * hashCode + arg.GetHashCode();   
        }
    }

Ngoài ra nó có phương pháp mở rộng để cung cấp một giao diện thông thạo, vì vậy bạn có thể sử dụng nó như thế này:

public override int GetHashCode()
{
    return HashHelper.GetHashCode(Manufacturer, PartN, Quantity);
}

hoặc như thế này:

public override int GetHashCode()
{
    return 0.CombineHashCode(Manufacturer)
        .CombineHashCode(PartN)
        .CombineHashCode(Quantity);
}

94
2018-04-04 18:26



Không cần T[] riêng biệt như nó đã IEnumerable<T> - nawfal
Bạn có thể cấu trúc lại các phương thức đó và hạn chế logic lõi thành một hàm - nawfal
Ngẫu nhiên, 31 là một sự thay đổi và trừ trên CPU, đó là cực kỳ nhanh. - Chui Tey
@nightcoder bạn có thể sử dụng thông số. - ANeves
@ChuiTey Đây là một cái gì đó tất cả Mersenne Primes có điểm chung. - Pharap


Tôi có một lớp Hashing trong thư viện trợ giúp mà tôi sử dụng nó cho mục đích này.

/// <summary> 
/// This is a simple hashing function from Robert Sedgwicks Hashing in C book.
/// Also, some simple optimizations to the algorithm in order to speed up
/// its hashing process have been added. from: www.partow.net
/// </summary>
/// <param name="input">array of objects, parameters combination that you need
/// to get a unique hash code for them</param>
/// <returns>Hash code</returns>
public static int RSHash(params object[] input)
{
    const int b = 378551;
    int a = 63689;
    int hash = 0;

    // If it overflows then just wrap around
    unchecked
    {
        for (int i = 0; i < input.Length; i++)
        {
            if (input[i] != null)
            {
                hash = hash * a + input[i].GetHashCode();
                a = a * b;
            }
        }
    }

    return hash;
}

Sau đó, chỉ đơn giản là bạn có thể sử dụng nó như:

public override int GetHashCode()
{
    return Hashing.RSHash(_field1, _field2, _field3);
}

Tôi đã không đánh giá hiệu quả của nó, vì vậy bất kỳ thông tin phản hồi được hoan nghênh.


57
2018-02-23 11:46



Vâng, nó sẽ gây ra boxing, nếu các lĩnh vực là loại giá trị. - nightcoder
+1 cho null kiểm tra xem các câu trả lời khác (nếu không có lẽ tốt hơn) chưa bao gồm. - Mark Hurd
"có thể được tăng cường sau đó bằng cách bắt OverflowException" Toàn bộ điểm của unchecked là để tránh ngoại lệ trên tràn mà là mong muốn trên GetHashCode. Vì vậy, nó không chính xác nếu giá trị tràn int và nó không đau chút nào. - Tim Schmelter
Một vấn đề với thuật toán này là bất kỳ mảng nào chứa đầy null sẽ luôn trả về 0, bất kể chiều dài của nó là bao nhiêu - Nathan Adams
Phương thức trợ giúp này cũng phân bổ một đối tượng mới [] - James Newton-King


Đây là lớp trợ giúp của tôi bằng cách sử dụng Triển khai của Jon Skeet.

public static class HashCode
{
    public const int Start = 17;

    public static int Hash<T>(this int hash, T obj)
    {
        var h = EqualityComparer<T>.Default.GetHashCode(obj);
        return unchecked((hash * 31) + h);
    }
}

Sử dụng:

public override int GetHashCode()
{
    return HashCode.Start
        .Hash(_field1)
        .Hash(_field2)
        .Hash(_field3);
}

Nếu bạn muốn tránh viết một phương thức mở rộng cho System.Int32:

public struct HashCode
{
    private readonly int _value;

    public HashCode(int value) => _value = value;

    public static HashCode Start { get; } = new HashCode(17);

    public static implicit operator int(HashCode hash) => hash._value;

    public HashCode Hash<T>(T obj)
    {
        var h = EqualityComparer<T>.Default.GetHashCode(obj);
        return unchecked(new HashCode((_value * 31) + h));
    }

    public override int GetHashCode() => _value;
}

Nó vẫn còn chung chung, nó vẫn tránh được bất kỳ phân bổ đống nào và nó được sử dụng chính xác theo cùng một cách:

public override int GetHashCode()
{
    // This time `HashCode.Start` is not an `Int32`, it's a `HashCode` instance.
    // And the result is implicitly converted to `Int32`.
    return HashCode.Start
        .Hash(_field1)
        .Hash(_field2)     
        .Hash(_field3);
}

Cập nhật sau bình luận của Martin:

obj != null gây ra boxing nên tôi chuyển sang bộ so sánh mặc định.

Chỉnh sửa (tháng 5 năm 2018):

EqualityComparer<T>.Default getter bây giờ là một bản chất JIT - yêu cầu kéo được đề cập bởi Stephen Toub trong bài đăng trên blog này.


49
2017-09-04 12:32



Tôi sẽ thay đổi dòng với toán tử đại học là: var h = Equals(obj, default(T)) ? 0 : obj.GetHashCode(); - Bill Barry
Tôi tin rằng toán tử bậc ba với obj != null sẽ biên dịch thành box hướng dẫn sẽ cấp phát bộ nhớ nếu T là một loại giá trị. Thay vào đó bạn có thể sử dụng obj.Equals(null) sẽ biên dịch thành cuộc gọi ảo của Equals phương pháp. - Martin Liversage
Bởi vì this.hashCode != h. Nó sẽ không trả về cùng một giá trị. - Şafak Gür
Xin lỗi, hãy quản lý để xóa nhận xét của tôi thay vì chỉnh sửa nhận xét đó. Có lợi hơn khi tạo cấu trúc mới sau đó thay đổi hashCode thành không chỉ đọc và làm: "bỏ chọn {this.hashCode ^ = h * 397;} trả về giá trị này;" ví dụ? - Erik Karlsson
Tính bất biến có lợi ích của nó (Tại sao các cấu trúc có thể thay đổi được là ác?). Về hiệu suất, những gì tôi làm là khá rẻ vì nó không phân bổ bất kỳ không gian nào trong heap. - Şafak Gür


Trong hầu hết các trường hợp mà Equals () so sánh nhiều trường, nó không quan trọng nếu GetHash () của bạn băm trên một trường hoặc trên nhiều trường. Bạn chỉ cần đảm bảo tính toán giá trị băm thực sự rẻ (Không phân bổ, xin vui lòng) và nhanh chóng (Không có tính toán nặng và chắc chắn không có kết nối cơ sở dữ liệu) và cung cấp một bản phân phối tốt.

Việc nâng hạng nặng phải là một phần của phương thức Equals (); băm nên là một hoạt động rất rẻ để cho phép gọi Equals () trên càng ít các mục càng tốt.

Và một mẹo cuối cùng: Đừng dựa vào GetHashCode () được ổn định trên nhiều ứng dụng chạy. Nhiều loại .Net không đảm bảo mã băm của chúng vẫn giữ nguyên sau khi khởi động lại, vì vậy bạn chỉ nên sử dụng giá trị của GetHashCode () cho trong cấu trúc dữ liệu bộ nhớ.


26
2018-02-23 11:55



"Trong hầu hết các trường hợp mà Equals () so sánh nhiều trường, nó không thực sự quan trọng nếu GetHash () của bạn băm trên một trường hoặc trên nhiều trường." Đây là lời khuyên nguy hiểm, bởi vì đối với các đối tượng chỉ khác nhau trong các trường chưa băm, bạn sẽ nhận được các xung đột băm. Nếu điều này xảy ra thường xuyên, hiệu suất của các bộ sưu tập dựa trên băm (HashMap, HashSet, vv) sẽ làm suy giảm (lên đến O (n) trong trường hợp xấu nhất). - sleske
Điều này thực sự đã xảy ra trong Java: Trong các phiên bản đầu của JDK String.hashCode () chỉ được coi là đầu của chuỗi; điều này dẫn đến các vấn đề về hiệu suất nếu bạn đã sử dụng các chuỗi như các khóa trong HashMaps, điều này chỉ khác nhau ở cuối (ví dụ phổ biến cho các URL). Do đó, thuật toán đã thay đổi (trong JDK 1.2 hoặc 1.3 tôi tin). - sleske
Nếu một trường 'cung cấp một phân phối tốt' (phần cuối cùng của câu trả lời của tôi), thì một trường là đủ .. Nếu nó không cung cấp phân phối tốt, sau đó (và ngay sau đó) bạn cần một phép tính khác. (Ví dụ: chỉ sử dụng một trường khác làm cung cấp phân phối tốt hoặc sử dụng nhiều trường) - Bert Huijben
Tôi không nghĩ có vấn đề gì GetHashCode thực hiện phân bổ bộ nhớ, miễn là nó chỉ làm như vậy lần đầu tiên nó được sử dụng (với các lời gọi tiếp theo chỉ đơn giản là trả lại kết quả được lưu trong bộ nhớ cache). Điều quan trọng không phải là người ta nên đi đến độ dài lớn để tránh va chạm, mà là người ta nên tránh va chạm "có hệ thống". Nếu một loại có hai int lĩnh vực oldX và newX thường khác nhau một, giá trị băm của oldX^newX sẽ chỉ định 90% giá trị băm của bản ghi là 1, 2, 4 hoặc 8. Sử dụng oldX+newX [số học không được kiểm soát] có thể tạo ra nhiều va chạm hơn ... - supercat
... hơn là chức năng phức tạp hơn, nhưng một bộ sưu tập 1.000.000 thứ có 500.000 giá trị băm khác nhau sẽ rất tốt nếu mỗi giá trị băm có hai thứ liên quan và rất nặng nếu một giá trị băm có 500.001 thứ và các giá trị băm khác có giá trị băm. - supercat


Cho đến gần đây câu trả lời của tôi sẽ rất gần với Jon Skeet ở đây. Tuy nhiên, gần đây tôi đã bắt đầu một dự án sử dụng bảng băm hai bảng, đó là các bảng băm có kích thước của bảng nội bộ là 8, 16, 32, v.v. Có một lý do chính đáng để ưu tiên các kích thước số nguyên tố, nhưng cũng có một số lợi thế đối với hai kích cỡ nguồn.

Và nó khá nhiều hút. Vì vậy, sau một chút thử nghiệm và nghiên cứu, tôi bắt đầu tái băm băm của tôi với những điều sau đây:

public static int ReHash(int source)
{
  unchecked
  {
    ulong c = 0xDEADBEEFDEADBEEF + (ulong)source;
    ulong d = 0xE2ADBEEFDEADBEEF ^ c;
    ulong a = d += c = c << 15 | c >> -15;
    ulong b = a += d = d << 52 | d >> -52;
    c ^= b += a = a << 26 | a >> -26;
    d ^= c += b = b << 51 | b >> -51;
    a ^= d += c = c << 28 | c >> -28;
    b ^= a += d = d << 9 | d >> -9;
    c ^= b += a = a << 47 | a >> -47;
    d ^= c += b << 54 | b >> -54;
    a ^= d += c << 32 | c >> 32;
    a += d << 25 | d >> -25;
    return (int)(a >> 1);
  }
}

Và rồi bảng băm hai của tôi không còn hút nữa.

Điều này làm tôi băn khoăn, bởi vì điều trên không nên hoạt động. Hay chính xác hơn, nó sẽ không hoạt động trừ khi bản gốc GetHashCode() nghèo nàn theo cách rất đặc biệt.

Việc trộn lại mã băm không thể cải thiện mã băm lớn, bởi vì hiệu ứng duy nhất có thể là chúng tôi giới thiệu thêm một vài xung đột.

Việc trộn lại mã băm không thể cải thiện mã băm khủng khiếp, bởi vì hiệu ứng duy nhất có thể là chúng tôi thay đổi, ví dụ: một số lượng lớn các va chạm trên giá trị 53 đến một số lượng lớn giá trị 18.3487.291.

Việc trộn lại mã băm chỉ có thể cải thiện mã băm ít nhất cũng khá tốt trong việc tránh va chạm tuyệt đối trong phạm vi của nó (232 các giá trị có thể) nhưng không tốt khi tránh va chạm khi modulo xuống để sử dụng thực tế trong bảng băm. Trong khi modulo đơn giản của một bảng power-of-two làm cho điều này rõ ràng hơn, nó cũng có tác động tiêu cực với các bảng số nguyên tố phổ biến hơn, điều đó không rõ ràng (công việc phụ trong phục hồi sẽ lớn hơn lợi ích , nhưng lợi ích vẫn sẽ ở đó).

Chỉnh sửa: Tôi cũng đang sử dụng địa chỉ mở, điều này cũng sẽ làm tăng độ nhạy cảm với va chạm, có lẽ nhiều hơn so với thực tế đó là sức mạnh của hai.

Và tốt, nó đã làm phiền bao nhiêu string.GetHashCode() triển khai trong .MẠNG LƯỚI (hoặc nghiên cứu đây) có thể được cải thiện theo cách này (theo thứ tự các thử nghiệm chạy nhanh hơn khoảng 20-30 lần do ít va chạm hơn) và càng làm phiền thêm bao nhiêu mã băm của riêng tôi có thể được cải thiện (nhiều hơn thế).

Tất cả các triển khai GetHashCode () tôi đã mã hóa trong quá khứ và thực sự được sử dụng làm cơ sở của các câu trả lời trên trang web này, đã tồi tệ hơn nhiều so với tôi đã thông qua. Phần lớn thời gian đó là "đủ tốt" cho nhiều công dụng, nhưng tôi muốn cái gì đó tốt hơn.

Vì vậy, tôi đặt dự án đó sang một bên (dù đó là dự án thú cưng) và bắt đầu xem xét cách tạo ra một mã băm tốt, được phân phối tốt trong .NET một cách nhanh chóng.

Cuối cùng tôi quyết định chuyển SpookyHash tới .NET. Thật vậy, đoạn mã trên là phiên bản đường dẫn nhanh của việc sử dụng SpookyHash để tạo ra đầu ra 32 bit từ đầu vào 32 bit.

Bây giờ, SpookyHash không phải là một cách nhanh chóng để nhớ đoạn mã. Cổng của tôi của nó thậm chí còn ít hơn vì tôi đã phác thảo rất nhiều cho tốc độ tốt hơn *. Nhưng đó là những gì tái sử dụng mã là cho.

Sau đó tôi đặt cái đó dự án ở một bên, bởi vì cũng giống như dự án ban đầu đã tạo ra câu hỏi về cách tạo ra mã băm tốt hơn, do đó dự án đã tạo ra câu hỏi về cách tạo ra một bản ghi .NET tốt hơn.

Sau đó tôi quay lại và tạo ra rất nhiều tình trạng quá tải để dễ dàng cho ăn tất cả các loại bản địa (ngoại trừ decimal†) vào một mã băm.

Thật nhanh, Bob Jenkins xứng đáng nhận được hầu hết tín dụng vì mã ban đầu mà tôi chuyển từ vẫn nhanh hơn, đặc biệt là trên các máy 64 bit mà thuật toán được tối ưu hóa cho ‡.

Bạn có thể xem mã đầy đủ tại https://bitbucket.org/JonHanna/spookilysharp/src nhưng hãy xem xét mã ở trên là một phiên bản đơn giản của nó.

Tuy nhiên, vì nó đã được viết, người ta có thể sử dụng nó dễ dàng hơn:

public override int GetHashCode()
{
  var hash = new SpookyHash();
  hash.Update(field1);
  hash.Update(field2);
  hash.Update(field3);
  return hash.Final().GetHashCode();
}

Nó cũng có giá trị hạt giống, vì vậy nếu bạn cần phải đối phó với đầu vào không tin cậy và muốn bảo vệ chống lại các cuộc tấn công Hash DoS, bạn có thể thiết lập một hạt giống dựa trên thời gian hoạt động hoặc tương tự, và làm cho kết quả không thể đoán trước bởi kẻ tấn công:

private static long hashSeed0 = Environment.TickCount;
private static long hashSeed1 = DateTime.Now.Ticks;
public override int GetHashCode()
{
  //produce different hashes ever time this application is restarted
  //but remain consistent in each run, so attackers have a harder time
  //DoSing the hash tables.
  var hash = new SpookyHash(hashSeed0, hashSeed1);
  hash.Update(field1);
  hash.Update(field2);
  hash.Update(field3);
  return hash.Final().GetHashCode();
}

* Một bất ngờ lớn trong việc này là bàn tay nội tuyến một phương pháp quay trở lại (x << n) | (x >> -n) cải thiện mọi thứ. Tôi chắc chắn rằng người jitter có thể đã vạch ra điều đó cho tôi, nhưng hồ sơ cho thấy khác.

decimal không có nguồn gốc từ quan điểm .NET mặc dù nó là từ C #. Vấn đề với nó là của riêng nó GetHashCode() xử lý độ chính xác là đáng kể trong khi chính nó Equals() không làm. Cả hai đều là lựa chọn hợp lệ, nhưng không được trộn lẫn như vậy. Khi triển khai phiên bản của riêng bạn, bạn cần phải chọn một hoặc phiên bản khác, nhưng tôi không thể biết bạn muốn gì.

‡ Bằng cách so sánh. Nếu được sử dụng trên một chuỗi, SpookyHash trên 64 bit nhanh hơn đáng kể so với string.GetHashCode() trên 32 bit nhanh hơn một chút so với string.GetHashCode() trên 64 bit, nhanh hơn đáng kể so với SpookyHash trên 32 bit, mặc dù vẫn đủ nhanh để trở thành lựa chọn hợp lý.


19
2018-01-14 14:15



Khi kết hợp nhiều giá trị băm thành một, tôi có xu hướng sử dụng long các giá trị cho kết quả trung gian và sau đó giảm kết quả cuối cùng xuống một int. Điều đó có vẻ như là một ý tưởng hay không? Mối quan tâm của tôi là người ta sử dụng ví dụ: hash = (hash * 31) + nextField, sau đó các cặp giá trị khớp sẽ chỉ ảnh hưởng đến 27 bit trên của băm. Để tính toán mở rộng thành longvà gói các thứ trong sẽ giảm thiểu nguy hiểm đó. - supercat
@supercat nó phụ thuộc vào sự phân phối của munging cuối cùng của bạn. Thư viện SpookilySharp sẽ đảm bảo rằng phân phối tốt, lý tưởng (vì nó không cần tạo đối tượng) bằng cách chuyển một con trỏ tới một kiểu blittable, hoặc truyền một trong số các enumerables nó xử lý trực tiếp, nhưng nếu bạn không có blittable dữ liệu hoặc một điều tra thích hợp, sau đó gọi .Update() với nhiều giá trị theo câu trả lời ở trên sẽ thực hiện thủ thuật. - Jon Hanna
@ JonHanna bạn sẽ sẵn sàng để chính xác hơn với hành vi có vấn đề bạn gặp phải? Tôi đang cố gắng triển khai một thư viện giúp thực hiện các đối tượng giá trị tầm thường (ValueUtils) và tôi rất thích một bài kiểm tra thể hiện sự sai lệch băm kém trong các thẻ bắt đầu bằng sức mạnh của hai nguồn. - Eamon Nerbonne
@EamonNerbonne Tôi không thực sự có bất cứ điều gì chính xác hơn "tổng thời gian chậm hơn theo cách đó". Như tôi đã thêm vào trong một chỉnh sửa, thực tế là tôi đã sử dụng địa chỉ mở có thể quan trọng hơn yếu tố sức mạnh của hai yếu tố. Tôi có kế hoạch thực hiện một số trường hợp thử nghiệm trên một dự án cụ thể mà tôi sẽ so sánh một vài cách tiếp cận khác nhau, vì vậy tôi có thể có câu trả lời tốt hơn cho bạn sau đó, mặc dù đó không phải là ưu tiên cao. , vì vậy tôi sẽ nhận được nó khi tôi nhận được nó ...) - Jon Hanna
@ JonHanna: vâng tôi biết lịch trình dự án cá nhân diễn ra như thế nào - chúc may mắn! Trong mọi trường hợp, tôi thấy tôi không có cụm từ mà bình luận cuối cùng tốt: Tôi có nghĩa là để yêu cầu đầu vào có vấn đề, và không nhất thiết phải chi tiết các vấn đề mà kết quả. Tôi rất thích sử dụng nó như một bộ kiểm tra (hoặc cảm hứng cho một bộ kiểm tra). Trong mọi trường hợp - chúc may mắn với dự án thú cưng của bạn :-). - Eamon Nerbonne


Đây là một người tốt:

/// <summary>
/// Helper class for generating hash codes suitable 
/// for use in hashing algorithms and data structures like a hash table. 
/// </summary>
public static class HashCodeHelper
{
    private static int GetHashCodeInternal(int key1, int key2)
    {
        unchecked
        {
           var num = 0x7e53a269;
           num = (-1521134295 * num) + key1;
           num += (num << 10);
           num ^= (num >> 6);

           num = ((-1521134295 * num) + key2);
           num += (num << 10);
           num ^= (num >> 6);

           return num;
        }
    }

    /// <summary>
    /// Returns a hash code for the specified objects
    /// </summary>
    /// <param name="arr">An array of objects used for generating the 
    /// hash code.</param>
    /// <returns>
    /// A hash code, suitable for use in hashing algorithms and data 
    /// structures like a hash table. 
    /// </returns>
    public static int GetHashCode(params object[] arr)
    {
        int hash = 0;
        foreach (var item in arr)
            hash = GetHashCodeInternal(hash, item.GetHashCode());
        return hash;
    }

    /// <summary>
    /// Returns a hash code for the specified objects
    /// </summary>
    /// <param name="obj1">The first object.</param>
    /// <param name="obj2">The second object.</param>
    /// <param name="obj3">The third object.</param>
    /// <param name="obj4">The fourth object.</param>
    /// <returns>
    /// A hash code, suitable for use in hashing algorithms and
    /// data structures like a hash table.
    /// </returns>
    public static int GetHashCode<T1, T2, T3, T4>(T1 obj1, T2 obj2, T3 obj3,
        T4 obj4)
    {
        return GetHashCode(obj1, GetHashCode(obj2, obj3, obj4));
    }

    /// <summary>
    /// Returns a hash code for the specified objects
    /// </summary>
    /// <param name="obj1">The first object.</param>
    /// <param name="obj2">The second object.</param>
    /// <param name="obj3">The third object.</param>
    /// <returns>
    /// A hash code, suitable for use in hashing algorithms and data 
    /// structures like a hash table. 
    /// </returns>
    public static int GetHashCode<T1, T2, T3>(T1 obj1, T2 obj2, T3 obj3)
    {
        return GetHashCode(obj1, GetHashCode(obj2, obj3));
    }

    /// <summary>
    /// Returns a hash code for the specified objects
    /// </summary>
    /// <param name="obj1">The first object.</param>
    /// <param name="obj2">The second object.</param>
    /// <returns>
    /// A hash code, suitable for use in hashing algorithms and data 
    /// structures like a hash table. 
    /// </returns>
    public static int GetHashCode<T1, T2>(T1 obj1, T2 obj2)
    {
        return GetHashCodeInternal(obj1.GetHashCode(), obj2.GetHashCode());
    }
}

Và đây là cách sử dụng nó:

private struct Key
{
    private Type _type;
    private string _field;

    public Type Type { get { return _type; } }
    public string Field { get { return _field; } }

    public Key(Type type, string field)
    {
        _type = type;
        _field = field;
    }

    public override int GetHashCode()
    {
        return HashCodeHelper.GetHashCode(_field, _type);
    }

    public override bool Equals(object obj)
    {
        if (!(obj is Key))
            return false;
        var tf = (Key)obj;
        return tf._field.Equals(_field) && tf._type.Equals(_type);
    }
}

12
2017-10-07 10:51



@ Magnus, bạn có thể giải thích tại sao Đó là một điều tốt? - David Rutten
Khóa được xác định như thế nào? GetHashCode () không nhận bất kỳ tham số nào, vì vậy nó cần phải gọi cái này bằng hai Phím cần được xác định bằng cách nào đó. Xin lỗi, không có lời giải thích nào khác, điều này chỉ trông rất thông minh, nhưng không tốt. - Michael Stum♦
Khi bạn sử dụng đối tượng thay vì generics, bạn sẽ nhận được quyền phân bổ quyền anh và bộ nhớ, mà bạn không muốn trong GetHashCode. Cho nên Generics là con đường để đi. - CodesInChaos
Các bước thay đổi / xor sau (h += (h << 10); h ^= (h >> 6); h += (h << 3); h ^= (h >> 11); h += (h << 15); có một codesmell: họ không phụ thuộc vào bất kỳ đầu vào và nhìn awundant dư thừa với tôi. - sehe
@Magnus có quyền, tôi sẽ xóa bình luận ban đầu của tôi. Chỉ cần một chút lưu ý rằng điều này có thể không nhanh như một số giải pháp khác ở đây, nhưng như bạn nói không nên quan trọng. Việc phân phối là rất tốt, tốt hơn so với hầu hết các giải pháp ở đây, vì vậy +1 từ tôi! :) - nawfal


Đây là cách tiếp cận đơn giản của tôi. Tôi đang sử dụng mô hình xây dựng cổ điển cho việc này. Nó là an toàn (không có boxing / unboxing) và cũng tương thích với .NET 2.0 (không có phương thức mở rộng, v.v.).

Nó được sử dụng như thế này:

public override int GetHashCode()
{
    HashBuilder b = new HashBuilder();
    b.AddItems(this.member1, this.member2, this.member3);
    return b.Result;
} 

Và đây là lớp người xây dựng chính thức:

internal class HashBuilder
{
    private const int Prime1 = 17;
    private const int Prime2 = 23;
    private int result = Prime1;

    public HashBuilder()
    {
    }

    public HashBuilder(int startHash)
    {
        this.result = startHash;
    }

    public int Result
    {
        get
        {
            return this.result;
        }
    }

    public void AddItem<T>(T item)
    {
        unchecked
        {
            this.result = this.result * Prime2 + item.GetHashCode();
        }
    }

    public void AddItems<T1, T2>(T1 item1, T2 item2)
    {
        this.AddItem(item1);
        this.AddItem(item2);
    }

    public void AddItems<T1, T2, T3>(T1 item1, T2 item2, T3 item3)
    {
        this.AddItem(item1);
        this.AddItem(item2);
        this.AddItem(item3);
    }

    public void AddItems<T1, T2, T3, T4>(T1 item1, T2 item2, T3 item3, 
        T4 item4)
    {
        this.AddItem(item1);
        this.AddItem(item2);
        this.AddItem(item3);
        this.AddItem(item4);
    }

    public void AddItems<T1, T2, T3, T4, T5>(T1 item1, T2 item2, T3 item3, 
        T4 item4, T5 item5)
    {
        this.AddItem(item1);
        this.AddItem(item2);
        this.AddItem(item3);
        this.AddItem(item4);
        this.AddItem(item5);
    }        

    public void AddItems<T>(params T[] items)
    {
        foreach (T item in items)
        {
            this.AddItem(item);
        }
    }
}

8
2018-03-22 12:15



bạn có thể tránh tạo đối tượng bên trong hàm gethashcode như trong câu trả lời của Mangus. Chỉ cần gọi hàm băm tĩnh chết tiệt (ai quan tâm đến hàm băm khởi động). Ngoài ra, bạn có thể sử dụng AddItems<T>(params T[] items) phương pháp thường xuyên hơn trong lớp trợ giúp (hơn gọi AddItem(T) mỗi lần). - nawfal
Và bạn thấy lợi ích gì khi làm this.result * Prime2 * item.GetHashCode() khi thường được sử dụng là this.result * Prime2 + item.GetHashCode()? - nawfal
Đó là một lỗi đánh máy, cảm ơn! - bitbonk
Tôi không thể sử dụng AddItems<T>(params T[] items) thường xuyên hơn bởi vì typeof(T1) != typeof(T2) v.v. - bitbonk
ồ vâng tôi đã bỏ lỡ điều đó. - nawfal


Dưới đây là một cách thực hiện thông thạo khác thuật toán được đăng trên Jon Skeetnhưng không bao gồm phân bổ hoặc hoạt động quyền anh:

public static class Hash
{
    public const int Base = 17;

    public static int HashObject(this int hash, object obj)
    {
        unchecked { return hash * 23 + (obj == null ? 0 : obj.GetHashCode()); }
    }

    public static int HashValue<T>(this int hash, T value)
        where T : struct
    {
        unchecked { return hash * 23 + value.GetHashCode(); }
    }
}

Sử dụng:

public class MyType<T>
{
    public string Name { get; set; }

    public string Description { get; set; }

    public int Value { get; set; }

    public IEnumerable<T> Children { get; set; }

    public override int GetHashCode()
    {
        return Hash.Base
            .HashObject(this.Name)
            .HashObject(this.Description)
            .HashValue(this.Value)
            .HashObject(this.Children);
    }
}

Trình biên dịch sẽ đảm bảo HashValue không được gọi với một lớp do ràng buộc kiểu generic. Nhưng không có hỗ trợ trình biên dịch cho HashObject kể từ khi thêm một đối số chung cũng cho biết thêm một hoạt động đấm bốc.


8
2018-01-20 23:41