为什么新的哈希有七个对象比六个长度哈希慢得多？

我发现当我新建一个Hash时,有七个对象比六个长度哈希慢得多.我知道哈希的长度会影响性能.但我不知道为什么七是一个特殊的.

这是benchmark(Ruby 2.2.3)的代码:

require 'benchmark/ips'

Benchmark.ips do |x|
  x.report(5) { { a: 0, b: 1, c: 2, d: 3, e: 4 } }
  x.report(6) { { a: 0, b: 1, c: 2, d: 3, e: 4, f: 5 } }
  x.report(7) { { a: 0, b: 1, c: 2, d: 3, e: 4, f: 5, g: 6 } }
  x.report(8) { { a: 0, b: 1, c: 2, d: 3, e: 4, f: 5, g: 6, h: 7 } }
  x.report(9) { { a: 0, b: 1, c: 2, d: 3, e: 4, f: 5, g: 6, h: 7, i: 8 } }

  x.compare!
end

结果就是打击:

Calculating -------------------------------------
                   5    65.986k i/100ms
                   6    63.966k i/100ms
                   7    30.713k i/100ms
                   8    28.991k i/100ms
                   9    27.115k i/100ms
-------------------------------------------------
                   5      1.243M (± 4.3%) i/s -      6.203M
                   6      1.202M (± 5.3%) i/s -      6.013M
                   7    373.366k (±13.7%) i/s -      1.843M
                   8    351.945k (± 8.8%) i/s -      1.768M
                   9    331.398k (± 8.2%) i/s -      1.654M

Comparison:
                   5:  1243005.5 i/s
                   6:  1202032.4 i/s - 1.03x slower
                   7:   373366.5 i/s - 3.33x slower
                   8:   351945.1 i/s - 3.53x slower
                   9:   331398.3 i/s - 3.75x slower

Gagan Gami.. 5

从Ruby中的Hash查找,为什么它如此之快？:

Ruby动态管理bin的大小.它从11开始,一旦其中一个箱具有5个或更多元素,则增加箱大小并将所有散列元素重新分配到它们新的相应箱.

在某些时候,当Ruby调整bin池的大小时,你会花费指数增加的时间惩罚,但是如果你考虑它,它值得花时间,因为这将使查询时间和内存使用尽可能低.

这意味着更多的箱子,在箱子中寻找特定钥匙所花费的时间越少.

希望有助于理解这种行为.

1> Gagan Gami..：

---

从Ruby中的Hash查找,为什么它如此之快？:

Ruby动态管理bin的大小.它从11开始,一旦其中一个箱具有5个或更多元素,则增加箱大小并将所有散列元素重新分配到它们新的相应箱.

在某些时候,当Ruby调整bin池的大小时,你会花费指数增加的时间惩罚,但是如果你考虑它,它值得花时间,因为这将使查询时间和内存使用尽可能低.

这意味着更多的箱子,在箱子中寻找特定钥匙所花费的时间越少.

希望有助于理解这种行为.

---

这是一个很好的信息,但你可以引用一个参考吗？

---

请注意,这是特定于Ruby的特定实现的特定版本.其他实现或甚至同一实现的其他版本可能表现不同.例如,在JRuby中,`Hash`是使用Java`Map`实现的,在IronRuby中,它是使用.NET`字典`实现的,在Topaz中,它实现为RPython`dict`.Rubinius甚至有两种不同的`Hash`实现,你可以在编译时切换,其中一种基于Hash Array Mapped Trie(HAMT).