数据结构之哈希表

哈希函数的设计

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构

看下面的一组数据，如果是用红黑二叉树进行存储，性能在O(longn)，但是如果将这些数字直接放到内存中，比如这组数据中最大的是940，那就开辟一个940的大小的内存，每个数字都在对应的位置上，数字本身就是在内存上的索引，这样的话查找数据的话时间复杂度为O(1),但是这损失了空间。

为了解决上面的问题，可以通过取余来解决：比如将正整数与一定的数M进行相除，比如100，那么所得的余数便作为他们的键值，这样内存的开销就会小了很多，但是也会出现取余之后出现数字相同的情况，这叫哈希冲突，不能解决，只能避免。

素数：就是除了1和它自身外，再没有其它因子的自然数。如果把1也看作一个特殊的素数，写出来素数的集合为{1，2，3，5，7，11，13，17，19，23，......}

为了避免上述情况M最好为素数，比如97。可以看到分步更为均匀了，但是还是无法避免哈希冲突。

当然你不可能只存储正整数，可能还有浮点数和字符串，比如下面字符串也是转为二进制，其中a的ASCII码为97，b的ASCII码为98，c的ASCII码为99，但是你调用内置的GetHashCode函数得到的结果很可能与左边算的不一样，这是因为内部实现上不一样，不必管。

拉链法

比如下面k1,k3返回的哈希值都是2，那么都指向arr数组索引为2的地方，将k1与k3存在同一线性链表中，所以在查找的时候根据索引找到是在哪个位置的链表(k2是在索引为4位置上的链表)，然后在这个链表中找到对应的键。

比如找k3键，通过计算k3的哈希值为2，所以到指向索引为2的链表中寻找具体的值。

基于链表数组实现的哈希类

    /// <summary>
    /// 基于链表数组实现的哈希类
    /// </summary>
    /// <typeparam name="Key"></typeparam>
    class HashST1<Key>
    {
        /// <summary>
        /// 链表数组
        /// </summary>
        private MyLinkedList<Key>[] hashTable;
        /// <summary>
        /// 元素数
        /// </summary>
        private int N;
        /// <summary>
        /// 容量大小
        /// </summary>
        private int M;
        public HashST1(int M)
        {
            this.M = M;
            N = 0;
            //初始化数组链表
            hashTable = new MyLinkedList<Key>[M];
            //给数组中每一个位置都开辟一个链表
            for (int i = 0; i < M; i++)
            {
                hashTable[i] = new MyLinkedList<Key>();
            }
        }

        public HashST1() : this(97)
        {

        }

        public int Count { get { return N; } }
        public bool IsEmpty { get { return N == 0; } }

        private int Hash(Key key)
        {
            // 
            return (key.GetHashCode() & 0x7fffffff) % M;
        }

        public void Add(Key key)
        {
            MyLinkedList<Key> list = hashTable[Hash(key)];
            if (list.Contains(key))
                return;
            else
            {
                list.AddFirst(key);
                N++;
            }
        }

        public void Remove(Key key)
        {
            MyLinkedList<Key> list = hashTable[Hash(key)];
            if (list.Contains(key))
            {
                list.Remove(key);
                N--;
            }

        }

        public bool Contains(Key key)
        {
            MyLinkedList<Key> list = hashTable[Hash(key)];
            return list.Contains(key); 
        }

    }

其他方法:

集合和映射

c#中的HashSet是基于哈希实现的集合，对于查找最大,最小，floor,celing,等有序性操作的性能差于红黑树。

HashSet示例