引言：

作為資深老鳥，有事沒事，出去面試；找準差距、定位價值。

面試必談哈希，

Q1：什么是哈希?

Q2：哈希為什么快?

Q3：你是怎么理解哈希算法利用空間換取時間的？

Q4：你是怎么解決哈希沖突的？

Q5：你有實際用寫過哈希算法嗎？

1. 知識儲備

　　哈希（也叫散列）是一種查找算法（可用于插入），哈希算法希望能做到不經過任何比較（發生沖突，還是需要少許比較），通過一次存取就能得到查找的數據。

因此哈希的關鍵在key和數據元素的存儲位置之間建立一個確定的對應關系，每個key在哈希表中都有唯一的地址相對應（形成有限、連續的地址空間），查找時根據對應關系經過一步計算得到key在散列表的位置。

在數學上， 原Key叫做原像，由映射函數h(key)映射的存儲位置叫做像；在IT領域，以上存儲位置叫哈希地址（散列地址），這個映射過程叫做哈希/散列。

故我們可以預見：

　　① 不同的key值，由哈希函數h(x) 作用后可能映射到同一個哈希地址， 這就是哈希沖突，沖突發生的概率取決于 定義的哈希函數

　　② 由哈希表作用后的哈希地址需要空間存儲，這一系列連續相鄰的地址空間叫哈希表、 散列表。?

　　處理哈希沖突可分為兩大類：

　　（1）開散列法發生沖突的元素存儲于數組空間之外。可以把“開”字理解為需要另外“開辟”空間存儲發生沖突的元素， 又稱【鏈地址法】

　　（2）閉散列法發生沖突的元素存儲于數組空間之內。可以把“閉”字理解為所有元素，不管是否有沖突，都“關閉”于數組之中，閉散列法又稱【開放定址法】，意指數組空間對所有元素，不管是否沖突都是開放的

?　　哈希表是用數組實現的一片連續的地址空間，兩種沖突解決方案的區別在于發生沖突的元素是存儲在這片數組的空間之外還是空間之內

2. 看圖說話

---以下是開散列法（鏈地址法）解決沖突的示意圖------

　　從圖上看實現【哈希】過程分兩部分：

① 哈希函數

　　收斂函數，不可避免會沖突，需要思考設定一個均衡的哈希函數，使哈希地址盡可能均勻地分布在哈希地址空間

②? 構造哈希表 + 沖突鏈表

　　裝填因子loadfactor ：所謂裝填因子是指哈希表中已存入的記錄數n與哈希地址空間大小m的比值，即 α=n / m ，α越小，沖突發生的可能性就越小；α越大（最大可取1），沖突發生的可能性就越大。

　　另一方面，α越小，存儲窨的利用率就越低；反之，存儲窨的利用率就越高。為了既兼顧減少沖突的發生，又兼顧提高存儲空間的利用率，通常把α控制在0.6～0.9的范圍之內

哈希在.Net中的應用

　　Object基類中有GetHashCode方法，HashCode是一個數字值，用于在【基于哈希特性的集合】中插入和查找某對象；GetHashCode方法為需要快速檢查對象相等性的算法提供此哈希代碼；

　　Do not test for equality of hash codes to determine whether two objects are equal. (Unequal objects can have identical hash codes.) To test for equality, call the?ReferenceEquals?or?Equals?method.??（重要的話要讀3遍）

單純判斷【邏輯相等】時，本無所謂重寫 GetHashCode方法；但若在基于hash的集合中快速查找/插入某元素，則一定要重寫GetHashCode方法。

? 我們看一個實錘：

　　統計參加Footabll,Basketball 兩個球隊的所有成員，自然會想到對?footabllTeam,?basketballTeam 成員使用Union方法求并集 （A∪B）

　　觀察Union源碼計算A,B并集的實現，內部會構造哈希表Set<TElement>?快速查找和插入并集元素，故我們需要給元素編寫合適的哈希函數。

public static IEnumerable<TSource> Union<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)

{

? ? if (first == null) throw Error.ArgumentNull("first");

? ? if (second == null) throw Error.ArgumentNull("second");

? ? ? ? return UnionIterator<TSource>(first, second, comparer);

}

static IEnumerable<TSource> UnionIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)

{

? ? ? Set<TSource> set = new Set<TSource>(comparer);

? ? ? foreach (TSource element in first)

? ? ? ? ? if (set.Add(element)) yield return element;? ? ? //? Set 便是Union方法內部構造的哈希表

? ? ? foreach (TSource element in second)

? ? ? ? ? ?if (set.Add(element)) yield return element;

}

Union方法入口

?

高潮來了，不是總說沒處理過哈希沖突嗎？結

合

【知識儲備】

圍觀鏈地址法處理哈希沖突：

因此有最佳實踐: 當兩對象重寫Equal方法返回true時， 請務必重寫GetHashCode方法為對象返回相同的hashcode。

話雖如此，寫一個合適、均衡的哈希函數還是比較考驗算法的。

在一般場景中，經驗會幫助你編寫哈希函數， 比如以上Person類中，字符串類型Name的HashCode總是相等的。

That‘all ??看完了通篇文章的同棧猿，應該就可以回答文章引言 5大提問。

總結

以上是生活随笔為你收集整理的面试必谈的哈希，.Net 程序员温故而知新的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。