简介
hash的基本原理，可以理解为一个加强版的数组。为什么这么说呢，数组通过index来实现随机访问Log(1),而hash的key也是类似，把key理解为index,本质上还是一个基于数组的随机访问。
那么问题来了，如何把hash的key转换成数组的index呢？
hash函数如何实现
hash函数的作用是把任意长度的输入（key）转化成固定长度的输出（index），通过hash函数，把对象转成一个固定且唯一的非负数整形
首先，我们需要为key寻找一个唯一标识，且最好是整数。对象在内存中的地址是一个很好的选择。
因为最高位编码的存在，hashcode有可能为负数。因此我们需要保证它为正数。
我们可以使用补码的原理，直接把最高位强制为0.
static void Main(string[] args) { var a1 = "sss".GetHashCode(); a1 = a1 & 0x7fffffff; Console.WriteLine($"hashcode={a1}"); Console.ReadLine(); } 有了一个唯一的正整数，看上去万事大吉了。但还有一个缺点，生成的正整数太大了。如果使用，会创建一个巨大的数组，这明显不可取。
所以这个时候，我们需要对它进行瘦身，参考上面讲到的环形数组，我们使用求模来保证key在一个合理的范围
static void Main(string[] args) { int[] arr = new int[] { 1, 2, 3, 4, 5, 6, 7 }; var a1 = "sss".GetHashCode(); a1 = a1 & 0x7fffffff; Console.WriteLine($"hashcode={a1}"); a1 = a1 % arr.Length; Console.WriteLine($"a1={a1}"); Console.ReadLine(); } 求模也比较消耗性能，正经的类库会使用位运算来提高性能，我只是举个例子。
hash冲突
上面简单描述了key如何转换为index过程，如果两个key得到了相同的index，这种问题就叫做hash冲突。
hash冲突无法避免，取模的过程相当于压缩。压缩就必定带来信息损失，信息损失肯定无法一比一还原信息，所以冲突是无法避免的。
面对hash冲突，主流有两种常见解法。
- 拉链法
拉链法的思路是Arr[i]不存储key/Value,而是存储一个链表的地址 。如果多个key映射到同一个index,那么存入这个链表，来解决冲突。
- 开放寻址法
开放寻址法的思路是，当一个key发现自己的index被占了，它就index+1，直到找到位置为止。
负载因子(Load Factor)
虽然拉链法与开放寻址法解决了hash冲突，但也带来了新的问题。那就是性能下降，尤其是hash冲突严重的时候。
以拉链法举例，hash冲突越严重，链表长度越长。众所周知，链表的查询复杂度为Log(N),因此hash表的查找复杂度取决于链表的长度。
开放寻址法同理可得，你也同样需要遍历整个数组，因为你不知道这个key是真的不存在还是在下一个位置.这个过程中的时间复杂度也是Log(N)
因此，loadFactor应运而生。负载因子代表的是一个hash table装满的程度，负载因子越大，说明key/value越多，越多则hash冲突的可能性越大，从而查找复杂度也越高。
因此当hash table达到负载因子的临界点时，会进行扩容。扩容的过程中会将底层的Array扩大,并对所有对象重新取模，重新分配Index。
负载因子计算公式：size / table.length
这里有个细微的区别，那就是拉链法的负载因子可以无限大，因为Array并不存储key/value。而使用开发寻址法，则不能超过1。这是它们的原理导致的。
不要被高大上的方法名所忽悠住，本质上一个横向拓展，一个是垂直拓展。
一个简单的拉链法
点击查看代码
/// <summary> /// 拉链法hashtable /// 不考虑负载因子与动态扩容的问题 /// </summary> public class ChainingHashTableSimple { public static void Run() { var ht = new ChainingHashTableSimple(10); ht.Put(1, "value1"); ht.Put(1, "value2"); ht.Put(11, "value11"); ht.Remove(1); } //一个链表数组，每个元素都是一个链表 private LinkedList<KVNode>[] _tables; public ChainingHashTableSimple(int capactity) { _tables=new LinkedList<KVNode>[capactity]; } /// <summary> /// 简单取模,方便模拟hash冲突 /// 比如1跟11的hash值都是1 /// </summary> /// <param name="key"></param> /// <returns></returns> private int Hash(int key) { return key % _tables.Length ; } public KVNode? Get(int key) { var hash = Hash(key); //找到hash对应的链表 var bucket = _tables[hash]; if (bucket == null) return null; //遍历整个链表,找到对应key/value //Log(N) KVNode node = null; foreach (var kv in bucket) { if (kv.Key.Equals(key)) { node= kv; break; } } return node; } /// <summary> /// 增/改 /// </summary> /// <param name="key"></param> /// <param name="value"></param> public void Put(int key, string value) { var hash=Hash(key); var bucket = _tables[hash]; //初始化链表 if (bucket == null) { bucket = new LinkedList<KVNode>(); _tables[hash] = bucket; } var node = Get(key); //新增 or 修改 //Log(1) if (node == null) { bucket.AddLast(new KVNode(key,value)); } else { node.Value= value; } } /// <summary> /// 删 /// </summary> /// <param name="key"></param> public void Remove(int key) { var hash = Hash(key); var bucket = _tables[hash]; if (bucket == null) return; //遍历整个链表,找到对应key/value //Log(N) KVNode node = null; foreach (var kv in bucket) { if (kv.Key.Equals(key)) { node = kv; break; } } if (node == null) return; //在知道节点的前提下删除 //Log(1) bucket.Remove(node); } /// <summary> /// 链表的节点，必须同时存储key,value /// 否则当hash冲突时，是不知道hash对应的value是哪一个的 /// </summary> public class KVNode { public int Key { get; set; } public string Value { get; set; } public KVNode(int key, string value) { Key = key; Value = value; } } /// <summary> /// 从原理角度出发,当你返回keys/values时 /// 只能给你一个全新的list /// https://www.cnblogs.com/lmy5215006/p/18712729 /// </summary> public List<int> Keys { get { var list=new List<int>(); foreach (var kv in _tables) { foreach (var node in kv) { list.Add(node.Key); } } return list; } } } 解法还有很多，你也可以用二维数组实现。
一个简单的开放寻址法
点击查看代码
public class LinearProbingHashTableSimple { public static void Run() { var hash = new LinearProbingHashTableSimple(); hash.Put(1, "value1"); hash.Put(11, "value11"); hash.Put(21, "value21"); hash.Put(31, "value31"); hash.Remove(21); } private KVNode[] _tables=new KVNode[10]; private int Hash(int key) { return key % _tables.Length; } public string Get(int key) { var index = Hash(key); //开放寻址，从idex向后找"坑位" // 难点1：这里仅仅实现先后查找，如果数组满了。 // 我们需要从头开始寻找。这就得利用到之前说的环形数组 while (index < _tables.Length && _tables[index] != null && _tables[index].Key != key) { index++; } return _tables[index].Value; } public void Put(int key,string value) { var index=Hash(key); var node = _tables[index]; if (node == null) { _tables[index] = new KVNode(key, value); } else { //开放寻址，从idex向后找对应的key while (index < _tables.Length && _tables[index] != null && _tables[index].Key != key) { index++; } _tables[index] = new KVNode(key, value); } } public void Remove(int key) { var index = Hash(key); //向后寻址，直到找到key while (index < _tables.Length && _tables[index] != null && _tables[index].Key != key) { index++; } //伪代码：删除该元素，并位移后面元素 //难点2：删除操作比较复杂。你不能无脑移动后续元素。而是只能讲哈希冲突的区间移动。 for (int i = index; i < _tables.Length; i++) { _tables[i] = _tables[i + 1]; } _tables[_tables.Length] = default; } public class KVNode { public int Key { get; set; } public string Value { get; set; } public KVNode(int key, string value) { Key = key; Value = value; } } } 开放寻址有两个难点：
1：是查找时要利用环形数组来实现头尾遍历
2：在_tables中删除元素时，可以进行类似数组的数据搬移操作，把后面的元素往前挪，保证元素的连续性。但你不能无脑搬移，你只能搬迁当前hash冲突的range
2.1： 如果你不想搬移，可以用一个特殊的占位符来标记，但随着时间的推移，不断的删除插入会导致”大量碎片“。影响get的效率。
基于这个原因，目前大多数编程语言实现hash table. 都使用拉链法。这样维护起来足够简单，负载因子也可以无限大。
个人认为，他们是替代关系，而不是平行关系。
Hash表的变种：双链表加强哈希表
众所周知，哈希表中键的遍历顺序是无序的。是核心原始是因为，hash函数对key进行映射时，有一个因子是你底层数组的长度，也就是一个取模的过程。
但因为动态扩容的存在，所以底层数组的长度是不定的。在扩容的过程中，key的哈希值可能变化，即这个key/value存储在table的索引变了，所以遍历结果的顺序就和之前不一样了.
那如果需要有序的遍历hash table怎么办？
在数据结构与算法中，只要你愿意拿空间换，Log(1) & Sort 都可以兼得！
所以我们的思路就是在不改变hash table 复杂度的前提下,又能够维护排序，又不受扩容影响。那我们只有一个选择，那就是使用链表加强hash.
如果选数组会受到扩容影响
一个简单的有序hash table
点击查看代码
public class ChainingHashTablePro<T,K> { public static void Run() { var hash = new ChainingHashTablePro<string, string>(); hash.Put("aaa", "value1"); hash.Put("bbb", "value2"); hash.Put("ccc", "value3"); hash.Put("ddd", "value4"); hash.Put("aaa", "value5"); hash.Remove("ccc"); foreach (var item in hash.Keys) { Console.WriteLine(item); } } private KVNode _head, _tail; private Dictionary<T, KVNode> _hashTable; public ChainingHashTablePro() { _head = new KVNode(default, default); _tail = new KVNode(default, default); _hashTable = new Dictionary<T, KVNode>(); _head.Next = _tail; _tail.Prev = _head; } public KVNode? Get(T key) { if (_hashTable.ContainsKey(key)) { return _hashTable[key]; } return null; } public void Put(T key,K value) { var node = Get(key); if (node == null) { node = new KVNode(key, value); _hashTable.Add(key, node); //在新增时，排序 var prev = _tail.Prev; var next = _tail; node.Prev = prev; node.Next = next; prev.Next = node; next.Prev = node; } else { _hashTable[key] = new KVNode(key, value); } } public void Remove(T key) { _hashTable.Remove(key, out var node); var next = node.Next; var prev = node.Prev; prev.Next = next; next.Prev = prev; node = null; } /// <summary> /// 从_head开始遍历，保证有序 /// </summary> public List<T> Keys { get { var list = new List<T>(); while (_head.Next != null&&_head.Next.Key!=null) { list.Add(_head.Next.Key); _head = _head.Next; } return list; } } public class KVNode { public T Key { get; set; } public K Value { get; set; } /// <summary> /// 空间换时间 /// 维护他们插入的顺序，以实现key有序 /// </summary> public KVNode Next { get; set; } public KVNode Prev { get; set; } public KVNode(T key, K value) { Key = key; Value = value; } } } - 无序遍历
- 有序遍历
对比这两种遍历方式，我相信你能get到有序的精髓。
Hash表的变种：数组加强哈希表
如果客户有一个需求，那就是让你在hash table中返回一个随机的key.我们应该怎么弄？
随机key需要均衡随机
开放寻址法思路
链表的底层是数组，很容易想到，数组是最适合随机读取的。那么我们只需要随机一个数作为一个index，似乎问题就迎刃而解了。
private List<KVNode> _tables; public KVNode Random() { var r = new Random(_tables.Count); var i = r.Next(); return _tables[i]; } 这个前提是数组中没有空洞，比如[1,2,3,4,5],就没有问题.
但如果你的数组是[1,null,3,null,4,5],而你的随机index好死不死的随机到了1。这时候咋办？
根据前面几篇文章的套路，你会想到利用环形数组来实现线性查找。
private List<KVNode> _tables; public KVNode Random2() { var r = new Random(_tables.Count); var i = r.Next(); var result = _tables[i]; //环形数组，找到not null while (result == null) { i = (i + 1) % _tables.Count; result = _tables[i]; } return result; } 看上去已经完美了，但这里还有两个问题
- 时间复杂度退化为O(N)
因为有循环 - 不均匀
环形数组的查找方向是固定的，不管你向左还是向右。另一侧被选中的几率会更低。
那如果我不用环形数组，二次随机行不行？
答案依旧是不行
public KVNode Random3() { var r = new Random(_tables.Count); var i = r.Next(); var result = _tables[i]; while (result == null) { //再随机一次，总能找到有用的 i = r.Next(); result = _tables[i]; } return result; } 时间复杂依旧为O(N),因为还是有随机到null的可能。
到目前为止，我们陷入了死胡同。让我们换个思路，用拉链法看能不能行。
拉链法则思路
如果你用拉链法，那你就算踢到铁板了
private LinkedList<KVNode>[] _tables; public KVNode Random() { var r = new Random(_tables.Length); var i = r.Next(); //bucket是链表，做不到随机访问。只能顺序访问。 //时间复杂度O(N) var bucket = _tables[i]; } 问题好像无解了，我们能想到的办法都尝试了。还有其它办法吗？
终极蛇皮大招
正如我一直强调的一点，任何时间问题都可以靠空间换时间来解决。
如果上面讲的，使用双链表解决顺序访问的问题。那么我们也可以用双数组来解决随机访问的问题
public class HashTableSimple<T,K> { public static void Run() { var hashPro = new HashTableSimple<string, string>(); hashPro.Put("aaa", "value1"); hashPro.Put("bbb", "value2"); hashPro.Put("ccc", "value3"); hashPro.Put("ddd", "value4"); hashPro.Put("aaa", "value5"); hashPro.Remove("ccc"); } private Dictionary<T, K> _hash=new Dictionary<T, K>(); /// <summary> /// 空间换时间 /// 用一个数组来存储所有的key /// </summary> private List<T> _keys=new List<T>(); public void Put(T key,K value) { if (_hash.ContainsKey(key)) { _hash[key] = value; } else { _hash.Add(key, value); _keys.Add(key); } } public void Remove(T key) { _hash.Remove(key); //如果key位于数组中间，会涉及到移动元素。O(N) //面对随机访问的场景，有一种"奇技淫巧" //_keys.Remove(key); //要删除key的index var index= _keys.IndexOf(key); //找到最后一个元素 var lastItem = _keys[_keys.Count - 1]; //要删除的元素与最后元素交换位置。 //当然，这样的代价就是数组中的元素顺序会被打乱， //但是对于我们当前的场景来说，数组中的元素顺序并不重要，所以打乱了也无所谓。 _keys[index] = lastItem; //取巧，实现array删除的O(1) _keys.RemoveAt(_keys.Count - 1); } /// <summary> /// 随机弹出一个key，O(1) /// </summary> /// <returns></returns> public T GetRandomKey() { var r = new Random(_keys.Count); var i = r.Next(); return _keys[i]; } } 
![洛谷 P11345 [KTSC 2023 R2] 基地简化 题解](http://www.itfaba.com/wp-content/themes/kemi/timthumb.php?src=http://www.itfaba.com/wp-content/themes/kemi/img/random/3.jpg&w=218&h=124&zc=1)
