在对象图上创建校验和

Question

这个问题关系到这一个,但我认为应该分开询问.

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

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

1. 我该如何序列化对象？它必须快速且不会消耗太多内存.此外,它必须始终以相同的方式可靠地序列化.如果我使用.NET默认序列化,我真的可以确定如果实际数据相同,创建的二进制流总是相同的吗？我对此表示怀疑.
2. 那么序列化的另一种方法是什么呢？

更新:

您如何看待这种方法:

1. 浏览图形并使用此算法在图中创建标准的int哈希码 (但不包括表示图中节点的引用类型成员).将每个哈希码添加到整数列表
2. 将整数列表转换为字节数组
3. 使用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).

我要补充一点,考虑到你真的不需要序列化.最好使用Reflection并"浏览"计算哈希值的对象(与各种序列化程序"遍历"对象的方式相同).请参阅例如在C#中使用反射来获取嵌套对象的属性

经过深思熟虑,听到@Jon说的话,我可以告诉你,我的"次要"想法(使用Reflection)是非常非常困难的,除非你想花一个星期写一个对象解析器.是的,它是可行的...但是在计算哈希之前你会给数据什么样的代表？要明确:

two strings
"A"
"B"

显然是"A","B"!="AB","".但是MD5("A")与MD5("B")= MD5("AB")组合与MD5("")组合.可能最好的是预先设置长度(所以使用Pascal/BSTR表示法)

和null价值观？他们有什么"序列化"的价值？另一个问题.显然,如果你将一个字符串序列化为长度+字符串(所以为了解决上一个问题),你可以将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接收对象序列化(一次一个)的类,并以"流模式"计算哈希值.内存使用是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流,所以我们必须这样做,并且TRULY想要输入根对象而不是简单的"对象".

哦......还有你的问题:

我该如何序列化对象？它必须快速且不会消耗太多内存.此外,它必须始终以相同的方式可靠地序列化.如果我使用.NET默认序列化,我真的可以确定如果实际数据是相同的,创建的二进制流总是相同的吗？我对此表示怀疑.

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"保存"了一些内部状态(例如版本).这使得Binary Serialize和比较非常困难.你最好使用"可编程"串行器(如proto-buf).你告诉他要序列化的属性/字段,并将它序列化.

那么序列化的另一种方法是什么呢？

Proto-buf ...或DataContractSerializer(但它很慢).可以想象,数据序列化没有灵丹妙药.

Answer 2

您如何看待这种方法:

• 浏览图形并使用此算法在图中创建标准的int哈希码(但不包括表示图中节点的引用类型成员).
• 将每个哈希码添加到整数列表
• 将整数列表转换为字节数组
• 使用MD5,CRC或类似方法在字节数组上创建哈希

这种方法的想法非常接近我认为最好的方法,但它可以使用一些抛光.

哈希

考虑到你更喜欢速度超过准确性,并且int每个项目的大小哈希码为避免碰撞留下了足够的空间,哈希码算法的选择似乎是正确的.排除参与图表的参考类型意味着我们抛弃了一些信息; 请参阅下文了解更多信息.

改进节点哈希

不考虑连接到我们正在散列的节点的其他节点的想法是正确的,但也许我们可以做得比简单地丢弃所有这些信息更好？我们不想考虑其他节点的哈希码(它们也将自己进行哈希处理),但是我们丢弃了图边缘提供的信息:内部数据X连接到N的节点的哈希码对于数据X连接到M个其他节点的节点,其他节点不应该相同.

如果您有一种廉价的方法来考虑边缘数据的一部分,请使用它.例如,如果图形是定向的,那么您可以将为每个节点计算的哈希码添加到其他节点的边缘数量.

聚合哈希码

创建一个哈希码列表将是将哈希码加在一个中的中间方法long(非常快并将一些额外的信息保存到总和中int)并创建一个依赖于图中项目总顺序的哈希码列表.如果您期望图表中有很多项目,那么求和可能更合适(我先尝试一下,看看它是否足够碰撞); 如果图表没有很多项目(比如<1000),那么我首先尝试总订单方法.记得在创建列表时为列表分配足够的内存(或者只是使用数组); 你已经知道它的最终长度,这是一个自由的速度增加.

生成固定大小的哈希

如果已将哈希码总结为基元,则根本不需要此步骤.否则,将列表散列为byte[]我认为最好的列表.由于与创建列表相比,散列字节将花费很少的时间,因此您可能希望使用比md5或crc32更大的散列函数来减少冲突,而不会影响实际性能.

提高最终的哈希质量

在得到这个"最终"哈希之后,我会在哈希图中添加或附加哈希图中的项目数作为固定大小的十六进制编码字符串,因为:

• 它可能有助于减少碰撞(多少取决于图的性质)
• 我们已经知道图中的项目数(我们只是对它们进行了哈希)所以它是一个O(1)操作

定义总订单

如果没有严格定义图表中项目的处理顺序,那么门是开放的假阴性:两个应该散列到相同值的图形不会因为即使它们在逻辑上等价,也是哈希的实现function选择以不同的顺序处理每个项目的哈希值.只有在使用列表时才会出现此问题,因为添加是可传递的,因此"添加到long方法"不受它的影响.

要解决这个问题,您需要以明确定义的顺序处理图中的节点.这可能是一个很容易从节点的数据结构产生的顺序(例如像树上的预先遍历遍历)和/或其他信息(例如,每个节点的类名或节点类型,节点ID,如果存在等).

由于对图表进行预处理以产生总订单需要一些时间,因此您可能需要根据我上面提到的假阴性结果所产生的成本进行权衡.此外,如果图表足够大,那么这个讨论可能没有实际意义,因为节点哈希码求和方法更适合您的需求.