算法：哈希表格（Hash Table）

背景

Java 和 .Net 平台都有一个所有引用类型都会间接或直接继承的类型：Object，这个类型提供最基本的相等性比较算法和哈希算法，很多书上都给出了在重写这两个算法的时候的主意事项，其中大多数主意事项都和哈希表有关。

《CLR VIA C#》的作者觉得将哈希算法放到 Object 不是很适合，我也有这种感觉，每次重写相等性比较算法都要重新哈希算法，非常不爽，我就没打算将其用到哈希表中作为键使用。

哈希表

定义

使用哈希算法将 A 数值空间（键）映射到 B 数值空间（存储），如下：

A -> 0

B -> 1

C -> 2

D -> 3

B 数值空间的查询速度要求非常快，毫无疑问就是数值了。

冲突

数组的大小是固定，当出现冲突（两个键映射为同一个数值了）的时候如何处理呢？有两种策略：

• 在数组中按照一定的算法继续探测其它地址。
• 在数组的每个元素存储的都是链表，冲突的元素会被插入到链表中。

实现

链表节点

        class Node<TKey, TValue>
        {
            public TKey Key { get; set; }

            public TValue Value { get; set; }

            public Node<TKey, TValue> Next { get; set; }
        }

链表

        class LinkedList<TKey, TValue>
        {
            public Node<TKey, TValue> First { get; set; }

            public void Insert(TKey key, TValue value)
            {
                if (this.Contains(key))
                {
                    throw new InvalidOperationException("不能插入重复的键");
                }

                var node = new Node<TKey, TValue> { Key = key, Value = value };
                node.Next = this.First;
                this.First = node;
            }

            public void Delete(TKey key)
            {
                Node<TKey, TValue> parent;
                Node<TKey, TValue> node;

                if (!this.Find(key, out   parent, out  node))
                {
                    throw new InvalidOperationException("不存在指定的键");
                }

                if (parent == null)
                {
                    this.First = null;
                }
                else
                {
                    parent.Next = node.Next;
                }
            }

            public bool Contains(TKey key)
            {
                Node<TKey, TValue> parent;
                Node<TKey, TValue> node;

                return this.Find(key, out   parent, out  node);
            }

            public bool Find(TKey key, out Node<TKey, TValue> node)
            {
                Node<TKey, TValue> parent;

                return this.Find(key, out  parent, out  node);
            }

            public bool Find(TKey key, out Node<TKey, TValue> parent, out Node<TKey, TValue> node)
            {
                parent = null;
                node = this.First;

                while (node != null)
                {
                    if (node.Key.Equals(key))
                    {
                        return true;
                    }

                    parent = node;
                    node = node.Next;
                }

                return false;
            }
        }

哈希表

        class HashTable<TKey, TValue>
        {
            private LinkedList<TKey, TValue>[] _items;

            public HashTable(int size)
            {
                _items = new LinkedList<TKey, TValue>[size];
            }

            public void Insert(TKey key, TValue value)
            {
                var index = this.HashToIndex(key);
                if (_items[index] == null)
                {
                    _items[index] = new LinkedList<TKey, TValue>();
                }

                _items[index].Insert(key, value);
            }

            public void Delete(TKey key)
            {
                var index = this.HashToIndex(key);
                if (_items[index] == null)
                {
                    throw new InvalidOperationException("不存在指定的键");
                }

                _items[index].Delete(key);
            }

            public bool Find(TKey key, out TValue value)
            {
                value = default(TValue);

                var index = this.HashToIndex(key);
                if (_items[index] == null)
                {
                    return false;
                }

                Node<TKey, TValue> node;
                var finded = _items[index].Find(key, out  node);
                if (!finded)
                {
                    return false;
                }
                else
                {
                    value = node.Value;
                }

                return true;
            }

            private int HashToIndex(TKey key)
            {
                return key.GetHashCode() % _items.Length;
            }
        }

备注

哈希算法、负载因子、自动扩容都是需要考虑的，这里就不多说了。