title: Calculating HashMap overhead in Java
body: <p>Let's say I'm storing 1000 objects in a hashmap. This hashmap is extended to allow me to map three dimensional coordinates to the objects stored in it; the objects inside have a fixed size. The hash key is a long integer.</p>
  
  <p>How would I go about figuring out (mathematically) the probable overhead for this structure? </p>
  
  <ol>
  <li>Is it significant enough that, for instance, if the data inside is around 256mb that the overhead will matter?</li>
  <li>Is there a reliable way (Aside from a profiler, which I've found are unreliable in some cases) to mathematically calculate what its overhead <em>should be</em>?</li>
  </ol>
  
  <p>I'm not interested in the total size of the hashmap - only the <em>overhead</em> that using the hashmap will incur. For instance, if I have 10 ints they're 4 bytes a piece, so it's 40 bytes. If I stick them in an array, I get a constant overhead of 12 bytes - 8 for the object header, 4 for the length. If I put them in another structure (a TreeSet for instance) my overhead will not be constant because a tree needs nodes - so I might get an overhead expressed in terms of n where n is the number of items in the set.</p>
  
  <p>A few things are obvious to me, which I'll give as my starting point here.</p>
  
  <ol>
  <li>I will need to store at least 1000 longs. These are nullable types, so they're actually objects. I will assume therefore that the 8 byte long integer being used has an object header also of 8 bytes. I will add a factor of 16n.</li>
  <li>I will need references to every object as well, which must exist whether or not the object has been recalled from the map and is being used; so that's an additional 8 bytes per object. We could factor it into the data size instead, but since the references are in the hashmap itself, I feel like it's best to make them part of the overhead. My logic is as follows: If I took all of the data out of the hashmap and stored it in variables, those n references would still exist in the hashmap, provided I didn't <em>remove</em> these data objects, which I won't be doing. The set of objects is constant, though they may be recycled with a different key.</li>
  <li>The hashmap itself has an overhead of 8 bytes. </li>
  <li>The hashmap <em>must</em> store the number of items inside (or so I think!) so that's 4 bytes.</li>
  <li>I will suppose ignorantly that the hash keys are in an array, sorted by hash key order. That's 12 bytes for the array.</li>
  <li>I will assume ignorantly as well that the objects are in a matching array, which it dereferences when it finds the key. I will guess another 12 bytes.</li>
  </ol>
  
  <p>This gives me a polynomial equation: 36 + 24n</p>
  
  <p>Thus I have a guess of 24036 bytes overhead for 1000 data objects using long keys. This is somewhat of an insignificant overhead, but my question for you is, what is the real overhead, just sitting there?</p>
  
  <hr>
  
  <p>A secondary valid question is, how much does this vary from JVM to JVM? Is there any JVM independent way to figure it out? To exemplify what I mean, consider a JVM that only has 32bit object headers - when looking at arrays you might say, even though the size varies from JVM to JVM, it's a fair estimate that the overhead on an array would become 8 bytes instead of 12 in that case. </p>
  
  <p>I'm assuming a fixed implementation of HashMap across the same version of Java. </p>
  
  <hr>
  
  <p>I could try to read the source code or run profiling, this however may produce misleading results based on my JVM. I'm asking for your help - perhaps someone who knows - for some piece of info that we both don't already know about the situation. Thanks!</p>
  
  <hr>
  
  <p>See the answer below, the actual estimate can be expressed as follows:</p>
  
  <p>8 words per entry, plus 8 bytes for each long, plus 8 bytes for the hashmap object header.</p>
  
  <p>In my present environment (32 bit OS) that makes 1 word = 4 bytes.</p>
  
  <ul>
  <li>40n + 8 in a 32bit environment: ~ 40k for 1000 entries</li>
  <li>72n + 8 in a 64bit environment: ~ 72k for 1000 entries.</li>
  </ul>
  
  <p>So it seems to be under 100kbytes.</p>