【愚公系列】2021年11月 C#版 数据结构与算法解析(哈希)

1、引言

HASH是根据文件内容的数据通过逻辑运算得到的数值, 不同的文件(即使是相同的文件名)得到的HASH值是不同的。

通过一定的哈希算法（典型的有MD5，SHA-1等），将一段较长的数据映射为较短小的数据，这段小数据就是大数据的哈希值。他最大的特点就是唯一性，一旦大数据发生了变化，哪怕是一个微小的变化，他的哈希值也会发生变化。类似于DNA，既然是DNA，那就保证了没有两个数据的哈希值是完全相同的。

哈希值的作用：哈希值，即HASH值，是通过对文件内容进行加密运算得到的一组二进制值，主要用途是用于文件校验或签名。正是因为这样的特点，它常常用来判断两个文件是否相同。

比如，从网络上下载某个文件，只要把这个文件原来的哈希值同下载后得到的文件的哈希值进行对比，如果相同则表示两个文件完全一致，下载过程没有损坏文件。而如果不一致，则表明下载得到的文件跟原来的文件不同，文件在下载过程中受到了损坏。Hash的应用非常广泛，主要应用于：

1.文件校验

我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗数据篡改的能力，它们一定程度上能检测并纠正数据传输中的信道误码，但却不能防止对数据的恶意破坏。

MD5Hash算法的”数字指纹”特性，使它成为目前应用最广泛的一种文件完整性校验和(Checksum)算法，不少Unix系统有提供计算md5checksum的命令。

2. 唯一标识

现在有十万个文件, 给你一个文件, 要你在这十万个文件中查找是否存在. 一个很笨的办法就是把每一文件都拿出来, 然后按照二进制串一一进行对比. 但是这个操作注定是比较费时的。可以用哈希算法对文件进行计算, 然后比较哈希值是否相同。 因为存在哈希冲突的情况, 你可以在相同哈希值的文件再进行二进制串比较.

3. 数字签名

Hash算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮演了一个重要的角色。对Hash值，又称”数字摘要”进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。

4. 哈希表

在哈希表中使用哈希函数已经并不陌生了, 不再赘述。

5. 负载均衡

比如说, 现在又多台服务器, 来了一个请求, 如何确定这个请求应该路由到哪个路由器呢?当然, 必须确保相同的请求经过路由到达同一个服务器. 一种办法就是保存一张路由关系的表, 比如客户端IP和服务器编号的映射, 但是如果客户端很多, 势必查找的时间会很长。 这时, 可以将客户端的唯一标识信息(如:IP、username等)进行哈希计算, 然后与服务器个数取模, 得到的就是服务器的编号。

6. 分布式存储

当我们有大量数据时, 为了提高读取与写入的速度, 一般会选择将数据存储到多个服务器。 决定将文件存储到哪台服务器, 就可以通过哈希算法取模的操作来得到。

但是, 如果数据多了, 要增加服务器了, 问题就来了, 比如原来是10台服务器, 现在变成15台了, 那么原来哈希值为16的文件被分配到编号6的服务器, 现在被分配到编号1的服务器, 也就意味着所有文件都要重新计算哈希值并重新非陪服务器进行存储。 一致性哈希就是这个用途。

2、C#开发用于计算文件Hash的辅助类HashHelper

在C#中，数据的Hash以MD5或SHA1的方式实现，MD5与SHA1都是Hash算法，MD5输出是128位的，SHA1输出是160位的，MD5比SHA1快，SHA1比MD5强度高。

2.1、SHA-1和MD5的比较

因为二者均由MD4导出，SHA-1和MD5彼此很相似。相应的，他们的强度和其他特性也是相似，但还有以下几点不同：

1）对强行攻击的安全性：最显著和最重要的区别是SHA-1摘要比MD5摘要长32 位。使用强行技术，产生任何一个报文使其摘要等于给定报摘要的难度对MD5是2128数量级的操作，而对SHA-1则是2160数量级的操作。这样，SHA-1对强行攻击有更大的强度。

2）对密码分析的安全性：由于MD5的设计，易受密码分析的攻击，SHA-1显得不易受这样的攻击。

3）速度：在相同的硬件上，SHA-1的运行速度比MD5慢。

2.2、SHA-1和MD5在C#中的实现

/// <summary>
/// Hash辅助类
/// </summary>
public class HashHelper
{
    /// <summary>
    /// 计算文件的 MD5 值
    /// </summary>
    /// <param name="fileName">要计算 MD5 值的文件名和路径</param>
    /// <returns>MD5 值16进制字符串</returns>
    public static string MD5File(string fileName)
    {
        return HashFile(fileName, "md5");
    }

    /// <summary>
    /// 计算文件的 sha1 值
    /// </summary>
    /// <param name="fileName">要计算 sha1 值的文件名和路径</param>
    /// <returns>sha1 值16进制字符串</returns>
    public static string SHA1File(string fileName)
    {
        return HashFile(fileName, "sha1");
    }

    /// <summary>
    /// 计算文件的哈希值
    /// </summary>
    /// <param name="fileName">要计算哈希值的文件名和路径</param>
    /// <param name="algName">算法:sha1,md5</param>
    /// <returns>哈希值16进制字符串</returns>
    private static string HashFile(string fileName, string algName)
    {
        if (!System.IO.File.Exists(fileName))
        {
            return string.Empty;
        }

        System.IO.FileStream fs = new System.IO.FileStream(fileName, System.IO.FileMode.Open, System.IO.FileAccess.Read);
        byte[] hashBytes = HashData(fs, algName);
        fs.Close();
        return ByteArrayToHexString(hashBytes);
    }

    /// <summary>
    /// 计算哈希值
    /// </summary>
    /// <param name="stream">要计算哈希值的 Stream</param>
    /// <param name="algName">算法:sha1,md5</param>
    /// <returns>哈希值字节数组</returns>
    private static byte[] HashData(System.IO.Stream stream, string algName)
    {
        System.Security.Cryptography.HashAlgorithm algorithm;
        if (algName == null)
        {
            throw new ArgumentNullException("algName 不能为 null");
        }

        if (string.Compare(algName, "sha1", true) == 0)
        {
            algorithm = System.Security.Cryptography.SHA1.Create();
        }
        else
        {
            if (string.Compare(algName, "md5", true) != 0)
            {
                throw new Exception("algName 只能使用 sha1 或 md5");
            }
            algorithm = System.Security.Cryptography.MD5.Create();
        }

        return algorithm.ComputeHash(stream);
    }

    /// <summary>
    /// 字节数组转换为16进制表示的字符串
    /// </summary>
    private static string ByteArrayToHexString(byte[] buf)
    {
        return BitConverter.ToString(buf).Replace("-", "");
    }
}      

2.2、SHA-1和MD5在C#中的实现的测试用例

[TestClass]
public class HashHelperUnitTest
{
    [TestMethod]
    public void TestMethod1()
    {
        string fileName = @"D:\TempTest\RDIFramework.BizLogic.dll";
        Assert.AreEqual(0, 0);

        //01.计算文件的 MD5 值
        Console.WriteLine(string.Format("计算文件的 MD5 值：{0}", HashHelper.MD5File(fileName)));

        //02.计算文件的 sha1 值
        Console.WriteLine(string.Format("计算文件的 sha1 值：{0}", HashHelper.SHA1File(fileName)));
    }
}