didn't do any speed test but it works pretty well
Code: Select all
;
; hashtable.pb
; provide associative strings storage
; global methods
; .i addmultimap(key$, value$, Array key$(1), Array value$(1), Array table.s_hashtable(1))
;
; desc: add value pair to respective arrays
; generate hash for key and append relation information to
; table and return index of added value pair
;
; key$ value pair to be added to map
; value$
; key$() storage arrays for the type
; value$()
; table relation table, uses initial size as table width
; conflicting hashes will add depth to the table
;
; .i querymapindex(key$, start, Array key$(1), Array table.s_hashtable(1))
;
; desc: search for key in table and return the index number of the
; value pair
;
; key$ search string
; start starting index of valid results
; key$()
; table
;
; private methods
; .i hashtable_hashingfunction(string$)
;
; desc: generate a deterministic positive number
; associated with the string
;
; string$
;
; global structures
; s_hashtable
;
; desc: data structure for associative relation of value pair
;
; private structures
; hashtable_char
;
; desc: pointer access of string contents
;
XIncludeFile "generic.pb"
; structures
Structure s_hashtable
c.i ; index of current value
n.i ; index of next value
EndStructure
Structure hashtable_char
c.c
EndStructure
; methods
Procedure.i hastable_hashingfunction(string$)
*p.hashtable_char = @string$
s = SizeOf(*p\c)
; calculate hash value using the shift-add algorithm
For i = 1 To Len(string$)
h << 4
h + *p\c
*p + s
Next
; make sure h is positive
If h < 0
h = ~h + 1
EndIf
ProcedureReturn h
EndProcedure
Procedure.i addmultimap(key$, value$, Array key$(1), Array value$(1), Array table.s_hashtable(1))
c = -1 ; default value for the index parameter
ks = ArraySize(key$()) ; get initial array size
vs = ArraySize(value$())
ts = ArraySize(table())
; table size must be >= 1
; should be about the size of the anticipated datum
Assert(ts < 1)
; check whether table has been initialized
; use initial table size as hash size
If table(0)\c = 0
table(0)\n = ts
EndIf
; get hash table size
hs = table(0)\n
; add key, value to array
; resize array as necessary
c = table(0)\c
If c > ks
ks = ((ks + 1) * 2 - 1)
ReDim key$(ks)
EndIf
key$(c) = key$
If c > vs
vs = ((vs + 1) * 2 - 1)
ReDim value$(vs)
EndIf
value$(c) = value$
; calculate hash and array index
i = hastable_hashingfunction(key$) % hs + 1
; go to the end of the hash space
While Not(table(i)\n = 0)
i = table(i)\n
Wend
; add new hash link
; resize array as necessary
t = 1 + table(0)\c + table(0)\n
If t > ts
ts = ((ts + 1) * 2 - 1)
ReDim table(ts)
EndIf
table(t)\c = c
table(i)\n = t
; change index parameter to next position
table(0)\c + 1
ProcedureReturn c
EndProcedure
Procedure.i querymapindex(key$, start, Array key$(1), Array table.s_hashtable(1))
c = -1 ; default value for the index parameter
ts = ArraySize(table()) ; get array size
; table size must be >= 1
; should be about the size of the anticipated datum
Assert(ts < 1)
hs = table(0)\n ; get hash table size
; calculate hash and array index
i = hastable_hashingfunction(key$) % hs + 1
; go to the first match greater than start
; stop at the end of hash space
While Not(table(i)\n = 0 Or (key$(table(i)\c) = key$ And table(i)\c >= start))
i = table(i)\n
Wend
If i > 0
c = table(i)\c ; return the index of the value pair
EndIf
ProcedureReturn c
EndProcedure
i.e. a csv could be a settings file
Code: Select all
XIncludeFile "readcsv.pb"
XIncludeFile "hashtable.pb"
; main program
Dim csv$(0)
Dim index(0)
Dim key$(0)
Dim value$(0)
Dim table.s_hashtable(500)
If readcsv("test3.csv", csv$(), index())
; do csv processing here
For i = 0 To ArraySize(index()) - 1
j = index(i)
k = index(i + 1) - j
If k >= 2
addmultimap(csv$(j), csv$(j + 1), key$(), value$(), table())
EndIf
Next
For i = 0 To table(0)\c - 1
Debug Str(i) + ": " + key$(i) + " -> " + value$(i)
Next
i = querymapindex(key$(10), 0, key$(), table())
If i >= 0
Debug Str(i) + ": " + key$(i) + " -> " + value$(i)
EndIf
EndIf
End
