Which is more efficient; which is faster? Trade-offs?

Goal is for fast look-ups in a web application.

UUIDs are the keys, so global will work.
Approx 50 million values.

A global cache is definitely more manageable than many smaller ones, even using JMX. But, I had a hunch that maybe the total overhead of the hashtable's internals would somehow be less with a global hashtable vs many spread out through various classes. However, I cannot find any evidence of this.

Edit: Please, you must back-up your claim if it is that the overhead is minimal or even if it is significant. Maybe this should be moved to the Computer Science forum?

  • 2
    Just make sure your hash map has at least a 64-bit key; a 32-bit key will start to see collisions after around 50,000 random entries. – user23157 Aug 12 '11 at 8:25
  • +1 for insight. The Birthday problem. Mouth, do you know of any 64-bit implementations in Java? – Tom Jones Aug 12 '11 at 23:22
  • Yes - it's the birthday problem (in a previous life I was a mathematician). I know that they don't exist natively in the .NET world, where I live, I guess the same goes for Java, but rolling your own is not difficult. However you then have the maintenance cost of the containers and it all gets awful. IMO the 32-bit hash is the next millennium bug. – user23157 Aug 12 '11 at 23:50
  • After reviewing the b-day prob, I take back what I said... I think. The hashspace is the table size, not the key space (actually the min of the two). So, unless I want to have a table size = 2^64, collisions will just be unavoidable. Do you see? I'm using this formula: en.wikipedia.org/wiki/…. – Tom Jones Aug 13 '11 at 0:07
  • So, if the hash is perfectly randomly distributed then when there is 1 value in the hash set the chance of NOT having a collision (i find it easier to think this way) is 1 (i.e. no collision); when there are two there is (N-1)/N where N is the size of the set that the hash injects onto; with three it is (N-1)*(N-2)/N^2... (N-1)*(N-2)*...*(N-n)/N^n. Naturally as n --> N the probability of not having a collision tends to 0. So of course there is always the chance of a collision, the big question is when should you be worried about it. With a 32-bit hash and 50 M values it is almost guaranteed. – user23157 Aug 13 '11 at 0:30

There won't be any significant difference in space. The per-table overhead is negligible compared to the 50 million table entries. Just write the cleanest possible code.


I have to ask, are you sure you are not re-inventing the wheel? There are several good in-memory caches out there (JCS, Terracotta, EHCache and many more)

Not the answer you're looking for? Browse other questions tagged or ask your own question.