Array asosiatif

Dalam ilmu komputer , array asosiatif, peta, tabel simbol, atau kamus adalah tipe data abstrak terdiri dari (key, value) koleksi dari  pasang, sehingga setiap kunci yang mungkin muncul paling banyak sekali dalam koleksi.

Operasi yang terkait dengan tipe data ini memungkinkan:

- penambahan pasangan untuk koleksi

- penghapusan pasang dari koleksi

- modifikasi nilai-nilai yang ada pasang

- ookup dari nilai yang terkait dengan kunci tertentu

Kamus masalah adalah tugas merancang sebuah struktur data yang mengimplementasikan array asosiatif. Sebuah solusi standar untuk masalah kamus adalah tabel hash , dalam beberapa kasus juga memungkinkan untuk memecahkan masalah dengan menggunakan langsung ditujukan array , pohon pencarian biner, atau struktur yang lebih khusus lainnya.

Banyak bahasa pemrograman termasuk array asosiatif sebagai tipe data primitif , dan mereka tersedia dalam perpustakaan software bagi banyak orang lain. Content-addressable memori merupakan bentuk dukungan hardware-tingkat langsung untuk array asosiatif. Array asosiatif memiliki banyak aplikasi termasuk seperti dasar pola pemrograman sebagai memoization dan pola dekorator .

Operasi

Dalam array asosiatif, hubungan antara kunci dan nilai sering dikenal sebagai "mengikat", dan kata yang sama "mengikat" dapat juga digunakan untuk merujuk kepada proses menciptakan hubungan baru.

Operasi yang biasanya ditetapkan untuk array asosiatif adalah:

- Menambah atau menyisipkan Tambahkan baru (key, value) pasangan untuk koleksi, mengikat kunci baru untuk nilai baru. Argumen untuk operasi ini adalah kunci dan nilai.

- Tugaskan: ganti nilai di salah satu (key, value) pasangan yang sudah dalam koleksi, mengikat kunci lama ke nilai baru. Seperti dengan penyisipan, argumen untuk operasi ini adalah kunci dan nilai.

- Hapus atau menghapus: menghapus (key, value) pasangan dari koleksi, tidak mengikat kunci yang diberikan dari nilainya. Argumen untuk operasi ini adalah kuncinya.

- Lookup: menemukan nilai (jika ada) yang terikat dengan kunci yang diberikan. Argumen untuk operasi ini adalah kuncinya, dan nilai yang kembali dari operasi. Jika tidak ada nilai ditemukan, beberapa implementasi array asosiatif menaikkan pengecualian .

Selain itu, array asosiatif juga dapat mencakup operasi lain seperti menentukan jumlah binding atau membangun sebuah iterator loop atas semua binding. Biasanya, untuk operasi semacam itu, urutan binding dikembalikan mungkin sewenang-wenang.

Sebuah multimap menggeneralisasi array asosiatif dengan memungkinkan beberapa nilai untuk dihubungkan dengan satu tombol. Sebuah peta dua arah adalah tipe data abstrak terkait di mana binding beroperasi di kedua arah: setiap nilai harus terkait dengan kunci yang unik, dan operasi pencarian kedua mengambil nilai sebagai argumen dan mendongak kunci yang terkait dengan nilai tersebut.

Implementasi

Untuk kamus dengan jumlah yang sangat kecil dari binding, mungkin masuk akal untuk menerapkan kamus menggunakan daftar asosiasi , sebuah linked list binding. Dengan implementasi ini, waktu untuk melakukan operasi kamus dasar adalah linier dalam jumlah binding, namun mudah untuk menerapkan dan faktor-faktor konstan dalam waktu yang berjalan kecil.

Teknik pelaksanaan lain yang sangat sederhana, dapat digunakan ketika tombol dibatasi untuk kisaran sempit bilangan bulat, adalah langsung menangani ke dalam sebuah array: nilai untuk k kunci yang diberikan disimpan di array sel A, atau jika tidak ada yang mengikat untuk k maka sel menyimpan khusus nilai sentinel yang menunjukkan tidak adanya mengikat. Serta menjadi sederhana, teknik ini cepat: setiap operasi kamus membutuhkan waktu konstan. Namun, kebutuhan ruang untuk struktur ini adalah ukuran seluruh ruang kunci, sehingga tidak praktis kecuali keyspace kecil.

Yang paling sering digunakan pelaksanaan tujuan umum dari array asosiatif adalah dengan tabel hash : sebuah array yang binding, bersama-sama dengan fungsi hash yang memetakan setiap tombol mungkin ke indeks array. Ide dasar dari tabel hash adalah bahwa mengikat untuk diberikan kunci disimpan di posisi yang diberikan dengan menerapkan fungsi hash untuk kunci itu, dan bahwa operasi pencarian dilakukan dengan melihat bahwa sel array dan menggunakan mengikat ditemukan di sana . Namun, kamus berbasis tabel hash harus siap untuk menangani tabrakan yang terjadi ketika dua tombol dipetakan oleh fungsi hash untuk indeks yang sama, dan banyak strategi resolusi tabrakan yang berbeda telah dikembangkan untuk menangani situasi ini, sering didasarkan baik pada menangani terbuka ( melihat urutan indeks tabel hash bukan indeks tunggal, sampai menemukan salah satu kunci yang diberikan atau sel kosong) atau hash chaining (menyimpan daftar asosiasi kecil bukannya mengikat tunggal dalam setiap sel tabel hash).

Kamus juga dapat disimpan dalam pohon pencarian biner atau dalam struktur data khusus untuk jenis tertentu kunci seperti pohon radix , mencoba , Judy array , atau pohon van Emde Boas , namun metode pelaksanaan ini kurang efisien daripada tabel hash serta menempatkan pembatasan lebih besar pada jenis data yang mereka dapat menangani. Keuntungan dari struktur alternatif berasal dari kemampuan mereka untuk menangani operasi di luar yang dasar dari array asosiatif, seperti menemukan mengikat yang utama adalah yang paling dekat dengan kunci tanya, bila permintaan tidak sendiri hadir di set binding.

Dukungan bahasa

Array asosiatif dapat diimplementasikan dalam bahasa pemrograman sebagai sebuah paket dan banyak sistem bahasa menyediakan mereka sebagai bagian dari perpustakaan standar mereka. Dalam beberapa bahasa, mereka tidak hanya dibangun ke dalam sistem standar, namun memiliki sintaks khusus, yang sering menggunakan array seperti subscripting.

Built-in mendukung sintaksis untuk array asosiatif diperkenalkan oleh SNOBOL 4, di bawah "meja" nama. gondok membuat array asosiatif multi-dimensi, opsional gigih, struktur data kunci. SETL mendukung mereka sebagai salah satu kemungkinan pelaksanaan set dan peta. Kebanyakan bahasa scripting modern, dimulai dengan AWK dan termasuk Perl , Tcl , JavaScript , Python , Ruby , dan Lua , mendukung array asosiatif sebagai jenis wadah primer. Dalam banyak bahasa, mereka yang tersedia sebagai fungsi perpustakaan tanpa sintaks khusus.

Di Smalltalk , Objective-C , . NET , [7] Python , dan REALbasic mereka disebut kamus, dalam Perl dan Ruby mereka disebut hash, dalam C + + , Java , Go , Clojure , Scala , OCaml , Haskell mereka disebut peta ( lihat peta (C + +) , unordered_map (C + +) , dan Map ), dalam Common Lisp dan Windows PowerShell , mereka disebut tabel hash (karena keduanya biasanya menggunakan implementasi ini). Dalam PHP , semua array dapat asosiatif, kecuali bahwa tombol yang terbatas pada bilangan bulat dan string. Dalam JavaScript (lihat juga JSON ), semua benda berperilaku sebagai array asosiatif. Di Lua, mereka disebut meja, dan digunakan sebagai blok bangunan primitif untuk semua struktur data. Dalam Visual FoxPro , mereka disebut Collections.