Page 1 of 1

### Hash table

Posted: Sat Feb 02, 2013 9: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.

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 "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
``````
Toivoisin, että virheitä löydetään (ja parempi hash-funktio?).

### Re: Hash table

Posted: Sat Feb 02, 2013 9:29 pm
Mukava väkerrys mutta vähän epäilyttää että todennäköisesti tuolla toteutuksella aika helposti tulee hashien törmäyksiä ja eri avaimella olevat tiedot päätyvät päällekkäin. Myös olisi kiva jos hashtaulukon koko kasvaisi tarvittaessa.

### Re: Hash table

Posted: Sat Feb 02, 2013 9:35 pm
Latexi95 wrote:Mukava väkerrys mutta vähän epäilyttää että todennäköisesti tuolla toteutuksella aika helposti tulee hashien törmäyksiä ja eri avaimella olevat tiedot päätyvät päällekkäin. Myös olisi kiva jos hashtaulukon koko kasvaisi tarvittaessa.
Törmäykset eivät kovinkaan vaikuta, koska systeemi osaa käsitellä ne. Dynaamisuus vaatisi kokonaan erilaisen systeemin, joka olisi samalla tehosyöppö.
EDIT:

Tuo tyyppi on siis juurikin törmäysten käsittelyä varten.
EDIT2: Juuripa nin.

### Re: Hash table

Posted: Sat Feb 02, 2013 9:44 pm
Joo joo... Tutkin nyt vähän tarkemmin toteutustasi. Kyllähän tuo näköjään näyttää tukevan periaatteessa rajatonta määrää avain-arvo pareja mutta vain sitten maksimissaan HT_HASHCOUNTin verran erilaisia hashejä jolloin hashien mennessä päällekkäin haetaan lineaarisesti.