Tabelle hash: risoluzione delle collisioni con linked list in Visual Basic .NET

Ora la gestione con le liste concatenate può presentare lo stesso ordine di problemi.
Salvo il codice precedente:

Public Class Form1
    Dim nodeArray(366) As Nodo

    Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load
        createItem("abc")
        createItem("fds")
        createItem("ghr")
        createItem("uyj")
        createItem("jhk")
        createItem("fgh")
        elenca()
    End Sub
    Sub createItem(stringa As String)
        Dim hf As Integer = hashFunction(stringa)
        If nodeArray(hf) Is Nothing Then
            nodeArray(hf) = New Nodo
            nodeArray(hf).valore = stringa
            nodeArray(hf).prossimo = Nothing
        Else
            Do
                hf = hf + 1
                If hf > UBound(nodeArray) Then Exit Do
                If nodeArray(hf) Is Nothing Then
                    nodeArray(hf) = New Nodo
                    nodeArray(hf).valore = stringa
                    nodeArray(hf).prossimo = Nothing
                    Exit Do
                End If
            Loop

        End If

    End Sub

    Sub elenca()
        For n = 0 To UBound(nodeArray)
            If nodeArray(n) Is Nothing Then
                Debug.Print(n & "---")
            Else
                Debug.Print(n & "---" & nodeArray(n).valore)
            End If
        Next
    End Sub
    Function hashFunction(stringa As String) As Integer
        Dim asciValue As Integer = 0
        For n = 1 To Len(stringa)
            asciValue += Asc(Mid(stringa, n, 1))
        Next
        Return asciValue
    End Function
End Class

Class Nodo
    Public valore As String
    Public prossimo As Nodo
End Class

---

---

---

E ora provo...

Ci vuole sempre una funzione Hash, che può essere anche quella che ho già usato:

    Function hashFunction(stringa As String) As Integer
        Dim asciValue As Integer = 0
        For n = 1 To Len(stringa)
            asciValue += Asc(Mid(stringa, n, 1))
        Next
        Return asciValue
    End Function
End Class

In base a questa, ora, devo modificare questa:

    Sub createItem(stringa As String)
        Dim hf As Integer = hashFunction(stringa)
        If nodeArray(hf) Is Nothing Then
            nodeArray(hf) = New Nodo
            nodeArray(hf).valore = stringa
            nodeArray(hf).prossimo = Nothing
        Else
            Do
                hf = hf + 1
                If hf > UBound(nodeArray) Then Exit Do
                If nodeArray(hf) Is Nothing Then
                    nodeArray(hf) = New Nodo
                    nodeArray(hf).valore = stringa
                    nodeArray(hf).prossimo = Nothing
                    Exit Do
                End If
            Loop

        End If

    End Sub

In base alla funzione hashFunction, dovrei piazzare il valore nel nodo adeguato:

    Sub createItem(stringa As String)
        Dim hf As Integer = hashFunction(stringa)
        If nodeArray(hf) Is Nothing Then
            nodeArray(hf) = New Nodo
            nodeArray(hf).valore = stringa
            nodeArray(hf).prossimo = Nothing
        End If

    End Sub
    Sub elenca()
        For n = 0 To UBound(nodeArray)
            If nodeArray(n) Is Nothing Then
                Debug.Print(n & "---")
            Else
                Debug.Print(n & "---" & nodeArray(n).valore)
            End If
        Next
    End Sub

Tutto come prima: vediamo cosa succede.

294---abc
309---fgh
317---fds
321---ghr
344---uyj

Confrontando con il codice:

        createItem("abc")
        createItem("fds")
        createItem("ghr")
        createItem("uyj")
        createItem("jhk")
        createItem("fgh")

Anche qui c'è la stessa collisione: la funzione hashFunction restituisce 317 per "fds" e per "jhk", che però trovando il posto già occupato non viene inserita nella tabella.

---

Ora dobbiamo gestire però la creazione di liste concatenate per poter piazzare anche questo valore.
Dovrebbe cominciare dalla funzione createItem...
Se il nodo è già occupato va creato un altro nodo e impostato come "prossimo" del primo.

Ecco trovata la soluzione:

Public Class Form1
    Dim nodeArray(366) As Nodo

    Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load
        createItem("abc")
        createItem("fds")
        createItem("ghr")
        createItem("uyj")
        createItem("jhk")
        createItem("fgh")
        elenca()
    End Sub
    Sub createItem(stringa As String)
        Dim hf As Integer = hashFunction(stringa)
        Dim tail As Nodo, temp As Nodo

        'se il nodo base non è istanziato, si istanzia e gli si dà il valore.
        If nodeArray(hf) Is Nothing Then
            nodeArray(hf) = New Nodo
            nodeArray(hf).valore = stringa
            nodeArray(hf).prossimo = Nothing
        Else
            'se il nodo base è istanziato, si dà al nodo base istanziato il nome tail (in quanto è la coda della fila)
            tail = nodeArray(hf)
            Do
                'se non esiste un nodo prossimo al nodo tail... si istanzia un nuovo nodo chiamato temp...
                If tail.prossimo Is Nothing Then
                    temp = New Nodo
                    'e gli si danno i valori.
                    temp.valore = stringa
                    temp.prossimo = Nothing

                    'si pone questo nodo temp appena istanziato come prossimo rispetto al nodo tail
                    tail.prossimo = temp

                    'si dà a questo nuovo nodo il nome di tail.
                    tail = temp
                    Exit Do
                Else
                    'se invece esiste il nodo prossimo, allora questo diventerà il nuovo tail.
                    tail.prossimo = tail

                End If

            Loop


        End If

    End Sub

    Sub elenca()
        For n = 0 To UBound(nodeArray)
            'se il nodo non è istanziato si scriverà solo il numero
            If nodeArray(n) Is Nothing Then
                Debug.Print(n & "---")
            Else
                'se il nodo è istanziato, si scriverà il valore
                Debug.Print(n & "---" & nodeArray(n).valore)

                'e bisogna cercare se ci sono altri nodi nella linked list
                Dim tail As Nodo
                tail = nodeArray(n)
                Do
                    If Not tail.prossimo Is Nothing Then
                        tail = tail.prossimo
                        Debug.Print(n & "---" & tail.valore)

                    Else
                        Exit Do
                    End If
                Loop
            End If
        Next
    End Sub
    Function hashFunction(stringa As String) As Integer
        Dim asciValue As Integer = 0
        For n = 1 To Len(stringa)
            asciValue += Asc(Mid(stringa, n, 1))
        Next
        Return asciValue
    End Function
End Class

Class Nodo
    Public valore As String
    Public prossimo As Nodo
End Class

Ed ecco i due valori che erano entrati in collisione, rappresentati su un'unica colonna con gli altri (non ho voluto cimentarmi per una rappresentazione migliore)

294---abc
309---fgh
317---fds
317---jhk
321---ghr
344---uyj

Confronto:

        createItem("abc")
        createItem("fds")
        createItem("ghr")
        createItem("uyj")
        createItem("jhk")
        createItem("fgh")

Perfetto! I due elementi appaiono con lo stesso numero in quanto sono parte di una lista concatenata.
Ora creo intenzionalmente altri elementi il cui risultato della funzione hashFunction sia 317 e vediamo...

        createItem("abc")
        createItem("fds")
        createItem("ghr")
        createItem("uyj")
        createItem("jhk")
        createItem("fgh")
        createItem("ddu")
        createItem("dax")
        createItem("uce")

E scopro che il programma si blocca.
Dopo qualche incazzatura, trovo la fonte dell'errore.

    Sub createItem(stringa As String)
        Dim hf As Integer = hashFunction(stringa)
        Dim tail As Nodo, temp As Nodo

        temp = New Nodo
        temp.valore = stringa
        temp.prossimo = Nothing

        'se il nodo base non è istanziato, si istanzia e gli si dà il valore.
        If nodeArray(hf) Is Nothing Then
            nodeArray(hf) = temp
        Else
            'se il nodo base è istanziato, si dà al nodo base istanziato il nome tail (in quanto è la coda della fila)
            tail = nodeArray(hf)
            Do
                'se non esiste un nodo prossimo al nodo tail... si istanzia un nuovo nodo chiamato temp...
                If tail.prossimo Is Nothing Then
                    tail.prossimo = temp
                    Exit Do
                Else
                    'se invece esiste il nodo prossimo, allora questo diventerà il nuovo tail.
                    tail.prossimo = tail
                End If
            Loop
        End If
    End Sub

Una volta che il programma vede che un nodo è stato già istanziato, deve ripetere il ciclo usando questo come nodo tail, ma tail.prossimo = tail non attribuisce il nome tail al prossimo nodo, ma fa diventare il nodo successivo uguale a quello che attualmente è tail. Correggendo l'errore, il problema si risolve (ho impostato come oggetto iniziale sub Main credendo erroneamente che il pfoblema stesse nel caricamento del form ma va bene lo stesso).

Module Module1
    Dim nodeArray(366) As Nodo
    Sub main()
        createItem("abc")
        createItem("fds")
        createItem("ghr")
        createItem("uyj")
        createItem("jhk")
        createItem("fgh")
        createItem("ddu")
        createItem("dax")
        createItem("uce")
        elenca()
    End Sub

    Sub createItem(stringa As String)
        Dim hf As Integer = hashFunction(stringa)
        Dim tail As Nodo, temp As Nodo

        temp = New Nodo
        temp.valore = stringa
        temp.prossimo = Nothing

        'se il nodo base non è istanziato, si istanzia e gli si dà il valore.
        If nodeArray(hf) Is Nothing Then
            nodeArray(hf) = temp
        Else
            'se il nodo base è istanziato, si dà al nodo base istanziato il nome tail (in quanto è la coda della fila)
            tail = nodeArray(hf)
            Do
                'se non esiste un nodo prossimo al nodo tail... si istanzia un nuovo nodo chiamato temp...
                If tail.prossimo Is Nothing Then
                    tail.prossimo = temp
                    Exit Do
                Else
                    'se invece esiste il nodo prossimo, allora questo diventerà il nuovo tail.
                    tail = tail.prossimo
                End If
            Loop
        End If
    End Sub

    Sub elenca()
        For n = 0 To UBound(nodeArray)
            'se il nodo non è istanziato si scriverà solo il numero
            If nodeArray(n) Is Nothing Then
                Debug.Print(n & "---")
            Else
                'se il nodo è istanziato, si scriverà il valore
                Debug.Print(n & "---" & nodeArray(n).valore)

                'e bisogna cercare se ci sono altri nodi nella linked list
                Dim tail As Nodo
                tail = nodeArray(n)
                Do
                    If Not tail.prossimo Is Nothing Then
                        tail = tail.prossimo
                        Debug.Print(n & "---" & tail.valore)

                    Else
                        Exit Do
                    End If
                Loop
            End If
        Next
    End Sub
    Function hashFunction(stringa As String) As Integer
        Dim asciValue As Integer = 0
        For n = 1 To Len(stringa)
            asciValue += Asc(Mid(stringa, n, 1))
        Next
        Return asciValue
    End Function


    Class Nodo
        Public valore As String
        Public prossimo As Nodo
    End Class

End Module

Vediamo:

294---abc
309---fgh
317---fds
317---jhk
317---ddu
317---dax
317---uce
321---ghr
344---uyj

Mi sembra perfetto! Tutti quelli marcati in rosso fanno parte della linked list creata per risolvere il problema della collisione!