Хеширование нескольких значений в golang

В настоящее время я работаю над приложением, которое должно кэшировать различные ресурсы. Различные типы ресурсов имеют обработчики, которые будут знать, какие данные имеют отношение к определению, нужно ли нам перестраивать ресурс или мы можем извлечь его из кэша. Для этого обработчики должны генерировать хэш всех соответствующих данных для кэширования. В зависимости от контекста эти данные могут быть примитивами (int, float, ...), строками, слайсами, структурами и картами. Так что почти все. Количество объектов, используемых для хеширования, также может варьироваться.

Чтобы вычислить этот хэш в обработчиках, я создал функцию хеширования с переменными параметрами типа interface{},

Мой текущий подход заключается в следующем:

func Hash(objs ...interface{})([]byte) {
    // Use MD5 because it's fast and is reasonably enough protected against accidental collisions.
    // There is no scenario here where intentional created collisions could do harm.
    digester := crypto.MD5.New()

    encoder := gob.NewEncoder(digester)
    encoder.Encode(objs) // In real life one would handle that error

    return digester.Sum(make([]byte, 0))
}

Это работает. Но есть несколько вещей, которые доставляют мне головную боль с этой реализацией. Поскольку я не уверен, что gob всегда будет вести себя детерминистически, для текущей версии, которая, кажется, имеет место, но, как указывает ссылочный ответ, между версиями могут быть изменения. Согласно документации для gob, значения по умолчанию (0 для целых, пустые строки, nil, ...) будут опущены при транспортировке структур. Также все значения int будут передаваться как общие числа. Так что unit64 и int будут одинаковыми. Я не могу думать о фактической проблеме с этим для моего сценария использования, но это пахнет источником неприятностей.

Теперь, если бы я написал эту функцию с нуля, я бы правильно ее проигнорировал, перебрал структуру с помощью отражения и создал дерево хеширования. Но я не хочу этого делать.

Я почти уверен, что я не первый, кто придерживается этих требований, но я не смог найти в Интернете ни одного хорошо протестированного кода go, который решает эту проблему.

аппендикс

Также см.: https://crypto.stackexchange.com/questions/10058/how-to-hash-a-list-of-multiple-items

Это не так тривиально, как может показаться. Простое объединение данных, как указал Адриан, не сработает, потому что тогда Hash("12", "3") а также Hash("123") будет генерировать тот же хэш. Одним из возможных решений является предварительное добавление длины данных (и количества элементов списков) перед хэшированием или создание дерева хешей, но я не могу придумать надежного способа сделать это со сложными структурами данных, без написание большого количества кода отражения, который обрабатывает все различные случаи (целые числа, числа с плавающей запятой, строки, структуры, фрагменты,...) и проходит по всей структуре. Я хочу избежать этого, потому что есть много особых случаев, которые можно наблюдать, и это кажется мне ненужным сложным. Вот почему я попытался решить проблему с помощью сериализации, которая позаботится о большинстве проблем, описанных выше. Я просто не уверен, есть ли какие-то недостатки использования gob в этом сценарии и нет ли более разумного решения проблемы.

Источник

3 ответа

Возможно добавить, чтобы добавить к ответу Адриана. Если вы добавите fmt.Fprintf(digester, reflect.TypeOf(ob)) перед каждым объектом. Это сделало бы Hash("12", "3") и Hash("123") разными.

основной пакет

import (
    "crypto"
    _ "crypto/md5"
    "fmt"
    "reflect"
)

func main() {
    fmt.Printf("%x\n", Hash("12", "3"))
    fmt.Printf("%x\n", Hash("123"))
}

func Hash(objs ...interface{}) []byte {
    digester := crypto.MD5.New()
    for _, ob := range objs {
        fmt.Fprint(digester, reflect.TypeOf(ob))
        fmt.Fprint(digester, ob)
    }
    return digester.Sum(nil)
}

Выход:

c3d5dcf1d7540d3e46e7d7b5a8c6e8ae
787ca7e12a2fa991cea5051a64b49d0c

https://play.golang.org/p/nufD3wTJkb

Источник

Хэш-провайдеры внедряютio.WriterЭто означает, что вы можете просто записывать в них данные по мере необходимости - вам не нужно делать все это за один вызов Sum:

for _,ob := range objs {
    fmt.Fprint(digester, ob)
}
return digester.Sum(nil)

Пример рабочей площадки: https://play.golang.org/p/HtObhrmoaP

Если вам нужно поддерживать не примитивные типы, вы можете использовать что-то вроде:

fmt.Fprintf(digester, "%+v", ob)

Или даже просто:

json.NewEncoder(digester).Encode(&objs)

подобно gob, выход json может меняться между версиями Go, но это кажется гораздо менее вероятным, поскольку JSON является очень стабильным форматом с очень стабильной реализацией.

Источник

Это не решит проблему с сериализацией, но хэширование нескольких байтовых срезов совсем не сложно.

Это называется объединением хешей.

Одним из практических способов объединения хэшей является их операция XOR, но вы также можете использовать другую функцию (например, хеш-функцию над хеш-значениями). Просто убедитесь, что любое полученное вами хэш-значение будет равномерно распределено.

Вот полный пример:

      package main

import (
    "crypto/md5"
    "fmt"
    "hash"
)

func main() {
    fmt.Printf("%x\n", HashArray(md5.New, []byte("12"), []byte("3")))
    fmt.Printf("%x\n", HashArray(md5.New, []byte("123")))
}

func HashArray(newH func() hash.Hash, values ...[]byte) []byte {
    h := newH()
    result := h.Sum(nil)
    for _, v := range values {
        next := HashValue(newH, v)
        // XORing to combine hashes
        for i, _ := range result {
            result[i] ^= next[i]
        }
    }
    return result
}

func HashValue(newH func() hash.Hash, v []byte) []byte {
    h := newH()
    h.Write(v)
    return h.Sum(nil)
}

Производит:

      fadc9070abb527a36b97268885a09f9d
f43135bb2359b55f7fcb0e8dc1db090e

(одна и та же первая буква — совпадение)

Источник
Другие вопросы по тегам