4

Why does Ruby hash an integer n to 2 * n + 1?

>> [0,1,2,3].each {|x| puts x.hash}
1
3
5
7

I can see that you don't always need to have complicated hashes, especially for simple objects. But why the 'double and add 1' rule as opposed to doing what Python does, which is to hash integers to themselves?

>>> map(hash,[0,1,2,3])
[0, 1, 2, 3]

Is there a reason?

Chris Taylor
  • 46,912
  • 15
  • 110
  • 154
  • what version of ruby are you using? – J. Holmes Feb 09 '12 at 21:24
  • I've got a very different output in ruby19 on Linux: `-4507979699089292723 -2858483109482119521 -3969476086452127319 2371950802045904379` – Oleg Mikheev Feb 09 '12 at 21:26
  • ruby 1.8.7 (2010-01-10 patchlevel 249) [universal-darwin11.0] – Chris Taylor Feb 09 '12 at 21:26
  • 2
    I'd love to know the answer too. I can think of at least two interesting characteristics of that hash: (1) as long as 'n' isn't too big, you can easily calculate the original number given the hash, and (2) the low-order bit of the hash is always set. If a different type always hashed to have a zero low-order bit, you could very quickly filter between the two types by checking that bit. – Bruce Feb 09 '12 at 21:26
  • @oleg i get similar results on windows and mac with 1.9 – J. Holmes Feb 09 '12 at 21:28

1 Answers1

4

Integers are objects, so they have an object_id. But there is an infinite number of integers. Seemingly, no room for other objects. How does Ruby pull this off?

10.times{|i| puts i.object_id}

Output:

1
3
5
7
9
11
13
15
17
19

Integers take all odd object_id's, the rest of the objects go in between, they use the even numbers. The conversion from object_id (and hash) to integer (and vice versa) is very easy: chop the rightmost 1 bit (or add it).

steenslag
  • 79,051
  • 16
  • 138
  • 171