Asocijativni niz, koji se također naziva hash tablica ili hash mapa, sličan je standardnom nizu osim što indeks polja može biti niz umjesto cijelog broja. U mnogim aplikacijama baza podataka i u drugim programima koji se bave velikim količinama podataka, asocijativni niz je vitalni element koji pomaže sortiranju i pristupu informacijama na učinkovit način. U jezgri asocijativnog niza nalazi se standardni niz koji je indeksiran cijelim brojevima, kao što bi to inače bio slučaj. Poseban algoritam nazvan hash funkcija pretvara indeks stringa u cijeli broj kako bi pronašao vrijednost. Ovo je dosljedna pretvorba, tako da se stvarni cjelobrojni indeks nikada ne mora pohraniti, već se svaki put izračunava iz niza prema potrebi.
Terminologija koja se koristi kada se govori o asocijativnom nizu može se malo razlikovati od onoga što se koristi kada se govori o normalnom nizu. Ono što bi se inače nazvalo indeksom – numeričkom lokacijom elementa unutar niza – naziva se ključem. Podaci povezani s ključem nazivaju se vrijednošću. To znači da je, unutar asocijativnog niza, ključ pridružen vrijednosti, koja korelira s indeksom koji upućuje na element u standardnom nizu u strukturi podataka.
U srcu svakog asocijativnog niza je hash funkcija. Ovo je algoritam koji se koristi za određivanje numeričkog indeksa vrijednosti na temelju ključa. Postoji nekoliko vrsta hash funkcija, neke su dizajnirane za rad na ključevima koji su cijeli brojevi, a neke za rad na ključevima koji su nizovi. U slučaju cjelobrojnog ključa, popularna metoda je dijeljenje vrijednosti ključa s veličinom niza i korištenje ostatka dijeljenja da se, nadamo se, dobije jedinstvena vrijednost indeksa.
Hash funkcija može biti puno složenija za ključeve koji su nizovi. Neke metode uključuju zbrajanje numeričke vrijednosti svakog znaka u nizu, a zatim dijeljenje s nekim brojem ili korištenje samo prvih nekoliko znakova niza za dobivanje jedinstvenog broja. Postoji mnogo načina da se broj izvede iz niza znakova.
Kada se radi s velikom količinom parova ključ/vrijednost u asocijativnom nizu, jedan problem koji se može pojaviti naziva se kolizija. Kolizija se događa kada je cjelobrojni indeks izveden iz ključa identičan cjelobrojnom indeksu drugog ključa. Ova dva ključa tada učinkovito pokazuju na isti indeks u nizu vrijednosti. Postoje različita rješenja za koliziju, uglavnom zato što ima veliku vjerojatnost da će se dogoditi u većini praktičnih primjena.
Jedno rješenje za koliziju je da svaki indeks vrijednosti zapravo bude povezan popis tako da, kada se više od jednog ključa riješi na tu lokaciju indeksa, lokacija može sadržavati više od jedne vrijednosti. To se zove ulančavanje i jednostavan je način rješavanja kolizije, iako također može usporiti vrijeme potrebno za dohvaćanje informacija. Druga metoda rješavanja sudara naziva se linearno sondiranje. Kada dođe do kolizije, linearno ispitivanje radi tako što se kreće kroz niz vrijednosti dok se ne pronađe neiskorišteni indeks. Ovo rješenje može pomoći da podaci budu ravnomjerno raspoređeni u asocijativnom nizu, ali također može povećati količinu vremena potrebnog za traženje vrijednosti.