Assosiatiivinen taulukko, jota kutsutaan myös hajautaulukkoksi tai hajautuskarttaksi, on samanlainen kuin tavallinen taulukko, paitsi että taulukon indeksi voi olla merkkijono kokonaisluvun sijasta. Monissa tietokantasovelluksissa ja muissa ohjelmissa, jotka käsittelevät suuria tietomääriä, assosiatiivinen taulukko on tärkeä osa tietojen tehokasta lajittelua ja käyttöä. Assosiatiivisen taulukon ytimessä on vakiotaulukko, joka on indeksoitu kokonaislukuilla, kuten normaalisti tapahtuisi. Erityinen algoritmi, jota kutsutaan hash -funktioksi, muuntaa merkkijonon kokonaislukuindeksiksi arvon löytämiseksi. Tämä on johdonmukainen muunnos, joten varsinaista kokonaislukuindeksiä ei tarvitse koskaan tallentaa, vaan se lasketaan sen jälkeen merkkijonosta tarpeen mukaan joka kerta.
Termit, joita käytetään viitattaessa assosiatiiviseen taulukkoon, voivat olla hieman erilaiset kuin mitä käytetään puhuttaessa normaalista taulukosta. Mitä normaalisti kutsuttaisiin indeksiksi – elementin numeeriseksi sijainniksi taulukon sisällä – kutsutaan avaimeksi. Avaimeen liittyviä tietoja kutsutaan arvoiksi. Tämä tarkoittaa, että assosiatiivisen taulukon sisällä avain liittyy arvoon, joka vastaa indeksiä, joka viittaa tietorakenteen vakiotaulukon elementtiin.
Jokaisen assosiatiivisen taulukon ytimessä on tiivistefunktio. Tätä algoritmia käytetään arvon numeerisen indeksin määrittämiseen avaimen perusteella. Hajautustoimintoja on useita tyyppejä, joista osa on suunniteltu toimimaan kokonaislukuna olevilla näppäimillä ja osa on suunniteltu toimimaan merkkijonojen avaimilla. Kokonaislukuavaimen tapauksessa suosittu tapa on jakaa avainarvo taulukon koolla ja käyttää jakauman loppuosaa toivottavasti yksilöllisen indeksi arvon saamiseksi.
Hajautusfunktio voi olla paljon monimutkaisempi avaimille, jotka ovat merkkijonoja. Jotkut menetelmät sisältävät jokaisen merkkijonon numeerisen arvon lisäämisen merkkijonoon ja jakamisen sitten jollakin numerolla tai käyttämällä vain merkkijonon ensimmäisiä merkkejä yksilöllisen numeron saamiseksi. On monia tapoja saada numero merkkijonosta.
Kun käsitellään suurta määrää avain-arvo-pareja assosiatiivisessa taulukossa, yksi ongelma, jota voi syntyä, on törmäys. Törmäys tapahtuu, kun avaimesta johdettu kokonaislukuindeksi on identtinen toisen avaimen kokonaislukuindeksin kanssa. Nämä kaksi avainta osoittavat sitten tehokkaasti samaan indeksiin arvotaulukossa. Törmäykseen on olemassa erilaisia ratkaisuja lähinnä siksi, että sen todennäköisyys tapahtuu useimmissa käytännön sovelluksissa.
Yksi ratkaisu törmäykseen on, että jokainen arvoindeksi on itse asiassa linkitetty luettelo, jotta kun useampi kuin yksi avain ratkaisee kyseisen indeksin sijainnin, sijainti voi sisältää useamman kuin yhden arvon. Tätä kutsutaan ketjutukseksi ja se on yksinkertainen tapa käsitellä törmäystä, mutta se voi myös hidastaa tietojen hakemiseen kuluvaa aikaa. Toista törmäystapaa kutsutaan lineaariseksi koetukseksi. Törmäyksen sattuessa lineaarinen mittaus toimii siirtymällä arvotaulukon läpi, kunnes löydetään käyttämätön indeksi. Tämä ratkaisu voi auttaa pitämään tiedot tasaisesti jaettuna assosiatiivisessa taulukossa, mutta se voi myös lisätä arvon etsimiseen tarvittavaa aikaa.