Converting a nested hash into a flat hash

Question

This question is the inverse of this question.

Given a nested hash like

{
    :a => {
       :b => {:c => 1, :d => 2},
       :e => 3,
    },
    :f => 4,
}

what is the best way to convert it into a flat hash like

{
    [:a, :b, :c] => 1,
    [:a, :b, :d] => 2,
    [:a, :e] => 3,
    [:f] => 4,
}

Solution 1

Another way:

def flat_hash(h,f=[],g={})
  return g.update({ f=>h }) unless h.is_a? Hash
  h.each { |k,r| flat_hash(r,f+[k],g) }
  g
end

h = { :a => { :b => { :c => 1,
                      :d => 2 },
              :e => 3 },
      :f => 4 }

flat_hash(h) #=> {[:a, :b, :c]=>1, [:a, :b, :d]=>2, [:a, :e]=>3, [:f]=>4}

Solution 2

Very similar to Adiel Mittmann's solution

def flat_hash(h, k = [])
  new_hash = {}
  h.each_pair do |key, val|
    if val.is_a?(Hash)
      new_hash.merge!(flat_hash(val, k + [key]))
    else
      new_hash[k + [key]] = val
    end
  end
  new_hash
end

Edit: Refactored for elegance. Should be almost as fast.

def flat_hash(hash, k = [])
  return {k => hash} unless hash.is_a?(Hash)
  hash.inject({}){ |h, v| h.merge! flat_hash(v[-1], k + [v[0]]) }
end

Solution 3

My attempt:

def flatten_hash(h)
  return { [] => h } unless h.is_a?(Hash)
  Hash[h.map { |a,v1| flatten_hash(v1).map { |b,v2| [[a] + b, v2] } }.flatten(1)]
end

Sorry for the bad variables names, had to fit it in one line.

Solution 4

This is not an attempt to give you the best way to do it, but it is a way :P

def flatten(hash)
  return {[] => hash} if !hash.is_a?(Hash)
  map = {}
  hash.each_pair do |key1, value1|
    flatten(value1).each_pair do |key2, value2|
      map[[key1] + key2] = value2
    end
  end
  return map
end

It works for your example, producing this result:

{[:a, :b, :c]=>1, [:a, :b, :d]=>2, [:a, :e]=>3, [:f]=>4}

It may not produce the result you expect if there are empty hashes.

Solution 5

A functional approach (see the history for an alternative implementations):

def recursive_flatten(hash)
  hash.flat_map do |key, value|
    if value.is_a?(Hash)
      recursive_flatten(value).map { |ks, v| [[key] + ks, v] } 
    else
      [[[key], value]]
    end
  end.to_h
end

View more solutions

Comments

[Linuxios]

So you want an array of keys in order that lead to a value?

[sawa]

This one ran the fastest. Thanks.

[Niklas B.]

@sawa: Just a tip for the future: If you want a fast solution, mention this in the question next time. Usually the main criterion in dynamic languages like Python or Ruby is elegancy and conciseness. If you specifically ask for performance as well, you could get much better suited answers :)

[Kyle]

@sawa: refactored for elegance.

[sawa]

@Kyle One thing that was good about your earlier code was that it can be redefined as a method on Hash. The rewritten one cannot.

[rusty]

I know Ruby doesn't necessarily support TCO out of the box, but if you didn't return g here, would this be tail-call optimized?

[Cary Swoveland]

I've heard the term "tail-call optimized" but I have no idea what it means. Perhaps a computer scientist can answer your question.

[Stefan Majewsky]

You can't optimize the tail call here IMO since you have a cascaded recursion.

[Cary Swoveland]

@Niklas, perhaps, but most Ruby-readers know sawa is a speed-freak.