Как VB.NET определяет, какой ключ является уникальным в Dictionary (Of)?

Question

У меня есть следующий класс:

Public Class Pair(Of T1, T2)

    Public Property First As T1
    Public Property Second As T2

    Public Sub New(Optional ByVal first As T1 = Nothing, Optional ByVal second As T2 = Nothing)
        Me.First = first
        Me.Second = second
    End Sub

    Public Overrides Function tostring() As String
        Return String.Format("<[{0},{1}]>", First, Second)
    End Function

    Public Overrides Function GetHashCode() As Integer         
        Return Integer.Parse(String.Format("{0}{1}", First.GetHashCode, Second.GetHashCode))
    End Function
End Class

Однако, когда я создаю словарь, используя в качестве ключа пару:

    Dim Pairs as Dictionary(Of Pair(Of Integer, Integer), String)

    Dim p = new Pair(of integer, integer)(1234, 13)
    Dim p2 = new Pair(of integer, integer)(1234, 13)

    console.writeline(String.Format("Hash 1:{0} Hash 2:{1}", p.gethashcode(), p2.gethashcode()))
    Pairs.add(p, "Hello")

    Console.WriteLine(Pairs(p2))

Я ожидаю, что, поскольку и p, и p2 имеют хеш-код 123413, они попадут в один и тот же элемент словаря и что WriteLine будет отображать "Hello". Однако на самом деле происходит то, что я получаю KeyNotFoundException, что заставляет меня поверить, что Dictionary (Of...) на самом деле не использует метод GetHashCode.

Так что мне нужно сделать, чтобы обе эти пары ссылались на один и тот же элемент словаря?

Спасибо!

Answer 1

Одного хеш-кода недостаточно - оба ключа должны быть равными , т. Е. key1.Equals(key2) должно быть истинным (или эквивалентным значением в пользовательском компараторе).

Вы не изменили Equals, поэтому два Pair объекта всегда неравны.

(Обратите внимание, что ваша функция хеш-кода также может не работать различными способами, например, если они оба отрицательны. Почему бы просто не объединить два целочисленных значения каким-либо образом?)

Я не знаю VB достаточно хорошо, чтобы сам придумать подходящее переопределение, когда я должен идти спать, но в C # это было бы что-то вроде:

public override bool Equals(object other)
{
    if (other == null)
    {
        return false;
    }
    if (other.GetType() != this.GetType())
    {
        return false;
    }
    var otherPair = (Pair<T1, T2>) other;
    return EqualityComparer<T1>.Default(this.First, otherPair.First) &&
           EqualityComparer<T2>.Default(this.Second, otherPair.Second);
}

(кстати, я бы использовал EqualityComparer<T>.Default и для генерации хеш-кода.)

Answer 2

Несколько вещей:

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

На практике значения в словаре хранятся в индексе в массиве.С 2 ^ 32 различными типами хеш-кодов невозможно создать индекс массива для каждого хеш-кода, поэтому Словарь преобразует хеш-код в индекс массива, где хранятся значения.Из-за этого Словарь испытывает то, что называется "хеш-коллизиями".Это означает, что разные ключи будут отображаться на одно и то же значение хеш-функции.

Словарь справляется с этим, но в конечном итоге, когда два или более хэш-кода создают один и тот же индекс (что будет , когдаколлекция становится достаточно большой), метод Equals должен определить, какой ключ использовать для поиска пары ключ / значение, содержащей искомое значение.Если Equals имеет значение false для всех элементов в корзине, он возвращает KeyNotFoundException, который вы испытали.

On к коду:

Хотя вы можете переопределить Equals, я непонимаю, зачем тебе это нужноДля начала я бы избавился от твоего GetHashCode.Со временем у вас возникнут проблемы, как показано здесь:

Dim p = new Pair(of integer, integer)(Int32.MaxValue, Int32.MaxValue)
p.gethashcode() 'BOOM!!!

Вместо этого, исходя из того, что вы здесь делаете, я бы рекомендовал вам преобразовать ваш класс Pair в struct (Структура в VB), оставив Equals и GetHashCode в покое.Это действительно хорошая идея, если вы присваиваете паре типы значений (int, byte, bool и т. Д.) По соображениям производительности.Я бы действительно подумал об этом.

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

Public Function GetKey() As KeyValuePair(Of T1, T2)        
    Return New KeyValuePair(Of T1, T2)(First, Second)
End Function

И ваш словарь становится

Dim Pairs as Dictionary(Of KeyValuePair(Of Integer, Integer), String)
Pairs.add(p.GetKey(), "Hello")
Console.WriteLine(Pairs(p2.GetKey()))

(Если естьлюбые синтаксические ошибки, это потому, что я не программист VB.)

Answer 3

У вас есть ряд проблем, с которыми вам приходится сталкиваться здесь.

Для начала - вы также должны переопределить Equals, так как GetHashCode предназначен только для быстрого определения, если два объекта не равны .Это никогда не означает, что объекты равны .Вот для чего Equals - это последняя проверка, что два объекта равны , и вычисление может быть намного медленнее, чем GetHashCode.

Вот пример.Скажем, у вас есть три очень длинные строки, две одинаковой длины, а другие разныеЕсли GetHashCode вернул длину строк, то вы могли бы очень быстро определить, что третья строка определенно не равна первым двум.Вы должны проверить фактическое содержание первых двух, чтобы увидеть, равны ли они, и это может быть сравнительно длительный процесс.

Следующее, и это не менее важно, вы не можете имеет хеш-код, который изменяется в течение срока службы объекта.

Ключевое слово не может .Это сломает вещи.

Класс Dictionary(Of ,) использует серию «сегментов» для быстрого поиска значений на основе хеш-кода ключа.Таким образом, если хэш-код вашего ключа изменится на после того, как он был добавлен в словарь, то словарь не сможет его найти и позволит вам добавить ключ дважды!

Вотпример:

Dim d = New Dictionary(Of Pair(Of Integer, Integer), String)
Dim p = new Pair(Of Integer, Integer)(10, 11)
d.Add(p, "James")
Dim before = d(p) ' Found!
p.First = 12
Dim after = d(p) ' NOT Found!

Или вот это:

Dim d = New Dictionary(Of Pair(Of Integer, Integer), String)
Dim p = new Pair(Of Integer, Integer)(10, 11)
d.Add(p, "James")
p.First = 12
d.Add(p, "Tom") ' ALLOWED!

Вот почему изменяемые структуры плохи.

Надеюсь, это поможет.