Could we also try to confgure the key size? I wonder whether we get results based on our assumption that the key takes really just 10 bytes - in fact there is the String object, holding char[] object which has more than 10 byte - we can account the String stuff as the overhead, but still... I'd personally prefer some wrapper for variable-length byte[], which would define the required equals() and hashCode(). Then, changing the array size, you could find out the actual overhead for the wrapper (assuming that this stays constant).