StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><b>Edit</b>: I just saw you mentioned the String were UK postcodes so I'm fairly confident you couldn't get very wrong by using a Trove <em>TLongIntHashMap</em> (btw Trove is a small library and it's very easy to use).</p> <p><b>Edit 2</b>: Lots of people seem to find this answer interesting so I'm adding some information to it.</p> <p>The goal here is to use a map containing keys/values in a memory-efficient way so we'll start by looking for memory-efficient collections.</p> <p>The following SO question is related (but far from identical to this one).</p> <p><a href="https://stackoverflow.com/questions/629804/what-is-the-most-efficient-java-collections-library">What is the most efficient Java Collections library?</a></p> <p><em>Jon Skeet</em> mentions that Trove is <em>"just a library of collections from primitive types"</em> [sic] and, that, indeed, it doesn't add much functionality. We can also see a few benchmarks (by <em>the.duckman</em>) about memory and speed of Trove compared to the default Collections. Here's a snippet:</p> <pre><code> 100000 put operations 100000 contains operations java collections 1938 ms 203 ms trove 234 ms 125 ms pcj 516 ms 94 ms </code></pre> <p>And there's also an example showing how much memory can be saved by using <em>Trove</em> instead of a regular Java <em>HashMap</em>:</p> <pre><code>java collections oscillates between 6644536 and 7168840 bytes trove 1853296 bytes pcj 1866112 bytes </code></pre> <p>So even though benchmarks always need to be taken with a grain of salt, it's pretty obvious that <em>Trove</em> will save not only memory but will always be much faster.</p> <p>So our goal now becomes to use Trove (seen that by putting millions and millions of entries in a regular <em>HashMap</em>, your app begins to feel unresponsive). </p> <p>You mentioned 2 million pairs, 7 characters long keys and a String/int mapping.</p> <p>2 million is really not that much but you'll still feel the "Object" overhead and the constant (un)boxing of primitives to Integer in a regular HashMap{String,Integer} which is why Trove makes a <em>lot</em> of sense here.</p> <p>However, I'd point out that if you have control over the "7 characters", you could go even further: if you're using say only ASCII or ISO-8859-1 characters, your 7 characters would fit in a long (*). In that case you can dodge altogether objects creation and represent your 7 characters on a long. You'd then use a Trove <em>TLongIntHashMap</em> and bypass the "Java Object" overhead altogether.</p> <p>You stated specifically that your keys were 7 characters long and then commented they were UK postcodes: I'd map each postcode to a long and save a tremendous amount of memory by fitting millions of keys/values pair into memory using Trove.</p> <p>The advantage of Trove is basically that it is <strong>not</strong> doing constant boxing/unboxing of Objects/primitives: Trove works, in many cases, directly with primitives and primitives only.</p> <p><i>(*) say you only have at most 256 codepoints/characters used, then it fits on 7*8 == 56 bits, which is small enough to fit in a long.</i></p> <p>Sample method for encoding the <code>String</code> keys into <code>long</code>'s (assuming ASCII characters, one byte per character for simplification - 7 bits would be enough):</p> <pre><code>long encode(final String key) { final int length = key.length(); if (length > 8) { throw new IndexOutOfBoundsException( "key is longer than 8 characters"); } long result = 0; for (int i = 0; i < length; i++) { result += ((long) ((byte) key.charAt(i))) << i * 8; } return result; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload