探索 Hashes 在 Ruby 中的运行方式

2016-10-25 09:31:36来源:作者:开源中国翻译文章人点击

在Ruby的语言中, 可以说 哈希是最有用的数据类型。利用结构本身以及现实世界的问题,结合快速查找,它通常是脚本、网页和复杂的业务逻辑。它甚至可以在Ruby中存储所工作方式有功能、变量与常量(虽然Ruby实现方法不同,通过预测分支的热路径和使用网站方法缓存,其实这是另一个岗位)。我们通常认为它“ 只是工作 ”。今天,我们将会对哈希的用法进行 充分挖掘 ,探究它的工作方式,工作效率效率如何,以及执行方式。一起来看看吧!

big_four_stock_prices = { :google => 801.23, :apple => 115.57, :facebook => 128.35, :microsoft => 57.19}

这里发生了什么? 让我们来理一下。

首先,运行时为数据结构分配一个连续的内存块。 下面表示的是哈希的第一个键:

:google.hash=> 3592

哈希函数是在Ruby的内核类中定义的,只要别的类继承它就能使用。 实际数值将取决于许多因素,但重要的是它在会话中是保持一致。

接下来,我们必须存储这个值。 该值放置在所谓的“bucket”(类似其它他语言的“bin”)。 Ruby的Hash最初默认是分配11个bucket,因此我们需要决定在哪个bucket中存储我们的哈希值。 为此,运行时简单地执行以下计算:

:google.hash % 11 => 5

这意味着:google的值为801.23,放在哈希表的第5个bucket中,其键的标识符如下:

[:google, 801.23]

它对其余的键/值对也重复这个过程。 要将它拉回来,解释器只是重复计算并从bucket中取出值。 简单吧? 让我们进入边缘情况。

冲突

相对精明的读者可能抓住一个事实:如果只有11个水桶,迟早会把 两个量值放进 一个桶里。然后会发生什么呢?Ruby的哈希值将会被存储在链表的相同容器内。假如标识(键)匹配其中一个(它会使用 equal 来比较?),它会返回结果,如果没有匹配,那么会继续遍历集合。

当然,这个过程将会很耗时——假如一个元素与其它1000个同存储于一个桶会怎样?理论上,这会非常耗时才能返回想要的结果,使用哈希表的全局指针将会很快。Ruby,当然你已经很了解。它是通过遍历整个表的每个桶的所有元素来工作的。一旦这个值超过5,Ruby将会丢弃这个11个桶的数组,创建一个新的数组,正是因为这一点,Ruby需要重复遍历值。通过这样的操作,可以保证链表的长度很短,减少查找时间。

查找时间是哈希的一个卖点。对于处于一个大O倾斜的值,哈希表将会很快查找出来,虽然表存储的数量增多,但查找时间保持不变。在实践中,它的时间复杂度接近O(log n),但是也不要掉以轻心。

一个好哈希算法的重要性

巩固我们对哈希实现的理解,让我们试着来做个简单的实验:如果一个自定义的哈希函数每次都返回相同的整数这将会发生什么?我们马上会想到,这意味着每一个项都链接在同一个容器的列表上,并且在查找一个项的时候,越趋近于结尾,所用的时间就越多。让我们来试着写一些代码:

require 'benchmark'class GoodHashendclass BadHash def hash 7 endendhashing_algorithm == BadHash # switch to GoodHash for inverse17.times do |ex| lookup_key = nil size = 2**ex test_hash = {} (1..size).each do |n| index = hashing_algorithm.new lookup_key = index if n > size/2 and lookup_key.nil? test_hash[index] = rand end Benchmark.bm do |bench| bench.report("Hash size: #{size} elements 10000 times/n") do 10000.times do test_hash[lookup_key] end end endend

这将生成一个 类似于这样的 哈希(大小不同):

test_hash = { #<BadHash:0x007f92941eaae0> => 0.029655456018705673, #<BadHash:0x007f92941e3c68> => 0.973576967117432, #<BadHash:0x007f92941e1508> => 0.2443654110192186, #<BadHash:0x007f92941d1ab8> => 0.7536013342129247}

让我们来过一遍代码吧:

首先我们创建一个类,GoodHash,它使用Ruby的本地散列算法。然后我们循环17次(65536条似乎是一个终止的好地方),其基数为2的幂指数(ex)。然后,我们用类GoodHash中的实例计算的值作为随机数插入到test_hash中。我们查找该值1000次并对结果进行基准测试,然后使用类BadHash重复此过程。

得到的结果(从“实际”列获得的读数):

这非常清楚的证明了我们的假设。随着哈希算法中项目数量的增加,在BadHash类的查找时间成指数增长,而GoodHash类实现中仍然牢牢的稳定在相同的时间。 GoodHash列中的离群值也说明了一旦存储被占满,Ruby重新计算hash值。

有趣的是,Ruby 2.0开始对小哈希不起作用。如果您的哈希值为6个或更少的项目,它将被存储为一个数组列表并遍历直到键匹配到所需查找。虽然哈希表很快,但对哈希值的计算也需要很大的成本; 这个进程用这个方法完美的躲避了这个问题。在散列增长到7个项目的情况下,该数组被丢弃,并且使用传统的hash表。这在结果表中的hash size为8的条目可以看到。

Ruby如何分配Bin?

在Ruby中bin的数量不会随着其中元素的增加而线性增加,那么Ruby是如何确定一个哈希中有多少bin的呢?Ruby计算一系列初始数值接近2次幂。这样的好处是绑定到哈希值上的数值大大减少了共用同一个因子的可能性。如果这不正确的话,我们之前涉及到的系数计算可以每次释放相同的数值,这样会把任何东西放入相同的bin,而不是像之前测试的那样。

相对于研究Ruby内部原理,探究哈希的运行方式是相对简单的。虽然我们已经广泛了解哈希的用法,但更重要的是,要清楚要在什么时候以及在哪里使用它。迄今为止在哈希中最大的成本是哈希散列,哈希计算与哈希对,所以当性能要用一个因素来衡量时,得谨记这些用法。(就内部来说,JRuby运行要避免依赖散列正是这个原因)。但是总体上,哈希是一个优越的工具,鉴于优秀的设计与精心的优化。如今我们已清楚地知道哈希的运行方式,及它性能优越的原因,并且不会因为一个对象就去重写哈希函数。

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台