using hashes as keys in hashes

Discussion in 'Ruby' started by Steven Arnold, Nov 23, 2005.

  1. 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
     
    Steven Arnold, Nov 23, 2005
    #1
    1. Advertising

  2. Hi --

    On Wed, 23 Nov 2005, Steven Arnold wrote:

    > 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

    --
    David A. Black
     
    David A. Black, Nov 23, 2005
    #2
    1. Advertising

  3. On Nov 23, 2005, at 9:06 AM, David A. Black wrote:

    > 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
     
    Steven D. Arnold, Nov 23, 2005
    #3
  4. On Thu, Nov 24, 2005 at 12:03:48AM +0900, Steven D. Arnold wrote:
    > On Nov 23, 2005, at 9:06 AM, David A. Black wrote:
    > >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.

    --
    Mauricio Fernandez
     
    Mauricio Fernández, Nov 23, 2005
    #4
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ben Holness

    Hashes of Hashes via subs

    Ben Holness, Oct 5, 2003, in forum: Perl
    Replies:
    8
    Views:
    579
    Ben Holness
    Oct 8, 2003
  2. Harry George
    Replies:
    9
    Views:
    723
    sonal
    Jun 13, 2006
  3. shenry
    Replies:
    14
    Views:
    252
    Rick DeNatale
    Nov 3, 2009
  4. Palaniappan
    Replies:
    3
    Views:
    117
    Tad McClellan
    Oct 27, 2003
  5. Tim O'Donovan

    Hash of hashes, of hashes, of arrays of hashes

    Tim O'Donovan, Oct 27, 2005, in forum: Perl Misc
    Replies:
    5
    Views:
    223
Loading...

Share This Page