面試必談的哈希，.Net 程式設計師溫故而知新
- 2019 年 10 月 3 日
- 筆記
引言問題
作為資深老鳥，有事沒事，出去面試；找准差距、定位價值。
面試必談哈希，
Q1：什麼是哈希?
Q2：哈希為什麼快?
Q3：你是怎麼理解哈希演算法利用空間換取時間的？
Q4：你是怎麼解決哈希衝突的？
Q5：你有實際用寫過哈希演算法嗎？
知識儲備
哈希（也叫散列）是一種查找演算法（可用於插入），哈希演算法希望能做到不經過任何比較（發生衝突，還是需要少許比較），通過一次存取就能得到查找的數據。
因此哈希的關鍵在key和數據元素的存儲位置之間建立一個確定的對應關係，每個key在哈希表中都有唯一的地址相對應（形成有限、連續的地址空間），查找時根據對應關係經過一步計算得到key在散列表的位置。
在數學上， 原Key叫做原像，由映射函數h(key)映射的存儲位置叫做像；在IT領域，以上存儲位置叫哈希地址（散列地址），這個映射過程叫做哈希/散列。
故我們可以預見：
① 不同的key值，由哈希函數h(x) 作用後可能映射到同一個哈希地址， 這就是哈希衝突，衝突發生的概率取決於 定義的哈希函數
② 由哈希表作用後的哈希地址需要空間存儲，這一系列連續相鄰的地址空間叫哈希表、 散列表。
處理哈希衝突可分為兩大類：
（1）開散列法發生衝突的元素存儲於數組空間之外。可以把“開”字理解為需要另外“開闢”空間存儲發生衝突的元素， 又稱【鏈地址法】
（2）閉散列法發生衝突的元素存儲於數組空間之內。可以把“閉”字理解為所有元素，不管是否有衝突，都“關閉”於數組之中，閉散列法又稱【開放定址法】，意指數組空間對所有元素，不管是否衝突都是開放的
2. 看圖說話
從圖上看實現【哈希】過程分兩部分：
① 哈希函數
收斂函數，不可避免會衝突，需要思考設定一個均衡的哈希函數，使哈希地址儘可能均勻地分布在哈希地址空間
② 構造哈希表 + 衝突鏈表
裝填因子loadfactor ：所謂裝填因子是指哈希表中已存入的記錄數n與哈希地址空間大小m的比值，即 α=n / m ，α越小，衝突發生的可能性就越小；α越大（最大可取1），衝突發生的可能性就越大；另一方面，α越小，存儲窨的利用率就越低；反之，存儲窨的利用率就越高。
為了既兼顧減少衝突的發生，又兼顧提高存儲空間的利用率，通常把α控制在0.6～0.9的範圍之內
哈希在.Net中的應用
GetHashCode方法
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）
using System; using System.Threading; using System.Threading.Tasks; using System.Net.Http; using System.Collections.Generic; using System.Linq; using System.Collections; namespace Test { public class Person { public string Name { get; set; } public int Age { get; set; } // 單純判斷邏輯相等，只需重寫Equals方法 public override bool Equals(object obj) { return Name == (obj as Person).Name; } public override int GetHashCode() { return Name.GetHashCode(); } } /// <summary> /// 體育小組成員 /// </summary> public class TeamMember { public Person Member { get; set; } public string Sport { get; set; } = "footabll"; } public class Program { static void Main() { var Beckham = new Person { Name = "Beckham", Age = 21 }; var Kobe = new Person { Name = "Kobe", Age = 21 }; var footabllTeam = new List<TeamMember> { new TeamMember { Member = new Person { Name = "nash", Age=21 } }, new TeamMember { Member = Beckham } }; var basketballTeam = new List<TeamMember> { new TeamMember { Member = new Person { Name = "nash", Age=21 },Sport="basketball" }, new TeamMember { Member = Kobe,Sport = "basketball" } }; // “==”操作符：判斷引用相等 Console.WriteLine($"足球隊[0]和籃球隊[0]是不同引用對象，footabllTeam[0].Member == basketballTeam[0].Member輸出：{footabllTeam[0].Member == basketballTeam[0].Member}"); // 對兩個記憶體對象，判斷邏輯相等 Console.WriteLine($"足球隊[0]和籃球隊[0]邏輯上是一個人,footabllTeam[0].Member.Equals(basketballTeam[0].Member輸出：{footabllTeam[0].Member.Equals(basketballTeam[0].Member )}"); // 統計兩個球隊中所有隊員, hash-base查找/插入，務必重寫GetHashCode方法 var members = footabllTeam.Select(x=>x.Member).Union(basketballTeam.Select(x=>x.Member)); Console.WriteLine($"總成員人數：{members.Count()} "); Console.Read(); } } }
------------------------output----------------------------------------
足球隊[0]和籃球隊[0]是不同引用對象，footabllTeam[0].Member == basketballTeam[0].Member輸出：False
足球隊[0]和籃球隊[0]邏輯上是一個人,footabllTeam[0].Member.Equals(basketballTeam[0].Member輸出：True
總成員人數：3
觀察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方法入口
高潮來了，不是總說沒處理過哈希衝突嗎？看下文。
鏈地址法哈希表
internal class Set<TElement> { int[] buckets; // 連續相鄰的地址空間，盛放不同衝突鏈表的容器，俗稱哈希桶 Slot[] slots; // 用於解決衝突的鏈表 int count; int freeList; IEqualityComparer<TElement> comparer; public Set() : this(null) { } public Set(IEqualityComparer<TElement> comparer) { if (comparer == null) comparer = EqualityComparer<TElement>.Default; this.comparer = comparer; buckets = new int[7]; // 初始哈希桶和衝突鏈表長度 都是7 slots = new Slot[7]; freeList = -1; } // If value is not in set, add it and return true; otherwise return false public bool Add(TElement value) { return !Find(value, true); } // Check whether value is in set public bool Contains(TElement value) { return Find(value, false); } // If value is in set, remove it and return true; otherwise return false public bool Remove(TElement value) { int hashCode = InternalGetHashCode(value); int bucket = hashCode % buckets.Length; int last = -1; for (int i = buckets[bucket] - 1; i >= 0; last = i, i = slots[i].next) { if (slots[i].hashCode == hashCode && comparer.Equals(slots[i].value, value)) { if (last < 0) { buckets[bucket] = slots[i].next + 1; } else { slots[last].next = slots[i].next; } slots[i].hashCode = -1; slots[i].value = default(TElement); slots[i].next = freeList; freeList = i; return true; } } return false; } bool Find(TElement value, bool add) { int hashCode = InternalGetHashCode(value); for (int i = buckets[hashCode % buckets.Length] - 1; i >= 0; i = slots[i].next) { if (slots[i].hashCode == hashCode && comparer.Equals(slots[i].value, value)) return true; } if (add) { int index; if (freeList >= 0) { index = freeList; freeList = slots[index].next; } else { if (count == slots.Length) Resize(); index = count; count++; } int bucket = hashCode % buckets.Length; slots[index].hashCode = hashCode; slots[index].value = value; slots[index].next = buckets[bucket] - 1; buckets[bucket] = index + 1; } return false; } void Resize() { int newSize = checked(count * 2 + 1); // 嘗試擴容 int[] newBuckets = new int[newSize]; Slot[] newSlots = new Slot[newSize]; Array.Copy(slots, 0, newSlots, 0, count); for (int i = 0; i < count; i++) { int bucket = newSlots[i].hashCode % newSize; newSlots[i].next = newBuckets[bucket] - 1; newBuckets[bucket] = i + 1; } buckets = newBuckets; slots = newSlots; } internal int InternalGetHashCode(TElement value) { //Microsoft DevDivBugs 171937. work around comparer implementations that throw when passed null return (value == null) ? 0 : comparer.GetHashCode(value) & 0x7FFFFFFF; } internal struct Slot { internal int hashCode; internal TElement value; internal int next; } }
總結
因此有最佳實踐: 當兩對象重寫Equal方法返回true時， 請務必重寫GetHashCode方法為對象返回相同的hashcode。
話雖如此，寫一個合適、均衡的哈希函數還是比較考驗演算法的。
在一般場景中，經驗會幫助你編寫哈希函數， 比如以上Person類中，字元串類型Name的HashCode總是相等的。
That‘all 看完了通篇文章的同棧猿，應該就可以回答文章引言 5大提問。
碼甲拙見，如有問題請下方留言大膽斧正；碼字+Visio製圖，均為原創，看官請不吝好評+關注， ~。。~
本文歡迎轉載，請轉載頁面明顯位置註明原作者及原文鏈接。
