在Ruby中递归遍历哈希表

Question

我遇到了一个遍历哈希表的函数问题。哈希表可能包含哈希数组。我想让这个方法寻找一个id，然后只返回所找到的嵌套哈希表。

它似乎可以正常遍历，但是却返回传入的原始值。

require 'rubygems'
require 'ruby-debug'

def find_by_id(node, find_this="")
  if node.is_a?(Hash)
    node.each do |k,v|
      if v.is_a?(Array)
        v.each do |elm|
          if elm["_id"] == find_this && !find_this.empty?
            return elm      # THIS IS WHAT I WANT!
          else
            find_by_id(elm, find_this)
          end
        end
      end
    end
  end
end

x = {"name" => "first", "_id"=>'4c96a9a56f831b0eb9000005', "items"=>["name" => "second", "_id"=>'4c96a9af6f831b0eb9000009', "others"=>[{"name" => "third", "_id"=>'4c96a9af6f831b0eb9000007'}, {"name" => "fourth", "_id"=>'4c96a9af6f831b0eb9000008'}] ] }

find_by_id(x, '4c96a9af6f831b0eb9000008')

- Dex

Answer 1

当你递归调用 find_by_id 方法时，你并没有对返回值进行任何操作。你需要检查它是否找到了某个值，如果找到了就返回它，例如：

result = find_by_id(elm, find_this)
return result if result

你还需要在该方法结尾（each循环后）返回nil，这样如果没有找到任何内容，它就会返回nil。如果不这样做，它将返回你迭代的哈希表的返回值each。

编辑：

以下是我概述的更改后的全部代码：

def find_by_id(node, find_this="")
  if node.is_a?(Hash)
    node.each do |k,v|
      if v.is_a?(Array)
        v.each do |elm|
          if elm["_id"] == find_this && !find_this.empty?
            return elm      # THIS IS WHAT I WANT!
          else
            result = find_by_id(elm, find_this)
            return result if result
          end
        end
      end
    end
  end
  # Return nil if no match was found
  nil
end

编辑2：

另一种我认为更加清晰的方法是将迭代结构的逻辑与查找正确id的元素的逻辑分开处理：

def dfs(hsh, &blk)
  return enum_for(:dfs, hsh) unless blk

  yield hsh
  hsh.each do |k,v|
    if v.is_a? Array
      v.each do |elm|
        dfs(elm, &blk)
      end
    end
  end
end

def find_by_id(hsh, search_for)
  dfs(hsh).find {|node| node["_id"] == search_for }
end

通过使dfs返回一个Enumerable，我们可以使用Enumerable＃find方法，从而使代码变得更简单。

这还能够实现代码重用，如果你需要编写另一个需要递归遍历哈希表的方法，你只需重用dfs方法即可。

- sepp2k

---

我尝试过了，它返回了错误的值。但是当它应该到达时，return elm确实被执行了。 - Dex

我想指出的是，递归并不是问题的根源，而是 each 运算符。从这个运算符内部调用的最后一个运算符没有从原函数中返回其值。 - P Shved

@Dex：只要在方法结尾处（最后一个 "end" 之前）加上nil，这对我来说可以正常工作。 - sepp2k

我也是！谢谢，这让我很烦恼！ - Dex

在“Edit2”下有一个优雅的解决方案。我喜欢可重用性。dfs是指深度优先搜索，对吗？ - John McCarthy