MurmurHash 真的比 MD5 速度快吗？

MurmurHash 介绍

MurmurHash 是一种非加密型哈希算法，英文是 (multiply and rotate) and (multiply and rotate) Hash。适用于一般的哈希检索操作，具有高性能、低碰撞率、分布均匀的特点。由 Google 的工程师 Austin Appleby 于 2008 年创建。MurmurHash 与其它流行的哈希函数相比，对于规律性较强的 Key，其随机分布特征表现的更好。非加密意味着着相对 MD5，SHA 这些哈希算法，MurmurHash 的性能更高。也正是由于它的这些优点，虽然，它出现于 2008 年，但目前已经广泛应用到 Redis 等众多著名的软件中。MurmurHash2 提供了两种长度的哈希值是 32 bit 和 64 bit；而 MurmurHash3 提供的两种长度的哈希值是 32 bit 和 128 bit。

MurmurHash 的应用

MurmurHash 在分布式系统的节点选择和负载均衡中的应用：

1. 普通哈希。将一个关键字（通常是字符串，如 URL）使用 MurmurHash 得到一个 无符号的 32 位的整数哈希值，然后用哈希值和节点数 N 取模（hash % N）得到的余数，来确定处理该任务的节点的索引。

2. 一致性哈希。把节点标识使用 MurmurHash 映射到哈希环上（哈希环的范围 0~2^23-1）。把请求关键字也使用 MurmurHash 映射到同一个哈希环上，按顺时针查找到的第一个节点，就是处理该请求的节点。如下图。

测试 MurmurHash，MD5，SHA 的速度

都说 MurmurHash 比 MD5，SHA 速度快，今天就来测试对比一下 MurmurHash，MD5，SHA256 的速度。（以 C# 为例）

1、工具类。分别用于计算 MurmurHash，MD5, SHA256 的哈希值。

public static class Utils{    public static string GetMurmurHash(string value)    {        byte[] srcBytes = Encoding.UTF8.GetBytes(value);        var cfg = new MurmurHash3Config() { HashSizeInBits = 32 };        var murmur = MurmurHash3Factory.Instance.Create(cfg);        IHashValue hv = murmur.ComputeHash(srcBytes);        return hv.AsBase64String();    }
    public static string GetMD5(string value)    {        using var md5 = MD5.Create();        var bytes = md5.ComputeHash(Encoding.UTF8.GetBytes(value));        return Convert.ToBase64String(bytes);    }
    public static string GetSHA256(string value)    {        using var sha = SHA256.Create();        var bytes = sha.ComputeHash(Encoding.UTF8.GetBytes(value));        return Convert.ToBase64String(bytes);    }}

2、Main 方法。

循环 count 次数，分别调用工具类的 GetMurmurHash、GetMD5、GetSHA256 方法计算哈希。使用 Stopwatch 记录所使用的时间。最后，把 GetMD5、GetSHA256 使用的时间和 GetMurmurHash 使用的时间做比较。

internal class Program{    static void Main(string[] args)    {        Stopwatch sw = new();        int count = 100; // 循环次数        var value = "1234567890abcdefghijklmnopqrstuvwxyz";
        Console.WriteLine();        Console.WriteLine($" 测试 MurmurHash、MD5 和 SHA256。循环 {count:0,0} 次");        Console.WriteLine($" 测试数据: {value}");        Console.WriteLine();
        // MurmurHash        sw.Restart();        for (int i = 0; i < count; i++)        {            Utils.GetMurmurHash(value);        }        sw.Stop();        var usedTimeMmh = sw.Elapsed.TotalSeconds;        Console.WriteLine($" MurmurHash 用时: {usedTimeMmh:0.####} 秒");
        // MD5        sw.Restart();        for (int i = 0; i < count; i++)        {            Utils.GetMD5(value);        }        sw.Stop();        var usedTimeMd5 = sw.Elapsed.TotalSeconds;        Console.WriteLine($" MD5 用时: \t  {usedTimeMd5:0.####} 秒");
        // SHA256        sw.Restart();        for (int i = 0; i < count; i++)        {            Utils.GetSHA256(value);        }        sw.Stop();        var usedTimeSHA256 = sw.Elapsed.TotalSeconds;        Console.WriteLine($" SHA256 用时: \t  {usedTimeSHA256:0.####} 秒");
        Console.WriteLine($"\n MD5 的用时是 MurmurHash 的 {usedTimeMd5 / usedTimeMmh :0.##} 倍");        Console.WriteLine($" SHA256 的用时是 MurmurHash 的 {usedTimeSHA256 / usedTimeMmh:0.##} 倍");        Console.WriteLine();
        Console.ReadKey();    }}

循环 100 次

count = 100。测试结果令人惊讶，MurmurHash、MD5 、SHA256，这 3 个哈希算法中，MurmurHash 是最慢的，而 SHA256 最快。差距还很大，不是说 MurmurHash 性能高、速度快吗？为什么实际测试恰恰相反呢？

MurmurHash 用时: 0.0295 秒

MD5 用时: 0.0165 秒

SHA256 用时: 0.0004 秒

MD5 的用时是 MurmurHash 的 0.56 倍

SHA256 的用时是 MurmurHash 的 0.01 倍

循环 1000 次

增加循环次数，再测试，count = 1000。可以看到循环 1000 次时，MurmurHash 和 MD5、SHA256 的差距有所缩小，但还是比后两者慢。

MurmurHash 用时: 0.0238 秒

MD5 用时: 0.0145 秒

SHA256 用时: 0.0017 秒

MD5 的用时是 MurmurHash 的 0.61 倍

SHA256 的用时是 MurmurHash 的 0.07 倍

循环 1 万 次

继续增加循环次数，count = 10000。循环 1 万次时，MurmurHash 和 MD5、SHA256 的差距进一步所缩小。

MurmurHash 用时: 0.0324 秒

MD5 用时: 0.0253 秒

SHA256 用时: 0.0082 秒

MD5 的用时是 MurmurHash 的 0.78 倍

SHA256 的用时是 MurmurHash 的 0.25 倍

循环 10 万 次

count = 100000。当循环增加到 10 万次时，MurmurHash 的速度“首次”超过 MD5、SHA256，性能是后者的 1.5 倍以上。

MurmurHash 用时: 0.0666 秒

MD5 用时: 0.1017 秒

SHA256 用时: 0.1063 秒

MD5 的用时是 MurmurHash 的 1.53 倍

SHA256 的用时是 MurmurHash 的 1.6 倍

循环 100 万 次

count = 1000000。当循环增加到 100 万次时，MurmurHash 的速度分别是 MD5、SHA256 的 2.3、2.76 倍 。

MurmurHash 用时: 0.2903 秒

MD5 用时: 0.6684 秒

SHA256 用时: 0.8001 秒

MD5 的用时是 MurmurHash 的 2.3 倍

SHA256 的用时是 MurmurHash 的 2.76 倍

循环 1000 万 次

count = 10000000。当循环增加到 1000 万次时，MurmurHash 的速度是 MD5、SHA256 的 3.36、4.22 倍。

MurmurHash 用时: 2.3166 秒

MD5 用时: 7.7821 秒

SHA256 用时: 9.7662 秒

MD5 的用时是 MurmurHash 的 3.36 倍

SHA256 的用时是 MurmurHash 的 4.22 倍

总结

MurmurHash 的在小输入的情况下，性能比 MD5 、SHA256 差；在大输入的情况下，性能比 MD5 、SHA256 好。

题外话

MD5 存在安全漏洞，是已退役哈希算法，在有安全要求的项目中不推荐使用。