面试必谈的哈希，.Net 程序员温故而知新
引言：
作为资深老鸟，有事没事，出去面试；找准差距、定位价值。
面试必谈哈希，
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方法的偏门警示
- .Net 并不保证GetHashCode方法有默认的输出，实际上在不同的 .Net实现(.Net Framework、.NetCore)中这个方法的返回值可能不同
- hashcode仅仅用于在基于hash特性的集合中查找/插入元素，并不是一个持久值，故不要尝试序列化或者持久化hashcode，也不要跨进程传递使用
在单纯判断【逻辑相等】时，本无所谓重写 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; }
Union方法入口
若单纯比较元素逻辑相等，重写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。
话虽如此，写一个合适、均衡的哈希函数还是比较考验算法的。
在一般场景中，经验会帮助你编写哈希函数， 比如以上Person类中，字符串类型Name的HashCode总是相等的。
That‘all 看完了通篇文章的猿，应该就可以回答文章引言 5大提问。