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.

About these ads

Pages: 1 2

6 Responses to “Universal Hash Function”

  1. burr said

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

  2. Probably cheating in Python: use the id() function. From calling help(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.)

  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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 643 other followers

%d bloggers like this: