搜尋Searching和雜湊Hashing

搜尋

搜尋空間，通常指一系列狀態的匯集，因此也稱為狀態空間

搜尋策略

• 寬度優先搜尋演算法是沿著樹的寬度遍歷樹的節點，如果發現目標，則演算法中止。屬於盲目搜尋。
• 深度優先搜尋沿著樹的最大深度方向生成節點並與目標節點進行比較。
• 模擬退火演算法
• A*搜尋演算法

雜湊

雜湊函式是一種從任何一種資料中建立小的數字「指紋」的方法。雜湊函式把訊息或資料壓縮成摘要，使得資料量變小，將資料的格式固定下來。該函式將資料打亂混合，重新建立一個叫做雜湊值（hash values，hash codes，hash sums，或hashes）的指紋。雜湊值通常用一個短的隨機字母和數字組成的字串來代表。好的雜湊函式在輸入域中很少出現雜湊衝突。在雜湊表和資料處理中，不抑制衝突來區別資料，會使得資料庫記錄更難找到。

簡單雜湊函式

• Simple Mod Function
• Binning
• The Mid-Square Method

  //Mod Function
  int h(int x) {
  return x % 16;
  }
  

  Bucket Hashing

  

Collision Resolution

• Linear Probing by Steps
• Pseudo-Random Probing
• Quadratic Probing
• Double Hashing