Apa perbedaan antara hash dan kamus?

46

Apa perbedaan antara Hashdan Dictionary?

Berasal dari latar belakang scripting, saya merasa mereka mirip, tetapi saya ingin mengetahui perbedaan yang tepat. Googling tidak banyak membantu saya.

data-structures hashing dictionary difference hashtable Sairam
sumber

Jawaban:

92

Hashadalah struktur data dengan nama yang sangat buruk di mana programmer telah membingungkan antarmuka dengan implementasi ( dan terlalu malas untuk menulis nama lengkap, yaitu HashTablealih-alih menggunakan singkatan, Hash).

Dictionaryadalah nama "benar" dari antarmuka (= ADT ), yaitu wadah asosiatif yang memetakan kunci (biasanya unik) ke nilai (tidak harus unik).

Tabel hash adalah salah satu implementasi yang memungkinkan dari kamus yang menyediakan karakteristik akses yang cukup baik (dalam hal runtime) dan oleh karena itu seringkali merupakan implementasi standar.

Implementasi semacam itu memiliki dua sifat penting:

  1. kunci harus dapat hashable dan kesetaraan sebanding .
  2. entri muncul tanpa urutan tertentu dalam kamus.

(Untuk kunci yang bisa hashable berarti kita dapat menghitung nilai numerik dari kunci yang selanjutnya digunakan sebagai indeks dalam array.)

Terdapat implementasi alternatif dari struktur data kamus yang memaksakan pemesanan pada kunci - ini sering disebut kamus yang diurutkan (dan biasanya diimplementasikan dalam istilah pohon pencarian, meskipun ada implementasi efisien lainnya).

Untuk meringkas: kamus adalah ADT yang memetakan kunci nilai. Ada beberapa kemungkinan implementasi ADT ini, di mana tabel hash adalah satu. Hashadalah nama yang salah tetapi dalam konteks itu setara dengan kamus yang diimplementasikan dalam hal tabel hash.

Konrad Rudolph
sumber
4
Untuk memberikan contoh dalam C ++, templat wadah asosiatif standar tidak dapat diimplementasikan sebagai hash, meskipun standar berikutnya akan memiliki apa yang secara efektif tabel hash. Mereka dipanggil unordered_mapuntuk menunjukkan apa yang mereka lakukan dan bukan apa yang mereka lakukan.
David Thornley
6
"Benar" menurut otoritas apa? Dalam beberapa bahasa, seperti Ruby dan Perl, nama resmi - baca "benar" - nama untuk struktur ini adalah "hash".
nohat
11
@nohat: Perhatikan saya menggunakan kutipan. Lebih jauh, saya telah menjelaskan mengapa nama itu dipilih dengan buruk, bukan? Jadi, jika Anda memerlukan otoritas, maka saya akan mengatakan itu oleh otoritas polisi ilmu komputer teoritis.
Konrad Rudolph
9
Menariknya, di Ruby 1.9, sebenarnya tidak mungkin untuk mengimplementasikan Hashkelas dengan tabel hash, karena Ruby 1.9 Hashmempertahankan perintah penyisipan sementara tabel hash tidak. Jadi, di Ruby 1.9, namanya Hashbahkan tidak mencerminkan implementasi lagi.
Jörg W Mittag
7
@hippietrail Anda salah - pertama, itu adalah deskripsi yang objektif. Lagi pula, saya memenuhi syarat mengapa penamaannya buruk dan keliru (lihat di bawah). "Terlalu malas" adalah lisensi artistik di pihak saya tetapi intinya tetap bahwa alasan untuk mempersingkat nama adalah intrinsik, yaitu tidak ada alasan untuk menggunakan nama pendek di sini selain untuk mempersingkat nama. Dan Anda salah tentang "kamus": itu hanyalah nama resmi dari struktur data. Definisi "kamus" Anda salah dalam konteks ilmu komputer, dan namanya mendahului Python selama beberapa dekade.
Konrad Rudolph
8

"Kamus" adalah nama konsep. Hashtable adalah implementasi yang mungkin.

dan_waterworth
sumber
1
Hash juga merupakan ADT. HashTable adalah implementasi dari Hash
Sairam
3
@Airam Saya pikir jauh lebih umum untuk 'hash' berarti fungsi hash daripada tabel hash.
jk.
@ jk Sebenarnya "hash" adalah hasil dari penerapan "fungsi / algoritma hash" untuk beberapa input. "Hash table" atau "hash map" omehoe berhubungan dan objek hashable ke beberapa objek (objek dalam bentuk generik, tidak terbatas pada OOP)
johannes
Ada bahasa yang menggunakan 'Hash' untuk merujuk pada struktur tipe kamus daripada hanya untuk operasi fungsi hash. Ruby, misalnya .
Sean Burton
7

Kamus adalah istilah kolektif yang diberikan untuk implementasi struktur data apa pun yang digunakan untuk pencarian / penyisipan cepat. Ini dapat dicapai / diimplementasikan dengan menggunakan berbagai struktur data seperti tabel hash, daftar lompatan, rb tree dll. Tabel hash adalah struktur data spesifik yang berguna untuk banyak tujuan termasuk mengimplementasikan kamus.

ayah
sumber
Hash juga merupakan ADT. Apakah ada perbedaan khusus antara Hash dan Kamus ADT?
Sairam
2
@Airam: Tidak, hash adalah output dari jenis algoritma tertentu (fungsi hash).
5

Sebuah kamus menggunakan kunci untuk referensi nilai langsung di dalam sebuah array asosiatif .

yaitu (KEY => VALUE)

Sebuah hash lebih sering digambarkan sebagai tabel hash yang menggunakan fungsi hash untuk menghitung posisi dalam memori (atau lebih mudah array) di mana nilai akan. Hash akan mengambil KUNCI sebagai input dan memberikan nilai sebagai output. Kemudian colokkan nilai itu ke dalam memori atau indeks array.

yaitu KEY => HASH FUNCTION => VALUE

Saya kira satu langsung sedangkan yang lain tidak. Fungsi hash mungkin juga tidak sempurna dan terkadang menyediakan indeks yang merujuk nilai yang salah. Tapi itu bisa diperbaiki.

Tempat terbaik untuk melihat: Wikipedia ( array asosiatif dan tabel hash )

Ross
sumber