Performance of TreeMap, HashMap and LinkedHashMap?

Use a HashMap unless you have some need for ordering. HashMap is faster.

That said, you can make it easy to switch by using the generic interface as your declaration:

 Map<String,String> M = new HashMap<String,String>();
 ...use M lots of places...

Then all you have to do is switch one place and your code uses the new map type.

Edit:

A simple timing test:

import java.util.*;
class TimingTest {
  public static void main(String[] args) {
    Map<String,String> M = new HashMap<String,String>();
    long start = System.currentTimeMillis();
    for (int i = 0; i < 100000; i++) {
      M.put(Integer.toString(i), "foo");
    }
    long end = System.currentTimeMillis();
    System.out.println(end - start);
  }
}