Universal Hash Function
October 23, 2012
Recently, when writing a program that shall remain anonymous, I needed a hash table with keys that could be either strings or integers. That may sound weird to you — it felt weird enough to me that I rearranged things so that all the keys had the same type. But the experience got me thinking about a universal hash function that could be used with keys of any type.
Your task is to write a hash function, suitable for your normal programming environment, that can take a value of any type and return a thirty-two bit integer suitable for use in a hash table. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
>>> ht = {“Test”: “String”, 1: “Integer”}
>>> ht[1]
‘Integer’
>>> ht[“Test”]
‘String’
>>>
Probably cheating in Python: use the
id()function. From callinghelp(id)in my Python environment:
id(…)
id(object) -> integer
Return the identity of an object. This is guaranteed to be unique among
simultaneously existing objects. (Hint: it’s the object’s memory address.)
In Python it is trivial, as you can use hash(object), which gives a hash for many data types. Hash refuses to give a value for mutable objects like a list, which makes sense.
Using Shen (which I’m definitely intrigued by):
(tc +) (define praxis-hash {A --> number --> number} X N -> (hash X N)) (praxis-hash praxising 1729)Sorry, link above is wrong; here’s the correct link.
[…] Pages: 1 2 […]