Apa perbedaan antara peta dan kamus?

Saya tahu peta adalah struktur data yang memetakan kunci nilai. Bukankah kamus itu sama? Apa perbedaan antara peta dan kamus ¹ ?

_{1. Saya tidak bertanya bagaimana mereka didefinisikan dalam bahasa X atau Y (yang tampaknya menjadi apa yang umumnya orang tanyakan di sini pada SO), saya ingin tahu apa perbedaan mereka dalam teori.}

Dua istilah untuk hal yang sama:

• "Peta" digunakan oleh Java, C ++
• "Kamus" digunakan oleh .Net, Python
• "Array asosiatif" digunakan oleh PHP

"Peta" adalah istilah matematika yang benar, tetapi dihindari karena memiliki arti yang terpisah dalam pemrograman fungsional .

Beberapa bahasa masih menggunakan istilah lain ("Objek" dalam Javascript, "Hash" di Ruby, "Tabel" di Lua) , tetapi semua itu memiliki arti yang terpisah dalam pemrograman juga, jadi saya akan menghindarinya.

Lihat di sini untuk info lebih lanjut.

Satu adalah istilah yang lebih tua untuk yang lain. Biasanya istilah "kamus" digunakan sebelum istilah matematika "peta" mulai berlaku. Juga, kamus cenderung memiliki tipe kunci string, tetapi itu tidak 100% benar di mana-mana.

2 sen saya.

Kamus adalah kelas abstrak di Jawa sedangkan Peta adalah antarmuka. Karena, Java tidak mendukung banyak pewarisan, jika suatu kelas memperluas Kamus, itu tidak dapat memperluas kelas lain.

Oleh karena itu, antarmuka Peta diperkenalkan.

Kelas kamus sudah usang dan penggunaan Peta lebih disukai.

Menjawab pertanyaan ini rumit oleh programmer yang telah melihat istilah yang diberikan makna yang lebih spesifik dalam bahasa atau sistem tertentu yang mereka gunakan, tetapi pertanyaannya meminta perbandingan agnostik bahasa "dalam teori", yang saya maksudkan dalam istilah Ilmu Komputer. .

Terminologi itu dijelaskan

Daftar Ilmu Komputer Universitas Oxford daftar:

kamus setiap struktur data yang mewakili sekumpulan elemen yang dapat mendukung penyisipan dan penghapusan elemen serta menguji keanggotaan

• Misalnya, kami memiliki serangkaian elemen {A, B, C, D ...} yang dapat kami sisipkan dan dapat mulai dihapus, dan kami dapat menanyakan "apakah C ada?" .

Computing Ilmu gagasan peta meskipun didasarkan pada jangka linguistik matematika pemetaan , yang Oxford Dictionary mendefinisikan sebagai:

mapping Suatu operasi yang mengaitkan setiap elemen dari himpunan tertentu (domain) dengan satu atau lebih elemen dari himpunan kedua (rentang).

• Dengan demikian, peta struktur data menyediakan cara untuk beralih dari elemen set yang diketahui - adalah " kunci " di peta, ke satu atau lebih elemen pada set kedua - yang dikenal sebagai " nilai " yang terkait .
• Aspek "... atau lebih banyak elemen di set kedua" dapat didukung oleh implementasi adalah dua cara berbeda:
  • Banyak implementasi peta menegakkan keunikan kunci dan hanya memungkinkan setiap kunci dikaitkan dengan satu nilai, tetapi nilai itu mungkin bisa menjadi struktur data itu sendiri yang mengandung banyak nilai dari tipe data yang lebih sederhana, misalnya {{1, {"one" , "ichi"}, {2, {"two", "ni"}}} menggambarkan nilai yang terdiri dari pasangan string.
  • Implementasi peta lainnya memungkinkan duplikat kunci setiap pemetaan dengan nilai yang sama atau berbeda - yang secara fungsional memenuhi "asosiasi ... setiap elemen [kunci] ... dengan ... lebih dari [lebih dari satu] elemen [nilai] elemen". Misalnya, {{1, "one"}, {1, "ichi"}, {2, "two"}, {2, "ni"}}.

Kamus dan peta dikontraskan

Jadi, menggunakan terminologi Comp Sci yang ketat di atas, kamus hanyalah peta jika antarmuka terjadi untuk mendukung operasi tambahan yang tidak diperlukan dari setiap kamus:

• kemampuan untuk menyimpan elemen dengan kunci dan nilai yang berbeda komponen

• kemampuan untuk mengambil nilai yang diberikan hanya kunci

Twist twist:

• antarmuka peta mungkin tidak secara langsung mendukung pengujian apakah pasangan {key, value} ada di dalam wadah, yang merupakan persyaratan kamus di mana elemen-elemennya adalah pasangan {key, value}; sebuah peta bahkan mungkin tidak memiliki fungsi untuk menguji kunci, tetapi paling buruk Anda dapat melihat apakah upaya pengambilan-nilai-demi-kunci berhasil atau gagal, maka jika Anda peduli, Anda dapat memeriksa apakah kunci tersebut mengambil nilai yang diharapkan.

Berkomunikasi dengan jelas kepada audiens Anda

⚠ Terlepas dari semua hal di atas, jika Anda menggunakan kamus dalam arti Computing Science yang dijelaskan di atas, jangan berharap audiens akan mengikuti Anda pada awalnya, atau terkesan saat Anda berbagi dan mempertahankan terminologi. Jawaban lain untuk pertanyaan ini (dan upvote mereka) menunjukkan seberapa besar kemungkinan "kamus" akan identik dengan "peta" dalam pengalaman sebagian besar programmer. Cobalah untuk memilih terminologi yang akan lebih luas dan jelas dipahami: misalnya

• wadah asosiatif : wadah apa pun yang menyimpan pasangan kunci / nilai dengan pengambilan nilai dan penghapusan dengan kunci
• peta hash : implementasi tabel hash dari wadah rekanan
• hash mengatur penegakan kunci unik : implementasi tabel hash dari kamus yang menyimpan elemen / nilai tanpa memperlakukannya sebagai mengandung kunci / komponen nilai yang berbeda, di mana duplikat elemen tidak dapat dimasukkan
• menyeimbangkan peta pohon biner yang mendukung kunci rangkap : ...

Terminologi Cross Screferencing Comp Sains dengan implementasi spesifik

C ++ Perpustakaan Standar

• peta: map, multimap, unordered_map,unordered_multimap
• kamus lainnya: set, multiset, unordered_set,unordered_multiset
• Catatan: dengan iterator atau std::findAnda dapat menghapus elemen dan tes untuk keanggotaan dalam array, vector, list, dequedll, tapi antarmuka kontainer tidak langsung mendukung itu karena menemukan unsur spektakuler tidak efisien di O (N), dalam beberapa kasus insert / menghapus yaitu tidak efisien, dan mendukung operasi-operasi itu merusak API yang sengaja dibatasi oleh wadah - misalnyadeque s hanya mendukung penghapusan / pop di bagian depan dan belakang dan tidak dalam hal kunci. Harus melakukan lebih banyak pekerjaan dalam kode untuk mengatur pencarian dengan lembut mendorong programmer untuk beralih ke struktur data kontainer dengan pencarian yang lebih efisien.

... dapat menambahkan bahasa lain nanti / silakan mengedit di ...

Biasanya saya berasumsi bahwa peta didukung oleh tabel hash; itu berkonotasi dengan toko yang tidak diurusi Kamus berkonotasi toko yang dipesan.

Ada kamus berbasis pohon yang disebut Trie .

Dalam Lisp, akan terlihat seperti ini:

(a (n (d t)) n d )

Yang merangkum kata-kata:

• Sebuah
• dan
• semut
• sebuah
• iklan

Traversal dari atas ke daun menghasilkan kata.

Bukan hal yang sama. Peta adalah bagian dari kamus. Kamus didefinisikan di sini sebagai memiliki fungsi menyisipkan, menghapus, dan menemukan. Peta seperti yang digunakan oleh Java (menurut ini ) adalah kamus dengan persyaratan pemetaan kunci ke nilai dipetakan secara ketat sebagai fungsi satu-ke-satu. Kamus mungkin memiliki lebih dari satu peta kunci untuk satu nilai, atau satu peta kunci untuk beberapa nilai (seperti rantai di hasthtable), misalnya pencarian tagar Twitter.

Sebagai contoh yang lebih "dunia nyata", mencari kata dalam kamus dapat memberi kita sejumlah definisi untuk kata yang sama, dan ketika kita menemukan entri yang mengarahkan kita ke entri lain (lihat kata lain), sejumlah kata untuk daftar definisi yang sama. Di dunia nyata, peta jauh lebih luas, memungkinkan kita untuk memiliki lokasi untuk nama atau nama untuk koordinat, tetapi juga kita dapat menemukan tetangga terdekat atau atribut lainnya (populasi, dll), jadi IMHO mungkin ada argumen untuk perluasan yang lebih besar dari tipe peta mungkin memiliki implementasi berbasis grafik, tetapi akan lebih baik untuk selalu mengasumsikan hanya pasangan nilai kunci, terutama karena tetangga terdekat dan atribut lainnya terhadap nilai semua bisa hanya anggota data dari nilai tersebut.

Peta java, terlepas dari persyaratan satu-ke-satu, dapat mengimplementasikan sesuatu yang lebih seperti kamus umum jika nilainya digeneralisasikan sebagai koleksi itu sendiri, atau jika nilainya hanyalah referensi ke koleksi yang disimpan di tempat lain.

Ingatlah bahwa pengelola Java bukan pengelola definisi ADT, dan bahwa keputusan Java khusus untuk Java.

Istilah lain untuk konsep ini yang cukup umum: array asosiatif dan hash.

Ya, mereka sama, Anda dapat menambahkan "Array Asosiatif" ke dalam campuran.

menggunakan Hashtable atau Hashofter mengacu pada implementasi.

begitu juga pada level teoretis semata.

Kamus adalah nilai yang dapat digunakan untuk menemukan Nilai Tertaut. Peta adalah Nilai yang memberikan instruksi tentang cara menemukan nilai lain

semua koleksi yang memungkinkan akses non linear (yaitu hanya mendapatkan yang pertama atau yang terakhir) adalah Peta, karena Array sederhana pun memiliki indeks yang memetakan ke nilai yang benar. Jadi, sementara Kamus adalah Jenis peta, peta memiliki cakupan fungsi yang jauh lebih luas.

Dalam Praktek biasanya fungsi pemetaan yang menentukan nama, sehingga HashMap adalah struktur data yang dipetakan yang menggunakan algoritma hashing untuk menautkan kunci ke nilai, sedangkan sebagai Kamus tidak menentukan bagaimana kunci terkait dengan nilai. jadi bisa disimpan melalui daftar yang ditautkan, pohon atau algoritma lainnya. dari akhir penggunaan Anda biasanya tidak peduli apa algoritma itu hanya bekerja sehingga Anda menggunakan kamus umum dan hanya bergeser ke salah satu struktur lain hanya ketika Anda perlu memeriksa jenis algoritma

Ini adalah dua istilah berbeda untuk konsep yang sama.
Hashtabledan HashMapjuga merujuk pada konsep yang sama.

Perbedaan utama adalah bahwa Peta , mengharuskan semua entri (nilai & pasangan kunci) memiliki kunci unik. Jika tabrakan terjadi, yaitu ketika entri baru memiliki kunci yang sama dengan entri yang sudah ada dalam koleksi, maka diperlukan penanganan tabrakan.

Biasanya, kami menangani tabrakan menggunakan Chaining Terpisah . Atau Probing Linear .

Sebuah kamus memungkinkan untuk beberapa entri untuk dihubungkan dengan tombol yang sama.

Ketika Peta telah menerapkan Chaining Terpisah, maka cenderung menyerupai Kamus.