I worked late this long week-end to improve the implementation of Javolution high-performance FastMap . But finally, I believe that I got it! The "Swiss Knife/Universal /Holy Grail" map for developers! But judge for yourself:

• Performance on par with HashMap; but LinkedHashMap behavior (keep insertion order)


• Thread-safe without synchronization when marked shared (including map collection's iterations). Unlike ConcurrentHashMap access never blocks.


• Predictable response time (real-time), no large resize/rehash performed ever.


• Support for custom key/value comparators (e.g. custom hashcode implementations).


• Support for custom entries implementation (e.g. to implement efficient caching, the map's entries may include a time-stamp).


• RTSJ-Safe, FastMap can be allocated in ImmortalMemory (static instances) without causing memory leak when entries are removed (unlike standard maps)


• Utilities to print statistic, provide an unmodifiable view, etc...

What do you think? Is it the map "Holy Grail" ?

Note for the technical savvy: The new implementation uses a different approach for collision. Basically all entries are stored in the table, if there is a collision the entry is placed in the next available slot. The number of entries is always less than half the size of the table (creating enough holes). Large maps are recursively broken into smaller maps to maintain time predictability.

With regard to "get(key)" access HashMap, LinkedHashMap and FastMap do about the same thing. Basically, they are indexing a table based upon the key hash code. The first difference is that FastMap will not rehash the hash code unless it can determine that the hashcodes are not evenly distributed. For example, the default hash code for an object using the Sun VM is evenly distributed; on the other hand IBM VM uses the memory address for default hashcode (or something like that) which is far from optimal. A test is performed at startup to determine if the platform has an evenly distributed default hashcode (if not, rehash is performed). When hashcodes are calculated (e.g. String), they are generally well distributed.
Not having to rehash saves few computational cycles at least on the Sun platform (access to the entry is a direct: table[hashcode & (table.length - 1)] ).

Memory-wise, what takes the most space are the entries objects (not the tables). This is why FastMap and LinkedHashMap have a larger footprint than HashMap (the entries have two additional fields: next and previous). FastMap entries do not need the extra field to link to the entries in the same slot (otherwise it would be difficult to maintain thread-safety when resizing). Colliding entries are stored on adjacent slots.

Time-wise, allocating large arrays (HashMap/LinkedHashMap) is likely to create memory problems and delays (fragmentation, significant gc delays, etc). Try to allocate arrays greater than 1 million elements and you will see what I am talking about. FastMap does not have this issue because it resizes only up to a certain size then after that, forwards to sub-maps (which themselves resize up to a certain size and so on).

import java.util.HashMap;
 
import javolution.util.FastMap;
 
 
public class Test {
 
  static int SIZE = 200000;
  static Object value = new Object();
  static Integer[] keys;
  
  public static void main(String[] args) {
    keys = new Integer[SIZE];
    for ( int i =0; i < SIZE; i++ ) {
      keys[i] = new Integer(i);
    }
    for ( int i =0; i < 10; i++ ) {
      test();
      testJDK();
    }
  }
  
  
  public static void test() {
    
    long start,end;
    
    FastMap map = new FastMap(SIZE*2 + 1);
    
    // heat up the map
    
    for ( int i =0; i < SIZE; i++ ) {
      map.put(keys[i], value);
    }
    
    map.clear();
    
    for ( int i =SIZE-1; i >=0; i-- ) {
      map.put(keys[i], value);
    }
    
    start = System.nanoTime();
    
    for ( int i =SIZE-1; i >=0; i-- ) {
      map.remove(keys[i]);
    }
    
    
    end = System.nanoTime();
    System.out.println("EASY " + (end-start)/1000000.0 + "ms");
    
    
    
    map.clear();
    
    for ( int i =0; i < SIZE; i++ ) {
      map.put(keys[i], value);
    }
    
    
    start = System.nanoTime();
    
    for ( int i =0; i < SIZE; i++ ) {
      map.remove(keys[i]);
    }
    
    
    end = System.nanoTime();
    System.out.println("HARD " + (end-start)/1000000.0 + "ms");
  }
  
  
  public static void testJDK() {
    
    HashMap map = new HashMap(SIZE*2 + 1);
    
    // heat up the map
    
    for ( int i =0; i < SIZE; i++ ) {
      map.put(keys[i], value);
    }
    
    map.clear();
    
    
    for ( int i =SIZE-1; i >=0; i-- ) {
      map.put(keys[i], value);
    }
    
    
    long start = System.nanoTime();
    
    for ( int i =SIZE-1; i >=0; i-- ) {
      map.remove(keys[i]);
    }
    
    
    long end = System.nanoTime();
    System.out.println("JDKEASY " + (end-start)/1000000.0 + "ms");
    
    
    
    map.clear();
    
    for ( int i =0; i < SIZE; i++ ) {
      map.put(keys[i], value);
    }
    
    
    start = System.nanoTime();
    
    for ( int i =0; i < SIZE; i++ ) {
      map.remove(keys[i]);
    }
    
    
    end = System.nanoTime();
    System.out.println("JDKHARD " + (end-start)/1000000.0 + "ms");
  }
  
}
 

              _entries[slot & mask] = null;

              _entries[slot & mask] = NULL;