using hashes as keys in hashes

S

Steven Arnold

I've seen several posts related in some way to the subject of using
hashes as keys in hashes, but I haven't seen a clear solution to the
issue. My problem is I want to generate a set of unique hashes.
Since hash keys are unique, I was hoping to just put the hashes in as
keys, something like:

myUniqueHashes[aHash] ||= 0
myUniqueHashes[aHash] += 1

This would not only give me a list of unique hashes, but it would
also tell me how many times each one was seen.

Unfortunately, this does not work because in a hash, each different
hash that is inserted as a key is considered to be different, even if
the contents are the same. When used as keys in a hash, two hashes
are considered equal if aHash.id = bHash.id, meaning if they are the
very same hash located at the same place in memory.

At the micro level, what I need is a special kind of hash that will
consider two hash keys to be equal if aHash == bHash. At a higher
level, I need an efficient way to collect a unique set of hashes. An
array would work, but for a large set it'd be much slower....and
storing the number of accesses would be relatively clunky compared to
a hash's interface.

What is the Ruby way to solve this problem?

Thanks,
steve
 
D

David A. Black

Hi --

I've seen several posts related in some way to the subject of using
hashes as keys in hashes, but I haven't seen a clear solution to the
issue. My problem is I want to generate a set of unique hashes.
Since hash keys are unique, I was hoping to just put the hashes in
as keys, something like:

myUniqueHashes[aHash] ||= 0
myUniqueHashes[aHash] += 1

This would not only give me a list of unique hashes, but it would
also tell me how many times each one was seen.

Unfortunately, this does not work because in a hash, each different
hash that is inserted as a key is considered to be different, even
if the contents are the same. When used as keys in a hash, two
hashes are considered equal if aHash.id = bHash.id, meaning if they
are the very same hash located at the same place in memory.

At the micro level, what I need is a special kind of hash that will
consider two hash keys to be equal if aHash == bHash. At a higher
level, I need an efficient way to collect a unique set of hashes.
An array would work, but for a large set it'd be much slower....and
storing the number of accesses would be relatively clunky compared
to a hash's interface.

What is the Ruby way to solve this problem?

You could define an appropriate default behavior for the hash of
hashes:

unique_hashes = Hash.new do |hash,key|
existing = hash.keys.find {|k| k == key }
if existing
hash[existing] += 1
else
hash[key] = 1
end
end

a = {"a","b"}
b = {"a","b"}

unique_hashes[a]
unique_hashes
unique_hashes[{"some","other"}]

p unique_hashes # {{"some"=>"other"}=>1, {"a"=>"b"}=>2}


David
 
S

Steven D. Arnold

You could define an appropriate default behavior for the hash of
hashes:

unique_hashes = Hash.new do |hash,key|
existing = hash.keys.find {|k| k == key }
if existing
hash[existing] += 1
else
hash[key] = 1
end
end

This is a cool idea (and taught me about the block approach to
creating hashes, thanks!). The one (seeming) flaw is the
hash.keys.find, which would do an O(n) search on the hash.keys array,
giving O(n) instead of a hash's normal O(ln(n)) behavior. Am I wrong
about that?

steve
 
M

Mauricio Fernández

You could define an appropriate default behavior for the hash of
hashes:

unique_hashes = Hash.new do |hash,key|
existing = hash.keys.find {|k| k == key }
if existing
hash[existing] += 1
else
hash[key] = 1
end
end

This is a cool idea (and taught me about the block approach to
creating hashes, thanks!). The one (seeming) flaw is the
hash.keys.find, which would do an O(n) search on the hash.keys array,
giving O(n) instead of a hash's normal O(ln(n)) behavior.

[O(1)]

Yes.

unique_hashes = Hash.new do |h,k|
k2 = Struct.new:)h) do
def eql?(o); h == o.h end
def hash; h.to_a.hash end
end.new(k) # hoise the Struct def or use singleton methods for better
# performance
h.has_key?(k2) ? h[k2] += 1 : h[k2] = 1
end

unique_hashes[{1 => 2}] # => 1
[{1 => 2}.object_id, {1 => 2}.object_id] # => [-605360772, -605360782]
unique_hashes[{2 => 3}] # => 1
unique_hashes[{1 => 2}] # => 2
unique_hashes[{1 => 2}] # => 3
RUBY_VERSION # => "1.8.3"

You can also redefine Hash#{eql?,hash} globally or using singleton
methods, of course.
 

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

Iterating hashes 11
Hashes in Sets 0
Hashes 6
Array of Hashes in an array of hashes - Complicated! 16
Merging hashes using both symbols and strings as keys 14
Hashes 4
process multiple hashes 5
Hashes in 1.9 index 4

Members online

Forum statistics

Threads
473,733
Messages
2,569,440
Members
44,830
Latest member
ZADIva7383

Latest Threads

Top