Apa sebenarnya (dan tepatnya) itu "hash?"

Saya telah mendengar kata "hash" digunakan dalam konteks yang berbeda (semua dalam dunia komputasi) dengan makna yang berbeda. Misalnya, dalam buku Learn Python the Hard Way, dalam bab tentang kamus dikatakan "Python menyebut mereka" dicts. "Bahasa lain menyebutnya" hashes. "

Penggunaan kata lain yang umum dalam kaitannya dengan enkripsi. Saya juga mendengar (& membaca) orang yang menggunakan kata "hash" sebagai fungsi spesifik dalam pemrograman tingkat tinggi.

Jadi, apa sebenarnya itu?

Adakah yang bisa (dengan waktu dan siapa yang berpengetahuan) dengan baik hati menjelaskan seluk-beluk "hash (atau hash)?"

Artikel Wikipedia tentang fungsi hash sangat bagus, tetapi saya akan memberikan pendapat saya di sini.

Apa itu hash?

"Hash" adalah istilah yang luas dengan makna formal yang berbeda dalam konteks yang berbeda. Tidak ada jawaban sempurna untuk pertanyaan Anda. Saya akan menjelaskan konsep dasar yang mendasarinya dan menyebutkan beberapa penggunaan istilah yang paling umum.

"Hash" adalah fungsi disebut sebagai fungsi hash yang mengambil sebagai objek input dan output string atau angka. Objek input biasanya anggota tipe data dasar seperti string, integer, atau yang lebih besar yang terdiri dari objek lain seperti struktur yang ditentukan pengguna. Outputnya biasanya berupa angka atau string. Kata benda "hash" sering merujuk pada hasil ini. Kata kerja "hash" sering berarti "menerapkan fungsi hash". Properti utama yang harus dimiliki oleh fungsi hash adalah:$h$

1. Seharusnya mudah untuk menghitung dan
2. Outputnya harus relatif kecil.

Contoh:

Katakanlah kita ingin nomor hash dalam kisaran dari 0 hingga 999.999.999 ke angka antara 0 dan 99. Satu fungsi hash sederhana dapat .$h(x) = x \mod 100$

Properti tambahan umum:

Bergantung pada use case kami mungkin ingin fungsi hash memenuhi properti tambahan. Berikut adalah beberapa properti tambahan yang umum:

1. Keseragaman : Seringkali kita ingin hash objek menjadi berbeda. Selain itu kita mungkin ingin hash menjadi "menyebar". Jika saya ingin hash beberapa objek turun menjadi 100 ember (jadi output dari fungsi hash saya adalah angka dari 0-99), maka saya biasanya berharap sekitar 1/100 objek mendarat di bucket 0, sekitar 1/100 mendarat di ember 1, dan seterusnya.

2. Resistensi tabrakan kriptografi : Kadang-kadang ini diambil lebih jauh, misalnya, dalam kriptografi saya mungkin ingin fungsi hash sedemikian rupa sehingga sulit bagi musuh untuk menemukan dua input berbeda yang memetakan ke output yang sama.

3. Kompresi : Saya sering ingin memotong input besar secara sewenang-wenang menjadi output ukuran konstan atau jumlah bucket tetap.

4. Determinisme : Saya mungkin menginginkan fungsi hash yang outputnya tidak berubah di antara run, yaitu output dari fungsi hash pada objek yang sama akan selalu tetap sama. Ini mungkin tampak bertentangan dengan keseragaman di atas, tetapi satu solusi adalah memilih fungsi hash secara acak satu kali, dan tidak mengubahnya antara menjalankan.

Beberapa aplikasi

Salah satu aplikasi umum adalah dalam struktur data seperti tabel hash, yang merupakan cara untuk mengimplementasikan kamus. Di sini, Anda mengalokasikan sebagian memori, katakanlah, 100 "ember"; kemudian, ketika diminta untuk menyimpan pasangan (kunci, nilai) dalam kamus, Anda mengaitkan kunci tersebut ke angka 0-99, dan menyimpan pasangan tersebut dalam ember yang sesuai dalam memori. Kemudian, ketika Anda diminta untuk mencari kunci, Anda hash kunci ke nomor 0-99 dengan fungsi hash yang sama dan periksa ember itu untuk melihat apakah kunci itu ada di sana. Jika demikian, Anda mengembalikan nilainya.

Perhatikan bahwa Anda juga bisa mengimplementasikan kamus dengan cara lain, seperti dengan pohon pencarian biner (jika objek Anda sebanding).

Aplikasi praktis lain adalah checksum, yang merupakan cara untuk memeriksa bahwa dua file adalah sama (misalnya, file tersebut tidak rusak dari versi sebelumnya). Karena fungsi hash sangat tidak mungkin untuk memetakan dua input ke output yang sama, Anda menghitung dan menyimpan hash dari file pertama, biasanya direpresentasikan sebagai string. Hash ini sangat kecil, mungkin hanya beberapa lusin karakter ASCII. Kemudian, ketika Anda mendapatkan file kedua, Anda hash itu dan periksa apakah hasilnya sama. Jika demikian, hampir pasti itu adalah file byte-untuk-byte yang sama persis.

Aplikasi lain adalah dalam kriptografi, di mana hash ini harus sulit untuk "dibalik" - yaitu, mengingat output dan fungsi hash, harus sulit secara komputasi untuk mengetahui input yang mengarah ke output tersebut. Salah satu penggunaannya adalah untuk kata sandi: Alih-alih menyimpan kata sandi itu sendiri, Anda menyimpan hash kriptografi kata sandi (mungkin dengan beberapa bahan lain). Kemudian, ketika pengguna memasukkan kata sandi, Anda menghitung hash-nya dan memeriksa apakah itu cocok dengan hash yang benar; jika demikian, Anda mengatakan kata sandi itu benar. (Sekarang bahkan seseorang yang dapat melihat dan mencari tahu hash yang disimpan di server tidak memiliki waktu yang mudah berpura-pura menjadi pengguna.) Aplikasi ini dapat menjadi kasus di mana output sama panjang atau lebih lama dari input, karena inputnya sangat pendek.

Sebuah fungsi hash adalah fungsi yang mengambil input dan menghasilkan nilai ukuran tetap. Misalnya Anda mungkin memiliki fungsi hash stringHashyang menerima stringpanjang apa saja dan menghasilkan bilangan bulat 32-bit.

Biasanya benar untuk mengatakan bahwa output dari fungsi hash adalah hash (juga dikenal sebagai nilai hash atau jumlah hash). Namun, kadang-kadang orang menyebut fungsi itu sendiri sebagai hash . Ini secara teknis salah, tetapi biasanya diabaikan karena secara umum dipahami (dalam konteks) bahwa orang itu berarti fungsi hash .

Penggunaan khas fungsi hash adalah mengimplementasikan tabel hash . Tabel hash adalah struktur data yang mengaitkan nilai dengan nilai lain yang biasanya disebut sebagai kunci. Itu melakukan ini dengan menggunakan fungsi hash pada kunci untuk menghasilkan nilai hash berukuran tetap yang dapat digunakan untuk pencarian cepat dari data yang disimpannya. Saya tidak akan masuk ke detail lengkap tentang bagaimana melakukan itu, tetapi fakta kunci di sini adalah bahwa itu disebut tabel hash karena bergantung pada fungsi hash untuk menghasilkan nilai hash (hashes).

Di sinilah beberapa kebingungan muncul, karena beberapa orang (sekali lagi, agak salah) menyebut tabel hash sebagai hash. Seperti yang dinyatakan dalam jawaban lain, kadang-kadang implementasi bahasa hash dari tabel hash merujuk ke tabel hash sebagai hash (terutama Perl melakukan ini, meskipun saya berharap bahasa lain juga melakukannya). Bahasa lain memilih untuk merujuk pada penerapan tabel hash sebagai kamus. Python adalah salah satu dari bahasa-bahasa ini, tetapi karena seberapa mendarah daging dalam bahasa mereka, banyak pengguna Python mempersingkat istilah kamus menjadi 'dict'.

Jadi sementara penggunaan yang tepat dari istilah hash adalah untuk merujuk pada nilai hash yang dihasilkan oleh fungsi hash , orang juga kadang-kadang menggunakan istilah secara informal untuk merujuk ke fungsi hash dan tabel hash , karenanya menciptakan kebingungan.

Fungsi hash secara luas fungsi apa pun di mana gambar lebih kecil dari domain . Output dari fungsi tersebut f(x)dapat disebut sebagai "hash of x".

Dalam ilmu komputer kita biasanya menemukan dua aplikasi fungsi hash.

Yang pertama adalah untuk struktur data seperti tabel hash , di mana kami ingin memetakan domain utama (misalnya bilangan bulat 32-bit atau string sewenang-wenang) ke indeks array (misalnya bilangan bulat antara 0 dan 100). Tujuannya di sini adalah untuk memaksimalkan kinerja struktur data; properti dari fungsi hash yang biasanya diinginkan adalah kesederhanaan dan distribusi keluaran yang seragam.

Perl menyebut array asosiatif bawaannya sebagai "hash" , yang tampaknya menjadi penyebab kebingungan Anda di sini. Saya tidak tahu bahasa lain yang melakukan ini. Secara longgar struktur data dapat dilihat sebagai fungsi hash itu sendiri (di mana domain adalah set kunci saat ini), tetapi juga diimplementasikan sebagai tabel hash.

Yang kedua adalah untuk kriptografi : otentikasi pesan, kata sandi / verifikasi tanda tangan, dll. Domain ini biasanya berupa string byte acak. Di sini kita peduli dengan keamanan - yang kadang-kadang berarti kinerja rendah sengaja - di mana properti yang berguna adalah tabrakan dan resistensi pra-gambar.

Pertanyaan bagus Basil Ajith,

Inilah perspektif saya tentang apa hash untuk sesuatu yang saya kerjakan hari ini.

*

Gunakan cek jumlah untuk memverifikasi bahwa tarball telah kongruen dengan halaman unduhan

*

Mengenakan topi auditor, maksudku jubah penyihir

hash adalah nilai / string / apa pun / label pastikan sama pada mesin Anda sebagai sumber unduhan.

Saya akan mencoba hanya menambahkan ringkasan singkat dari apa yang orang lain katakan.

Fungsi hash

Ada jenis fungsi khusus yang disebut fungsi hash.

"SHA256 adalah fungsi hash terkenal yang aman secara kriptografis"

Tiga aplikasi utama adalah * tabel hash, * checksum (pemeriksaan integritas data misalnya dalam hard drive atau protokol ADSL), * dan kriptografi (berbagai bentuk otentikasi kriptografi termasuk tetapi tidak terbatas pada tanda tangan digital dan penyimpanan kata sandi aman).

Meja hash

Tabel hash adalah struktur data untuk pencarian cepat. Menggunakan fungsi hash secara internal, maka namanya.

"Database menggunakan tabel hash dan pohon pencarian secara internal untuk mempercepat eksekusi permintaan pencarian"

Hash

1. tipe data abstrak kamus

"Hash" adalah nama resmi kamus internal di Perl. Mereka adalah tabel hash secara internal, maka namanya. "Subrutin ini menerima hash sebagai argumen pertama". Hari-hari ini dapat digunakan untuk berbagai array asosiatif, tidak harus berupa tabel hash.

2. hasil penerapan fungsi hash ke beberapa input

"Hash MD5 dari gambar .iso disediakan untuk memeriksa integritasnya setelah mengunduh".