Hash-kartat ovat indeksoituja tietorakenteita. Hash-kartta käyttää a hash-toiminto laskea indeksin avaimella joukkoon ryhmiä tai paikkoja. Sen arvo kartoitetaan lokeroon vastaavan indeksin kanssa. Avain on ainutlaatuinen ja muuttumaton. Ajattele hash-karttaa kaappina, jossa on laatikot, joissa on tarrat niihin varastoituille tavaroille. Esimerkiksi käyttäjätietojen tallentaminen - pidä sähköpostia avaimena, ja voimme kartoittaa käyttäjää vastaavat arvot, kuten etunimi, sukunimi jne., ämpäriin.
Hash-funktio on hash-kartan toteuttamisen ydin. Se ottaa avaimen sisään ja kääntää sen ämpäriluettelon hakemistoksi. Ihanteellisen hajautusarvon tulisi tuottaa erilainen indeksi jokaiselle avaimelle. Törmäyksiä voi kuitenkin tapahtua. Kun hajautus antaa olemassa olevan indeksin, voimme yksinkertaisesti käyttää ryhmää useille arvoille lisäämällä luettelon tai tiivistämällä uudelleen.
Pythonissa sanakirjat ovat esimerkkejä hash-kartoista. Näemme hash-kartan käyttöönoton tyhjästä, jotta opimme rakentamaan ja mukauttamaan tällaisia tietorakenteita haun optimointia varten.
Wordin pikatyökalurivi
Hash-kartan suunnittelu sisältää seuraavat toiminnot:
- set_val(avain, arvo): Lisää avain-arvo-parin hash-karttaan. Jos arvo on jo tiivistekartassa, päivitä arvo.
- get_val(avain): Palauttaa arvon, johon määritetty avain on yhdistetty, tai Tietuetta ei löytynyt, jos tämä kartta ei sisällä määritystä avaimelle.
- delete_val(avain): Poistaa tietyn avaimen yhdistämisen, jos tiivistekartta sisältää avaimen määrityksen.
Alla toteutus.
Python 3
javafx on eclipse
class> HashTable:> ># Create empty bucket list of given size> >def> __init__(>self>, size):> >self>.size>=> size> >self>.hash_table>=> self>.create_buckets()> >def> create_buckets(>self>):> >return> [[]>for> _>in> range>(>self>.size)]> ># Insert values into hash map> >def> set_val(>self>, key, val):> > ># Get the index from the key> ># using hash function> >hashed_key>=> hash>(key)>%> self>.size> > ># Get the bucket corresponding to index> >bucket>=> self>.hash_table[hashed_key]> >found_key>=> False> >for> index, record>in> enumerate>(bucket):> >record_key, record_val>=> record> > ># check if the bucket has same key as> ># the key to be inserted> >if> record_key>=>=> key:> >found_key>=> True> >break> ># If the bucket has same key as the key to be inserted,> ># Update the key value> ># Otherwise append the new key-value pair to the bucket> >if> found_key:> >bucket[index]>=> (key, val)> >else>:> >bucket.append((key, val))> ># Return searched value with specific key> >def> get_val(>self>, key):> > ># Get the index from the key using> ># hash function> >hashed_key>=> hash>(key)>%> self>.size> > ># Get the bucket corresponding to index> >bucket>=> self>.hash_table[hashed_key]> >found_key>=> False> >for> index, record>in> enumerate>(bucket):> >record_key, record_val>=> record> > ># check if the bucket has same key as> ># the key being searched> >if> record_key>=>=> key:> >found_key>=> True> >break> ># If the bucket has same key as the key being searched,> ># Return the value found> ># Otherwise indicate there was no record found> >if> found_key:> >return> record_val> >else>:> >return> 'No record found'> ># Remove a value with specific key> >def> delete_val(>self>, key):> > ># Get the index from the key using> ># hash function> >hashed_key>=> hash>(key)>%> self>.size> > ># Get the bucket corresponding to index> >bucket>=> self>.hash_table[hashed_key]> >found_key>=> False> >for> index, record>in> enumerate>(bucket):> >record_key, record_val>=> record> > ># check if the bucket has same key as> ># the key to be deleted> >if> record_key>=>=> key:> >found_key>=> True> >break> >if> found_key:> >bucket.pop(index)> >return> ># To print the items of hash map> >def> __str__(>self>):> >return> ''.join(>str>(item)>for> item>in> self>.hash_table)> hash_table>=> HashTable(>50>)> # insert some values> hash_table.set_val(>'[email protected]'>,>'some value'>)> print>(hash_table)> print>()> hash_table.set_val(>'[email protected]'>,>'some other value'>)> print>(hash_table)> print>()> # search/access a record with key> print>(hash_table.get_val(>'[email protected]'>))> print>()> # delete or remove a value> hash_table.delete_val(>'[email protected]'>)> print>(hash_table)> |
>
>
Lähtö:
Aika monimutkaisuus:
Muistiindeksin käyttö vie jatkuvasti aikaa ja hajautus kestää jatkuvasti. Siten hajautuskartan haun monimutkaisuus on myös vakioaika, eli O(1).
HashMapsin edut
● Nopea satunnaismuistin käyttö hash-toimintojen avulla
● Pystyy käyttämään negatiivisia ja ei-integraalisia arvoja päästäkseen arvoihin.
● Avaimet voidaan tallentaa lajiteltuun järjestykseen, joten ne voivat toistaa karttoja helposti.
HashMapsin haitat
merkkijono boolen javaan
● Törmäykset voivat aiheuttaa suuria rangaistuksia ja räjäyttää ajan monimutkaisuuden lineaariseksi.
● Kun avainten määrä on suuri, yksi hajautustoiminto aiheuttaa usein törmäyksiä.
HashMapsin sovellukset
● Niissä on sovelluksia välimuistin toteutuksissa, joissa muistipaikat on yhdistetty pieniin ryhmiin.
● Niitä käytetään monikkojen indeksointiin tietokannan hallintajärjestelmissä.
● Niitä käytetään myös algoritmeissa, kuten Rabin Karp -kuvion sovituksessa