Forum: Ruby using hashes as keys in hashes

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
4803547ff3eaf23efe7d0f56a9af3f95?d=identicon&s=25 stevena (Guest)
on 2005-11-23 14:53
(Received via mailing list)
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
1fba4539b6cafe2e60a2916fa184fc2f?d=identicon&s=25 dblack (Guest)
on 2005-11-23 15:09
(Received via mailing list)
Hi --

On Wed, 23 Nov 2005, Steven Arnold wrote:

> also tell me how many times each one was seen.
> 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[b]
   unique_hashes[{"some","other"}]

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


David
4803547ff3eaf23efe7d0f56a9af3f95?d=identicon&s=25 stevena (Guest)
on 2005-11-23 16:06
(Received via mailing list)
On Nov 23, 2005, at 9:06 AM, David A. Black wrote:

>   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
Dd76a12d66f843de5c5f8782668e7127?d=identicon&s=25 mfp (Guest)
on 2005-11-23 16:26
(Received via mailing list)
On Thu, Nov 24, 2005 at 12:03:48AM +0900, Steven D. Arnold wrote:
> >    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.
This topic is locked and can not be replied to.