計算機概論、大意(資訊科學概論,電腦常識,電子計算機概論)題庫下載題庫

雜湊搜尋法所使用的數學函數就稱為雜湊函數 ( Hashing Function )。而在尚未介紹雜湊函數之前，先介紹有關雜湊函數的相關名詞：
1.桶 ( Bucket )
　是指在雜湊表中儲存資料的位置，每個位置被給定一個唯一的位址，稱之為 Bucket Address 。
2.槽 ( Slot )
　每一個桶可能有好幾個儲存區，此儲存區便稱之為槽 ( Slot ) 。每一個槽可以容納一個記錄。
3.碰撞 ( Collision )
　當兩個不同的識別字經過雜湊函數運算後，放到相同的桶位址，稱之為碰撞。
4.溢位 ( Overflow )
　如果一個識別字經過雜湊函數運算後，所對應的桶已經滿了，就稱之為溢位。

 
一般常見的雜湊函數有下列幾種方法：

1. 中間平方法 ( Mid - square )
此法是將鍵值平方後，取出中間某些位元來當作資料儲存的位址。例如我們可以利用中間平方法將英文字的「ABC」轉換為雜湊表中的位置。

2. 折疊法 ( Folding )
此法是將鍵值分為數段，除了最後一段外，其餘各段皆須等長，然後將每一段相加，即可得到其所對應的位址。在相加的時候，有兩種方式：
(1) 位移折疊 ( Shift Folding )
將各段資料直接相加。
(2) 邊界折疊 ( Folding at the boundaries )
將奇數位段或偶數位段反轉後相加。

3. 除法 ( Division )
此法利用Mod運算，將識別字 X 除以某一個數值 M ，取其餘數當做 X 的位址。這個位址介於 0 ~ M-1 之間。而在使用除法時，一般建議利用質數會有較佳的效果。
即 H( X ) = X mod M

4. 數字分析法 ( Digit Analysis )
數字分析法有二種：
(1) 觀察數字分析法：利用觀察法，將Key分佈不平均的數字刪除，其餘保留為Hash位址。
(2)統計數字分析法：利用統計方法分析鍵值各位數的分析情形，求出Hash位址。