Page 1 of 1

Hash table

Posted: Sat Feb 02, 2013 8:09 pm
by Jani
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 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
Toivoisin, että virheitä löydetään (ja parempi hash-funktio?).

Re: Hash table

Posted: Sat Feb 02, 2013 8:29 pm
by Latexi95
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 8:35 pm
by Jani
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 8:44 pm
by Latexi95
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.