Hash Algorithms

一、Hash概念

Hash（散列，也称“哈希”）。散列方法的主要思想是根据结点的关键码值来确定其存储地址：以关键码值k为自变量，通过一定的函数关系h(k)（称为散列函数），计算出对应的函数值来，把这个值解释为结点的存储地址，将节点存入到此存储单元中。

二、Hash优点

先分类再查找，通过计算缩小范围，加快查找速度。

例：

集合：｛13,19,25,27，17｝

若是采用数组或链表结构：

访问其中的一个元素（如18），需要遍历整个集合的元素，时间复杂度为O(n).

而采用哈希表时:

假如散列函数为H[key] = key % 5；则集合元素对应的hash值分别为｛3,4,0,2,2｝。
访问元素（18）只需要在Hash值为2的集合中寻找即可.
如果访问没有哈希冲突的元素，例如访问（25），可以直接访问哈希值为（0）的值。
故hash时间复杂度最差才为O(n),最优情况下只需要O(1);

由上面的例子，我们可以想象，如果由大量的数据，采用数组或是链表存储时，访问需要遍历，耗费的时间非常多，而Hash表通过哈希计算，可以直接定位到数据所在位置（发生哈希冲突时，哈希值相同，可以定位到较小范围）大大加快了 查找的速度，节省了大量时间。

三、Hash函数

常见的Hash函数h(k)：直接定址法、数字分析法、平方取中法、折叠法、随机数法、除留余数法。

所有的Hash函数都有如下基本特性：

• 如果两个散列值h(k)是不相同的，那么这两个散列值对应的k值肯定是不同的
• 如果两个k值不同，那么h(k)是有可能相同的，这种现象又叫哈希碰撞

解决碰撞的方法

开放寻址法，再散列法等。

常用hash算法

MD4、MD5、SHA1等

四、Hash函数的应用

错误校正、语音识别、信息安全等。

五、举例

HashAlgorithm抽象类在System.Security.Cryptography命名空间下。

            string msg = "e1r2364uh发货的前方后仍1和和和破i就9哦破吉普请法25它";
            byte[] msgBytes = Encoding.Default.GetBytes(msg);
            MD5 d5 = MD5.Create();
            Console.WriteLine(d5.HashSize+"bits");
            byte[] d5Hash = d5.ComputeHash(msgBytes);
            Console.WriteLine(BitConverter.ToString(d5Hash));


            SHA1 hA1 = SHA1.Create();
            Console.WriteLine(hA1.HashSize+"bits");
            byte[] hA1Hash = hA1.ComputeHash(msgBytes);
            Console.WriteLine(BitConverter.ToString(hA1Hash));

output:128bits
       41-56-A7-0C-C9-3C-C1-C0-AE-43-EC-2E-62-DA-88-92
       160bits
       0A-A9-96-D7-0B-57-0F-5C-11-09-49-55-31-E0-EB-03-D0-AB-C8-87