How to map 13 bit value to 4 bit code?

Question

I have a std::map for some packet processing program.

I didn't noticed before profiling but unfortunately this map lookup alone consume about 10% CPU time (called too many time).

Usually there only exist at most 10 keys in the input data. So I'm trying to implement a kind of key cache in front of the map.

Key value is 13 bit integer. I know there are only 8192 possible keys and array of 8192 items can give constant time lookup but I feel already ashamed and don't want use such a naive approach :(

Now, I'm just guessing some method of hashing that yield 4 bit code value for 13 bit integer very fast.

Any cool idea?

Thanks in advance.

UPDATE

Beside my shame, I don't have total control over source code and it's almost prohibited to make new array for this purpose.

Project manager said (who ran the profiler) linked list show small performance gain and recommended using std::list instead of std::map.

UPDATE

Value of keys are random (no relationship) and doesn't have good distribution.

Sample:
1) 0x100, 0x101, 0x10, 0x0, 0xffe
2) 0x400, 0x401, 0x402, 0x403, 0x404, 0x405, 0xff

Answer 1

Assuming your hash table either contains some basic type -- it's almost no memory at all. Even on 64-bit systems it's only 64kb of memory. There is no shame in using a lookup table like that, it has some of the best performance you can get.

Answer 2

You may want to go with middle solution and open addressing technique: one array of size 256. Index to an array is some simple hash function like XOR of two bytes. Element of the array is struct {key, value}. Collisions are handled by storing collided element at the next available index. If you need to delete element from array, and if deletion is rare then just recreate array (create a temporary list from remaining elements, and then create array from this list).

If you pick your hash function smartly there would not be any collisions almost ever. For instance, from your two examples one such hash would be to XOR low nibble of high byte with high nibble of low byte (and do what you like with remaining 13-th bit).