# Using hashes as keys in hashes

**URL:** <https://www.ruby-forum.com/t/using-hashes-as-keys-in-hashes/48688>\
**Category:** Ruby\
**Created:** [November 23, 2005, 2:53pm UTC](https://www.ruby-forum.com/t/using-hashes-as-keys-in-hashes/48688 "2005-11-23T14:53:21Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![stevena](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/b5a626/32.png) [@stevena](https://www.ruby-forum.com/u/stevena)\
**Post date:** [November 23, 2005, 2:53pm UTC](https://www.ruby-forum.com/t/using-hashes-as-keys-in-hashes/48688/1 "2005-11-23T14:53:21Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![stevena](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/b5a626/32.png) [@stevena](https://www.ruby-forum.com/u/stevena)\
**Post date:** [November 23, 2005, 3:09pm UTC](https://www.ruby-forum.com/t/using-hashes-as-keys-in-hashes/48688/2 "2005-11-23T15:09:27Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![stevena](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/b5a626/32.png) [@stevena](https://www.ruby-forum.com/u/stevena)\
**Post date:** [November 23, 2005, 4:06pm UTC](https://www.ruby-forum.com/t/using-hashes-as-keys-in-hashes/48688/3 "2005-11-23T16:06:17Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![stevena](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/b5a626/32.png) [@stevena](https://www.ruby-forum.com/u/stevena)\
**Post date:** [November 23, 2005, 4:26pm UTC](https://www.ruby-forum.com/t/using-hashes-as-keys-in-hashes/48688/4 "2005-11-23T16:26:25Z")

</div>

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.