【愚公系列】2021年11月 C#版 資料結構與算法解析(哈希查找)

哈希查找的實際目的其實非常簡單,就是利用空間換時間.

哈希技術是在記錄的存儲位置和記錄的關鍵字之間建立一個确定的對應關系f，使得每個關鍵字key對應一個存儲位置f(key)。查找時，根據這個确定的對應關系找到給定值的映射f(key),若查找集合中存在這個記錄，則必定在f(key)的位置上。哈希技術既是一種存儲方法，也是一種查找方法。

示例：

namespace HashSearch.CSharp

{

   class Program

   {

       //初始化哈希表

       static int hashLength = 7;

       static int[] hashTable= new int[hashLength];

       //原始資料

       static List<int> list = new List<int>() { 13,29,27,28,26,30,38 };

       static void Main(string[] args)

       {

           Console.WriteLine("********************哈希查找(C#版)********************\n");

           //建立哈希表

           for (int i = 0; i < list.Count; i++)

           {

               Insert(hashTable,list[i]);

           }

           Console.WriteLine("展示哈希表中的資料：{0}",String.Join(",",hashTable));

           while (true)

               //哈希表查找

               Console.Write("請輸入要查找的資料:");

               int data = int.Parse(Console.ReadLine());

               var result = Search(hashTable, data);

               if (result == -1) Console.WriteLine("對不起，沒有找到!");

               else Console.WriteLine("資料的位置是：{0}", result);

       }

       /// <summary>

       /// 哈希表插入

       /// </summary>

       /// <param name="hashTable">哈希表</param>

       /// <param name="data">待插入值</param>

       public static void Insert(int[] hashTable, int data)

       {  

           //哈希函數,除留餘數法

           int hashAddress = Hash(hashTable,data);

           //如果不為0，則說明發生沖突

           while (hashTable[hashAddress] != 0)

               //利用開放定址的線性探測法解決沖突

               hashAddress = (++hashAddress) % hashTable.Length;

           //将待插入值存入字典中

           hashTable[hashAddress] = data;

       /// 哈希表查找

       /// <param name="data">待查找的值</param>

       /// <returns></returns>

       public static int Search(int[] hashTable, int data)

           //沖突發生

           while (hashTable[hashAddress] != data)

               //查找到了開放單元或者循環回到原點，表示查找失敗

               if (hashTable[hashAddress] == 0 || hashAddress==Hash(hashTable,data)) return -1;

           //查找成功,傳回值的下标

           return hashAddress;

       /// 哈希函數(除留餘數法)

       /// <param name="hashTable">待操作哈希表</param>

       /// <param name="data"></param>

       /// <returns>傳回資料的位置</returns>

       public static int Hash(int[] hashTable, int data)

           return data % hashTable.Length;

   }

}