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

THL9bKQrZm

简介

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 = _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;        }这个前提是数组中没有空洞，比如[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;            //环形数组，找到not null            while (result == null)            {                i = (i + 1) % _tables.Count;                result = _tables;            }            return result;        }看上去已经完美了，但这里还有两个问题

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

那如果我不用环形数组，二次随机行不行？
答案依旧是不行
        public KVNode Random3()        {            var r = new Random(_tables.Count);            var i = r.Next();            var result = _tables;                        while (result == null)            {                //再随机一次，总能找到有用的                i = r.Next();                result = _tables;            }            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;                    }问题好像无解了，我们能想到的办法都尝试了。还有其它办法吗？
终极蛇皮大招

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