检查两个哈希表是否具有相同的键集

Question

如何高效地检查两个哈希表h1和h2是否具有相同的键集（无视顺序）？是否有比我发布的答案更快或更简洁但效率相近的方法？

- sawa

---

我认为你应该在问题中提到这一点。而且我会将解决方案作为问题的一部分发布，而不是作为答案。 - Sergio Tulentsev

我并不认为我的答案比其他任何答案更特别。我认为将所有可能的答案，包括我的答案，列在一起比在问题中随机选择一个（我的）更好。 - sawa

我认为这只是纯粹的方便。你写了“难道比我的答案更简单吗？”现在我必须向下滚动，解析答案，并找到你的答案。这对我来说是额外的工作，没有任何理由。 - Sergio Tulentsev

一个有点离题的问题：这是纯粹为了好玩还是你有非常大的哈希（并且你已经对代码进行了分析），改进代码的这一部分将会给你巨大的性能提升？ - Tomek Wałkuski

我会反复使用这个方法来处理不是很大的哈希值。 - sawa

Answer 1

好的，让我们打破所有“生活智慧”和可移植性的规则。MRI的C API开始发挥作用。

/* Name this file superhash.c. An appropriate Makefile is attached below. */
#include <ruby/ruby.h>

static int key_is_in_other(VALUE key, VALUE val, VALUE data) {
  struct st_table *other = ((struct st_table**) data)[0];
  if (st_lookup(other, key, 0)) {
    return ST_CONTINUE;
  } else {
    int *failed = ((int**) data)[1];
    *failed = 1;
    return ST_STOP;
  }
}

static VALUE hash_size(VALUE hash) {
  if (!RHASH(hash)->ntbl)
    return INT2FIX(0);
  return INT2FIX(RHASH(hash)->ntbl->num_entries);
}

static VALUE same_keys(VALUE self, VALUE other) {
  if (CLASS_OF(other) != rb_cHash)
    rb_raise(rb_eArgError, "argument needs to be a hash");
  if (hash_size(self) != hash_size(other))
    return Qfalse;
  if (!RHASH(other)->ntbl && !RHASH(other)->ntbl)
    return Qtrue;
  int failed = 0;
  void *data[2] = { RHASH(other)->ntbl, &failed };
  rb_hash_foreach(self, key_is_in_other, (VALUE) data);
  return failed ? Qfalse : Qtrue;
}

void Init_superhash(void) {
  rb_define_method(rb_cHash, "same_keys?", same_keys, 1);
}

这是一个 Makefile 文件。

CFLAGS=-std=c99 -O2 -Wall -fPIC $(shell pkg-config ruby-1.9 --cflags)
LDFLAGS=-Wl,-O1,--as-needed $(shell pkg-config ruby-1.9 --libs)
superhash.so: superhash.o
    $(LINK.c) -shared $^ -o $@

一个人工的、合成的和简单化的基准测试展示了以下内容。

require 'superhash'
require 'benchmark'
n = 100_000
h1 = h2 = {a:5, b:8, c:1, d:9}
Benchmark.bm do |b|
  # freemasonjson's state of the art.
  b.report { n.times { h1.size == h2.size and h1.keys.all? { |key| !!h2[key] }}}
  # This solution
  b.report { n.times { h1.same_keys? h2} }
end
#       user     system      total        real
#   0.310000   0.000000   0.310000 (  0.312249)
#   0.050000   0.000000   0.050000 (  0.051807)

- Jan

---

哇，太棒了！我一定要重新学习C语言。 - strider

Answer 2

结合freemasonjson和sawa的建议:

h1.size == h2.size and (h1.keys - h2.keys).empty?

- Jan

Answer 3

尝试：

# Check that both hash have the same number of entries first before anything
if h1.size == h2.size
    # breaks from iteration and returns 'false' as soon as there is a mismatched key
    # otherwise returns true
    h1.keys.all?{ |key| !!h2[key] }
end

Enumerable#all?

最坏情况下，你只需要遍历键一次。

- strider

---

更好的是，h2.include?(key)。 - akuhn

我进行了一些基准测试，目前看来这个答案是明显的赢家。使用 Hash#include? 对性能没有任何改进，但在可读性方面肯定是一个很好的进步。 - Jan

如果a，那么b结束 -> a && b - tokland

@Jan 注意基准测试。特别是合成的！只有在键集经常不同的情况下，使用此解决方案（无论是否使用包含）才会更快。如果支配情况是相等的键集，则速度会更慢。 - akuhn

@akuhn，这就是我的基准测试结果。虽然有些出乎意料，但仔细想想也很合理。与其他答案不同，这个解决方案不会在内存中创建许多额外的对象。因此，它对垃圾回收非常友好，在MRI的GC性能下尤为如此，这是一个巨大的优势。 - Jan

Answer 4

为了至少有一个基准，回答这个问题...

require 'securerandom'
require 'benchmark'

a = {}
b = {}

# Use uuid to get a unique random key
(0..1_000).each do |i|
  key = SecureRandom.uuid
  a[key] = i
  b[key] = i
end

Benchmark.bmbm do |x|
  x.report("#-") do
    1_000.times do
      (a.keys - b.keys).empty? and (a.keys - b.keys).empty?
    end
  end

  x.report("#&") do
    1_000.times do
      computed = a.keys & b.keys
      computed.size == a.size
    end
  end

  x.report("#all?") do
    1_000.times do
      a.keys.all?{ |key| !!b[key] }
    end
  end

  x.report("#sort") do
    1_000.times do
      a_sorted = a.keys.sort
      b_sorted = b.keys.sort
      a == b
    end
  end
end

结果如下：

Rehearsal -----------------------------------------
#-      1.000000   0.000000   1.000000 (  1.001348)
#&      0.560000   0.000000   0.560000 (  0.563523)
#all?   0.240000   0.000000   0.240000 (  0.239058)
#sort   0.850000   0.010000   0.860000 (  0.854839)
-------------------------------- total: 2.660000sec

            user     system      total        real
#-      0.980000   0.000000   0.980000 (  0.976698)
#&      0.560000   0.000000   0.560000 (  0.559592)
#all?   0.250000   0.000000   0.250000 (  0.251128)
#sort   0.860000   0.000000   0.860000 (  0.862857)

我必须同意 @akuhn 的观点，如果我们有更多关于你所使用的数据集的信息，那么这将是一个更好的基准测试。但话说回来，我认为这个问题确实需要一些硬性事实。

- Vincent B.

---

我建议将基准测试的名称作为参数添加到“report”方法中。这将使得在结果报告中添加名称变得更加容易，从而使其更易于阅读。 - the Tin Man

Answer 5

这取决于您的数据。

实际上并没有一个“通用情况”。例如，通常一次性检索整个键集比分别检查每个键的包含更快。但是，如果在您的数据集中，键集往往不同，则较慢但更快地失败的解决方案可能更快。例如：

h1.size == h2.size and h1.keys.all?{|k|h2.include?(k)}

另一个需要考虑的因素是哈希的大小。如果它们很大，使用高设置成本的解决方案，例如调用Set.new，可能会得到回报，但如果它们很小，则不会：

h1.size == h2.size and Set.new(h1.keys) == Set.new(h2.keys)

如果你需要反复比较相同的不变哈希值，缓存结果肯定是值得的。最终只有基准测试才能说明问题，但要编写基准测试，我们需要更多了解你的用例。当然，使用合成数据（例如随机生成的键）进行测试将不会真正代表实际情况。

- akuhn

Answer 6

这是我的尝试：

(h1.keys - h2.keys).empty? and (h2.keys - h1.keys).empty?

- sawa

Answer 7

这是我的解决方案：

class Hash
    # doesn't check recursively
    def same_keys?(compare)
        if compare.class == Hash
            if self.size == compare.size
               self.keys.all? {|s| compare.key?(s)}
            else
                return false
            end
        else
            nil
        end
    end
end

a = c = {  a: nil,    b: "whatever1",  c: 1.14,     d: true   }
b     = {  a: "foo",  b: "whatever2",  c: 2.14,   "d": false  }
d     = {  a: "bar",  b: "whatever3",  c: 3.14,               }

puts a.same_keys?(b)                    # => true
puts a.same_keys?(c)                    # => true
puts a.same_keys?(d)                    # => false   
puts a.same_keys?(false).inspect        # => nil
puts a.same_keys?("jack").inspect       # => nil
puts a.same_keys?({}).inspect           # => false

- Alphons