Hash table

Oletko tehnyt jotain, mistä muut voisivat hyötyä. Postita vinkit tänne.
Post Reply
Jani
Devoted Member
Posts: 741
Joined: Fri Oct 31, 2008 4:53 pm

Hash table

Post 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?).
Dead men tell no tales. Also, Python rocks!
Codegolf: 99 bottles of beer (oneliner) - Water map partition
Latexi95
Guru
Posts: 1166
Joined: Sat Sep 20, 2008 5:10 pm
Location: Lempäälä

Re: Hash table

Post 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.
Jani
Devoted Member
Posts: 741
Joined: Fri Oct 31, 2008 4:53 pm

Re: Hash table

Post 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.

Last edited by Jani on Sat Feb 02, 2013 8:49 pm, edited 1 time in total.
Dead men tell no tales. Also, Python rocks!
Codegolf: 99 bottles of beer (oneliner) - Water map partition
Latexi95
Guru
Posts: 1166
Joined: Sat Sep 20, 2008 5:10 pm
Location: Lempäälä

Re: Hash table

Post 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.
Post Reply