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.)

Answer 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

Answer 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

Answer 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

Answer 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

Answer 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]

Answer 6

Despite this appearing to be a common problem, I've just spent a while trying to find/come up with exactly what I need, which I think is the same as your requirement. Neither of the links in the first response are spot-on.

class Hash
  def deep_find(key)
    key?(key) ? self[key] : self.values.inject(nil) {|memo, v| memo ||= v.deep_find(key) if v.respond_to?(:deep_find) }
  end
end

So given:

hash = {:get_transaction_list_response => { :get_transaction_list_return => { :transaction => [ { ... 

The following:

hash.deep_find(:transaction)

will find the array associated with the :transaction key.

This is not optimal as the inject will continue to iterate even if memo is populated.

Answer 7

I use the following code

def search_hash(hash, key)
  return hash[key] if hash.assoc(key)
  hash.delete_if{|key, value| value.class != Hash}
  new_hash = Hash.new
  hash.each_value {|values| new_hash.merge!(values)}
  unless new_hash.empty?
    search_hash(new_hash, key)
  end
end

Answer 8

I ended up using this for a small trie search I wrote:

def trie_search(str, obj=self)
  if str.length <= 1
    obj[str]
  else
    str_array = str.chars
    next_trie = obj[str_array.shift]
    next_trie ? trie_search(str_array.join, next_trie) : nil
  end
end

Note: this is just for nested hashes at the moment. Currently no array support.

Answer 9

Because Rails 5 ActionController::Parameters no longer inherits from Hash, I've had to modify the method and make it specific to parameters.

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

If the key is found, it returns the value of that key, but it doesn't return an ActionController::Parameter object so Strong Parameters are not preserved.