申論題

建立雜湊表格：

使用除法雜湊函數 ℎ(?)=?mod  7h(k)=kmod7 並應用線性探測法來處理碰撞問題，將鍵值依序插入雜湊表：

• 鍵值：32, 17, 85, 16, 51, 60
• 雜湊函數：ℎ(?)=?mod  7h(k)=kmod7
• 桶數：7（編號0到6）

插入過程：

1. 32：

   • ℎ(32)=32mod  7=4h(32)=32mod7=4
   • 插入位置4：_,_,_,_,32,_,__,_,_,_,32,_,_

2. 17：

   • ℎ(17)=17mod  7=3h(17)=17mod7=3
   • 插入位置3：_,_,_,17,32,_,__,_,_,17,32,_,_

3. 85：

   • ℎ(85)=85mod  7=1h(85)=85mod7=1
   • 插入位置1：_,85,_,17,32,_,__,85,_,17,32,_,_

4. 16：

   • ℎ(16)=16mod  7=2h(16)=16mod7=2
   • 插入位置2：_,85,16,17,32,_,__,85,16,17,32,_,_

5. 51：

   • ℎ(51)=51mod  7=2h(51)=51mod7=2
   • 位置2已被佔用，使用線性探測法：
     • 檢查位置3（已佔用）
     • 檢查位置4（已佔用）
     • 檢查位置5（空）
   • 插入位置5：_,85,16,17,32,51,__,85,16,17,32,51,_

6. 60：

   • ℎ(60)=60mod  7=4h(60)=60mod7=4
   • 位置4已被佔用，使用線性探測法：
     • 檢查位置5（已佔用）
     • 檢查位置6（空）
   • 插入位置6：_,85,16,17,32,51,60_,85,16,17,32,51,60

最終雜湊表格：

_,85,16,17,32,51,60_,85,16,17,32,51,60

線性探測法的主要缺點：

1. 初始碰撞後的聚集：當多個鍵值發生碰撞並分配到相鄰的槽中時，會導致聚集效應（clustering），使得新的插入和查找操作的效率下降。
2. 槽利用率低：當雜湊表接近滿時，線性探測法的效能會顯著降低，因為需要檢查的槽數量增多，影響插入和查找的效率。