Array asosiatif, juga disebut tabel hash atau peta hash, mirip dengan array standar kecuali indeks array dapat berupa string, bukan integer. Dalam banyak aplikasi database dan program lain yang menangani data dalam jumlah besar, array asosiatif adalah elemen penting dalam membantu menyortir dan mengakses informasi dengan cara yang efisien. Inti dari array asosiatif adalah array standar yang diindeks dengan bilangan bulat, seperti biasanya. Sebuah algoritma khusus yang disebut fungsi hash mengubah indeks string menjadi indeks integer untuk menemukan nilainya. Ini adalah konversi yang konsisten, jadi indeks bilangan bulat yang sebenarnya tidak perlu disimpan tetapi malah dihitung dari string sesuai kebutuhan setiap kali.
Terminologi yang digunakan ketika mengacu pada array asosiatif dapat sedikit berbeda dari apa yang digunakan ketika berbicara tentang array normal. Apa yang biasanya disebut indeks — lokasi numerik elemen di dalam array — disebut kunci. Data yang terkait dengan kunci disebut nilai. Ini berarti bahwa, dalam larik asosiatif, kunci dikaitkan dengan nilai, yang berkorelasi dengan indeks yang mereferensikan elemen dalam larik standar dalam struktur data.
Inti dari setiap array asosiatif adalah fungsi hash. Ini adalah algoritma yang digunakan untuk menentukan indeks numerik suatu nilai berdasarkan kunci. Ada beberapa jenis fungsi hash, beberapa dirancang untuk beroperasi pada kunci yang merupakan bilangan bulat dan beberapa dirancang untuk bekerja pada kunci yang berupa string. Dalam kasus kunci bilangan bulat, metode yang populer adalah membagi nilai kunci dengan ukuran array dan menggunakan sisa pembagian untuk, semoga, mendapatkan nilai indeks yang unik.
Fungsi hash bisa jauh lebih kompleks untuk kunci yang berupa string. Beberapa metode termasuk menambahkan nilai numerik dari setiap karakter dalam string dan kemudian membaginya dengan beberapa angka, atau hanya menggunakan beberapa karakter pertama dari string untuk mendapatkan nomor unik. Ada banyak cara untuk menurunkan angka dari serangkaian karakter.
Ketika berhadapan dengan sejumlah besar pasangan nilai kunci dalam array asosiatif, satu masalah yang dapat muncul disebut tabrakan. Tabrakan terjadi ketika indeks bilangan bulat yang diturunkan dari sebuah kunci identik dengan indeks bilangan bulat dari kunci lain. Kedua kunci ini kemudian secara efektif menunjuk ke indeks yang sama dalam larik nilai. Ada berbagai solusi untuk tabrakan, terutama karena kemungkinan besar terjadi di sebagian besar aplikasi praktis.
Salah satu solusi untuk tabrakan adalah agar setiap indeks nilai benar-benar menjadi daftar tertaut sehingga, ketika lebih dari satu kunci diselesaikan ke lokasi indeks itu, lokasi dapat menyimpan lebih dari satu nilai. Ini disebut chaining dan merupakan cara sederhana untuk menangani tabrakan, meskipun juga dapat memperlambat waktu yang diperlukan untuk mengambil informasi. Metode lain untuk menangani tumbukan disebut penyelidikan linier. Ketika tabrakan terjadi, probing linier bekerja dengan bergerak melalui array nilai sampai indeks yang tidak digunakan ditemukan. Solusi ini dapat membantu menjaga data terdistribusi secara merata dalam array asosiatif, tetapi juga dapat meningkatkan jumlah waktu yang diperlukan untuk mencari nilai.