c# - C# 对象的 32 位哈希函数

Question

我希望在我的所有类中覆盖对象的 GetHashCode() 方法。此方法返回一个 Int32。我所知道的所有加密哈希函数的返回值都不适合 32 位整数。我想尽可能避免碰撞。我应该截断像 SHA 之类的安全散列，还是使用 32 位散列？如果使用 32 位哈希，最好使用什么 32 位哈希？

Answer 1

只是给大家一点信息。不同 .NET 平台上的 GetHashCode() 不同。例如:.NET 2.0 中的“Hello”.GetHashCode() 与 .NET 4.0 中的“Hello”.GetHashCode() 会产生不同的结果。因此，为什么不能使用 .NET 开箱即用地序列化 HashTable 或 Dictionaries。

实现您自己的哈希算法可提供跨平台的一致性。只是想让你知道，你不想小于 Int32。我的建议是坚持使用 Int64(长)。这样你就有更少的冲突，这是散列的目标 :) 这是我几年前写的一个库。每个哈希算法都有其优点和缺点(速度与最少碰撞)。此特定版本使用字符串作为输入，但您可以根据需要对其进行修改:

static public class StringHash
    {
        //---------------------------------------------------------------------
        static public Int64 RSHash(String str)
        {
            const Int32 b = 378551;
            Int32 a = 63689;
            Int64 hash = 0;

            for (Int32 i = 0; i < str.Length; i++)
            {
                hash = hash * a + str[i];
                a = a * b;
            }

            return hash;
        }
        //---------------------------------------------------------------------
        static public Int64 JSHash(String str)
        {
            Int64 hash = 1315423911;

            for (Int32 i = 0; i < str.Length; i++)
            {
                hash ^= ((hash << 5) + str[i] + (hash >> 2));
            }

            return hash;
        }
        //---------------------------------------------------------------------
        static public Int64 ELFHash(String str)
        {
            Int64 hash = 0;
            Int64 x = 0;

            for (Int32 i = 0; i < str.Length; i++)
            {
                hash = (hash << 4) + str[i];

                if ((x = hash & 0xF0000000L) != 0)
                {
                    hash ^= (x >> 24);
                }
                hash &= ~x;
            }

            return hash;
        }
        //---------------------------------------------------------------------
        static public Int64 BKDRHash(String str)
        {
            const Int64 seed = 131; // 31 131 1313 13131 131313 etc..
            Int64 hash = 0;

            for (Int32 i = 0; i < str.Length; i++)
            {
                hash = (hash * seed) + str[i];
            }

            return hash;
        }
        //---------------------------------------------------------------------
        static public Int64 SDBMHash(String str)
        {
            Int64 hash = 0;

            for (Int32 i = 0; i < str.Length; i++)
            {
                hash = str[i] + (hash << 6) + (hash << 16) - hash;
            }

            return hash;
        }
        //---------------------------------------------------------------------
        static public Int64 DJBHash(String str)
        {
            Int64 hash = 5381;

            for (Int32 i = 0; i < str.Length; i++)
            {
                hash = ((hash << 5) + hash) + str[i];
            }

            return hash;
        }
        //---------------------------------------------------------------------
        static public Int64 DEKHash(String str)
        {
            Int64 hash = str.Length;

            for (Int32 i = 0; i < str.Length; i++)
            {
                hash = ((hash << 5) ^ (hash >> 27)) ^ str[i];
            }

            return hash;
        }
        //---------------------------------------------------------------------
        static public Int64 BPHash(String str)
        {
            Int64 hash = 0;

            for (Int32 i = 0; i < str.Length; i++)
            {
                hash = hash << 7 ^ str[i];
            }

            return hash;
        }
        //---------------------------------------------------------------------
        static public Int64 FNVHash(String str)
        {
            Int64 fnv_prime = 0x811C9DC5;
            Int64 hash = 0;

            for (Int32 i = 0; i < str.Length; i++)
            {
                hash *= fnv_prime;
                hash ^= str[i];
            }

            return hash;
        }
        //---------------------------------------------------------------------
        static public Int64 APHash(String str)
        {
            Int64 hash = 0xAAAAAAAA;

            for (Int32 i = 0; i < str.Length; i++)
            {
                if ((i & 1) == 0)
                {
                    hash ^= ((hash << 7) ^ str[i] * (hash >> 3));
                }
                else
                {
                    hash ^= (~((hash << 11) + str[i] ^ (hash >> 5)));
                }
            }

            return hash;
        }
    }