如何在仅最后几个字节发生变化的golang数据中有效地散列（SHA 256）

Question

假设您有80个字节的数据，并且只有最后4个字节在不断变化，那么如何使用Go高效地哈希80个字节。本质上，前76个字节是相同的，而后4个字节则在不断变化。理想情况下，您希望保留前76个字节的哈希摘要的副本，而只需更改后4个字节即可。

Answer 1

您可以在Go Playground尝试以下示例。基准结果在最后。

注意：以下实现不能安全地并发使用；我故意使它们变得更简单，更快。

仅使用公共API时最快（始终对所有输入进行哈希处理）

Go的哈希算法的一般概念和接口就是该hash.Hash接口。这不允许您保存哈希器的状态以及返回或倒回已保存的状态。因此，使用Go标准库的公共哈希API，您始终必须从头开始计算哈希。

公共API提供的方法是，使用该Hash.Reset()方法重用已经构造的哈希器，以计算新输入的哈希值。这样很好，因此不需要（内存）分配即可计算多个哈希值。另外，您还可以利用可传递到的可选切片，该切片Hash.Sum()用于将当前哈希附加到该切片。这样很好，因此不需要分配就可以接收哈希结果。

这是一个利用这些优势的示例：

type Cached1 struct {
    hasher hash.Hash
    result [sha256.Size]byte
}

func NewCached1() *Cached1 {
    return &Cached1{hasher: sha256.New()}
}

func (c *Cached1) Sum(data []byte) []byte {
    c.hasher.Reset()
    c.hasher.Write(data)
    return c.hasher.Sum(c.result[:0])
}

测试数据

我们将使用以下测试数据：

var fixed = bytes.Repeat([]byte{1}, 76)
var variantA = []byte{1, 1, 1, 1}
var variantB = []byte{2, 2, 2, 2}

var data = append(append([]byte{}, fixed...), variantA...)
var data2 = append(append([]byte{}, fixed...), variantB...)

var c1 = NewCached1()

首先，让我们获得真实的结果（以验证哈希器是否正常工作）：

fmt.Printf("%x\n", sha256.Sum256(data))
fmt.Printf("%x\n", sha256.Sum256(data2))

输出：

fb8e69bdfa2ad15be7cc8a346b74e773d059f96cfc92da89e631895422fe966a
10ef52823dad5d1212e8ac83b54c001bfb9a03dc0c7c3c83246fb988aa788c0c

现在，让我们检查一下Cached1哈希器：

fmt.Printf("%x\n", c1.Sum(data))
fmt.Printf("%x\n", c1.Sum(data2))

输出是相同的：

fb8e69bdfa2ad15be7cc8a346b74e773d059f96cfc92da89e631895422fe966a
10ef52823dad5d1212e8ac83b54c001bfb9a03dc0c7c3c83246fb988aa788c0c

甚至更快，但可能会中断（在以后的Go版本中）：仅对最后4个字节进行哈希处理

现在，让我们来看一个不太灵活的解决方案，该解决方案只真正计算一次前76个固定部分的哈希值。

crypto/sha256包的哈希器是未导出的sha256.digest类型（更确切地说是指向该类型的指针）：

// digest represents the partial evaluation of a checksum.
type digest struct {
    h     [8]uint32
    x     [chunk]byte
    nx    int
    len   uint64
    is224 bool // mark if this digest is SHA-224
}

digeststruct类型的值基本上可以保存哈希器的当前状态。

我们可能要做的是将固定的前76个字节送入哈希器，然后保存此struct值。当我们需要计算前80个字节相同的约80个字节数据的哈希值时，我们以保存的值作为起点，然后输入变化的后4个字节。

请注意，仅保存此结构值就足够了，因为它不包含指针，也没有描述符类型，例如切片和映射。否则，我们也必须复制这些副本，但是我们很“幸运”。因此，如果将来的实现crypto/sha256会添加例如指针或切片字段，则需要对该解决方案进行调整。

由于sha256.digest未导出，因此我们只能使用反射（reflect包）来实现我们的目标，这必然会增加计算的延迟。

执行此操作的示例实现：

type Cached2 struct {
    origv   reflect.Value
    hasherv reflect.Value
    hasher  hash.Hash

    result [sha256.Size]byte
}

func NewCached2(fixed []byte) *Cached2 {
    h := sha256.New()
    h.Write(fixed)

    c := &Cached2{origv: reflect.ValueOf(h).Elem()}
    hasherv := reflect.New(c.origv.Type())
    c.hasher = hasherv.Interface().(hash.Hash)
    c.hasherv = hasherv.Elem()

    return c
}

func (c *Cached2) Sum(data []byte) []byte {
    // Set state of the fixed hash:
    c.hasherv.Set(c.origv)

    c.hasher.Write(data)
    return c.hasher.Sum(c.result[:0])
}

测试它：

var c2 = NewCached2(fixed)
fmt.Printf("%x\n", c2.Sum(variantA))
fmt.Printf("%x\n", c2.Sum(variantB))

输出再次相同：

fb8e69bdfa2ad15be7cc8a346b74e773d059f96cfc92da89e631895422fe966a
10ef52823dad5d1212e8ac83b54c001bfb9a03dc0c7c3c83246fb988aa788c0c

这样就可以了。

“最终”最快的解决方案

Cached2如果不涉及反思，可能会更快。如果我们想要一个更快的解决方案，只需将sha256.digest类型及其方法的副本复制到我们的包中即可，因此我们可以直接使用它，而不必求助于反射。

如果这样做，我们将可以访问digeststruct值，并且可以简单地对其进行复制，例如：

var d digest
// init d
saved := d

恢复它就像：

d = saved

我只是简单地将crypto/sha256包“克隆” 到我的工作区，并出于演示目的更改/导出了digest类型Digest。然后使用这种mysha256.Digest类型，我实现Cached3如下：

type Cached3 struct {
    orig   mysha256.Digest
    result [sha256.Size]byte
}

func NewCached3(fixed []byte) *Cached3 {
    var d mysha256.Digest
    d.Reset()
    d.Write(fixed)

    return &Cached3{orig: d}
}

func (c *Cached3) Sum(data []byte) []byte {
    // Make a copy of the fixed hash:
    d := c.orig
    d.Write(data)
    return d.Sum(c.result[:0])
}

测试它：

var c3 = NewCached3(fixed)

fmt.Printf("%x\n", c3.Sum(variantA))
fmt.Printf("%x\n", c3.Sum(variantB))

再次输出是相同的。因此，这也有效。

基准测试

我们可以使用以下代码对性能进行基准测试：

func BenchmarkCached1(b *testing.B) {
    for i := 0; i < b.N; i++ {
        c1.Sum(data)
        c1.Sum(data2)
    }
}

func BenchmarkCached2(b *testing.B) {
    for i := 0; i < b.N; i++ {
        c2.Sum(variantA)
        c2.Sum(variantB)
    }
}

func BenchmarkCached3(b *testing.B) {
    for i := 0; i < b.N; i++ {
        c3.Sum(variantA)
        c3.Sum(variantB)
    }
}

基准测试结果（go test -bench . -benchmem）：

BenchmarkCached1-4   1000000     1569 ns/op     0 B/op    0 allocs/op
BenchmarkCached2-4   2000000      926 ns/op     0 B/op    0 allocs/op
BenchmarkCached3-4   2000000      872 ns/op     0 B/op    0 allocs/op

Cached2比大约值得注意的速度快41％Cached1。Cached3与Cached2另外6％的性能相比，只能带来“一点”的性能提升。Cached3是44％的速度比Cached1。

还要注意，所有解决方案都没有使用任何分配，这也很好。

结论

对于那额外的40％或44％，我可能不会选择Cached2或Cached3解决方案。当然，这实际上取决于性能对您的重要性。如果很重要，我认为该Cached2解决方案可以在最小的复杂性和明显的性能提升之间找到一个很好的折衷方案。它确实构成了威胁，因为将来的Go实现可能会破坏它。如果有问题，则Cached3可以通过复制当前实现来解决此问题（并稍微提高其性能）。