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.


Pages: 1 2

6 Responses to “Universal Hash Function”

  1. burr said

    >>> ht = {“Test”: “String”, 1: “Integer”}
    >>> ht[1]
    >>> ht[“Test”]

  2. Probably cheating in Python: use the id() function. From calling help(id)
    in my Python environment:

    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.)

  3. Paul said

    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.

  4. Using Shen (which I’m definitely intrigued by):

    (tc +)
    (define praxis-hash
      {A --> number --> number}
      X N -> (hash X N))
    (praxis-hash praxising 1729)
  5. Sorry, link above is wrong; here’s the correct link.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: