重生之数据结构与算法----哈希表

郗燕岚 · 2025-6-1 23:34:16

简介

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不存储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];
      }
}
复制代码
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

账号		自动登录	找回密码
密码			立即注册

重生之数据结构与算法----哈希表

相关帖子

浏览过的版块

签约作者

重生之数据结构与算法----哈希表

相关帖子

相关推荐

浏览过的版块

签约作者