Avoid Storing Keys in Key-Value Store by Replacing the Key with 128-bit Murmur3 Hash

I want to develop LRU key-value data store and in that wanted to get rid of space to store the key itself. Instead wanted to store a 128 bit murmur hash. The structure of data-store that I want to explore is similar to CPU k-way set-associative caches.

So the algorithm I want to pursue is -

1. Compute a murmur 3 hash for given key.
2. Using the hash find the set where the data should be stored.
3. Let us say the cache is 4 way associative, therefore I have four slots where I can store the data.
4. If the slots are already full I kick out the one earliest used.
5. I store the hash in-place of key itself. But I understand that collisions are possible.
6. Banking on avalanche effect (this is risky and hence the question), I am assuming that if the two strings differ only by a little, the hash will be different. However, two 'largely' different strings may still collide.
7. Since the hash is of fixed size (128 bit) let us say, I can get rid of memcmp() of the whole key length, which is 256-byte long (max) in my system.
8. I store just the hash, and compare hash to the stored hash (which acts like TAG in the cache). In case the two strings collide, I also store few bytes (say 15-20 bytes) along with their offsets which needs to be compared only if hash values match.

Assumed benefit of this is -

1. no need to store keys and hence huge space can be saved
2. avoid memcmp() on full length of the key, and the hash which is calculated once is used both for matching keys and identifying slots.

I want evaluation and review of this method and if there are ways on we can solidify this. I understand that comparison of bytes at some offsets may not be the reliable way. Are there any other existing methods which avoid storing of keys?

• I don't think this is an appropriate place to ask this question. It strikes me as more appropriate for Software Engineering, although I don't hang out there so I don't really know what their criteria are. From a theoretical point of view, hash collisions are always possible, and if the consequences are sufficiently severe then saying "it's very unlikely" may not be a sufficient safeguard. From a more practical POV, memcmp will practically never take more time than a single-word comparison precisely because strings in the same hash set typically differ in the first few bytes. – rici Jun 16 at 16:18
• @rici Thanks for the alert. +1 – ultimate cause Jun 18 at 2:27
• @rici "because strings in the same hash set typically differ in the first few bytes." ... This is some thing I was not aware of. Can you please point me to any reference on this? – ultimate cause Jun 18 at 2:29
• It's a simple consequence of how hashing has to work if it is going to do a good job. It's not saying anything different from your point 6; similar keys have different hashes. – rici Jun 18 at 4:40