Proseguendo nello studio delle tabelle hash e delle liste concatenate, due cose fondamentali mi servono: una funzione che converta una stringa in un numero, ossia la funzione hash, e poi la creazioni di nodi.
Rivediamo la prima.
Mi serve una funzione per trasformare i caratteri nei loro codici ASCII e poi farne la somma.
Questa l'ho già vista prima ma ora la ripasso.
Come parametro, ci sarà una stringa.
Sub converti(stringa As String)
End Sub
Quindi predispongo una matrice dinamica:
Sub converti(stringa As String)
Dim caratteri() As Char
End Sub
Ridimensiono la matrice di caratteri alla lunghezza della stringa (-1 perché la matrice comincia con 0):
Sub converti(stringa As String)
Dim caratteri() As Char
ReDim caratteri(Len(stringa) - 1)
End Sub
Ora ho una matrice di caratteri di lunghezza uguale a quella della stringa.Ad ogni elemento della matrice devo far corrispondere un carattere della stringa.
Sub converti(stringa As String)
Dim caratteri() As Char
ReDim caratteri(Len(stringa) - 1)
For n = 0 To Len(stringa) - 1
caratteri(n) = Mid(stringa, n, 1)
Next
End Sub
Come prova, scrivo nella finestra di Debug i singoli valori della matrice caratteri():
Public Class Form1
Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load
converti("ciao")
End Sub
Sub converti(stringa As String)
Dim caratteri() As Char
ReDim caratteri(Len(stringa) - 1)
For n = 1 To Len(stringa)
caratteri(n - 1) = Mid(stringa, n, 1)
Next
For n = 0 To UBound(caratteri)
Debug.Print(caratteri(n))
Next
End Sub
e vediamo cosa ne viene fuori, per vedere se abbiamo fatto tutta la procedura corretta:
c i a oBene.
Adesso devo calcolare il valore ASCII dei caratteri e sommarli insieme:
Sub converti(stringa As String)
Dim asciValue As Integer = 0
Dim caratteri() As Char
ReDim caratteri(Len(stringa) - 1)
For n = 1 To Len(stringa)
caratteri(n - 1) = Mid(stringa, n, 1)
Next
For n = 0 To UBound(caratteri)
asciValue += Asc(caratteri(n))
Next
Debug.Print(asciValue)
End Sub
Ho predisposto un valore asciValue pari a zero che, ripassando tutti i caratteri della matrice convertiti nel loro valore ASCII vi vengono sommati:
c i a o 412
Ma non si può fare a meno della matrice?
Facciamo un calcolo abbreviato.
Sub converti(stringa As String)
Dim asciValue As Integer = 0
For n = 1 To Len(stringa)
asciValue += Asc(Mid(stringa, n, 1))
Debug.Print(Mid(stringa, n, 1))
Next
Debug.Print(asciValue)
End Sub
c i a o 412Considerando che abbiamo come input una stringa e come output vogliamo sapere il valore della somma dei codici ASCII dei suoi caratteri (possiamo evitare di stampare tutti i caratteri, cosa che ci serviva solo per verificare che avevamo fatto tutto bene), trasformiamo la Sub in una Function:
Function converti(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
E verifichiamola:
Public Class Form1
Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load
Debug.Print(converti("abc"))
End Sub
Function converti(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
294...che corrisponde alla somma dei codici ASCII di a,b,c.
Vorrei trovare un nome più consono alla funzione:
Public Class Form1
Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load
Debug.Print(asciiSum("abc"))
End Sub
Function asciiSum(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
Ora, in previsione dell'uso di liste concatenate come mezzo per superare le collisioni, dovrei inserire questi valori trovati in una serie di "nodi".
Creiamo la classe Nodo.
Class Nodo
Public valore As Integer
Public prossimo As Nodo
End Class
La proprietà valore è quella che ospita i valori asciiSum, ossia quelli ottenuti con la funzione hash. La proprietà prossimo dovrebbe indicare il nodo successivamente concatenato nell'eventualità ce ne fosse bisogno.
Come conciliare la funzione che ho trovato prima con i nodi?
Avrei una matrice di nodi, che però non dovrebbero essere istanziati tutti, bensì solo quelli utilizzati.
Ad esempio, per un asciSum di 294 dovrei istanziare l'elemento 294 dell'array di nodi.
Facciamo una lista di 500 nodi, ossia una matrice di 500 variabili nodo (non istanziate), e una variabile che servirà da index ogni volta che si creerà un nuovo valore.
Dim nodeArray(500) As Integer
Dim hashFunction As Integer
Mi sta venendo l'idea di chiamare la funzione, anziché asciValue, hashFunction, a sottolineare la funzione più generale di funzione hash.
Ora creo la funzione che crea un nuovo item:
Sub createItem(stringa As String)
End Sub
Ecco scritto il tutto:
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)
nodeArray(hashFunction(stringa)) = New Nodo
nodeArray(hashFunction(stringa)).valore = stringa
nodeArray(hashFunction(stringa)).prossimo = Nothing
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
Ed ecco l'output:
0--- 1--- 2--- 3--- 4--- 5--- 6--- 7--- 8--- 9--- 10--- 11--- 12--- 13--- 14--- 15--- 16--- 17--- 18--- 19--- 20--- 21--- 22--- 23--- 24--- 25--- 26--- 27--- 28--- 29--- 30--- 31--- 32--- 33--- 34--- 35--- 36--- 37--- 38--- 39--- 40--- 41--- 42--- 43--- 44--- 45--- 46--- 47--- 48--- 49--- 50--- 51--- 52--- 53--- 54--- 55--- 56--- 57--- 58--- 59--- 60--- 61--- 62--- 63--- 64--- 65--- 66--- 67--- 68--- 69--- 70--- 71--- 72--- 73--- 74--- 75--- 76--- 77--- 78--- 79--- 80--- 81--- 82--- 83--- 84--- 85--- 86--- 87--- 88--- 89--- 90--- 91--- 92--- 93--- 94--- 95--- 96--- 97--- 98--- 99--- 100--- 101--- 102--- 103--- 104--- 105--- 106--- 107--- 108--- 109--- 110--- 111--- 112--- 113--- 114--- 115--- 116--- 117--- 118--- 119--- 120--- 121--- 122--- 123--- 124--- 125--- 126--- 127--- 128--- 129--- 130--- 131--- 132--- 133--- 134--- 135--- 136--- 137--- 138--- 139--- 140--- 141--- 142--- 143--- 144--- 145--- 146--- 147--- 148--- 149--- 150--- 151--- 152--- 153--- 154--- 155--- 156--- 157--- 158--- 159--- 160--- 161--- 162--- 163--- 164--- 165--- 166--- 167--- 168--- 169--- 170--- 171--- 172--- 173--- 174--- 175--- 176--- 177--- 178--- 179--- 180--- 181--- 182--- 183--- 184--- 185--- 186--- 187--- 188--- 189--- 190--- 191--- 192--- 193--- 194--- 195--- 196--- 197--- 198--- 199--- 200--- 201--- 202--- 203--- 204--- 205--- 206--- 207--- 208--- 209--- 210--- 211--- 212--- 213--- 214--- 215--- 216--- 217--- 218--- 219--- 220--- 221--- 222--- 223--- 224--- 225--- 226--- 227--- 228--- 229--- 230--- 231--- 232--- 233--- 234--- 235--- 236--- 237--- 238--- 239--- 240--- 241--- 242--- 243--- 244--- 245--- 246--- 247--- 248--- 249--- 250--- 251--- 252--- 253--- 254--- 255--- 256--- 257--- 258--- 259--- 260--- 261--- 262--- 263--- 264--- 265--- 266--- 267--- 268--- 269--- 270--- 271--- 272--- 273--- 274--- 275--- 276--- 277--- 278--- 279--- 280--- 281--- 282--- 283--- 284--- 285--- 286--- 287--- 288--- 289--- 290--- 291--- 292--- 293--- 294---abc 295--- 296--- 297--- 298--- 299--- 300--- 301--- 302--- 303--- 304--- 305--- 306--- 307--- 308--- 309---fgh 310--- 311--- 312--- 313--- 314--- 315--- 316--- 317---jhk 318--- 319--- 320--- 321---ghr 322--- 323--- 324--- 325--- 326--- 327--- 328--- 329--- 330--- 331--- 332--- 333--- 334--- 335--- 336--- 337--- 338--- 339--- 340--- 341--- 342--- 343--- 344---uyj 345--- 346--- 347--- 348--- 349--- 350--- 351--- 352--- 353--- 354--- 355--- 356--- 357--- 358--- 359--- 360--- 361--- 362--- 363--- 364--- 365--- 366---
Ecco: le stringhe da porre nella tabella erano queste:
createItem("abc")
createItem("fds")
createItem("ghr")
createItem("uyj")
createItem("jhk")
createItem("fgh")
mentre quelle ritrovate nella tabella sono:
294---abc 309---fgh 317---jhk 321---ghr 344---uyjc'è una collisione fra le stringhe "fds" e "jhk", la cui somma è sempre 317
Proviamo con il metodo Open Addressing.
Innanzitutto bisogna vedere come individuare una collisione.
Con questo accorgimento, jhk non dovrebbe sostituire fds.
Sub createItem(stringa As String)
If nodeArray(hashFunction(stringa)) Is Nothing Then
nodeArray(hashFunction(stringa)) = New Nodo
nodeArray(hashFunction(stringa)).valore = stringa
nodeArray(hashFunction(stringa)).prossimo = Nothing
End If
End Sub
Vediamo...
294---abc
309---fgh
317---fds
321---ghr
344---uyj
Confrontando con la lista precedente:
294---abc
309---fgh
317---jhk
321---ghr
344---uyj
Esatto! Come nelle previsioni!
Ora, individuata la collisione, dove andiamo a mettere quel jhk che la funzione hash ha reso uguale al fds?
Dobbiamo scorrere avanti nella lista fino a trovare uno "slot" vuoto.
Innanzitutto è più comodo modificare così la funzione createItem:
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
Quindi...
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 nodeArray(hf) Is Nothing Then
nodeArray(hf) = New Nodo
nodeArray(hf).valore = stringa
nodeArray(hf).prossimo = Nothing
End If
Loop
End If
End Sub
Aumentiamo il numero di indice della variabile nodo facente parte della matrice nodeArray, fin quando troviamo una variabile non inizializzata, che inizializziamo con il valore rimastoci "vacante".Proviamo.
Ecco una migliore gestione che evita al ciclo Do... Loop di andare avanti superando i limiti della matrice nodeArray:
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
Ed ecco come è stata sistemata la collisione:
294---abc 309---fgh 317---fds 318---jhk 321---ghr 344---uyjEcco, ora "jhk" non sparisce più ma viene "incasellato" con l'indice 318, primo "slot" libero dopo quello con cui si contendeva l'indice.
Confronto con le stringhe da "disporre" nel codice:
createItem("abc")
createItem("fds")
createItem("ghr")
createItem("uyj")
createItem("jhk")
createItem("fgh")
Perfetto!
Ora se io voglio ritrovare il punto in cui si trova la stringa "jhk", come faccio?
Tramite la funzione hash (hashFunction) trovo immediatamente la "locazione" 317. A questo punto faccio un confronto che non mi dà la corrispondenza, in quanto in quella "locazione" io ci trovo "fds". Così con un ciclo "while" scorro le locazioni successive fino a quando il confronto darà esito positivo.
Molto più economico che cercare "jhk" su tutta la matrice nodeArray di sana pianta a cominciare dal primo fino a quando avrò trovato la stringa!
Nessun commento:
Posta un commento