title: Compact alternatives to Java ArrayList<String>
body: <p>I need to store a large dictionary of natural language words -- up to 120,000, depending on the language. These need to be kept in memory as profiling has shown that the algorithm which utilises the array is the time bottleneck in the system.  (It's essentially a spellchecking/autocorrect algorithm, though the details don't matter.)  On Android devices with 16MB memory, the memory overhead associated with Java <code>String</code>s is causing us to run out of space. Note that each <code>String</code> has a <a href="http://www.javamex.com/tutorials/memory/string_memory_usage.shtml" rel="nofollow noreferrer">38 byte overhead associated with it,</a> which gives up to a 5MB overhead. </p>
  
  <p>At first sight, one option is to substitute <code>char[]</code> for <code>String</code>. (Or even <code>byte[]</code>, as UTF-8 is more compact in this case.) But again, the memory overhead is an issue: <a href="https://stackoverflow.com/a/14919961/1908650">each Java array has a 32 byte overhead</a>. </p>
  
  <p>One alternative to <code>ArrayList&lt;String&gt;</code>, etc. is to create an class with much the same interface that internally concatenates all the strings into one gigantic string, e.g. represented as a single <code>byte[]</code>, and then store offsets into that huge string. Each offset would take up 4 bytes, giving a much more space-efficient solution.</p>
  
  <p>My questions are a) are there any other solutions to the problem with similarly low overheads* and b) is any solution available off-the-shelf?  Searching through the <a href="https://github.com/google/guava" rel="nofollow noreferrer">Guava</a>, <a href="https://bitbucket.org/trove4j/trove" rel="nofollow noreferrer">trove</a> and <a href="http://pcj.sourceforge.net/" rel="nofollow noreferrer">PCJ</a> collection libraries yields nothing.</p>
  
  <p>*I know one can get the overhead down below 4 bytes, but there are diminishing returns.</p>
  
  <p>NB. <a href="https://stackoverflow.com/questions/8833385/is-support-for-compressed-strings-being-dropped">Support for Compressed Strings being Dropped in HotSpot JVM?</a> suggests that the JVM option <code>-XX:+UseCompressedStrings</code> isn't going to help here.</p>