DSex3講解 - HackMD

# DSex3講解 ## 第二組 --- 1. 資料處理 2. Quadratic hash 3. Double hash 4. 質數判斷 5. SHA-256 --- # 資料處理 ---- ### 大家的讀寫二進位檔 ### 應該多少有參考老師的吧 ![](https://hackmd.io/_uploads/Byvn0HHNn.png) ---- ## std::fstream::open ```cpp void open(const char* filename,int mode,int access); ios::app：　　　以追加的方式打開文件，無法改變原本內容 ios::ate：　　　文件打開後定位到文件尾。 ios::binary：　以二進制方式打開文件。 ios::in：　　　文件以輸入方式打開 ios::out：　　　文件以輸出方式打開 ``` 我們可以透過$\color{red} |$來去增加我們需要的功能  ---- ### 所以我們可以寫成這樣 ```cpp ofstream Write(filename, std::ios::out | std::ios::binary); ``` ---- ## std::istream::read & std::ostream::write ```cpp [1-2|3-4] istream& read (char* s, streamsize n); Read.read((char*)&student, sizeof(student)); ostream& write (const char* s, streamsize n); Write.write((char*)&student, sizeof(student)); ``` --- # Quadratic hash ---- ### 學號的ASCII相乘 ```cpp int Get_index(int index){ unsigned long long index = 1; int i = 0; while(student_list[index].id[i] != '\0'){ index *= (unsigned long long)student_list[index].id[i]; i++; } index %= (unsigned long long) table_size; return index; } ``` ---- ### 或是可以這樣寫 #### $(a*b)\ \% \ c=[(a \% c) * (b \% c)] \% c$ ```cpp int Get_index(int index){ int index = 1; int i = 0; while(student_list[index].id[i] != '\0'){ index *= (int)student_list[index].id[i] % table_size; index %= table_size; i++; } return index; } ``` ---- ### 主要演算法 避免無窮的條件 ```cpp [1-12|5,7,8] for(int i = 0 ; i < student_list.size() ; i++){ int index = Get_index(i); int step = 0, cycle = 0; int prev_index = index; while(cycle < 10 && \ get<0>(hash_table[(index+step*step)%hash_size])!=-1){ if(prev_index > (index + step*step) % hash_size) cycle++; prev_index = (index + step*step) % hash_size; step++; } } ``` ---- ### 計算Successful search ```cpp if(get<1>(hash_table[(index + step*step) % hash_size]) == -1){ hash_table[(index+step*step)%hash_size]=make_tuple(index, i); successful_collisions+=(step+1); successful_save++; } else{ trash_can.push_back(std::make_tuple(index, i)); } ``` ---- ### 計算Unsuccessful search ```cpp for(int i = 0 ;i < hash_size ; i++){ int step = 0; int cycle = 0; int prev_index = i; while(cycle < 10 && \ get<0>(hash_table[(i + step*step) % hash_size]) != -1){ if(prev_index > (i + step*step) % hash_size) cycle++; prev_index = (i + step*step) % hash_size; unsuccessful_collisions++; step++; } } ``` --- # Double hash ---- ### 主要演算法 ```cpp for(int i = 0 ; i < student_list.size() ; i++){ int key = Get_stored_index(i); if(std::get<0>(hash_table[key]) != -1){ int step = Second_hash(i); int collision = 1; while(get<0>(hash_table[(key+step*collision)%hash_size])!=-1){ collision++; } hash_table[(key+step*collision)%hash_size]=make_tuple(key, i); successful_collisions+=(collision+1); } else{ hash_table[key] = std::make_tuple(key, i); successful_collisions++; } successful_save++; } ``` --- # 質數判斷 ---- ### 大部分的人應該都是這樣寫 ```cpp bool Prime_test(int num){ if(num < 2 || num % 2 == 0 ) return false; for(int i = 3 ; i < sqrt(num) ; i+=2 ){ if(num % i == 0 ) return false; } return true; } ``` $但是複雜度為O(n*log(log(n)))$ ---- ### Miller rabin ```cpp inline bool Miller_Rabin(int x){ int i, j, k; int s = 0, t = x - 1; if(x == 2) return true; if(x < 2 || !(x & 1)) return false; while(!(t & 1)){ s++; t >>= 1; } for(i = 0; i < 10 && prime[i] < x; ++i){ int a = prime[i]; int b = Quick_Power(a, t, x); for(j = 1; j <= s; ++j){ k = Quick_Multiply(b, b, x); if(k == 1 && b != 1 && b != x - 1) return false; b = k; } if(b != 1) return false; } return true; } ``` $複雜度為O(k*log^3n)\ k為檢驗次數$ ---- ![](https://hackmd.io/_uploads/S19ujb8N2.png) --- # SHA-256 ---- 1. SHA-256是什麼？ 2. SHA-256如何運作？ 3. SHA-256和其他hash function有什麼不同之處？ ---- #### SHA-256運算的過程中，主要包含以下四個步驟： ##### 1.初始化：SHA-256會先設定一個初始值（IV），並將該值作為運算的起點。 ##### 2.訊息擴展：將每個數據塊（512位元）進一步擴展成更大的數據塊（64個512位元），以增加訊息的隨機性和不可預測性。 ##### 3.壓縮：將擴展後的數據塊與上一次壓縮後的數值進行運算，得到新的數值。 ##### 4.輸出：當SHA-256運算完所有數據塊後，即可得到最終的256位元數值，即為SHA-256的訊息摘要。 ---- <style> .text-center{ text-align: center; //文字置中 } </style> ### $\color{yellow} {BlockChain}$ 以上這句話透過SHA-256得到的hash value為 #### $\color{yellow} {3a6fed5fc11392b3ee9f81caf017b48640d}$ #### $\color{yellow} {7458766a8eb0382899a605b41f2b9}$ --- # 謝謝大家