Find key/value pairs deep inside a hash containing an arbitrary number of nested hashes and arrays

Question

A web service is returning a hash that contains an unknown number of nested hashes, some of which contain an array, which in turn contains an unknown number of nested hashes.

Some of the keys are not unique -- i.e. are present in more than one of the nested hashes.

However, all the keys that I actually care about are all unique.

Is there someway I can give a key to the top-level hash, and get back it's value even if the key-value pair is buried deep in this morass?

(The web service is Amazon Product Advertising API, which slightly varies the structure of the results that it gives depending on the number of results and the search types permitted in each product category.)

Solution 1

Here's a simple recursive solution:

def nested_hash_value(obj,key)
  if obj.respond_to?(:key?) && obj.key?(key)
    obj[key]
  elsif obj.respond_to?(:each)
    r = nil
    obj.find{ |*a| r=nested_hash_value(a.last,key) }
    r
  end
end

h = { foo:[1,2,[3,4],{a:{bar:42}}] }
p nested_hash_value(h,:bar)
#=> 42

Solution 2

No need for monkey patching, just use Hashie gem: https://github.com/intridea/hashie#deepfind

user = {
  name: { first: 'Bob', last: 'Boberts' },
  groups: [
    { name: 'Rubyists' },
    { name: 'Open source enthusiasts' }
  ]
}

user.extend Hashie::Extensions::DeepFind

user.deep_find(:name)   #=> { first: 'Bob', last: 'Boberts' }

For arbitrary Enumerable objects, there is another extension available, DeepLocate: https://github.com/intridea/hashie#deeplocate

Solution 3

Combining a few of the answers and comments above:

class Hash
  def deep_find(key, object=self, found=nil)
    if object.respond_to?(:key?) && object.key?(key)
      return object[key]
    elsif object.is_a? Enumerable
      object.find { |*a| found = deep_find(key, a.last) }
      return found
    end
  end
end

Solution 4

Ruby 2.3 introduces Hash#dig, which allows you to do:

h = { foo: {bar: {baz: 1}}}

h.dig(:foo, :bar, :baz)           #=> 1
h.dig(:foo, :zot)                 #=> nil

Solution 5

A variation of barelyknown's solution: This will find all the values for a key in a hash rather than the first match.

class Hash
  def deep_find(key, object=self, found=[])
    if object.respond_to?(:key?) && object.key?(key)
      found << object[key]
    end
    if object.is_a? Enumerable
      found << object.collect { |*a| deep_find(key, a.last) }
    end
    found.flatten.compact
  end
end

{a: [{b: 1}, {b: 2}]}.deep_find(:b) will return [1, 2]

View more solutions

Comments

[Dave Newton]

This question comes up a lot, like here and here and many others.

[PJP]

It always helps if you can create some sample data showing what you have encountered, so we don't have to imagine. Also, how is the data being sent? Do you receive XML and parse it? JSON? Or, are you using an call that returns the mystical structure and everything else is a black box?

[Vigneshwaran]

This code caused me stack overflow. I guess it's due to Strings and/or something else that will respond to each method. I changed elsif obj.respond_to?(:each) to elsif obj.is_a?(Hash) or obj.is_a?(Array). Now it works fine. Thanks for your solution.

[Seamus Abshere]

it would be nice if this thing printed out its path (breadcrumbs?) as it went down...

[Rajdeep Singh]

What if there are multiple hashes containing :bar key, what would be the solution if we want array of the values of each :bar keys?

[Phrogz]

@RSB Ask this as its own question if you want an answer. Better yet, try to come up with a solution yourself. (Hints: With a recursive function where you want to accumulate results, you either need to return values or use a closed-over data structure; Alternatively, you can use a non-recursive depth-first or breadth-first crawl by using a queue.)

[JESii]

I found the Hashi::Extensions::DeepFind to be an excellent approach. And if you're looking to find keys that are duplicated, then the deep_find_all() method is awesome. Highly recommended.

[m1l05z]

Didn't work for multiple params keys: { 0: [{b: '1'}], 1: [{b: '2'}] }.deep_find(:b) returns: #> '1'

[Vaibhav Kaushal]

This here is what was needed!

[Andre Figueiredo]

I didn't vote down, but I wouldn't vote up because I find an overkill to use a gem for such a simple solution.

[Cary Swoveland]

@Andre, why wouldn't you use a gem here? This gem surely has efficient and thoroughly-tested code. How much time are you going to spend rolling your own? Recursive methods are rarely trivial and are challenging to test.