1

编辑：64 位或 128 位也可以。由于某种原因，我的大脑刚刚跳到 32 位，以为这就足够了。

我有一个结构，主要由数值（int、decimal）和 3 个字符串组成，每个字符串不超过 12 个字母字符。我正在尝试创建一个可以用作哈希码的整数值，并尝试快速创建它。一些数值也可以为空。

似乎 BitVector32 或 BitArray 将是用于此努力的有用实体，但我只是不确定如何在此任务中使它们符合我的意愿。我的结构包含 3 个字符串、12 个小数（其中 7 个可以为空）和 4 个整数。

为了简化我的用例，假设您有以下结构：

public struct Foo
{
    public decimal MyDecimal;
    public int? MyInt;
    public string Text;
}

我知道我可以获得每个值的数字标识符。从数值的角度来看，MyDecimal 和 MyInt 当然是独一无二的。该字符串有一个 GetHashCode() 函数，该函数将返回一个通常唯一的值。

那么，每个都有一个数字标识符，是否可以生成一个唯一标识该结构的哈希码？例如，我可以每次比较 2 个包含相同值的不同 Foo，并获得相同的哈希码（无论应用程序域、重新启动应用程序、一天中的时间、木星卫星的对齐方式等）。

哈希将是稀疏的，因此我预计我的用例不会发生冲突。

有任何想法吗？我第一次运行它时，我将所有内容都转换为字符串表示形式，将其连接起来，并使用内置的 GetHashCode() 但这似乎非常……低效。

编辑：更多背景信息。结构数据被传递到 web 客户端，客户端对包含的值、字符串构造等进行大量计算以重新渲染页面。前面提到的 19 个字段结构代表一个信息单元，每个页面可以有多个单元。我想对渲染结果进行一些客户端缓存，因此如果我从服务器看到相同的哈希标识符，我可以快速重新渲染一个单元，而无需在客户端重新计算。JavaScript 数值都是 64 位的，所以我想我的 32 位约束是人为的和限制性的。64 位可以工作，或者如果我可以在服务器上将它分成两个 64 位值，我想甚至是 128 位。

4

5 回答 5

3

好吧，即使在稀疏表中，也应该更好地为冲突做好准备，具体取决于“稀疏”的含义。

哈希冲突概率（均匀分布）

您需要能够对您将同时散列的数据做出非常具体的假设，才能用 32 位击败该图。

使用 SHA256。您的哈希值将不依赖于 CLR 版本，并且不会发生冲突。好吧，你仍然会有一些，但比陨石撞击的频率要低，所以你可以承受不去预料的后果。

于 2012-04-26T20:42:51.210 回答
1

我建议你看看这里和这里的两件事。我认为您无法保证仅使用 32 位就不会发生冲突。

于 2012-04-26T20:06:35.680 回答
1

散列函数定义的散列码并不意味着是唯一的。它们只是为了尽可能均匀地分布在所有结果值中。获取对象的哈希码是一种快速检查两个对象是否不同的方法。如果两个对象的哈希码不同，那么这些对象就不同。但是，如果哈希码相同，则必须深入比较对象才能确定。哈希码的主要用途是在所有基于哈希的集合中，它们可以实现接近 O(1) 的检索速度。

所以从这个角度来看，你GetHashCode不必很复杂，事实上它不应该。它必须在非常快速和产生均匀分布的值之间取得平衡。如果获取哈希码的时间太长，那么它就变得毫无意义，因为深度比较的优势已经消失。如果在另一个极端，哈希码总是1例如（快速点亮）它会在每种情况下导致深度比较，这使得这个哈希码也毫无意义。

所以要保持平衡，不要试图想出一个完美的哈希码。调用GetHashCode您的所有（或大多数）成员，并使用Xor运算符将​​结果与按位移运算符<<或>>. 框架类型已经GetHashCode相当优化，尽管它们不能保证在每个应用程序运行中都是相同的。不能保证，但它们也不必改变，而且很多都不需要。使用反射器来确保或根据反射代码创建自己的版本。

在您的特定情况下，仅通过查看其哈希码来确定您是否已经处理了一个结构有点冒险。哈希值越好，风险越小，但仍然如此。最终且唯一唯一的哈希码是……数据本身。使用哈希码时，您还必须重写Object.Equals以使您的代码真正可靠。

于 2012-04-26T21:22:17.140 回答
0

我相信 .NET 中的常用方法是对结构的每个成员调用 GetHashCode 并对结果进行异或运算。

但是，我不认为 GetHashCode 声称在不同的应用程序域中为相同的值生成相同的哈希值。

您能否在您的问题中提供更多信息，说明您为什么需要此哈希值以及为什么它需要随着时间的推移保持稳定、不同的应用程序域等。

于 2012-04-26T20:11:01.320 回答
0

你追求什么目标？如果它是性能，那么您应该使用一个类，因为每当您将结构作为函数参数传递时，它都会按值复制。

3 个字符串，12 个小数（其中 7 个可以为空）和 4 个整数。

在 64 位机器上，指针大小为 8 个字节，十进制占用 16 个字节，int 占用 4 个字节。忽略填充结构将使用每个实例 232 字节。与建议的最大 16 字节相比，这要大得多，这在性能方面是有意义的（由于其对象标头，类占用至少 16 字节，...）

如果您需要该值的指纹，您可以使用像 SHA256 这样的加密级哈希算法，它将产生一个 16 字节的指纹。这仍然不是唯一的，但至少足够独特。但这也会花费相当多的性能。

Edit1： 在您明确需要哈希码来识别 Java Script Web 客户端缓存中的对象后，我感到很困惑。为什么服务器再次发送相同的数据？让服务器更智能地只发送客户端尚未收到的数据不是更简单吗？

在您的情况下，可以使用 SHA 哈希算法来创建一些对象实例标签。

为什么你需要一个哈希码？如果您的目标是以内存有效的方式存储值，您可以创建一个 FooList ，它使用字典仅存储一次相同的值，并使用和 int 作为查找键。

using System;
using System.Collections.Generic;

namespace MemoryEfficientFoo
{
    class Foo // This is our data structure 
    {
        public int A;
        public string B;
        public Decimal C;
    }

    /// <summary>
    /// List which does store Foos with much less memory if many values are equal. You can cut memory consumption by factor 3 or if all values 
    /// are different you consume 5 times as much memory as if you would store them in a plain list! So beware that this trick
    /// might not help in your case. Only if many values are repeated it will save memory.
    /// </summary>
    class FooList : IEnumerable<Foo> 
    {
        Dictionary<int, string> Index2B = new Dictionary<int, string>();
        Dictionary<string, int> B2Index = new Dictionary<string, int>();

        Dictionary<int, Decimal> Index2C = new Dictionary<int, decimal>();
        Dictionary<Decimal,int> C2Index = new Dictionary<decimal,int>();

        struct FooIndex
        {
            public int A;
            public int BIndex;
            public int CIndex;
        }

        // List of foos which do contain only the index values to the dictionaries to lookup the data later.
        List<FooIndex> FooValues = new List<FooIndex>();

        public void Add(Foo foo)
        {
            int bIndex;
            if(!B2Index.TryGetValue(foo.B, out bIndex))
            {
                bIndex = B2Index.Count;
                B2Index[foo.B] = bIndex;
                Index2B[bIndex] = foo.B;
            }

            int cIndex;
            if (!C2Index.TryGetValue(foo.C, out cIndex))
            {
                cIndex = C2Index.Count;
                C2Index[foo.C] = cIndex;
                Index2C[cIndex] = cIndex;
            }

            FooIndex idx = new FooIndex
            {
                A = foo.A,
                BIndex = bIndex,
                CIndex = cIndex
            };

            FooValues.Add(idx);
        }

        public Foo GetAt(int pos)
        {
            var idx = FooValues[pos];
            return new Foo
            {
                A = idx.A,
                B = Index2B[idx.BIndex],
                C = Index2C[idx.CIndex]
            };
        }

        public IEnumerator<Foo> GetEnumerator()
        {
            for (int i = 0; i < FooValues.Count; i++)
            {
                yield return GetAt(i);
            }
        }
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }


    class Program
    {
        static void Main(string[] args)
        {
            FooList list = new FooList();
            List<Foo> fooList = new List<Foo>();
            long before = GC.GetTotalMemory(true);
            for (int i = 0; i < 1000 * 1000; i++)
            {
                list
                //fooList
                    .Add(new Foo
                    {
                        A = i,
                        B = "Hi",
                        C = i
                    });

            }
            long after = GC.GetTotalMemory(true);
            Console.WriteLine("Did consume {0:N0}bytes", after - before);
        }
    }
}

可以在此处找到类似的内存节省列表

于 2012-04-26T21:13:33.533 回答