经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置：技术经验 » 程序设计 » 编程经验 » 查看文章
重生之数据结构与算法----哈希表
来源：cnblogs　　作者：叫我安不理　　时间：2025/3/7 9:11:58　　对本文有异议

简介

hash的基本原理，可以理解为一个加强版的数组。为什么这么说呢，数组通过index来实现随机访问Log(1),而hash的key也是类似，把key理解为index,本质上还是一个基于数组的随机访问。

那么问题来了，如何把hash的key转换成数组的index呢？

hash函数如何实现

hash函数的作用是把任意长度的输入（key）转化成固定长度的输出（index），通过hash函数，把对象转成一个固定且唯一的非负数整形
首先，我们需要为key寻找一个唯一标识，且最好是整数。对象在内存中的地址是一个很好的选择。
image
因为最高位编码的存在，hashcode有可能为负数。因此我们需要保证它为正数。
image
我们可以使用补码的原理，直接把最高位强制为0.

  1.         static void Main(string[] args)
  2.         {
  3.             var a1 = "sss".GetHashCode();
  4.             a1 = a1 & 0x7fffffff;
  5.             Console.WriteLine($"hashcode={a1}");
  6.             Console.ReadLine();
  8.         }

有了一个唯一的正整数，看上去万事大吉了。但还有一个缺点，生成的正整数太大了。如果使用，会创建一个巨大的数组，这明显不可取。
所以这个时候，我们需要对它进行瘦身，参考上面讲到的环形数组，我们使用求模来保证key在一个合理的范围

  1.         static void Main(string[] args)
  2.         {
  3.             int[] arr = new int[] { 1, 2, 3, 4, 5, 6, 7 };
  4.             var a1 = "sss".GetHashCode();
  5.             a1 = a1 & 0x7fffffff;
  6.             Console.WriteLine($"hashcode={a1}");
  7.             a1 = a1 % arr.Length;
  8.             Console.WriteLine($"a1={a1}");
  9.             Console.ReadLine();
  11.         }

求模也比较消耗性能，正经的类库会使用位运算来提高性能，我只是举个例子。

hash冲突

上面简单描述了key如何转换为index过程，如果两个key得到了相同的index，这种问题就叫做hash冲突。

hash冲突无法避免，取模的过程相当于压缩。压缩就必定带来信息损失，信息损失肯定无法一比一还原信息，所以冲突是无法避免的。

面对hash冲突，主流有两种常见解法。

  1. 拉链法
    image

拉链法的思路是Arr[i]不存储key/Value,而是存储一个链表的地址 。如果多个key映射到同一个index,那么存入这个链表，来解决冲突。

  1. 开放寻址法
    image
    开放寻址法的思路是，当一个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
image

这里有个细微的区别，那就是拉链法的负载因子可以无限大，因为Array并不存储key/value。而使用开发寻址法，则不能超过1。这是它们的原理导致的。
不要被高大上的方法名所忽悠住，本质上一个横向拓展，一个是垂直拓展。

一个简单的拉链法

点击查看代码 
  1.     /// <summary>
  2.     /// 拉链法hashtable
  3.     /// 不考虑负载因子与动态扩容的问题
  4.     /// </summary>
  5.     public class ChainingHashTableSimple
  6.     {
  7.         public static void Run() 
  8.         {
  9.             var ht = new ChainingHashTableSimple(10);
  11.             ht.Put(1, "value1");
  12.             ht.Put(1, "value2");
  13.             ht.Put(11, "value11");
  15.             ht.Remove(1);
  16.         }
  17.         //一个链表数组，每个元素都是一个链表
  18.         private LinkedList<KVNode>[] _tables;
  20.         public ChainingHashTableSimple(int capactity)
  21.         {
  22.             _tables=new LinkedList<KVNode>[capactity];
  23.         }
  25.         /// <summary>
  26.         /// 简单取模,方便模拟hash冲突
  27.         /// 比如1跟11的hash值都是1
  28.         /// </summary>
  29.         /// <param name="key"></param>
  30.         /// <returns></returns>
  31.         private int Hash(int key)
  32.         {
  33.             return key % _tables.Length ;
  34.         }
  36.         public KVNode? Get(int key)
  37.         {
  38.             var hash = Hash(key);
  40.             //找到hash对应的链表
  41.             var bucket = _tables[hash];
  43.             if (bucket == null)
  44.                 return null;
  46.             //遍历整个链表,找到对应key/value
  47.             //Log(N)
  48.             KVNode node = null;
  49.             foreach (var kv in bucket)
  50.             {
  51.                 if (kv.Key.Equals(key))
  52.                 {
  53.                     node= kv;
  54.                     break;
  55.                 }
  56.             }
  58.             return node;
  59.         }
  61.         /// <summary>
  62.         /// 增/改
  63.         /// </summary>
  64.         /// <param name="key"></param>
  65.         /// <param name="value"></param>
  66.         public void Put(int key, string value)
  67.         {
  68.             var hash=Hash(key);
  70.             var bucket = _tables[hash];
  72.             //初始化链表
  73.             if (bucket == null)
  74.             {
  75.                 bucket = new LinkedList<KVNode>();
  76.                 _tables[hash] = bucket;
  77.             }
  79.             var node = Get(key);
  81.             //新增 or 修改
  82.             //Log(1)
  83.             if (node == null)
  84.             {
  85.                 bucket.AddLast(new KVNode(key,value));
  86.             }
  87.             else
  88.             {
  89.                 node.Value= value;
  90.             }
  93.             
  94.         }
  96.         /// <summary>
  97.         /// 删
  98.         /// </summary>
  99.         /// <param name="key"></param>
  100.         public void Remove(int key)
  101.         {
  102.             var hash = Hash(key);
  103.             var bucket = _tables[hash];
  105.             if (bucket == null)
  106.                 return;
  108.             //遍历整个链表,找到对应key/value
  109.             //Log(N)
  110.             KVNode node = null;
  111.             foreach (var kv in bucket)
  112.             {
  113.                 if (kv.Key.Equals(key))
  114.                 {
  115.                     node = kv;
  116.                     break;
  117.                 }
  118.             }
  120.             if (node == null)
  121.                 return;
  123.             //在知道节点的前提下删除
  124.             //Log(1)
  125.             bucket.Remove(node);
  126.         }
  128.         /// <summary>
  129.         /// 链表的节点，必须同时存储key,value
  130.         /// 否则当hash冲突时，是不知道hash对应的value是哪一个的
  131.         /// </summary>
  132.         public class KVNode 
  133.         {
  134.             public int Key { get; set; }
  135.             public string Value { get; set; }
  137.             public KVNode(int key, string value)
  138.             {
  139.                 Key = key;
  140.                 Value = value;
  141.             }
  142.         }
  144.         /// <summary>
  145.         /// 从原理角度出发,当你返回keys/values时
  146.         /// 只能给你一个全新的list
  147.         /// https://www.cnblogs.com/lmy5215006/p/18712729
  148.         /// </summary>
  149.         public List<int> Keys
  150.         {
  151.             get
  152.             {
  153.                 var list=new List<int>();
  154.                 foreach (var kv in _tables)
  155.                 {
  156.                     foreach (var node in kv)
  157.                     {
  158.                         list.Add(node.Key);
  159.                     }
  160.                 }
  161.                 return list;
  162.             }
  163.         }
  164.     }

解法还有很多，你也可以用二维数组实现。

一个简单的开放寻址法

点击查看代码 
  1.     public class LinearProbingHashTableSimple
  2.     {
  3.         public static void Run()
  4.         {
  5.             var hash = new LinearProbingHashTableSimple();
  7.             hash.Put(1, "value1");
  8.             hash.Put(11, "value11");
  9.             hash.Put(21, "value21");
  10.             hash.Put(31, "value31");
  12.             hash.Remove(21);
  13.         }
  16.         private KVNode[] _tables=new KVNode[10];
  19.         private int Hash(int key)
  20.         {
  21.             return key % _tables.Length;
  22.         }
  24.         public string Get(int key)
  25.         {
  26.             var index = Hash(key);
  27.             //开放寻址，从idex向后找"坑位"
  28.             // 难点1：这里仅仅实现先后查找，如果数组满了。
  29.             // 我们需要从头开始寻找。这就得利用到之前说的环形数组
  30.             while (index < _tables.Length && _tables[index] != null && _tables[index].Key != key)
  31.             {
  32.                 index++;
  33.             }
  35.             return _tables[index].Value;
  36.         }
  38.         public void Put(int key,string value)
  39.         {
  40.             var index=Hash(key);
  42.             var node = _tables[index];
  44.             if (node == null)
  45.             {
  46.                 _tables[index] = new KVNode(key, value);
  47.             }
  48.             else
  49.             {
  50.                 //开放寻址，从idex向后找对应的key
  51.                 while (index < _tables.Length && _tables[index] != null && _tables[index].Key != key)
  52.                 {
  53.                     index++;
  54.                 }
  56.                 _tables[index] = new KVNode(key, value);
  57.             }
  58.         }
  59.         
  60.         public void Remove(int key)
  61.         {
  62.             var index = Hash(key);
  64.             //向后寻址，直到找到key
  65.             while (index < _tables.Length && _tables[index] != null && _tables[index].Key != key)
  66.             {
  67.                 index++;
  68.             }
  71.             //伪代码：删除该元素，并位移后面元素
  73.             //难点2：删除操作比较复杂。你不能无脑移动后续元素。而是只能讲哈希冲突的区间移动。
  74.             for (int i = index; i < _tables.Length; i++)
  75.             {
  76.                 _tables[i] = _tables[i + 1];
  77.             }
  78.             _tables[_tables.Length] = default;
  79.         }
  81.         public class KVNode
  82.         {
  83.             public int Key { get; set; }
  84.             public string Value { get; set; }
  86.             public KVNode(int key, string value)
  87.             {
  88.                 Key = key;
  89.                 Value = value;
  90.             }
  91.         }
  92.     }

开放寻址有两个难点：
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.

如果选数组会受到扩容影响

image

一个简单的有序hash table

点击查看代码 
  1. public class ChainingHashTablePro<T,K>
  2. {
  3.     public static void Run()
  4.     {
  5.         var hash = new ChainingHashTablePro<string, string>();
  7.         hash.Put("aaa", "value1");
  8.         hash.Put("bbb", "value2");
  9.         hash.Put("ccc", "value3");
  10.         hash.Put("ddd", "value4");
  11.         hash.Put("aaa", "value5");
  13.         hash.Remove("ccc");
  15.         foreach (var item in hash.Keys)
  16.         {
  17.             Console.WriteLine(item);
  18.         }
  19.     }
  21.     private KVNode _head, _tail;
  22.     private Dictionary<T, KVNode> _hashTable;
  24.     public ChainingHashTablePro()
  25.     {
  26.         _head = new KVNode(default, default);
  27.         _tail = new KVNode(default, default);
  28.         _hashTable = new Dictionary<T, KVNode>();
  29.         
  30.         _head.Next = _tail;
  31.         _tail.Prev = _head;
  32.     }
  34.     public KVNode? Get(T key)
  35.     {
  36.         if (_hashTable.ContainsKey(key))
  37.         {
  38.             return _hashTable[key];
  39.         }
  40.         return null;
  41.     }
  43.     public void Put(T key,K value)
  44.     {
  45.         var node = Get(key);
  46.         if (node == null)
  47.         {
  48.             node = new KVNode(key, value);
  49.             _hashTable.Add(key, node);
  51.             //在新增时，排序
  52.             var prev = _tail.Prev;
  53.             var next = _tail;
  55.             node.Prev = prev;
  56.             node.Next = next;
  58.             prev.Next = node;
  59.             next.Prev = node;
  60.         }
  61.         else
  62.         {
  63.             _hashTable[key] = new KVNode(key, value);
  64.         }
  65.     }
  66.     public void Remove(T key)
  67.     {
  68.         _hashTable.Remove(key, out var node);
  70.         var next = node.Next;
  71.         var prev = node.Prev;
  73.         prev.Next = next;
  74.         next.Prev = prev;
  76.         node = null;
  77.     }
  79.     /// <summary>
  80.     /// 从_head开始遍历，保证有序
  81.     /// </summary>
  82.     public List<T> Keys
  83.     {
  84.         get
  85.         {
  86.             var list = new List<T>();
  87.             while (_head.Next != null&&_head.Next.Key!=null)
  88.             {
  89.                 list.Add(_head.Next.Key);
  90.                 _head = _head.Next;
  91.             }
  92.             return list;
  93.         }
  94.     }
  96.     public class KVNode
  97.     {
  98.         public T Key { get; set; }
  99.         public K Value { get; set; }
  101.         /// <summary>
  102.         /// 空间换时间
  103.         /// 维护他们插入的顺序，以实现key有序
  104.         /// </summary>
  105.         public KVNode Next { get; set; }
  106.         public KVNode Prev { get; set; }
  108.         public KVNode(T key, K value)
  109.         {
  110.             Key = key;
  111.             Value = value;
  112.         }
  113.     }
  114. }
  1. 无序遍历
    image
  2. 有序遍历
    image

对比这两种遍历方式，我相信你能get到有序的精髓。

Hash表的变种：数组加强哈希表

如果客户有一个需求，那就是让你在hash table中返回一个随机的key.我们应该怎么弄？

随机key需要均衡随机

开放寻址法思路

链表的底层是数组，很容易想到，数组是最适合随机读取的。那么我们只需要随机一个数作为一个index，似乎问题就迎刃而解了。

  1.         private List<KVNode> _tables;
  2.         public KVNode Random()
  3.         {
  4.             var r = new Random(_tables.Count);
  5.             var i = r.Next();
  7.             return _tables[i];
  8.         }

这个前提是数组中没有空洞，比如[1,2,3,4,5],就没有问题.
但如果你的数组是[1,null,3,null,4,5],而你的随机index好死不死的随机到了1。这时候咋办？

根据前面几篇文章的套路，你会想到利用环形数组来实现线性查找。

  1.         private List<KVNode> _tables;
  2.         public KVNode Random2()
  3.         {
  4.             var r = new Random(_tables.Count);
  5.             var i = r.Next();
  6.             var result = _tables[i];
  8.             //环形数组，找到not null
  9.             while (result == null)
  10.             {
  11.                 i = (i + 1) % _tables.Count;
  12.                 result = _tables[i];
  13.             }
  14.             return result;
  15.         }

看上去已经完美了，但这里还有两个问题

  1. 时间复杂度退化为O(N)
    因为有循环
  2. 不均匀
    环形数组的查找方向是固定的，不管你向左还是向右。另一侧被选中的几率会更低。

那如果我不用环形数组，二次随机行不行？
答案依旧是不行

  1.         public KVNode Random3()
  2.         {
  3.             var r = new Random(_tables.Count);
  4.             var i = r.Next();
  5.             var result = _tables[i];
  7.             
  8.             while (result == null)
  9.             {
  10.                 //再随机一次，总能找到有用的
  11.                 i = r.Next();
  12.                 result = _tables[i];
  13.             }
  14.             return result;
  15.         }

时间复杂依旧为O(N),因为还是有随机到null的可能。

到目前为止，我们陷入了死胡同。让我们换个思路，用拉链法看能不能行。

拉链法则思路

如果你用拉链法，那你就算踢到铁板了

  1.         private LinkedList<KVNode>[] _tables;
  2.         public KVNode Random()
  3.         {
  4.             var r = new Random(_tables.Length);
  5.             var i = r.Next();
  7.             //bucket是链表，做不到随机访问。只能顺序访问。
  8. 			//时间复杂度O(N)
  9.             var bucket = _tables[i];
  11.             
  12.         }

问题好像无解了，我们能想到的办法都尝试了。还有其它办法吗？

终极蛇皮大招

正如我一直强调的一点，任何时间问题都可以靠空间换时间来解决。
如果上面讲的，使用双链表解决顺序访问的问题。那么我们也可以用双数组来解决随机访问的问题

  1.     public class HashTableSimple<T,K>
  2.     {
  3.         public static void Run()
  4.         {
  5.             var hashPro = new HashTableSimple<string, string>();
  6.             hashPro.Put("aaa", "value1");
  7.             hashPro.Put("bbb", "value2");
  8.             hashPro.Put("ccc", "value3");
  9.             hashPro.Put("ddd", "value4");
  10.             hashPro.Put("aaa", "value5");
  12.             hashPro.Remove("ccc");
  13.         }
  15.         private Dictionary<T, K> _hash=new Dictionary<T, K>();
  16.         /// <summary>
  17.         /// 空间换时间
  18.         /// 用一个数组来存储所有的key
  19.         /// </summary>
  20.         private List<T> _keys=new List<T>();
  22.         public void Put(T key,K value)
  23.         {
  24.             if (_hash.ContainsKey(key))
  25.             {
  26.                 _hash[key] = value;
  27.             }
  28.             else 
  29.             {
  30.                 _hash.Add(key, value);
  31.                 _keys.Add(key);
  32.             }
  33.         }
  34.         public void Remove(T key)
  35.         {
  36.             _hash.Remove(key);
  38.             //如果key位于数组中间，会涉及到移动元素。O(N)
  39.             //面对随机访问的场景，有一种"奇技淫巧"
  40.             //_keys.Remove(key);
  43.             //要删除key的index
  44.             var index= _keys.IndexOf(key);
  45.             
  46.             //找到最后一个元素
  47.             var lastItem = _keys[_keys.Count - 1];
  49.             //要删除的元素与最后元素交换位置。
  50.             //当然，这样的代价就是数组中的元素顺序会被打乱，
  51.             //但是对于我们当前的场景来说，数组中的元素顺序并不重要，所以打乱了也无所谓。
  52.             _keys[index] = lastItem;
  53.             //取巧，实现array删除的O(1)
  54.             _keys.RemoveAt(_keys.Count - 1);
  55.         }
  57.         /// <summary>
  58.         /// 随机弹出一个key，O(1)
  59.         /// </summary>
  60.         /// <returns></returns>
  61.         public T GetRandomKey()
  62.         {
  63.             var r = new Random(_keys.Count);
  64.             var i = r.Next();
  65.             return _keys[i];
  66.         }
  68.     }

原文链接：https://www.cnblogs.com/lmy5215006/p/18748028

 友情链接：直通硅谷 　点职佳 　北美留学生论坛

编程经验热门文章

  • Prometheus监控之SNMP Exporter介绍和数据展现
  • Intel 82599网卡异常挂死原因
  • 腾讯防水墙的分析识别与破解
  • 桌面应用自动化WinAppDriver入门
  • 文档在线预览（三）使用js前端实现word、excel、pdf、ppt 在线预览
  • 「教程」如何下载AcFun网站上的视频、A站视频下载工具
  • 基于Hi3559AV100的SVP(NNIE)开发整体流程
  • GBDT(梯度提升树)scikit-klearn中的参数说明及简汇
  • antd之RangePicker设置默认值方式
  • 决胜经典算法之插入排序

    • 编程经验推荐文章

  • 被坑几百块钱后，我竟然真的恢复了删除的微信聊天记录！
  • 开发者必知的日志记录最佳实践
  • 没有源码，如何修改代码逻辑？
  • 百万级群聊的设计实践
  • vivo 大规模容器集群运维平台实践
  • 重生之数据结构与算法----哈希表
  • 为什么 退出登录 或 修改密码 无法使 token 失效
  • 为什么Raft算法是分布式系统的首选？
  • wifi基础(一)：无线电波与WIFI信号干扰、衰减
  • 甲方扔给两个存在包名与类名均相同的Jar包，要在工程中同时使用怎么办？

    • 本站QQ群：前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

    W3xue 的所有内容仅供测试，对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
    关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接（目前9元/月）请联系QQ：27243702 沸活量
    皖ICP备17017327号-2　皖公网安备34020702000426号