Visual Basic 2010 Hashtable - GetHashCode Implementaties Collecties en Interfaces

home links
visual basic 2010 broncode voorbeelden

22.16. Hashtable - GetHashCode Implementaties

Dit artikel is gepubliceerd op zondag 31 juli 2011 op vbvoorbeelden, bezoek de website voor een recente versie van dit artikel of andere artikels.

22.16.1. Voorwaarden voor de Implementatie

Logisch gelijke objecten zouden dezelfde hash code moeten opleveren. Twee logisch verschillende objecten moeten echter niet een verschillende hash code opleveren.

Naast bovenstaande richtlijnen zijn er nog enkele extra opmerkingen te maken over de implementatie van de GetHashCode method :

- Indien de Equals method wordt geherdefinieerd moet ook de GetHashCode method worden overschreven, en omgekeerd.
De typische GetHashCode implementatie gaat gebruik maken van dezelfde aspecten/properties/velden als de Equals implementatie.

- De implementatie van GetHashCode zou snel een hash code moeten genereren en mag geen excepties opwerpen, dit geldt ook voor de implementatie van Equals.

- De hash code van een object mag niet veranderen zolang de toestand, waarop logische gelijkheid is op gebaseerd, ook niet verandert. Indien een object van dit type dezelfde toestand heeft tijdens een andere uitvoeringsinstantie is niet verplicht dat hier ook dezelfde hash code wordt opgeleverd.

Hieronder volgen enkele voorbeelden hoe men GetHashCode kan implementeren.

Stel dat twee Counter objecten met identieke Value als gelijk worden aanzien :

Visual Basic 2010 Broncode

Namespace Example1
    Class Counter
        Private _Value As Integer
        Public Property Value() As Integer
            Get
                Value = _Value
            End Get
            Set(ByVal value As Integer)
                _Value = value
            End Set
        End Property
        Public Sub Raise()
            _Value += 1
        End Sub
        '
        Public Overrides Function GetHashCode() As Integer
            GetHashCode = Value
        End Function
        Public Overrides Function Equals(ByVal obj As Object) As Boolean
            If obj IsNot Nothing AndAlso TypeOf obj Is Counter Then
                Equals = (Me.Value = DirectCast(obj, Counter).Value)
            End If
        End Function
    End Class
    Class Client
        Public Shared Sub Main()
            Dim counter1 As New Counter With {.Value = 5}
            Dim counter2 As New Counter With {.Value = 5}
            '
            Console.WriteLine(counter1.Equals(counter2))
            Console.WriteLine(counter1.GetHashCode() = counter2.GetHashCode())
            '
            Console.ReadLine()
        End Sub
    End Class
End Namespace

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

Console Application Output

True
True

boven boven

22.16.2. Random Distribution

Indien meerdere numerieke aspecten/properties/velden worden gebruikt in de Equals implementatie, gaat men vaak deze meerdere aspecten in de GetHashCode implementatie combineren aan de hand van de Xor operator.
Deze wordt gebruikt omdat de kans hierbij groot is dat voor de meeste logisch verschillende objecten een vrij unieke hash code zal genereren.

Logisch gelijke objecten zouden dezelfde hash code moeten opleveren. Twee logisch verschillende objecten moeten echter niet een verschillende waarde opleveren.
Om een Hashtable echter performant te houden, is het toch aan te raden logisch verschillende objecten, een verschillende hash code te doen opleveren. Doet men dit niet, dan krijgt men "collisions", meerdere elementen in een bucket van de Hashtable, en zal het plaatsen en opzoeken van elementen in deze Hashtable minder snel functioneren.

Stel dat twee Coordinate instanties als gelijk worden beschouwd indien ze dezelfde X en Y waarde hebben, dan kan men deze twee toestanden combineren met de bitgewijze Xor operator :

Visual Basic 2010 Broncode

Namespace Example2
    Structure Coordinate
        Public X As Integer
        Public Y As Integer
        Public Overrides Function GetHashCode() As Integer
            Return X Xor Y                                                 ' (1)
        End Function
        Public Overrides Function Equals(ByVal obj As Object) As Boolean
            If obj IsNot Nothing AndAlso TypeOf obj Is Coordinate Then
                Dim other As Coordinate = DirectCast(obj, Coordinate)
                Equals = (Me.X = other.X AndAlso Me.Y = other.Y)
            End If
        End Function
    End Structure
    Class Client
        Public Shared Sub Main()
            Dim coord1 As New Coordinate With {.X = 3, .Y = 12}
            Dim coord2 As New Coordinate With {.X = 3, .Y = 12}
            Dim coord3 As New Coordinate With {.X = 9, .Y = 6}
            '
            Console.WriteLine(coord1.Equals(coord2))
            Console.WriteLine(coord1.GetHashCode() = coord2.GetHashCode())
            '
            'Console.WriteLine(coord1.GetHashCode() = coord3.GetHashCode())  (2)
            '
            Console.ReadLine()
        End Sub
    End Class
End Namespace

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

Console Application Output

True
True

De operator Xor zal de individuele bits van de Integer operanden combineren aan de hand van een exclusive or.  Meer details over deze operator zijn te vinden in het topic over operatoren.

In tegenstelling tot andere binaire operatoren als And, Or, +, *, -, ... is de kans groot dat Xor een uniek resultaat oplevert voor de mogelijke waardes die de eerste en tweede operand kunnen aannemen.

Enkele voorbeelden :
- 3 + 12 is gelijk aan 5 + 10
- 3 * 12 is gelijk aan 1 * 36
- 3 - 12 is gelijk aan 4 - 13
- 3 And 9 ( 0011 And 1100 ) is gelijk aan 9 And 6 ( 1001 And 0110 )

Dit laatste voorbeeld kan je uittesten door in bovenstaand voorbeeld regel (2) te activeren en op regel (1) de Xor operator te vervangen door And.  Hierbij zie je dat coord1 dezelfde hash code heeft als coord3, wat opzich niet echt fout is, maar gezien coord1 en coord3 niet als gelijk worden beschouwd valt toch aan te raden deze een verschillende hash code te laten genereren.

Onderstaand vind je een voorbeeld waarmee ik probeer te illustreren dat een zogenaamde "random distribution" van de gegenereerde hash codes belangrijk is, zodoende zo vaak mogelijk "collisions" te vermijden.
Of met andere woorden we wensen dat zo veel mogelijk logisch verschillende objecten een verschillende hash code opleveren.  Doe je dit niet, dan zijn er meerdere elementen voor dezelfde bucket, wat het plaatsen en zoeken van items in een Hashtable bijvoorbeeld een veel zwaardere operatie maakt.

In onderstaande client voegen we 100 000 elementen toe aan een Hashtable (1).  Het keytype is hier Counter.  Vervolgens gaan we 100 000 keer een item opzoeken in deze Hashtable (2).

Verschillende Counter objecten met dezelfde Value worden hier als logisch gelijk beschouwd.  De Equals implementatie gaat dan ook Value van Me met die van obj vergelijken (3).

De voor de hand liggende implementatie voor GetHashCode is dan ook Value op te leveren.  Objecten van type Counter die gelijk zijn ( dezelfde Value hebben ) leveren bijgevolg ook een gelijke hash code op.
Ondanks dat dit niet vereist is, zal hier toch voor elk logisch verschillend object een verschillende hash code worden opgeleverd.  Dit is dus een erg goed implementatie voor GetHashCode.

Stel dat we implementatie op regel (4) vervangen door deze van regel (5).  Hierdoor wordt de rest na deling door 10 000 opgeleverd, waardoor bijvoorbeeld Counters met Value 10 123 en met Value 20 123 dezelfde hash code opleveren.  Dit mag, en is dus op zich geen foutieve implementatie van GetHashCode.  Het blijft immers zo dat twee Counter objecten met Value 10 123 dezelfde hash code ( namelijk 123 ) opleveren, dit is dus strikt gezien een correcte GetHashCode implementatie.

Toch is het zo dat logisch verschillende objecten die dezelfde hash code opleveren in dezelfde bucket worden geplaatst, en in dezelfde bucket moeten worden opgezocht, wat uiteraard niet bevordelijk is voor de performantie.

Test onderstaand voorbeeld uit met regel (4) of (5) geactiveerd en let op het snelheidsverschil.

Visual Basic 2010 Broncode

Namespace Example3
    Class Client
        Public Shared Sub Main()
            Dim hashtable1 As New Hashtable
            Dim counters1 As New ArrayList
            Dim start As Integer = Environment.TickCount
            For value As Integer = 1 To 100000
                Dim key As New Counter With {.Value = value}
                counters1.Add(key)
                hashtable1.Add(key, value)                                 ' (1)
            Next
            Console.WriteLine("Creation : " & Environment.TickCount - start)
            Dim random1 As New Random
            start = Environment.TickCount
            For i As Integer = 1 To 100000
                Dim randomIndex As Integer = random1.Next(0, 100000)
                Dim randomKey As Counter = counters1(randomIndex)
                Dim randomValue As Object = hashtable1.Item(randomKey)     ' (2)
            Next
            Console.WriteLine("Search : " & Environment.TickCount - start)
            Console.ReadLine()
        End Sub
    End Class
    Class Counter
        Public Value As Integer
        Public Overrides Function Equals(ByVal obj As Object) As Boolean
            If obj IsNot Nothing AndAlso TypeOf obj Is Counter Then
                Equals = Me.Value.Equals(DirectCast(obj, Counter).Value)   ' (3)
            End If
        End Function
        Public Overrides Function GetHashCode() As Integer
            GetHashCode = Value            ' fast                            (4)
            'GetHashCode = Value Mod 10000 ' slow                            (5)
        End Function
    End Class
End Namespace

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

De output voor regel (4) ( de goede en performante implementatie ) kan bijvoorbeeld zijn :

Console Application Output

Creation : 47
Search : 31

De output voor regel (5) ( de correct, maar minder ideale en niet performante implementatie ) kan bijvoorbeeld zijn :

Console Application Output

Creation : 1841
Search : 1560

Het aantal milliseconden kan en zal waarschijnlijk op jouw systeem verschillend zijn. Toch zou je een significant snelheidsverschil moeten opmerken.

In onderstaand voorbeeld bevatten objecten van ClassA verwijzingen naar objecten van types Class1 en Class2. Indien het hier zo zou zijn dat verschillend objecten van type ClassA gelijk worden beschouwd indien ze naar gelijke objecten van types Class1 en Class2 verwijzen, dan kan men de Equals en GetHashCode van de containde objecten herbruiken ( (1) en (2) ) :

Visual Basic 2010 Broncode

Namespace Example4
    Public Class Class1
        Public A As Integer
        Public Overrides Function Equals(ByVal obj As Object) As Boolean
            If obj IsNot Nothing AndAlso TypeOf obj Is Class1 Then
                Equals = (Me.A = DirectCast(obj, Class1).A)
            End If
        End Function
        Public Overrides Function GetHashCode() As Integer
            GetHashCode = A
        End Function
    End Class
    Public Class Class2
        Public B As Integer
        Public Overrides Function Equals(ByVal obj As Object) As Boolean
            If obj IsNot Nothing AndAlso TypeOf obj Is Class2 Then
                Equals = (Me.B = DirectCast(obj, Class2).B)
            End If
        End Function
        Public Overrides Function GetHashCode() As Integer
            GetHashCode = B
        End Function
    End Class
    Public Class ClassA
        Public Object1 As New Class1
        Public Object2 As New Class2
        Public Overrides Function Equals(ByVal obj As Object) As Boolean
            If obj IsNot Nothing AndAlso TypeOf obj Is ClassA Then
                Dim other As ClassA = DirectCast(obj, ClassA)
                Equals = (Me.Object1.Equals(other.Object1) AndAlso _
                          Me.Object2.Equals(other.Object2))                ' (1)
            End If
        End Function
        Public Overrides Function GetHashCode() As Integer
            GetHashCode = Object1.GetHashCode() Xor Object2.GetHashCode()  ' (2)
        End Function
    End Class
    Class Client
        Public Shared Sub Main()
            Dim x As New ClassA With {.Object1 = New Class1 With {.A = 5}, _
                                      .Object2 = New Class2 With {.B = 10}}
            Dim y As New ClassA With {.Object1 = New Class1 With {.A = 5}, _
                                      .Object2 = New Class2 With {.B = 10}}
            '
            Console.WriteLine(x.Equals(y))
            Console.WriteLine(x.GetHashCode() = y.GetHashCode())
            '
            Console.ReadLine()
        End Sub
    End Class
End Namespace

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

Console Application Output

True
True

Stel dat in het bovenstaande eerste voorbeeld Value geen Integer is, maar van een groter datatype ( Long, ULong, Single, Double, Decimal ) of een datatype met ander bereik ( UInteger, String, Char, ... ), kan je gebruik maken van de GetHashCode van dit datatype (1) :

Visual Basic 2010 Broncode

Namespace Example5
    Class Counter
        Private _Value As Long
        Public Property Value() As Long
            Get
                Value = _Value
            End Get
            Set(ByVal value As Long)
                _Value = value
            End Set
        End Property
        Public Sub Raise()
            _Value += 1
        End Sub
        '
        Public Overrides Function GetHashCode() As Integer
            GetHashCode = Value.GetHashCode()                              ' (1)
        End Function
        Public Overrides Function Equals(ByVal obj As Object) As Boolean
            If obj IsNot Nothing AndAlso TypeOf obj Is Counter Then
                Equals = (Me.Value = DirectCast(obj, Counter).Value)
            End If
        End Function
    End Class
End Namespace

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

boven boven

22.16.3. Immutable Keytype

Het spreekt voor zich dat de toestand van objecten van een keytype waarop logisch gelijkheid is gebaseerd, niet mag wijzigen zoals deze objecten als key in een dictionary worden gebruikt.

Stel dat we in onderstaand voorbeeld de Value van counter1 aanpassen (2) nadat dit object reeds als key aan een dictionary is toegevoegd (1), dan zal de expressie hashtable1.Item(counter1) geen resultaat opleveren (3) :

Visual Basic 2010 Broncode

Namespace Example5
    Class Client
        Public Shared Sub Main()
            Dim counter1 As New Counter With {.Value = 5}
            '
            Dim hashtable1 As New Hashtable
            hashtable1.Add(counter1, "value 1")                            ' (1)
            '
            counter1.Value = 10                                            ' (2)
            '
            Console.WriteLine(hashtable1.Item(counter1) Is Nothing) ' True   (3)
            '
            Console.ReadLine()
        End Sub
    End Class
End Namespace

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

Console Application Output

True

Bovenstaande opmerking is natuurlijk onbelangrijk wanneer je meteen met een keytype zit dat, op het vlak voor de toestand waarop logisch gelijkheid wordt gebaseerd, immutable is.

In onderstaand voorbeeld, waar twee personen als logisch gelijk worden beschouwd indien ze dezelfde ID hebben, kan na creatie van een Person met een bepaalde ID waarde, deze ID nooit meer veranderen.

De toestand waarop logisch gelijkheid hier wordt gebaseerd, is hier dus ook immutable.

Visual Basic 2010 Broncode

Namespace Example6
    Class Person
        Public Sub New(ByVal ID As String)
            _ID = ID
        End Sub
        Private ReadOnly _ID As String
        Public ReadOnly Property ID() As String
            Get
                ID = _ID
            End Get
        End Property
        ' ...
        Public Overrides Function GetHashCode() As Integer
            GetHashCode = ID.GetHashCode()
        End Function
        Public Overrides Function Equals(ByVal obj As Object) As Boolean
            If obj IsNot Nothing AndAlso TypeOf obj Is Person Then
                Equals = (Me.ID = DirectCast(obj, Person).ID)
            End If
        End Function
    End Class
End Namespace

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

Dit artikel is gepubliceerd op zondag 31 juli 2011 op vbvoorbeelden, bezoek de website voor een recente versie van dit artikel of andere artikels.

visual basic 2010 broncode voorbeelden

22.16. Hashtable - GetHashCode Implementaties

Interfacing

Collecties en Interfaces

Collecties, Interfaces en Genericiteit

Dictionaries en Value Types

System.Collections.SortedList

22.16.1. Voorwaarden voor de Implementatie

22.16.2. Random Distribution

22.16.3. Immutable Keytype

22.16.1. Voorwaarden voor de Implementatie

22.16.2. Random Distribution

22.16.3. Immutable Keytype

Interfacing

Collecties en Interfaces

Collecties, Interfaces en Genericiteit

Dictionaries en Value Types

System.Collections.SortedList