Hashtable of sets

[Trevor Harmon]

Hi,

I'm new to Ruby and need a data structure that consists of a hashtable
of sets. While writing some code for this, I've run into some odd Ruby
behavior that I'm hoping someone can explain to me.

I started with a hashtable:

h = Hash.new([])

Here, I made the default value an empty set instead of nil. That way,
if I wanted to add a new element "q" to a set mapped to the key 'a', I
could do so in just one line. For example:

h['a'] = %w{q r s}
h['a'] << "t"

That seemed to work:

h['a'] => ["q", "r", "s", "t"]
h['b']

=> []

Great! Now let me add an element to the set mapped to 'b':

h['b'] << "x"

That seemed to work, too:

h['b']

=> ["x"]

But wait, now all the other keys are mapped to the same thing!

h['c'] => ["x"]
h['d']

=> ["x"]

Can someone please explain how this happened? I don't understand it. Thanks,

Trevor

P.S. I'm using Ruby 1.8.4.

 

[Marcin Mielżyński]

Hi,

I'm new to Ruby and need a data structure that consists of a hashtable
of sets. While writing some code for this, I've run into some odd Ruby
behavior that I'm hoping someone can explain to me.

I started with a hashtable:

h = Hash.new([])

This supplies the default object value when there is no key in a hash
and this object will not be copied, so:

h['foo'] << 4
h['blah'] << "ddd"

h['bar']

=> [4, "ddd"]

the same instance is referenced...

In order to create a hash that behaves the way you expect, is to create
a hash with a block that returns default value (in this case a separate
instance will be created):


h = Hash.new{[]}
h['foo'] << 4
h['blah'] << "ddd"

h['bar']

=> []

lopex

 

[Trevor Harmon]

In order to create a hash that behaves the way you expect, is to create
a hash with a block that returns default value (in this case a separate
instance will be created):

h = Hash.new{[]}
h['foo'] << 4
h['blah'] << "ddd"

h['bar']

=> []

That fixes the same-instance problem, but it still doesn't work right
because h['foo'] and h['blah'] also return [].

I could fix this by special-handling the case where the hashtable entry
is empty, but that would defeat the purpose of the Hash.new{[]} trick.
Isn't there some one-liner I could use to add elements to this data
structure? Thanks,

Trevor

 

[Daniel Mitterdorfer]

On 2006-04-30 14:35:37 -0700, Marcin MielżyÅ„ski <[email protected]> said:
Isn't there some one-liner I could use to add elements to this data
structure? Thanks,

Trevor

Gregory Brown discusses this issue in his NubyGems series. See [1]

hth

Daniel

[1]
http://www.oreillynet.com/ruby/blog/2006/04/nubygems_hash_initialization_1.html

 

[Robert Klemme]

Hi,

I'm new to Ruby and need a data structure that consists of a hashtable
of sets. While writing some code for this, I've run into some odd Ruby
behavior that I'm hoping someone can explain to me.

I started with a hashtable:

h = Hash.new([])

This supplies the default object value when there is no key in a hash
and this object will not be copied, so:

h['foo'] << 4
h['blah'] << "ddd"

h['bar']

=> [4, "ddd"]

the same instance is referenced...
Correct.

In order to create a hash that behaves the way you expect, is to create
a hash with a block that returns default value (in this case a separate
instance will be created):


h = Hash.new{[]}
h['foo'] << 4
h['blah'] << "ddd"

h['bar']

=> []

No, you need this

require 'set'
h = Hash.new {|ha,k| ha[k] = Set.new}

1. Class Set implements the requirement of Trevor who wants a hash of sets.

2. Assignment is needed in the block because otherwise a new Set / Array
is returned every time a key is not found.

Kind regards

robert