Hash function

Hash functions are often used to map a range of values to a smaller range
for example: you have bunch of pointers/integers/keys and you want to put them in a small array.
So what should a computer do to find out at what spot in array to put a key if there is only room for  100 keys?

there are many methods for doing that
simple one is to calculate key mod 100
here is a description of another one that uses floating point number format

code in C:

float f;
int i;
return uf.f*100

now how this works :
if we look at the 32 bit value of a key as a number in floating point format that C uses
this line
will make the sign bit, first and last exponent bits 0 while keeping all other bits as they were
this line
will set to 1 exponent bits between first and the last while keeping all other bits the same
so it will convert this integer/pointer  to a number between 0 and 1
that is nice since the bits manipulated were the upper bits and if a pointer is hashed they usually stay the same while the lower bits change because memory is allocated in one memory area called heap

now all that’s left is to multiply that floating point number with length of array to get its place in array

return uf.f*100

What it may be useful for? Maybe implementing a hash table for a new programming language 😀 but there are many other solutions so maybe it’s better to try a bunch of them out and do some benchmarking 🙂

Leave a Comment