Anyone know of a java.util.Map implementation optimized for low memory use?

Question

I've looked in the usual places (apache commons, google) and not been able to find one ...

It should be opensource.

Pretty much looking for one based on a linked list. The use case is 10'000's of maps, with not necessarily many values in. It does not need to scale up, as i can convert it when it gets too big.

Some numbers, sizes using some calculated jvm values (8bytes/java.lang.Object, 4bytes/ref) the HashMap is about 100+32n bytes, the theoretical best is 12+20*n. <-- I want that, for small n.

Answer 1

Simply, I recommend to use one of HashMap, Hashtable and ConcurrentHashMap of JDK depending on synchronization or concurrency requirements. If you decide to use them, setting initialCapacity and loadFactor appropriately in the constructor may help.

Google collections and apache commons collections provide more features: LRUMap, ReferenceMap, MultikeyMap and so on. But I don't think there are not for just small size.

Answer 2

LinkedHashMap uses a linked list, I think, but I doubt that it's optimized for low memory use. Usually the whole point of a map is to speed up lookups from key to value, which explains why you're not finding what you need in the common places. It might just be easiest to write your own implementation of Map, and maybe you could even release the code in case anyone else needs the same thing.

Answer 3

Write the code in a way that hides the use of maps (you should be doing that anyways, and it sounds like you are as well). At the point when it matters, because you have profiled the code and can see that the memory is really an issue, find one :-)

If you know at this point in time that there is an issue, then, sorry I don't know of one. However too often people deal with the "idea" that the code is going to be slow/se lots of memory/etc... and start trying to optimize it up front rather than making the code correct.

That said, if you are writing something that you know it matters your should be measuring as you go. For instance I am working on code to parse class files, I make a small change and then see how it effects performance. For instance I knew for a fact that a change I made (3 lines) made my program go 4 times slower... I spent the time at that point un finding out the faster way to do it.

Also, are you sure that maps are needed if the value of "n" is small? Perhaps a List is fast enough? Also have you tried tuning the existing Map to have it use less memory?

Answer 4

Could have a look at commons-collections Flat3Map, it's optimised to store 3 values in 3 fields and overflows to another map at 4.

I haven't looked at the implementation but it may be worth thinking about. Only trouble is that since commons-collections is 1.3 compatible there are no generic's.

Answer 5

Wrap an ArrayList with the Map interface. The ArrayList uses only a few bytes itself. Each node needs two pointers, one for the key and one for the value. Use sequential search to look up values. As long as there are only few entries, performance will be OK[*]. This will give you the leeway to use real maps for the few vases where you have a large number of values.

*: Say your average map size is 10. Todays computers can compare roughly 100 million keys per second, so each lookup will take less than five microseconds on average.

If the performance is still too bad for your use case, you can try to sort the array by key and use binary search.

Answer 6

It depends a lot on how you are going to use those maps, can you populate them in one shot and then just do lookups (do you need those lookups to be fast).

An implementation using a minimal amount of memory would be to put all elements in a array and to do a scan to find elements (but I guess this is not enough fast for your needs)...

If you now all elements at the beginning you can try to select a good hash method with not too much collisions.

Or maybe you could use TreeMap if you allow slow insertion time...

Answer 7

Ok, implemented it myself in the end. I did a speed comparison, and found when compared to a HashMap that it was still slightly faster with 4 entries, but slower with 5 or more. I did the tests with a longish list of keys that I tried to give a similar makeup as a list of random english words.

import java.util.*;

// PUBLIC DOMAIN
public class SmallMap extends AbstractMap {

 private Entry entry = null;

 public void clear() { entry = null; }
 public boolean isEmpty() { return entry==null; } 
 public int size() {
  int r = 0;
  for(Entry e = entry; e!=null; e = e.next) r++;
  return r;
 }

 public boolean containsKey(Object key) {
  for(Entry e = entry; e!=null; e = e.next){
   if(e.key.equals(key)){
    return true;
   }
  }
  return false;
 }

 public boolean containsValue(Object value) {
  for(Entry e = entry; e!=null; e = e.next){
   if(e.value==null){
    if(value==null) return true;
   }else if(e.value.equals(value)){
    return true;
   }
  }
  return false;
 }

 public Object get(Object key) {
  for(Entry e = entry; e!=null; e = e.next){
   if(e.key.equals(key)){
    return e.value;
   }
  }
  return null;
 }

 public Object put(Object key, Object value) {
  for(Entry e = entry; e!=null; e = e.next){
   if(e.key.equals(key)){
    Object r = e.value;
    e.value = value;
    return r;
   }
  }
  entry = new Entry(key, value, entry);
  return null;
 }

 public Object remove(Object key) {
  if(entry!=null){
   if(entry.key.equals(key)){
    Object r = entry.value;
    entry = entry.next;
    return r;
   }
   for(Entry e = entry; e.next!=null; e = e.next){
    if(key.equals(e.next.key)){
     Object r = e.next.value;
     e.next = e.next.next;
     return r;
    }
   }
  }
  return null;
 }

 public Set entrySet() { return new EntrySet(); }

 class EntrySet extends AbstractSet{
  public Iterator iterator() {
   return new Iterator(){

    Entry last = null;
    Entry e = entry;
    public boolean hasNext() { return e!=null; }

    public Object next() { 
     last = e;
     e = e.next;
     return last;
    }

    public void remove() { 
     if(last == null) throw new IllegalStateException();
     SmallMap.this.remove(last.key);
    }
   };
  }

  public int size() { return SmallMap.this.size();}
 }

 static private class Entry implements java.util.Map.Entry {
  final Object key;
  Object value;
  Entry next; 
  Entry(Object key, Object value, Entry next){
   if(key==null) throw new NullPointerException();
   this.key = key;
   this.value = value;
   this.next = next;
  }
  public Object getKey() { return key; }
  public Object getValue() { return value; }
  public Object setValue(Object value) { 
   Object r = this.value;
   this.value = value;
   return r;
  }
  public int hashCode() {
      return (key   == null ? 0 :   key.hashCode()) ^
      (value == null ? 0 : value.hashCode());
  }
 }
}

Answer 8

Maybe this answer is a bit late, but take a look at Javolution project. It contains implementations of many data structures, intended for embedded and real-time enviroments. Concretely, there is a FastMap class that might just do what you want.

Answer 9

If you store Strings only, take a look at http://code.google.com/p/flatmap

edit Oh sorry, I see you are looking for small not huge maps, forget about my advice then.