.net - 在对象图上创建校验和

Question

此问题与 this one 有关但我认为应该单独问。

我有一个复杂的对象实例图。现在我想在内存中直接在这个对象图上创建一个校验和，以检测自上次将校验和与对象图一起保存以来是否对其进行了更改。校验和计算应该很快并且不应该消耗太多内存。

据我所知，最好的解决方案可能是在对象图的二进制序列化形式上生成一个加密 key (如果我错了，请纠正我)。但这带来了几个问题:

我应该如何序列化对象？它必须快速而不是
消耗太多内存。还有它
必须始终可靠地序列化
一样的方法。如果我使用 .NET 默认序列化，如果实际数据相同，我真的可以确定创建的二进制流始终相同吗？我对此表示怀疑。

那么，有什么替代方法可以实现不需要很长时间的序列化呢？

更新:

您如何看待这种方法:

浏览图表和
图中的 foreach 对象创建一个
标准 int 哈希码使用
this算法(但不包括表示图中节点的引用类型成员)。添加每个
哈希码到整数列表

将整数列表转换为字节
数组

在字节数组上创建哈希
使用 MD5、CRC 或类似的

提到的 GetHashCode 算法应该快速计算出一个哈希码，该哈希码对于只考虑其原始成员的单个对象来说是非常安全的。基于此，字节数组也应该是对象图和 MD5/CRC 散列的相当安全的表示。

Answer 1

您可以使用 http://code.google.com/p/protobuf-net/ 而不是二进制序列化然后计算它的加密哈希。据说 protobuf 比 Bin Ser 更紧凑(参见示例 http://code.google.com/p/protobuf-net/wiki/Performance )。

我会补充一点，考虑到你真的不需要序列化。最好使用反射并“导航”通过计算您的哈希的对象(以相同的方式各种序列化程序“遍历”您的对象)。参见示例 Using reflection in C# to get properties of a nested object

经过深思熟虑，听了@Jon 的话，我可以告诉你，我的“次要”想法(使用反射)非常非常非常困难，除非你想花一周时间编写对象解析器。是的，它是可行的......但是在计算哈希之前你会给数据什么表示？要清楚:

two strings
"A"
"B"

显然是“A”，“B”!=“AB”，“”。但是 MD5("A") 结合了 MD5("B") == MD5("AB") 结合了 MD5("")。可能最好的方法是在前面加上长度(所以使用 Pascal/BSTR 表示法)

和null值(value)观？他们有什么“序列化”值(value)？另一个问题。显然，如果您将字符串序列化为长度+字符串(以便解决前面的问题)，您可以将 null 简单地序列化为 "null" (没有长度)...对象呢？你会在前面加上一个对象类型 ID 吗？肯定会更好。否则，可变长度对象可能会造成与字符串一样的困惑。

使用 BinaryFormatter(甚至可能是 protobuf-net)，您不必真正将序列化对象保存在某处，因为它们都支持流式传输......一个例子

public class Hasher : Stream
{
    protected readonly HashAlgorithm HashAlgorithm;

    protected Hasher(HashAlgorithm hash)
    {
        HashAlgorithm = hash;
    }

    public static byte[] GetHash(object obj, HashAlgorithm hash)
    {
        var hasher = new Hasher(hash);

        if (obj != null)
        {
            var bf = new BinaryFormatter();
            bf.Serialize(hasher, obj);
        }
        else
        {
            hasher.Flush();
        }

        return hasher.HashAlgorithm.Hash;
    }

    public override bool CanRead
    {
        get { throw new NotImplementedException(); }
    }

    public override bool CanSeek
    {
        get { throw new NotImplementedException(); }
    }

    public override bool CanWrite
    {
        get { return true; }
    }

    public override void Flush()
    {
        HashAlgorithm.TransformFinalBlock(new byte[0], 0, 0);
    }

    public override long Length
    {
        get { throw new NotImplementedException(); }
    }

    public override long Position
    {
        get
        {
            throw new NotImplementedException();
        }
        set
        {
            throw new NotImplementedException();
        }
    }

    public override int Read(byte[] buffer, int offset, int count)
    {
        throw new NotImplementedException();
    }

    public override long Seek(long offset, SeekOrigin origin)
    {
        throw new NotImplementedException();
    }

    public override void SetLength(long value)
    {
        throw new NotImplementedException();
    }

    public override void Write(byte[] buffer, int offset, int count)
    {
        HashAlgorithm.TransformBlock(buffer, offset, count, buffer, offset);
    }
}

static void Main(string[] args)
{
    var list = new List<int>(100000000);

    for (int i = 0; i < list.Capacity; i++)
    {
        list.Add(0);
    }

    Stopwatch sw = Stopwatch.StartNew();
    var hash = Hasher.GetHash(list, new MD5CryptoServiceProvider());
    sw.Stop();
    Console.WriteLine(sw.ElapsedMilliseconds);
}

我定义了 Hasher接收对象的序列化(一次一 block )并在“流模式”下计算哈希的类。内存使用量为 O(1)。时间显然是 O(n) (其中 n 是序列化对象的“大小”)。

如果您想使用 protobuf(但请注意，对于复杂对象，它需要用其属性(或 WCF 属性或...)标记它们)

public static byte[] GetHash<T>(T obj, HashAlgorithm hash)
{
    var hasher = new Hasher(hash);

    if (obj != null)
    {
        ProtoBuf.Serializer.Serialize(hasher, obj);
        hasher.Flush();
    }
    else
    {
        hasher.Flush();
    }

    return hasher.HashAlgorithm.Hash;
}

唯一的“大”区别是 protobuf 不 Flush流，所以我们必须这样做，并且它确实希望输入根对象而不是简单的“对象”。

哦...对于您的问题:

How should I serialize the object? It must be fast and not consume too much memory. Also it must reliably always be serialized the same way. If I use the .NET default serialization can I really be sure that the created binary stream is always the same if the acutal data is the same? I doubt it.

List<int> l1 = new List<int>();

byte[] bytes1, bytes2;

using (MemoryStream ms = new MemoryStream())
{
    new BinaryFormatter().Serialize(ms, l1);
    bytes1 = ms.ToArray();
}

l1.Add(0);
l1.RemoveAt(0);

using (MemoryStream ms = new MemoryStream())
{
    new BinaryFormatter().Serialize(ms, l1);
    bytes2 = ms.ToArray();
}

Debug.Assert(bytes1.Length == bytes2.Length);

可以这样说:Debug.Assert将失败。这是因为 List “保存”了一些内部状态(例如版本)。这使得二进制序列化和比较非常困难。您最好使用“可编程”序列化程序(如 proto-buf)。你告诉他要序列化哪些属性/字段，他会序列化它们。

So what would be an alternative way to serialize that doesn't take to long to implement?

Proto-buf... 或 DataContractSerializer(但它很慢)。可以想象，数据序列化没有 Elixir 。