O matrice asociativă, numită și tabel hash sau hartă hash, este similară cu o matrice standard, cu excepția faptului că indexul matricei poate fi un șir în loc de un număr întreg. În multe aplicații de baze de date și în alte programe care se ocupă cu cantități mari de date, o matrice asociativă este un element vital pentru a ajuta la sortarea și accesarea informațiilor într-un mod eficient. La baza unui tablou asociativ se află o matrice standard care este indexată cu numere întregi, așa cum ar fi cazul în mod normal. Un algoritm special numit funcție hash convertește indexul șirului într-un index întreg pentru a găsi valoarea. Aceasta este o conversie consecventă, astfel încât indexul întreg real nu trebuie să fie stocat, ci este calculat din șir după cum este necesar de fiecare dată.
Terminologia folosită atunci când se face referire la o matrice asociativă poate fi ușor diferită de cea folosită când se vorbește despre o matrice normală. Ceea ce s-ar numi în mod normal un index – locația numerică a unui element în interiorul unui tablou – se numește cheie. Datele asociate cu cheia se numesc valoare. Aceasta înseamnă că, în cadrul unui tablou asociativ, o cheie este asociată cu o valoare, care se corelează cu un index care face referire la un element dintr-o matrice standard din structura de date.
În centrul fiecărui tablou asociativ se află funcția hash. Acesta este un algoritm folosit pentru a determina indexul numeric al unei valori pe baza cheii. Există mai multe tipuri de funcții hash, unele concepute pentru a funcționa pe taste care sunt numere întregi și unele concepute pentru a funcționa pe taste care sunt șiruri. În cazul unei chei întregi, o metodă populară este de a împărți valoarea cheii la dimensiunea matricei și de a folosi restul diviziunii pentru, sperăm, a obține o valoare unică de index.
Funcția hash poate fi mult mai complexă pentru cheile care sunt șiruri. Unele metode includ adăugarea valorii numerice a fiecărui caracter din șir și apoi împărțirea acestuia la un număr sau folosirea doar a primelor caractere ale șirului pentru a obține un număr unic. Există multe modalități de a obține un număr dintr-un șir de caractere.
Când aveți de-a face cu o cantitate mare de perechi cheie-valoare într-o matrice asociativă, o problemă care poate apărea se numește coliziune. Ciocnirea are loc atunci când indexul întreg derivat dintr-o cheie este identic cu indexul întreg al altei chei. Aceste două chei indică apoi efectiv către același index în matricea de valori. Există diverse soluții pentru coliziunea, în principal pentru că are o probabilitate mare de a se întâmpla în majoritatea aplicațiilor practice.
O soluție la coliziune este ca fiecare index de valoare să fie de fapt o listă legată, astfel încât, atunci când mai multe chei se rezolvă la acea locație de index, locația poate conține mai multe valori. Aceasta se numește înlănțuire și este o modalitate simplă de a gestiona o coliziune, deși poate încetini și timpul necesar pentru a prelua informațiile. O altă metodă de a trata o coliziune se numește sondare liniară. Când are loc o coliziune, sondarea liniară funcționează prin deplasarea prin matricea de valori până când este găsit un index neutilizat. Această soluție poate ajuta la păstrarea datelor uniform distribuite în matricea asociativă, dar poate crește și timpul necesar pentru a căuta o valoare.