# What’ s the best general implementation of custom #hash methods?

**URL:** <https://www.ruby-forum.com/t/whata-s-the-best-general-implementation-of-custom-hash-methods/175293>\
**Category:** Ruby\
**Created:** [September 10, 2009, 5:56pm UTC](https://www.ruby-forum.com/t/whata-s-the-best-general-implementation-of-custom-hash-methods/175293 "2009-09-10T17:56:44Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![Shot\_SPiotr\_S.S](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/e79b87/32.png) [@Shot\_SPiotr\_S.S](https://www.ruby-forum.com/u/Shot_SPiotr_S.S)\
**Post date:** [September 10, 2009, 5:56pm UTC](https://www.ruby-forum.com/t/whata-s-the-best-general-implementation-of-custom-hash-methods/175293/1 "2009-09-10T17:56:44Z")

</div>

Hello, ruby-talk.

What’s the best (fast, yet with relatively few cases when equal hashes  
are generated for non-eql objects) way to implement a hash method?

Is XOR-ing the hashes of an object’s instance variables (assuming that  
two objects are eql if their ivars are eql) a good general approach?

I’m asking because I use this pattern in my code, and it seems quite  
fast; I needed to work around a bug in MRI’s Set#hash and this solution¹  
seems about as fast as the original MRI’s Set#hash. I’m just not sure  
whether it’s hashy enough (so to speak) in that two un-eql objects  
hashed in this way produce different hashes often enough.

¹

> <https://github.com/Chastell/art-decomp/commit/b465660b9dcc8eada86f50bbcb8f951aa8145a19>

— Shot

---

<div class="post-metadata">

**Author:** ![Shot\_SPiotr\_S.S](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/e79b87/32.png) [@Shot\_SPiotr\_S.S](https://www.ruby-forum.com/u/Shot_SPiotr_S.S)\
**Post date:** [September 10, 2009, 6:53pm UTC](https://www.ruby-forum.com/t/whata-s-the-best-general-implementation-of-custom-hash-methods/175293/2 "2009-09-10T18:53:31Z")

</div>

On Thu, Sep 10, 2009 at 11:56 AM, Shot (Piotr S.)[removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
wrote:

> seems about as fast as the original MRI’s Set#hash. I’m just not sure  
> whether it’s hashy enough (so to speak) in that two un-eql objects  
> hashed in this way produce different hashes often enough.

Well, let’s look at how Array#hash works here’s the 1.8 C code:

static VALUE  
rb\_ary\_hash(ary)  
VALUE ary;  
{  
long i, h;  
VALUE n;

```
h = RARRAY(ary)->len;
for (i=0; i<RARRAY(ary)->len; i++) {

```

h = (h \<\< 1) | (h\<0 ? 1 : 0);  
n = rb\_hash(RARRAY(ary)-\>ptr[i]);  
h ^= NUM2LONG(n);  
}  
return LONG2FIX(h);  
}

This looks like a typical cryptographic hash algorithm pattern  
combining bit rotation and xor. It seeds the value with the length of  
the array, then for each element, rotates the value 1 bit to the left,  
then xors in the elements hash.

This scrambles the bits more than just a straight xor

–  
Rick DeNatale

Blog: [http://talklikeaduck.denhaven2.com/](http://talklikeaduck.denhaven2.com/)  
Twitter: [http://twitter.com/RickDeNatale](http://twitter.com/RickDeNatale)  
WWR: [http://www.workingwithrails.com/person/9021-rick-denatale](http://www.workingwithrails.com/person/9021-rick-denatale)  
LinkedIn: [http://www.linkedin.com/in/rickdenatale](http://www.linkedin.com/in/rickdenatale)

---

<div class="post-metadata">

**Author:** ![Shot\_SPiotr\_S.S](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/e79b87/32.png) [@Shot\_SPiotr\_S.S](https://www.ruby-forum.com/u/Shot_SPiotr_S.S)\
**Post date:** [September 10, 2009, 8:04pm UTC](https://www.ruby-forum.com/t/whata-s-the-best-general-implementation-of-custom-hash-methods/175293/3 "2009-09-10T20:04:22Z")

</div>

Shot (Piotr S.) wrote:

> Hello, ruby-talk.
> 
> What’s the best (fast, yet with relatively few cases when equal hashes  
> are generated for non-eql objects) way to implement a hash method?

One way is to just put everything you care about into an array and hash  
that, as in:

[http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/230421](http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/230421)

But it might not qualify as “fast”, I suppose.

---

<div class="post-metadata">

**Author:** ![Shot\_SPiotr\_S.S](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/e79b87/32.png) [@Shot\_SPiotr\_S.S](https://www.ruby-forum.com/u/Shot_SPiotr_S.S)\
**Post date:** [September 11, 2009, 2:10am UTC](https://www.ruby-forum.com/t/whata-s-the-best-general-implementation-of-custom-hash-methods/175293/4 "2009-09-11T02:10:49Z")

</div>

You could check out some of these (in several languages including Ruby):

> **[.:: General Purpose Hash Function Algorithms - By Arash Partow ::.](http://www.partow.net/programming/hashfunctions/#Download)**
>
> The General Hash Function Algorithm library contains implementations for a series of commonly used additive and rotative string hashing algorithm in the Object Pascal, C and C++ programming languages

---

<div class="post-metadata">

**Author:** ![Shot\_SPiotr\_S.S](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/e79b87/32.png) [@Shot\_SPiotr\_S.S](https://www.ruby-forum.com/u/Shot_SPiotr_S.S)\
**Post date:** [November 5, 2009, 9:50pm UTC](https://www.ruby-forum.com/t/whata-s-the-best-general-implementation-of-custom-hash-methods/175293/5 "2009-11-05T21:50:35Z")

</div>

On Sep 10, 10:49 am, Rick DeNatale [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> > fast; I needed to work around a bug in MRI’s Set#hash and this solution¹  
> > long i, h;  
> > }
> 
> This looks like a typical cryptographic hash algorithm pattern  
> combining bit rotation and xor. It seeds the value with the length of  
> the array, then for each element, rotates the value 1 bit to the left,  
> then xors in the elements hash.
> 
> This scrambles the bits more than just a straight xor
> 
> –  
> Rick DeNatale

I must take STRONG exception to your characterization of this  
algorithm. This method performs parallel xors of the data. Change one  
bit of one of the values, and you change one bit of the hash. A  
fundamental property of cryptographic hashes is that changing one bit  
of the input changes many bits of output. This is even true of crcs.  
Cryptographic hashes do rotate & xor (sometimes), but only as part of  
a larger operation.

---

<div class="post-metadata">

**Author:** ![Shot\_SPiotr\_S.S](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/e79b87/32.png) [@Shot\_SPiotr\_S.S](https://www.ruby-forum.com/u/Shot_SPiotr_S.S)\
**Post date:** [September 11, 2009, 2:16am UTC](https://www.ruby-forum.com/t/whata-s-the-best-general-implementation-of-custom-hash-methods/175293/6 "2009-09-11T02:16:41Z")

</div>

On 9/10/09, Shot (Piotr S.) [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> Hello, ruby-talk.
> 
> What’s the best (fast, yet with relatively few cases when equal hashes  
> are generated for non-eql objects) way to implement a hash method?
> 
> Is XOR-ing the hashes of an object’s instance variables (assuming that  
> two objects are eql if their ivars are eql) a good general approach?

The drawback to this algorithm would be that if you have the same  
values but in different variables, they’ll end up hashing the same.  
For example:

class Pair  
def initialize(a,b)  
@a,@b=a,b  
end  
def hash  
@a.hash^@b.hash  
end  
end

Pair.new(“foo”,“bar”).hash==Pair.new(“bar”,“foo”).hash #=\>true

As a practical matter, this often doesn’t matter. It depends on the  
application and if you think this kind of situation is likely. For  
general purpose use, it’s better to have some way of encoding the  
‘location’ of each sub-value in the hash as well.