java implementation of SmallMap

gistfile1.txt

class SmallMap {
	  static  int MAX_ENTRIES=16;
	  Object[] keys=new Object[MAX_ENTRIES];
	  int[] hashCodes=new int[MAX_ENTRIES];
	  Object[] values=new Object[MAX_ENTRIES];
	  Map fallbackMap;
	  int currentSize=0;
	  // Turns out, meet-in-the middle search really helps! Improvement is quite visible on size 16
	  int _findIndex(int hashCode) {
	     for (int i=0, j=currentSize-1; j>=i; i++, j--) {
	        if (hashCodes[i]==hashCode) return i;
	        if (hashCodes[j]==hashCode) return j;
	     }
	     return -1;
	  }

	  void _createFallback() {
	    System.out.println("creating fallback!");
	    fallbackMap=new HashMap();
	    for (int i=0; i<currentSize; i++) {
	      fallbackMap.put(keys[i],values[i]);
	    }
	    _clear();
	  }
	  Object get(Object key) {
	     if (fallbackMap!=null) {
	       return fallbackMap.get(key);
	     }
	     int index=_findIndex(key.hashCode());
	     return index>=0 && keys[index].equals(key) ? values[index] : null;
	  }
	  void put(Object key, Object value) {
	    if (fallbackMap!=null) {
	      fallbackMap.put(key,value);
	      return;
	    }
	    int hashCode=key.hashCode();    
	    int index=_findIndex(hashCode);
	    // there are 3 cases: 1) adding new key 2) replacing value for old key 3) fallback
	    // case 1) is statistically most important so we try it first
	    // NOTE: don't "optimize" the redandant comparison of index with 0, it's intentional
	    if (index<0 && currentSize<MAX_ENTRIES) { // case 1: new key
	      keys[currentSize]=key;
	      values[currentSize]=value;
	      hashCodes[currentSize]=hashCode;
	      currentSize++;
	    } else if (index>=0 && keys[index].equals(key)) { // case 2: replacement
	      values[index]=value;
	    } else { // case 3: fallback
	      _createFallback();
	      fallbackMap.put(key,value);
	    }
	  }
	  void _clear() {
	    for (int i=0, j=currentSize-1; j>=i; i++, j--) {
	        keys[i]=keys[j]=null;
	        values[i]=values[j]=null;
	    }
	    currentSize=0;
	  }
	  void clear() {
	    _clear();
	    fallbackMap=null;
	  }
}