Fixed Point in Ruby Hash Function
A fixed point of a function \( f:S \to S \) is an element \(x \in S\) such that
That is, \(f\) is a noop on \(x\). Some examples:
 The identity function on any set has all points as fixed points
 The absolute value function has any positive real number as a fixed point
 The base64 encoding function has a string as a fixed point
(Check out that link above, fmota wrote about how they discovered a fixed point in the base64 encoding function, it’s very interesting)
Ruby’s Fixnum
class has an instance method called hash
. It is the
hash function
used by the Hash
class to locate the value.
One thing to note that is interesting,
1


The integer literal 42
is an instance of Ruby’s Fixnum
class,
which is exactly the type that is returned by Fixnum#hash
. So, if we
let N
be the set of all Fixnum
values, and h
be the hash function,
then the function
Does h
have a fixed point? Let’s find out, the generic way to find a
fixed point is to apply the function over and over and see if any of
the iterates are the same:
In Ruby, we could start with a value n
and loop until the next step
is the same as the current step:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 

This code terminates in 62 steps, here is the output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 

So the integer 4237831107247477683
is a fixed point of
Fixnum#hash
, that means that in the implementation of Hash
, the
value 4237831107247477683
would have itself as a key.
There are more examples (play with the code yourself!), and I would like to look deeper into why this hash function has a fixed point.