Hash table
Posted: Sat Feb 02, 2013 8:09 pm
Otsikko kertookin kaiken, mutta selvennyksenä vielä joillekkin:
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.
Toivoisin, että virheitä löydetään (ja parempi hash-funktio?).
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