CODEWITHSUNDEEP
vb.netlinked-listhashtablecollision-detection
stizzo96
stizzo96

Reputation: 726

Hash table collision detected solution

I am trying to find how to deal with collision detection with HashTable.

My hashing algorithm is bad and results in many collisions, I am working on a better algorithm: HashKey = (Mid(HashKey, 1, 3) * Mid(HashKey, 1, 3) Mod 11)

I am saving my structure Stock:

    <Serializable()>
Public Structure Stock
    'Create a structure for the hash table stock file
    <VBFixedString(10)> Public Barcode As String
    <VBFixedString(20)> Public Category As String
    <VBFixedString(20)> Public Title As String
    <VBFixedString(20)> Public Description As String
    <VBFixedString(4)> Public Quantity As Integer
    <VBFixedString(8)> Public RRP As Double
    <VBFixedString(8)> Public Cost As Double
End Structure

I am currently detecting collisions by means of:

If HashTable(HashKey) = "" Then
...
SaveStock
End If

Is this a reliable way of checking? If a collision is detected, how do I solve for VB.net. Do I have to implement my own linked list or does the Hashtable type have a property that deals with it?

Upvotes: 0

Views: 490

Answers (2)

Olivier Jacot-Descombes
Olivier Jacot-Descombes

Reputation: 112762

Don't confuse keys and hash codes! A key must be unique and identifies an object. The hash code is computed from the key when using hash tables. The HashTable does this by calling the GetHashCode method of the key.

The HashTable allows you to store and find objects by a key. Therefore you must use a known value as key. For instance the bar code which should be unique.

Dim stockTable As HashTable = New HashTable()
stockTable.Add(stock.Barcode, stock)

The Item property returns Nothing if an item with a given key is not found. Don't define Stock as structure define it as a class.

Dim stock As Stock = DirectCast(stockTable(someBarCode), Stock)
If stock Is Nothing Then
    ' No item found with this key
Else
    ' Success!
End If

Upvotes: 1

Chris Tavares
Chris Tavares

Reputation: 30411

Both HashTable and Dictionary deal with hash collisions for you. You'll get a lookup performance degredation, but as long as the key is unique (even if the hash of the key is not) you don't need to do anything. The containers will handle storage for you.

You still want to reduce hash collisions if you can for performance reasons; at worst case (all the keys hash the same) then it becomes a linear search through every key for a lookup.

Upvotes: 0

Related Questions