Метод System.Object.GetHashCode

В этой статье приводятся дополнительные замечания к справочной документации по этому API.

Этот GetHashCode метод предоставляет хэш-код для алгоритмов, требующих быстрых проверок равенства объектов. Хэш-код — это числовое значение, которое используется для вставки и идентификации объекта в хэш-коллекции, такой как класс Dictionary<TKey,TValue>, класс Hashtable или тип, производный от класса DictionaryBase.

Замечание

Сведения о том, как хэш-коды используются в хэш-таблицах и некоторых дополнительных алгоритмах хэш-кода, см. в записи хэш-функции в Википедии.

Два равных объекта возвращают одинаковые хеш-коды. Однако обратное не верно: равные хэш-коды не подразумевают равенство объектов, так как разные (неравные) объекты могут иметь одинаковые хэш-коды. Кроме того, .NET не гарантирует реализацию GetHashCode метода по умолчанию, и значение, возвращаемое этим методом, может отличаться между реализациями .NET, такими как разные версии .NET Framework и .NET Core, а также платформы, такие как 32-разрядные и 64-разрядные платформы. По этим причинам не используйте реализацию этого метода по умолчанию в качестве уникального идентификатора объекта для хэширования. Из этого следует два последствия:

• Не следует предполагать, что равные хэш-коды подразумевают равенство объектов.
• Никогда не следует сохранять хэш-код за пределами домена приложения, в котором он был создан, так как один и тот же объект может хэшировать между доменами приложений, процессами и платформами.

Предупреждение

Хэш-код предназначен для эффективной вставки и поиска в коллекциях, основанных на хэш-таблице. Хэш-код не является постоянным значением. По этой причине:

• Не сериализуйте значения хэш-кода или не храните их в базах данных.
• Не используйте хэш-код в качестве ключа для извлечения объекта из коллекции ключей.
• Не отправляйте хэш-коды между доменами или процессами приложений. В некоторых случаях хэш-коды могут вычисляться на основе каждого процесса или домена для каждого приложения.
• Не используйте хэш-код вместо значения, возвращаемого функцией шифрования хэширования, если требуется криптографически сильный хэш. Для криптографических хэшей используйте класс, производный от System.Security.Cryptography.HashAlgorithm класса или System.Security.Cryptography.KeyedHashAlgorithm класса.
• Не проверяйте равенство хэш-кодов, чтобы определить, равны ли два объекта. (Неравные объекты могут иметь идентичные хэш-коды.) Чтобы проверить равенство, вызовите ReferenceEquals метод или Equals метод.

Метод GetHashCode можно переопределить производным типом. Если GetHashCode не переопределено, хэш-коды для ссылочных типов вычисляются путем вызова Object.GetHashCode метода базового класса, который вычисляет хэш-код на основе ссылки объекта; дополнительные сведения см. в разделе RuntimeHelpers.GetHashCode. Другими словами, два объекта, для которых метод ReferenceEquals возвращает true, имеют одинаковые хэш-коды. Если типы значений не переопределяют GetHashCode, метод ValueType.GetHashCode базового класса использует рефлексию для вычисления хэш-кода на основе значений полей типа. Другими словами, типы значений, поля которых имеют равные значения, имеют равные хэш-коды. Дополнительные сведения о переопределении GetHashCode см. в разделе "Замечания для наследников".

Предупреждение

При переопределении GetHashCode метода также следует переопределить Equals, и наоборот. Если переопределенный Equals метод возвращается true , когда два объекта проверяются на равенство, переопределенный GetHashCode метод должен вернуть одно и то же значение для двух объектов.

Если объект, используемый в качестве ключа в хэш-таблице, не предоставляет полезную реализацию GetHashCode, можно указать поставщика хэш-кода, предоставив реализацию IEqualityComparer один из перегруженных конструкторов класса Hashtable.

Заметки о среде выполнения Windows

При вызове метода GetHashCode в классе среды выполнения Windows он предоставляет поведение по умолчанию для классов, которые не переопределяют GetHashCode. Это часть поддержки, которую предоставляет .NET для среды выполнения Windows (см. поддержку .NET для приложений Магазина Windows и среды выполнения Windows). Классы в среде выполнения Windows не наследуют Object, и в настоящее время не реализуют GetHashCode. Однако они, как представляется, имеют ToString, Equals(Object), и GetHashCode методы при их использовании в коде C# или Visual Basic, а структура .NET Framework обеспечивает поведение по умолчанию для этих методов.

Замечание

Классы среды выполнения Windows, написанные на C# или Visual Basic, могут переопределить метод GetHashCode.

Примеры

Один из самых простых способов вычисления хэш-кода для числового значения, имеющего тот же или меньший диапазон, чем Int32 тип, — просто возвращать это значение. В следующем примере показана такая реализация для Number структуры.

using System;

public struct Number
{
   private int n;

   public Number(int value)
   {
      n = value;
   }

   public int Value
   {
      get { return n; }
   }

   public override bool Equals(Object obj)
   {
      if (obj == null || ! (obj is Number))
         return false;
      else
         return n == ((Number) obj).n;
   }

   public override int GetHashCode()
   {
      return n;
   }

   public override string ToString()
   {
      return n.ToString();
   }
}

public class Example1
{
   public static void Main()
   {
      Random rnd = new Random();
      for (int ctr = 0; ctr <= 9; ctr++) {
         int randomN = rnd.Next(Int32.MinValue, Int32.MaxValue);
         Number n = new Number(randomN);
         Console.WriteLine("n = {0,12}, hash code = {1,12}", n, n.GetHashCode());
      }
   }
}
// The example displays output like the following:
//       n =   -634398368, hash code =   -634398368
//       n =   2136747730, hash code =   2136747730
//       n =  -1973417279, hash code =  -1973417279
//       n =   1101478715, hash code =   1101478715
//       n =   2078057429, hash code =   2078057429
//       n =   -334489950, hash code =   -334489950
//       n =    -68958230, hash code =    -68958230
//       n =   -379951485, hash code =   -379951485
//       n =    -31553685, hash code =    -31553685
//       n =   2105429592, hash code =   2105429592

open System

[<Struct; CustomEquality; NoComparison>]
type Number(value: int) =
    member _.Value = value

    override _.Equals(obj) =
        match obj with
        | :? Number as n ->
            n.Value = value
        | _ -> false

    override _.GetHashCode() =
        value

    override _.ToString() =
        string value

let rnd = Random()
for _ = 0 to 9 do
    let randomN = rnd.Next(Int32.MinValue, Int32.MaxValue)
    let n = Number randomN
    printfn $"n = {n,12}, hash code = {n.GetHashCode(),12}"
// The example displays output like the following:
//       n =   -634398368, hash code =   -634398368
//       n =   2136747730, hash code =   2136747730
//       n =  -1973417279, hash code =  -1973417279
//       n =   1101478715, hash code =   1101478715
//       n =   2078057429, hash code =   2078057429
//       n =   -334489950, hash code =   -334489950
//       n =    -68958230, hash code =    -68958230
//       n =   -379951485, hash code =   -379951485
//       n =    -31553685, hash code =    -31553685
//       n =   2105429592, hash code =   2105429592

Public Structure Number
   Private n As Integer

   Public Sub New(value As Integer)
      n = value
   End Sub

   Public ReadOnly Property Value As Integer
      Get
         Return n
      End Get
   End Property
   
   Public Overrides Function Equals(obj As Object) As Boolean
      If obj Is Nothing OrElse Not TypeOf obj Is Number Then
         Return False
      Else
         Return n = CType(obj, Number).n
      End If
   End Function      
   
   Public Overrides Function GetHashCode() As Integer
      Return n
   End Function
   
   Public Overrides Function ToString() As String
      Return n.ToString()
   End Function
End Structure

Module Example1
    Public Sub Main()
        Dim rnd As New Random()
        For ctr As Integer = 0 To 9
            Dim randomN As Integer = rnd.Next(Int32.MinValue, Int32.MaxValue)
            Dim n As New Number(randomN)
            Console.WriteLine("n = {0,12}, hash code = {1,12}", n, n.GetHashCode())
        Next
    End Sub
End Module
' The example displays output like the following:
'       n =   -634398368, hash code =   -634398368
'       n =   2136747730, hash code =   2136747730
'       n =  -1973417279, hash code =  -1973417279
'       n =   1101478715, hash code =   1101478715
'       n =   2078057429, hash code =   2078057429
'       n =   -334489950, hash code =   -334489950
'       n =    -68958230, hash code =    -68958230
'       n =   -379951485, hash code =   -379951485
'       n =    -31553685, hash code =    -31553685
'       n =   2105429592, hash code =   2105429592

Часто тип содержит несколько полей данных, которые могут участвовать в создании хэш-кода. Одним из способов создания хэш-кода является объединение этих полей с помощью XOR (eXclusive OR) операции, как показано в следующем примере.

using System;

// A type that represents a 2-D point.
public struct Point2
{
    private int x;
    private int y;

    public Point2(int x, int y)
    {
       this.x = x;
       this.y = y;
    }

    public override bool Equals(Object obj)
    {
       if (! (obj is Point2)) return false;

       Point2 p = (Point2) obj;
       return x == p.x & y == p.y;
    }

    public override int GetHashCode()
    {
        return x ^ y;
    }
}

public class Example3
{
   public static void Main()
   {
      Point2 pt = new Point2(5, 8);
      Console.WriteLine(pt.GetHashCode());

      pt = new Point2(8, 5);
      Console.WriteLine(pt.GetHashCode());
   }
}
// The example displays the following output:
//       13
//       13

// A type that represents a 2-D point.
[<Struct; CustomEquality; NoComparison>]
type Point(x: int, y: int) =
    member _.X = x
    member _.Y = y

    override _.Equals(obj) =
        match obj with
        | :? Point as p ->
            x = p.X && y = p.Y
        | _ -> 
            false

    override _.GetHashCode() =
        x ^^^ y

let pt = Point(5, 8)
printfn $"{pt.GetHashCode()}"

let pt2 = Point(8, 5)
printfn $"{pt.GetHashCode()}"
// The example displays the following output:
//       13
//       13

' A type that represents a 2-D point.
Public Structure Point3
    Private x As Integer
    Private y As Integer

    Public Sub New(x As Integer, y As Integer)
        Me.x = x
        Me.y = y
    End Sub

    Public Overrides Function Equals(obj As Object) As Boolean
        If Not TypeOf obj Is Point3 Then Return False

        Dim p As Point3 = CType(obj, Point3)
        Return x = p.x And y = p.y
    End Function

    Public Overrides Function GetHashCode() As Integer
        Return x Xor y
    End Function
End Structure

Public Module Example3
    Public Sub Main()
        Dim pt As New Point3(5, 8)
        Console.WriteLine(pt.GetHashCode())

        pt = New Point3(8, 5)
        Console.WriteLine(pt.GetHashCode())
    End Sub
End Module

В предыдущем примере возвращается тот же хэш-код для (n1, n2) и (n2, n1) и поэтому может создаваться больше конфликтов, чем желательно. Ряд решений доступны таким образом, чтобы хэш-коды в этих случаях не совпадали. Один из них — возвращать хэш-код Tuple объекта, который отражает порядок каждого поля. В следующем примере показана возможная реализация, которая использует Tuple<T1,T2> класс. Обратите внимание, что накладные расходы на производительность при создании экземпляра объекта Tuple могут существенно сказаться на общей производительности приложения, в котором хранится большое количество объектов в хэш-таблицах.

using System;

public struct Point3
{
    private int x;
    private int y;

    public Point3(int x, int y)
    {
       this.x = x;
       this.y = y;
    }

    public override bool Equals(Object obj)
    {
        if (obj is Point3)
        {
            Point3 p = (Point3) obj;
            return x == p.x & y == p.y;
        }
        else
        {
            return false;
        }      
    }

    public override int GetHashCode()
    {
        return Tuple.Create(x, y).GetHashCode();
    }
}

public class Example
{
   public static void Main()
   {
        Point3 pt = new Point3(5, 8);
        Console.WriteLine(pt.GetHashCode());

        pt = new Point3(8, 5);
        Console.WriteLine(pt.GetHashCode());
   }
}
// The example displays the following output:
//       173
//       269

[<Struct; CustomEquality; NoComparison>]
type Point(x: int, y: int) =
    member _.X = x
    member _.Y = y

    override _.Equals(obj) =
        match obj with
        | :? Point as p ->
            x = p.X && y = p.Y
        | _ -> 
            false

    override _.GetHashCode() =
        (x, y).GetHashCode()

let pt = Point(5, 8)
printfn $"{pt.GetHashCode()}"

let pt2 = Point(8, 5)
printfn $"{pt2.GetHashCode()}"
// The example displays the following output:
//       173
//       269

Public Structure Point
    Private x As Integer
    Private y As Integer

    Public Sub New(x As Integer, y As Integer)
       Me.x = x
       Me.y = y
    End Sub
    
    Public Overrides Function Equals(obj As Object) As Boolean
       If Not TypeOf obj Is Point Then Return False
       
       Dim p As Point = CType(obj, Point)
       Return x = p.x And y = p.y
    End Function
    
    Public Overrides Function GetHashCode() As Integer 
        Return Tuple.Create(x, y).GetHashCode()
    End Function 
End Structure 

Public Module Example
    Public Sub Main() 
        Dim pt As New Point(5, 8)
        Console.WriteLine(pt.GetHashCode())
        
        pt = New Point(8, 5)
        Console.WriteLine(pt.GetHashCode())
    End Sub 
End Module         
' The example displays the following output:
'       173
'       269

Второе альтернативное решение включает взвешивание отдельных хэш-кодов, которое осуществляется путем сдвига влево хэш-кодов последующих полей на два или более бита. Оптимально, биты, смещённые за бит 31, сбрасываются и продолжают отсчёт, а не отменяются. Так как биты удаляются операторами сдвига влево в C# и Visual Basic, для этого требуется создать метод циклического сдвига влево, как показано ниже:

public int ShiftAndWrap(int value, int positions)
{
    positions = positions & 0x1F;

    // Save the existing bit pattern, but interpret it as an unsigned integer.
    uint number = BitConverter.ToUInt32(BitConverter.GetBytes(value), 0);
    // Preserve the bits to be discarded.
    uint wrapped = number >> (32 - positions);
    // Shift and wrap the discarded bits.
    return BitConverter.ToInt32(BitConverter.GetBytes((number << positions) | wrapped), 0);
}

let shiftAndWrap (value: int) positions =
    let positions = positions &&& 0x1F

    // Save the existing bit pattern, but interpret it as an unsigned integer.
    let number = BitConverter.ToUInt32(BitConverter.GetBytes value, 0)
    // Preserve the bits to be discarded.
    let wrapped = number >>> (32 - positions)
    // Shift and wrap the discarded bits.
    BitConverter.ToInt32(BitConverter.GetBytes((number <<< positions) ||| wrapped), 0)

Public Function ShiftAndWrap(value As Integer, positions As Integer) As Integer
   positions = positions And &h1F
   
   ' Save the existing bit pattern, but interpret it as an unsigned integer.
   Dim number As UInteger = BitConverter.ToUInt32(BitConverter.GetBytes(value), 0)
   ' Preserve the bits to be discarded.
   Dim wrapped AS UInteger = number >> (32 - positions)
   ' Shift and wrap the discarded bits.
   Return BitConverter.ToInt32(BitConverter.GetBytes((number << positions) Or wrapped), 0)
End Function

В следующем примере затем используется метод shift-and-wrap для вычисления хэш-кода структуры Point, которая использовалась в предыдущих примерах.

using System;

public struct Point
{
    private int x;
    private int y;

    public Point(int x, int y)
    {
       this.x = x;
       this.y = y;
    }

    public override bool Equals(Object obj)
    {
       if (!(obj is Point)) return false;

       Point p = (Point) obj;
       return x == p.x & y == p.y;
    }

    public override int GetHashCode()
    {
        return ShiftAndWrap(x.GetHashCode(), 2) ^ y.GetHashCode();
    }

    private int ShiftAndWrap(int value, int positions)
    {
        positions = positions & 0x1F;

        // Save the existing bit pattern, but interpret it as an unsigned integer.
        uint number = BitConverter.ToUInt32(BitConverter.GetBytes(value), 0);
        // Preserve the bits to be discarded.
        uint wrapped = number >> (32 - positions);
        // Shift and wrap the discarded bits.
        return BitConverter.ToInt32(BitConverter.GetBytes((number << positions) | wrapped), 0);
    }
}

public class Example2
{
   public static void Main()
   {
        Point pt = new Point(5, 8);
        Console.WriteLine(pt.GetHashCode());

        pt = new Point(8, 5);
        Console.WriteLine(pt.GetHashCode());
   }
}
// The example displays the following output:
//       28
//       37

open System

[<Struct; CustomEquality; NoComparison>]
type Point(x: int, y: int) =
    member _.X = x
    member _.Y = y
    override _.Equals(obj) =
        match obj with
        | :? Point as p ->
            x = p.X && y = p.Y
        | _ -> 
            false

    override this.GetHashCode() =
        this.ShiftAndWrap(x.GetHashCode(), 2) ^^^ y.GetHashCode()

    member _.ShiftAndWrap(value, positions) =
        let positions = positions &&& 0x1F

        // Save the existing bit pattern, but interpret it as an unsigned integer.
        let number = BitConverter.ToUInt32(BitConverter.GetBytes value, 0)
        // Preserve the bits to be discarded.
        let wrapped = number >>> (32 - positions)
        // Shift and wrap the discarded bits.
        BitConverter.ToInt32(BitConverter.GetBytes((number <<< positions) ||| wrapped), 0)

let pt = Point(5, 8)
printfn $"{pt.GetHashCode()}"

let pt2 = Point(8, 5)
printfn $"{pt2.GetHashCode()}"
// The example displays the following output:
//       28
//       37

Public Structure Point5
    Private x As Integer
    Private y As Integer

    Public Sub New(x As Integer, y As Integer)
        Me.x = x
        Me.y = y
    End Sub

    Public Overrides Function Equals(obj As Object) As Boolean
        If Not TypeOf obj Is Point5 Then Return False

        Dim p As Point5 = CType(obj, Point5)
        Return x = p.x And y = p.y
    End Function

    Public Overrides Function GetHashCode() As Integer
        Return ShiftAndWrap(x.GetHashCode(), 2) Xor y.GetHashCode()
    End Function

    Private Function ShiftAndWrap(value As Integer, positions As Integer) As Integer
        positions = positions And &H1F

        ' Save the existing bit pattern, but interpret it as an unsigned integer.
        Dim number As UInteger = BitConverter.ToUInt32(BitConverter.GetBytes(value), 0)
        ' Preserve the bits to be discarded.
        Dim wrapped As UInteger = number >> (32 - positions)
        ' Shift and wrap the discarded bits.
        Return BitConverter.ToInt32(BitConverter.GetBytes((number << positions) Or wrapped), 0)
    End Function
End Structure

Module Example2
    Public Sub Main()
        Dim pt As New Point5(5, 8)
        Console.WriteLine(pt.GetHashCode())

        pt = New Point5(8, 5)
        Console.WriteLine(pt.GetHashCode())
    End Sub
End Module
' The example displays the following output:
'       28
'       37