Very simple Java implementation of a map from characters to objects based on a radix tree.

It's not actually that fast, as I've not bothered to optimise it at all (a brief attempt didn't work very well and I lost interest after that). It seems to be a little slower than a HashMap using boxed Characters and a little faster than a TreeMap (when the JIT gets up to speed anyway. Before the JIT has done any optimisation the hashmap is 2 or 3 times faster). I might at some point implement a HashMap using unboxed characters for keys to see what kind of performance improvement it gives.

Using a large array is of course faster than all of the options by an order of magnitude, but has the downside of being a bit too large to be useful. :-)

   1  
   2  public class RadixCharMap<T>
   3  {
   4      private RadixCharMap<T> map0; 
   5      private RadixCharMap<T> map1;
   6      private T value;
   7      
   8      private RadixCharMap<T> getMap(int i){
   9          if (i > 0) return map1 == null ? (map1 = new RadixCharMap<T>()) : map1;
  10          else return map0 == null ? (map0 = new RadixCharMap<T>()) : map0;}    
  11      
  12      public RadixCharMap<T> put(char key, T value){
  13          if (key == '\0') this.value = value;
  14          else getMap(key & 1).put((char)(key >> 1), value);
  15          return this;}
  16      
  17      public T get(char key){
  18          RadixCharMap current = this;
  19          if (key == '\0') return this.value;
  20          else return getMap(key & 1).get((char)(key >> 1));}
  21  }