引言：
作为资深老鸟，有事没事，出去面试；找准差距、定位价值。
面试必谈哈希，
Q1：什么是哈希?
Q2：哈希为什么快?
Q3：你是怎么理解哈希算法利用空间换取时间的？
Q4：你是怎么解决哈希冲突的？
Q5：你有实际用写过哈希算法吗？
1. 知识储备
哈希（也叫散列）是一种查找算法（可用于插入），哈希算法希望能做到不经过任何比较（发生冲突，还是需要少许比较），通过一次存取就能得到查找的数据。
因此哈希的关键在key和数据元素的存储位置之间建立一个确定的对应关系，每个key在哈希表中都有唯一的地址相对应（形成有限、连续的地址空间），查找时根据对应关系经过一步计算得到key在散列表的位置。
故我们可以预见：
① 不同的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方法：
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 Persion { public string Name { get; set; } public int Age { get; set; } public override bool Equals(object other1) // 逻辑相等 { return Name == (other1 as Persion)?.Name; } public override int GetHashCode() { return Name.GetHashCode(); } } public class Program { static void Main(string[] args) { var p1 = new Persion { Name="HJ" , Age=22}; var p2 = new Persion { Name = "HJ", Age = 21 }; var referenceEqual = (p1 == p2); var logicEqual = (p1.Equals(p2)); Console.WriteLine($"“==”操作符：引用相等（两变量指向一个实例），始终为：{referenceEqual}"); Console.WriteLine($"“Equal”方法：逻辑相等, {logicEqual}"); Console.Read(); } } } ---------------------------------------------------------------- output： “==”操作符：引用相等（两变量指向一个实例），始终为：False “Equal”方法： 逻辑相等, True
但是若需要利用HashCode快速 查找 /插入某元素， 则一定要重写GetHashCode方法。
🔨 我们看一个实锤：
在使用 LINQ.Union()方法计算A,B两集合的并集 ：A∪B， 自然会想到使用逻辑相等比较器Comparer 定义A,B中元素逻辑相等：
public static IEnumerable<TSource> Union<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer);
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; }
若单纯比较元素逻辑相等，重写Equal方法就可以了，为什么这里要强调必须重写GetHashCode方法？
观察Union源码中求A,B并集的实现，内部会构造哈希表Set 快速查找和插入并集元素。
故我们需要给元素编写合适的哈希函数， 请关注下方代码区的 internal int InternalGetHashCode(TElement value) 函数
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。
That‘all 看完了通篇文章的同栈猿，应该就可以回答文章引言 5大提问。
感谢您的认真阅读，如有问题请下方留言大胆斧正，共同进步；觉得有用，请下方或加关注。
本文欢迎转载，但请保留此段声明，且在文章页面明显位置注明本文的作者及原文链接。