Hash function for short strings

chashmathstring

I want to send function names from a weak embedded system to the host computer for debugging purpose. Since the two are connected by RS232, which is short on bandwidth, I don't want to send the function's name literally. There are some 15 chars long function names, and I sometimes want to send those names at a pretty high rate.

The solution I thought about, was to find a hash function which would hash those function names to a single byte, and send this byte only. The host computer would scan all the functions in the source, compute their hash using the same function, and then would translate the hash to the original string.

The hash function must be

  1. Collision free for short strings.
  2. Simple (since I don't want too much code in my embedded system).
  3. Fit a single byte

Obviously, it does not need to be secure by any means, only collision free. So I don't think using cryptography-related hash function is worth their complexity.

An example code:

int myfunc() {
    sendToHost(hash("myfunc"));
}

The host would then be able to present me with list of times where the myfunc function was executed.

Is there some known hash function which holds the above conditions?

Edit:

  1. I assume I will use much less than 256 function-names.
  2. I can use more than a single byte, two bytes would have me pretty covered.
  3. I prefer to use a hash function instead of using the same function-to-byte map on the client and the server, because (1) I have no map implementation on the client, and I'm not sure I want to put one for debugging purposes. (2) It requires another tool in my build chain to inject the function-name-table into my embedded system code. Hash is better in this regard, even if that means I'll have a collision once in many while.

Best Answer

Try minimal perfect hashing:

Minimal perfect hashing guarantees that n keys will map to 0..n-1 with no collisions at all.

C code is included.