雜湊法(Hashing)
- 在雜湊法的搜尋中，鍵值(key value)或識別字(identifier)在記憶體的存放位址，是經由雜湊函數(hashing function) 轉換而得。
- 常見的雜湊函數：
- 平方後取中間值法(mid-square)：先將鍵值平方，然後取中間的幾位數當做其儲存位址或索引值。 如有一鍵值是510324，其平方為260430584976，可以取中間的058為其儲存位址。
- 餘數法(modulo-division)：將鍵值除以某個數值並取餘數，如F(x)= x % m，則餘數必定介於0~m-1之間，既是該鍵值所對應的位址。較常用。
- 數位分析法(digit analysis)：檢查所有鍵值的所有位數，剔除掉分佈不均勻的位數，所剩的位數組合成索引值或儲存位址。 適合大量的靜態資料。
|
沒有留言:
張貼留言