Hash table on käytännössä taulukko, josta voi hakea avaimella. Koska en osaa asiaa sen paremmin selittää, http://en.wikipedia.org/wiki/Hash_table
Systeemissä on yksi paha vika ja se on listan koon asetus vakioksi. Testailuissa kuitenkin kävi liian hitaaksi tehdä listasta dynaaminen.
Funktiot, esimerkki ja nopeustestailua.
Code: Select all
Const HT_HASHCOUNT = 200
t = Timer()
table = htCreate()
Print "Created: " + (Timer() - t) + " ms"
t = Timer()
htWrite(table, "pro", 42)
htWrite(table, "pro", 1337) // päällekirjoitus toimii
htWrite(table, "Jani", "aika pro")
Print "Wrote: " + (Timer() - t) + " ms"
t = Timer()
Print htRead(table, "Jani")
Print htRead(table, "pro")
Print "Read: " + (Timer() - t) + " ms"
t = Timer()
htRemove(table)
Print "Removed: " + (Timer() - t) + " ms"
WaitKey
Type HT_PAIR
Field key As String
Field value As String
EndType
Function htWrite(mem As Integer, key As String, value As String)
hash = htHash(key)
If hash < 0 Then hash = hash * -1
pos = ((hash Mod HT_HASHCOUNT) * 4)
If PeekInt(mem, pos) = 0 Then
pairmem = MakeMEMBlock(6)
pair.HT_PAIR = New(HT_PAIR)
pair\key = key
pair\value = value
PokeShort pairmem, 0, 1
PokeInt pairmem, 2, ConvertToInteger(pair)
PokeInt mem, pos, pairmem
Else
pairmem = PeekInt(mem, pos)
count = PeekShort(pairmem, 0)
For i = 1 To count
pair.HT_PAIR = ConvertToType(PeekInt(pairmem, i * 4 - 2))
If pair\key = key Then
pair\value = value
Return True
EndIf
Next i
pairmemsize = MEMBlockSize(pairmem) + 4
ResizeMEMBlock pairmem, pairmemsize
pair.HT_PAIR = New(HT_PAIR)
pair\key = key
pair\value = value
PokeShort pairmem, 0, count + 1
PokeInt pairmem, pairmemsize - 4, ConvertToInteger(pair)
EndIf
EndFunction
Function htRead$(mem As Integer, key As String)
hash = htHash(key)
If hash < 0 Then hash = hash * -1
pos = ((hash Mod HT_HASHCOUNT) * 4)
If PeekInt(mem, pos) = 0 Then Return False
pairmem = PeekInt(mem, pos)
count = PeekShort(pairmem, 0)
For i = 1 To count
pair.HT_PAIR = ConvertToType(PeekInt(pairmem, i * 4 - 2))
If pair\key = key Then Return pair\value
Next i
EndFunction
Function htCreate()
Return MakeMEMBlock(4 + (HT_HASHCOUNT * 4))
EndFunction
Function htRemove(mem As Integer)
For i = 0 To HT_HASHCOUNT - 1
pairmem = PeekInt(mem, i * 4)
If pairmem <> 0 Then
count = PeekInt(pairmem, 0)
For n = 1 To count
pair.HT_PAIR = ConvertToType(PeekInt(pairmem, i * 4 - 2))
Delete pair
Next n
EndIf
Next i
DeleteMEMBlock mem
EndFunction
Function htHash(key As String)
length = Len(key)
hash = 0
For i = 1 To length
hash = hash + (Asc(Mid(key, i, 1)) * i)
If hash > 2147000000 Then hash - 2147000000
Next i
Return hash
EndFunction