An hash array dictonary step by step

[TempodiBasic]

Step1  Presentation of project


Just to keep in theme of the dictionary structure data made by array in QB64, here we attempt to build a dictionary with hash  index.

We start from here

Code: (Select All)

'Assosziatives Array: https://jeff.win/qbhash/
'28. Feb. 2023

Type element
    tag As String * 10
    value As String * 10
End Type
Dim Shared aa(10) As element
Dim Shared aalast ' Last occupied AA() element


setvalue "foo", "bar"
setvalue "foo", "coffee"

Print getvalue$("foo") ' prints bar also after adding coffee
End

Function getvalue$ (tag As String)
    tag = LTrim$(RTrim$(tag))
    tag = tag + String$(10 - Len(tag), " ")
    For i = 0 To aalast
        If (tag = aa(i).tag) Then
            getvalue$ = aa(i).value
            Exit Function
        End If
    Next
End Function

Sub setvalue (tag As String, value As String)
    aa(aalast).tag = tag
    aa(aalast).value = value
    aalast = aalast + 1
End Sub

this code has been taken from this article on this webpage QBHash

this demo is very simple and with many limitations that cannot let us think about it like a real dictonary data structure.
What is the data structure coded has these features:  you can store more than one value linked to the tag value; moreover these collisions (new values linked to the tag) are stored into different cells of the array.  The author to get this result used an external index/counter  (AALAST). In the while the GetValue SUB is broken because it returns only the first value linked to the string index.

However here more information.

Issues:
1 the value stored can fit only 10 characters (ASCII values)

Code: (Select All)

Type element
    tag As String * 10  ' <----- hash value stored as a string of 10 characters that is searched sequentially
    value As String * 10  '<----- max 10 character for value
End Type

2 the hash index is not direct but searched rowly from the start to the end of arrayList

Code: (Select All)

Function getvalue$ (tag As String)
    tag = LTrim$(RTrim$(tag))
    tag = tag + String$(10 - Len(tag), " ")
    For i = 0 To aalast
        If (tag = aa(i).tag) Then
            getvalue$ = aa(i).value
            Exit Function
        End If
    Next
End Function

3 the store value routine does not avoid that the hashindex value has no duplicates.

Code: (Select All)

Sub setvalue (tag As String, value As String)
    aa(aalast).tag = tag
    aa(aalast).value = value
    aalast = aalast + 1
End Sub

4 the search value routine get the first cell of the array that has the hashvalue searched

Code: (Select All)

  If (tag = aa(i).tag) Then
            getvalue$ = aa(i).value
            Exit Function
        End If

Now we try to work to solve these issues.