Hash Function Study Guide

Question

This is a question on my study guide for my Final and I don't seem to understand it.

Q: Assume all variable names are required to start with a letter, may be a mix of letters and numbers and is case sensitive, can be up to 10 characters long. Hash table is 1000 entries. Suggest a hash function that work for this table size.

Would this be something like 64^10?

Thank You

This is a related (maybe identical?) question: http://stackoverflow.com/questions/34595/what-is-a-good-hash-function — jogojapan, Jun 14 '13 at 06:00
There are many, many hash functions that could work. Without knowing more about what kind of operations you're (possibly) restricted to, it's difficult to answer. `64^10` makes no sense - it's a constant value - what does it have to do with hashing something? — Yuushi, Jun 14 '13 at 06:01

paxdiablo · Answer 1 · 2013-06-14T06:40:37.353

There are a great many hash functions that would work for those constraints and it really depends on the likely distribution of characters as to which is the best.

I assume your 64¹⁰ figure is meant to be the number of possibilities for variable names but it's slightly wrong - it should be 52x62⁹ to to the limitation that the first character cannot be numeric but, in any case, that doesn't allow for variables shorter than ten characters so it's approximate only. In reality, it would be something like 52 + 52x62 + 52x62² + 52x62² + ... + 52x62⁹.

It's also pretty much irrelevant to the hash function itself.

Probably the simplest hash function you can choose is to run through the variable name extracting each "value" (0 through 61 for the 26 uppercase, 26 lowercase and 10 numeric) and simply calculate a value between 0 and 999 based on that:

def hashIt (varname):
    chars =
        "0123456789" +
        "ABCDEFGHIJKLMNOPQRSTUVWXYZ" +
         abcdefghijklmnopqrstuvwxyz"
    hashVal = 0
    for each char in varname:
        hashVal = (hashVal * len(chars) + chars.findIndexOf(char)) % 1000
    return hashVal

Again, that doesn't take into account likely distribution of letters but, since you've provided no information on that, there's mot much we can do.

Hash Function Study Guide

1 Answers1