Nested hash constructor confusion

B

Ben Armstrong

Can anyone explain the following? Our "intuitive" solution (h1) to
creating a constructor for a hash nested within a hash did not work. It
was only after attempting a workaround (h3) and finding that it
performed very poorly that we Googled (h2) a correct solution. But it
is not obvious to us why this more complex constructor is required.

# Unexpected result, h1 hash is empty.
h1=Hash.new(Hash.new(0)) # => {}
h1[1][2]='h1' # => "h1"
h1 # => {}

# Expected result, h2 hash contains nested hash.
h2=Hash.new{|hash,key| hash[key]=Hash.new(0)} # => {}
h2[1][2]='h2' # => "h2"
h2 # => {1=>{2=>"h2"}}

# Expected result but expensive.
h3=Hash.new(Hash.new(0)) # => {}
temp=h3[1].dup # => {}
temp[2]='h3' # => "h3"
h3[1]=temp # => {2=>"h3"}
h3 # => {1=>{2=>"h3"}}

Thanks,
Ben Armstrong
 
M

Martin DeMello

Ben Armstrong said:
Can anyone explain the following? Our "intuitive" solution (h1) to
creating a constructor for a hash nested within a hash did not work. It
was only after attempting a workaround (h3) and finding that it
performed very poorly that we Googled (h2) a correct solution. But it
is not obvious to us why this more complex constructor is required.

Hash.new, when passed a block, stores the block as a sort of
"key_missing" callback, passing it the hash itself and the key. The
callback doesn't modify the hash, though, it just returns a virtual
value. However, because the block does have access to the hash, it can
call a method on that hash that updates it, hence the second
constructor you tried.

Compare:

irb(main):001:0> h = Hash.new {|h, k| 2*k}
=> {}
irb(main):002:0> h[1]
=> 2
irb(main):003:0> h[2]
=> 4
irb(main):004:0> h
=> {}
irb(main):005:0> h1 = Hash.new {|h, k| h[k] = 2*k}
=> {}
irb(main):006:0> h1[1]
=> 2
irb(main):007:0> h1[2]
=> 4
irb(main):008:0> h1
=> {1=>2, 2=>4}

And even something more complicated like:

irb(main):009:0> h2 = Hash.new {|h, k| h[k] = 2*k; "missing, filling it
in"}
=> {}
irb(main):010:0> h2[1]
=> "missing, filling it in"
irb(main):011:0> h2[1]
=> 2

martin

martin
 
D

David A. Black

Hi --

And even something more complicated like:

irb(main):009:0> h2 = Hash.new {|h, k| h[k] = 2*k; "missing, filling it
in"}
=> {}
irb(main):010:0> h2[1]
=> "missing, filling it in"
irb(main):011:0> h2[1]
=> 2

Or my favorite:

h = Hash.new {|h,k| raise "No such key: #{k}" }

:)


David
 
R

Ryan Leavengood

Can anyone explain the following? Our "intuitive" solution (h1) to
creating a constructor for a hash nested within a hash did not work. It
was only after attempting a workaround (h3) and finding that it
performed very poorly that we Googled (h2) a correct solution. But it
is not obvious to us why this more complex constructor is required.

# Unexpected result, h1 hash is empty.
h1=3DHash.new(Hash.new(0)) # =3D> {}
h1[1][2]=3D'h1' # =3D> "h1"
h1 # =3D> {}

When you pass an object to the Hash.new constructor, that object is
used as the default value for keys that don't have values. But that
object isn't really "in" the hashtable data structure, it is just
associated with the object (i.e. a member variable):

irb(main):001:0> h1=3DHash.new(Hash.new(0))
=3D> {}
irb(main):002:0> h1[0].object_id
=3D> 22753180
irb(main):003:0> h1[1].object_id
=3D> 22753180
irb(main):004:0> h1[0][0]
=3D> 0
irb(main):005:0> h1[0][0]=3D'foo'
=3D> "foo"
irb(main):006:0> h1[0][0]
=3D> "foo"
irb(main):007:0> h1
=3D> {}
# Expected result, h2 hash contains nested hash.
h2=3DHash.new{|hash,key| hash[key]=3DHash.new(0)} # =3D> {}
h2[1][2]=3D'h2' # =3D> "h2"
h2 # =3D> {1=3D>{2=3D>"h2"}}

Others have described why this works and is the proper solution.
# Expected result but expensive.
h3=3DHash.new(Hash.new(0)) # =3D> {}
temp=3Dh3[1].dup # =3D> {}
temp[2]=3D'h3' # =3D> "h3"
h3[1]=3Dtemp # =3D> {2=3D>"h3"}
h3 # =3D> {1=3D>{2=3D>"h3"}}

This is expensive because you are pulling out the default value from
the hashtable and duplicating it on each key operation then actually
putting it into the hashtable data structure. As you know now from the
above this is not the proper way to work with hashtables with
dynamically created values.

Ryan
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Need help fixing code 1
Nested hash 1
Hash == not always working? Or am I missing something? 8
Simple Processor VHDL Doubt 0
SHA1 1
SHA1 4
Hash#each with nested array as value 3
Memory Question 6

Members online

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,901
Latest member
Noble71S45

Latest Threads

Top