Fahami algoritma Hash dan senario aplikasi dalam satu artikel

1. Apakah algoritma hash

Kedua-dua cincang dan cincang berasal daripada perkataan cincang, yang pertama ialah transliterasi dan yang kedua ialah terjemahan percuma. Ia adalah algoritma yang boleh memetakan nilai perduaan sebarang panjang ke dalam nilai perduaan panjang tetap Nilai perduaan panjang tetap dipetakan dipanggil nilai cincang. Algoritma cincang yang sangat baik perlu memenuhi keperluan berikut:

tidak boleh menyimpulkan secara terbalik data asal daripada nilai cincang;

sangat sensitif kepada data input dan bit yang berbeza akan menyebabkan pencincangan. Nilai cincang sangat berbeza;

Kebarangkalian perlanggaran cincang mestilah sangat kecil;

Proses pengiraan algoritma cincang mestilah cukup mudah dan cekap, walaupun data asal adalah sangat panjang, cincang boleh diperoleh dengan cepat Nilai cincang;

2. Senario penggunaan algoritma cincang

2.1 Penyulitan selamat

Algoritma penyulitan cincang yang lebih biasa ialah MD5 ( Algoritma Message-Digest MD5, algoritma Digest mesej MD5) dan SHA (Algoritma Hash Selamat, algoritma cincang selamat).

Kata laluan teks biasa tidak boleh disimpulkan daripada teks sifir nilai cincang, dan kebarangkalian konflik cincang adalah agak kecil. Kedua-dua titik ini memastikan kebolehpercayaan algoritma cincang sebagai kaedah penyulitan yang selamat.

Mengapakah algoritma pencincangan tidak dapat mengelakkan perlanggaran cincang sepenuhnya, tetapi hanya boleh meminimumkannya?

Prinsip sarang merpati memberitahu kita bahawa jika 11 merpati terbang ke dalam 10 sangkar merpati, maka mesti ada 2 atau lebih merpati dalam satu sangkar merpati. Kemudian nilai cincang adalah panjang tetap, yang menentukan bahawa nilai cincang boleh habis, tetapi secara teorinya data asal adalah tidak terhingga, jadi mungkin menyebabkan konflik cincang.

Senario aplikasi ini menggunakan ciri 1 dan 3 algoritma cincang, di mana 3 daripadanya memastikan kata laluan sangat sukar untuk dipecahkan ke arah hadapan (mengambil MD5 sebagai contoh, panjang nilai cincang ialah 128 bit , dan terdapat 2 ^128 cincang berbeza, sangat sukar untuk dipecahkan).

Tiada keselamatan mutlak dalam medan keselamatan Walaupun MD5 sukar dipecahkan, masih ada cara untuk memecahkannya Contohnya, menggunakan padanan jadual pelangi boleh memecahkan kata laluan biasa.

Jadi secara amnya kami akan menggunakan algoritma cincang masin untuk penyulitan selamat Kaedah pengasinan perlu dirahsiakan, yang meningkatkan kesukaran dan kos retak.

2.2 Bendera unik

Apabila kami mengesahkan sama ada dua fail adalah sama, kami tidak boleh menilai berdasarkan nama fail sahaja. Kerana kewujudan fail dengan nama yang sama adalah terlalu biasa.

Kami boleh mengambil beberapa data perduaan daripada fail besar mengikut peraturan tertentu dan menggunakan algoritma cincang untuk mendapatkan nilai cincang sebagai pengecam unik fail. Dengan cara ini, fail yang sama mesti mempunyai nilai cincang yang sama, iaitu, pengecam unik yang sama mempunyai kebarangkalian tinggi untuk mempunyai pengecam unik yang berbeza dengan nilai cincang yang berbeza; nilai hash Jika terdapat konflik lajur, kita boleh membandingkan semua data binari kedua-dua fail secara terperinci untuk menentukan sama ada ia adalah fail yang sama Kebarangkalian peristiwa ini berlaku adalah terlalu kecil. Walau bagaimanapun, penyelesaian ini memastikan kecekapan dan kebolehpercayaan.

Senario aplikasi ini menggunakan ciri 2 dan 3 algoritma cincang.

2.3 Pengesahan Data

Dalam protokol muat turun P2P, kami akan memuat turun bahagian berlainan filem yang sama daripada mesin yang berbeza, dan kemudian memasang filem itu pada mesin kami sendiri. Jika terdapat ralat dalam proses memuat turun sesetengah bahagian filem atau kandungan diganggu, ia boleh menyebabkan ralat memuat turun atau virus.

Oleh itu, kami terlebih dahulu mencincang semua bahagian dan menyimpannya dalam fail benih. Selepas semua bahagian dimuat turun, kami mencincang semua bahagian untuk mendapatkan nilai cincang, dan kemudian membandingkannya dengan bahagian dalam fail benih untuk mengesahkan sama ada fail itu lengkap.

Senario aplikasi ini menggunakan ciri 2 dan 4 algoritma cincang.

2.4 Fungsi cincang

Senario ini telah diperkenalkan sebelum ini apabila kita bercakap tentang jadual cincang. Dalam senario ini, keperluan untuk Ciri 1 tidak terlalu tinggi Keperluan untuk Ciri 2 ialah nilai cincang hendaklah diedarkan sekata yang mungkin juga boleh menerima konflik pada tahap tertentu, yang boleh diselesaikan dengan menggunakan kaedah pengalamatan terbuka dan kaedah zipper Ciri 4 lebih menuntut dan perlu mengejar prestasi.

2.5 Pengimbangan Beban

Terdapat banyak algoritma pengimbangan beban, seperti pengundian, rawak, undian berwajaran, dll., tetapi matlamatnya adalah untuk melaksanakan algoritma pengimbangan beban melekit sesi, iaitu, yang sama Semua permintaan klien semasa sesi dihalakan ke pelayan yang sama.

Kami boleh mencincang IP atau ID sesi pelanggan, dan melakukan operasi modulo pada nilai cincang dan bilangan pelayan Nilai akhir ialah pelayan yang memerlukan penghalaan, supaya kemelekatan sesi dapat dicapai daripada genangan.

2.6 Perkongsian Data

Apabila kita perlu memproses data besar-besaran, pelayan tunggal tidak boleh memuatkan dan mengira data besar-besaran tersebut, maka kita perlu mengagihkan data besar-besaran secara sama rata kepada pelayan N Pelayan melakukan selari pengkomputeran. Bagaimana untuk mengagihkan data secara sama rata ke pelayan N?

Kami melakukan pengiraan cincang pada data, dan menggunakan modulo nilai cincang yang diperoleh bilangan pelayan N. Data dengan keputusan yang sama akan diberikan kepada pelayan yang sama dan diserahkan kepada pelayan ini untuk diproses. N pelayan memproses data besar secara selari, dan akhirnya menggabungkan hasilnya.

2.7 Storan Teragih

Simpan data besar-besaran dalam cache teragih atau pangkalan data teragih Idea meminjam adalah serupa dengan pecahan data di atas. Walau bagaimanapun, apakah yang perlu dilakukan apabila bilangan pelayan yang ditetapkan asal tidak mencukupi?

Ia tidak boleh diselesaikan dengan hanya menambah beberapa mesin Ini akan memusnahkan operasi modulo nilai cincang, membawa kepada penembusan cache dan menyebabkan kesan longsor. Begitu juga, masalah yang sama boleh berlaku apabila kerosakan mesin dialihkan. Pada masa ini, kita perlu menggunakan algoritma pencincangan yang konsisten untuk menyelesaikan masalah ini.

Algoritma cincang yang konsisten hanyalah untuk membina cincin cincang dengan 2^32 nod pada cincin itu dan cincang IP pelayan dan fail ke nod yang sepadan. Pelayan pertama yang semua fail hadapi mengikut arah jam ialah pelayan tempat ia disimpan. Dengan cara ini, apabila pelayan ditambah atau dipadamkan, bilangan fail yang terjejas boleh dikawal dan tidak akan menyebabkan longsor global.

gelang cincang

Walau bagaimanapun, dengan kebarangkalian tertentu, apabila IP pelayan dipetakan ke cincin cincang, masalah pencongan cincin cincang akan berlaku. Ini akan membawa kepada pengedaran fail yang sangat tidak sekata pada pelayan, merosot kepada senario di mana kesan longsoran mudah disebabkan apabila menambah atau memadam pelayan pada mulanya.

Kecondongan gelang cincang

Kami boleh menambah secara buatan beberapa nod maya pada pelayan ini supaya semua nod pelayan diagihkan sama rata pada cincang cincin.

Gelang cincang dengan nod maya

3 Ringkasan

Senario penggunaan algoritma Hash jauh lebih banyak daripada di atas, terdapat juga seperti semakan CRC.

Atas ialah kandungan terperinci Fahami algoritma Hash dan senario aplikasi dalam satu artikel. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!