在哈希查找中，符号如何比字符串更快？

Question

我理解为什么应该使用符号而不是哈希中的字符串的一方面。也就是说，在内存中只有一个给定符号的实例，而给定字符串可能有多个具有相同值的实例。

我不明白的是符号在哈希查找中为什么比字符串快。我看了答案here，但我还是不太明白。

如果 :foo.hash == :foo.object_id 返回 true，那么它就有意义了，因为这样它就可以使用对象 ID 作为散列的值，而不必每次都计算它。然而，情况并非如此，:foo.object_id 不等于 :foo.hash。因此我的困惑。

Answer 1

hash 没有义务等同于 object_id。这两件事服务于完全不同的目的。 hash 的要点是尽可能具有确定性和随机性，以便您插入到散列中的值均匀分布。 object_id 的要点是定义一个唯一的对象标识符，但不要求它们是随机的或均匀分布的。事实上，随机化它们会适得其反，这只会无缘无故地让事情变慢。

符号往往更快的原因是因为它们的内存分配一次（撇开垃圾收集问题）并为同一符号的所有实例回收。字符串不是那样的。它们可以用多种方式构造，甚至两个字节对字节相同的字符串也可能是不同的对象。事实上，除非您确定它们是同一个对象，否则假设它们是比其他方式更安全。

现在计算 hash，即使字符串变化很小，值也必须随机不同。由于符号无法更改计算，因此可以对其进行更多优化。您可以只计算 object_id 的哈希值，因为它不会改变，例如，而字符串需要考虑其自身的内容，这可能是动态的。

尝试基准测试：

require 'benchmark'

count = 100000000

Benchmark.bm do |bm|
  bm.report('Symbol:') do
    count.times { :symbol.hash }
  end
  bm.report('String:') do
    count.times { "string".hash }
  end
end

这给了我这样的结果：

       user     system      total        real
Symbol:  6.340000   0.020000   6.360000 (  6.420563)
String: 11.380000   0.040000  11.420000 ( 11.454172)

在这种最简单的情况下，速度轻松提升 2 倍。基于一些基本测试，随着字符串变长但符号时间保持不变，字符串代码的性能会降低 O(N)。

Answer 2

字符串作为散列键的额外开销是，由于字符串是可变的，而且常用的散列键也有散列键，因此散列 class 会复制所有字符串键（可能使用 dup 或克隆）以保护散列的完整性免受密钥损坏。

考虑：

irb(main):001:0> a = {}
=> {}
irb(main):002:0> b = "fred"
=> "fred"
irb(main):003:0> a[b] = 42
=> 42
irb(main):004:0> a
=> {"fred"=>42}
irb(main):005:0> b << " flintstone"
=> "fred flintstone"
irb(main):006:0> a
=> {"fred"=>42}
irb(main):007:0> b
=> "fred flintstone"
irb(main):008:0>
irb(main):008:0> b.object_id
=> 17350536
irb(main):009:0> a.keys[0].object_id
=> 15113052
irb(main):010:0>

符号是不可变的，不需要如此激烈的措施。

Answer 3

只是想补充一点，我并不完全同意@tadman 提出的数字。在我的测试中，使用 calcualte '#hash' 最多快 1.5 倍。我使用 benchmark/ips 来测试性能。

require 'benchmark/ips'

Benchmark.ips do |bm|
  bm.compare!
  bm.report('Symbol:') do
    :symbol.hash
  end
  bm.report('String:') do
    'string'.hash
  end
end

这导致

Comparison:
             Symbol:: 10741305.8 i/s
             String::  7051559.3 i/s - 1.52x slower

此外，如果您启用 'frozen string literals'（这将是未来 ruby 版本的默认设置），差异将降至 1.2 倍：

# frozen_string_literal: true

Comparison:
             Symbol::  9014176.3 i/s
             String::  7532196.9 i/s - 1.20x slower

在哈希查找中，符号如何比字符串更快？

How are Symbols faster than Strings in Hash lookups?

ruby

hash

symbols

hashmap