Mengapa std :: hash tidak dijamin deterministik?

28

Selanjutnya, kami menggunakan N4140 (Standar C ++ 14).

Menurut § 17.6.3.4 Persyaratan hash ,

Nilai yang dikembalikan hanya akan bergantung pada argumen k selama durasi program .

[Catatan: Demikian semua evaluasi ekspresi h(k)dengan nilai yang sama untuk kmenghasilkan hasil yang sama untuk eksekusi program yang diberikan . - catatan akhir]

dan § 20.9.12 Kelas Template hash mengatakan

...

Instansiasi hash<Key>akan:

(1.1) - memenuhi persyaratan Hash (17.6.3.4) ...

(1.2) - ...

Ini berarti nilai hash value(yaitu hash<decltype(value)>(value)) dapat mengambil nilai yang berbeda jika Anda me-restart program.

Tapi kenapa? Batasan ini bukan dalam Standar C ++ 11, tetapi dalam Standar C ++ 14, C ++ 17 dan C ++ 20. Sebagai pengguna (bukan pengembang STL), akan sangat berguna jika std::hashbersifat deterministik. Apakah ada kesulitan matematika dalam mengimplementasikan fungsi hash deterministik? Tetapi fungsi hash yang kita gunakan sehari-hari (mis. Usang md5sumatau lebih aman sha256) semuanya deterministik. Apakah ada masalah efisiensi?

c++ hash language-lawyer std ynn
sumber
7
"... Fungsi hash hanya diperlukan untuk menghasilkan hasil yang sama untuk input yang sama dalam satu eksekusi program; ini memungkinkan hash asin yang mencegah serangan tabrakan denial-of-service ." sumber: en.cppreference.com/w/cpp/utility/hash
Richard Critten
5
Ini memungkinkan algoritma deterministik untuk mengambil input non-deterministik. Nilai pointer, misalnya. Struktur data yang tidak berubah dapat mengaitkan alamat data internal, yang bisa menjadi jauh lebih cepat daripada hashing isinya.
John Kugelman
4
Jawaban ini memiliki beberapa tautan bagus mengapa Anda tidak ingin determinisme.
NathanOliver
3
Jangan mengancam ini sebagai batasan, tetapi membuat batasan standar sedikit kurang ketat.
Marek R
4
Berikut adalah penjelasan lengkap mengapa kendala telah dilonggarkan.
Marek R

Jawaban:

17

Tidak perlu fungsi hash untuk menjadi deterministik antara run, tetapi Anda masih dapat memberikan hash Anda sendiri, misalnya untuk wadah yang tidak berurutan jika itu adalah perilaku yang Anda andalkan.

Adapun alasannya, cppreference mengatakan:

Fungsi hash hanya diperlukan untuk menghasilkan hasil yang sama untuk input yang sama dalam satu eksekusi program; ini memungkinkan hash asin yang mencegah tabrakan serangan penolakan layanan.

Jika Hash persyaratan mengatakan itu deterministik, maka Anda tidak akan dapat memberikan hash asin tanpa melanggar persyaratan.

Inilah penjelasan sebenarnya mengapa

Geoffroy
sumber
7

Jawaban ini (dan tautan di dalamnya) yang disarankan oleh @NathanOliver pada akhirnya sangat membantu. Biarkan saya mengutip bagian-bagian penting.

Untuk fungsi hash non-kriptografi, dimungkinkan untuk melakukan pra-kalkulasi input masif dengan nilai hash yang sama untuk secara algoritmik memperlambat wadah yang tidak berurutan, dan menghasilkan serangan denial-of-service.

(dari Edisi 2291. std :: hash rentan terhadap serangan tabrakan DoS )

Karena alasan ini, perancang bahasa bermigrasi ke hashing acak. Dalam hashing acak, nilai hash dari string "a" dapat berubah setiap kali Anda menjalankan program Anda. Hash acak sekarang menjadi default dalam Python (pada versi 3.3), Ruby (pada versi 1.9) dan Perl (pada versi 5.18).

(dari Apakah Anda menyadari bahwa Anda menggunakan hashing acak? )

Pindah ke Siap, bukan Segera, karena bahkan izin telah diperdebatkan dalam diskusi reflektor

(dari Edisi 2291. std :: hash rentan terhadap serangan tabrakan DoS )

Dalam prakteknya, sejauh yang saya mengerti, tidak ada implementasi std::hashimplementasi hashing acak tetapi Anda dapat menulis sendiri my::secure_hash.

(dari jawaban ini )

PS

Saya baru saja googled "dos tabel hash" dan menemukan halaman informatif: Saat ketika Anda menyadari setiap server di dunia rentan .

ynn
sumber