将深层嵌套散列展平为数组以进行 sha1 散列

Question

我想从 ruby 哈希计算一个唯一的 sha1 哈希。我考虑过

(深)Hash转数组
排序数组
通过空字符串加入数组
计算 sha1

考虑以下散列：

hash = {
  foo: "test",
  bar: [1,2,3]
  hello: {
    world: "world",
    arrays: [
      {foo: "bar"}
    ]
  }
}

如何将这种嵌套散列放入数组中，例如

[:foo, "test", :bar, 1, 2, 3, :hello, :world, "earth", :arrays, :my, "example"]

然后我会对数组进行排序，将其与 array.join("") 连接起来，然后像这样计算 sha1 哈希：

require 'digest/sha1'
Digest::SHA1.hexdigest hash_string

我怎样才能像上面描述的那样展平散列？
这个已经有 gem 了吗？
有没有更快/更简单的方法来解决这个问题？我有大量对象要转换 (~700k)，因此性能很重要。

编辑

我从下面的答案中找出的另一个问题是这两个哈希值：

a = {a: "a", b: "b"}
b = {a: "b", b: "a"}

当展平散列并对其进行排序时，这两个散列产生相同的输出，即使 a == b => false.

编辑 2

整个事情的用例是产品数据比较。产品数据存储在哈希中，然后序列化并发送到创建/更新产品数据的服务。

我想检查产品数据内部是否有任何更改，因此我从产品内容生成一个散列并将其存储在数据库中。下次加载相同的产品时，我再次计算哈希值，将其与数据库中的哈希值进行比较，并决定该产品是否需要更新。

Answer 1

编辑：如您所详述，具有不同顺序的键的两个散列应该给出相同的字符串。我会重新打开哈希 class 以添加我的新自定义展平方法：

class Hash
  def custom_flatten()
    self.sort.map{|pair| ["key: #{pair[0]}", pair[1]]}.flatten.map{ |elem| elem.is_a?(Hash) ? elem.custom_flatten : elem }.flatten
  end
end

解释：

sort将散列转换成对的排序数组（用于比较具有不同键顺序的散列）
.map{|pair| ["key: #{pair[0]}", pair[1]]} 是在最终展平数组中区分键和值的技巧，以避免 {a: {b: {c: :d}}}.custom_flatten == {a: :b, c: :d}.custom_flatten
flatten 将数组数组转换为单个值数组
map{ |elem| elem.is_a?(Hash) ? elem.custom_flatten : elem } 在剩余的任何子哈希上回调 fully_flatten。

那么你只需要使用:

require 'digest/sha1'
Digest::SHA1.hexdigest hash.custom_flatten.to_s

Answer 2

我不知道 gem 可以做您正在寻找的事情。 ruby 中有一个 Hash#flatten 方法，但它不会递归地展平嵌套哈希。这是一个直接的递归函数，它将按照您在问题中请求的方式展平：

def completely_flatten(hsh)
  hsh.flatten(-1).map{|el| el.is_a?(Hash) ? completely_flatten(el) : el}.flatten
end

这将产生

hash = {
  foo: "test",
  bar: [1,2,3]
  hello: {
    world: "earth",
    arrays: [
      {my: "example"}
    ]
  }
}

completely_flatten(hash) 
#=> [:foo, "test", :bar, 1, 2, 3, :hello, :world, "earth", :arrays, :my, "example"]

要获得您正在寻找的字符串表示形式（在进行 sha1 哈希之前），请在排序之前将数组中的所有内容转换为字符串，以便可以对所有元素进行有意义的比较，否则您将收到错误消息：

hash_string = completely_flatten(hash).map(&:to_s).sort.join
#=> "123arraysbarearthexamplefoohellomytestworld"

Answer 3

使用 Marshal 进行快速序列化

您没有阐明在散列之前更改数据结构的有用理由。因此，您应该考虑使用 marshaling 来提高速度，除非您的数据结构包含不受支持的对象，例如绑定或过程。例如，使用语法更正后的 hash 变量：

require 'digest/sha1'

hash = {
  foo: "test",
  bar: [1,2,3],
  hello: {
    world: "world",
    arrays: [
      {foo: "bar"}
    ]
  }
}
Digest::SHA1.hexdigest Marshal.dump(hash)
#=> "f50bc3ceb514ae074a5ab9672ae5081251ae00ca"

Marshal 通常比其他序列化选项更快。如果您只需要速度，那将是您最好的选择。但是，由于其他原因，您可能会发现 JSON、YAML 或简单的#to_s 或#inspect 更能满足您的需求。只要您比较对象的相似表示，散列对象的内部格式在很大程度上与确保您拥有唯一或未修改的对象无关。

Answer 4

任何基于展平散列的解决方案对于嵌套散列都将失败。一个健壮的解决方案是递归显式地对每个散列的键进行排序（从 ruby 1.9.x 开始，保留散列键顺序），然后将其序列化为字符串并对其进行消化。

  def canonize_hash(h)
    r = h.map { |k, v| [k, v.is_a?(Hash) ? canonize_hash(v) : v] }
    Hash[r.sort]
  end

  def digest_hash(hash)
    Digest::SHA1.hexdigest canonize_hash(hash).to_s
  end

  digest_hash({ foo: "foo", bar: "bar" })
  # => "ea1154f35b34c518fda993e8bb0fe4dbb54ae74a"
  digest_hash({ bar: "bar", foo: "foo" })
  # => "ea1154f35b34c518fda993e8bb0fe4dbb54ae74a"

Answer 5

问题是如何"flatten" 哈希。关于 sha1，还有第二个隐含的问题，但是根据 SO 规则，需要在单独的问题中解决。您可以 "flatten" 任何散列或数组，如下所示。

代码

def crush(obj)
  recurse(obj).flatten
end

def recurse(obj)
  case obj
  when Array then obj.map { |e| recurse e }
  when Hash  then obj.map { |k,v| [k, recurse(v)] }
  else obj
  end
end

例子

crush({
  foo: "test",
  bar: [1,2,3],
  hello: {
    world: "earth",
    arrays: [{my: "example"}]
  }
})
  #=> [:foo, "test", :bar, 1, 2, 3, :hello, :world, "earth", :arrays, :my, "example"]

crush([[{ a:1, b:2 }, "cat", [3,4]], "dog", { c: [5,6] }])
  #=> [:a, 1, :b, 2, "cat", 3, 4, "dog", :c, 5, 6]

将深层嵌套散列展平为数组以进行 sha1 散列

Flatten deep nested hash to array for sha1 hashing

ruby

hash

sha1

sha

使用 Marshal 进行快速序列化