单线程
单线程环境下可以使用HashMap和TreeMap。TreeMap上遍历返回结果是按照Key排序的。

测试方法
记录写入Map中N条记录的时间，单位毫秒。
记录从N条记录的Map中读取10W条记录的时间，单位毫秒。
N=25W,50W,75W,100W

测试结果

多线程
多线程环境下可以使用以下四种Map容器。
1）Collections.synchronizedMap(new HashMap());
2）ConcurrentHashMap
3）Collections.synchronizedSortedMap(new TreeMap())
4）ConcurrentSkipListMap

测试方法
先启动N个写线程，每个写线程写入Map中100W/N条记录。
之后启动N个读线程，每个读线程从100W条记录的Map中读取10W条记录。
记录每个线程的写入/读取时间，单位毫秒。
在一台8核的Intel CPU上执行测试。

测试结果

单线程环境下，毫无疑问synchronizedHashMap 优于ConcurrentHashMap；synchronizedTreeMap 优于ConcurrentSkipListMap。
随着线程数增多，ConcurrentHashMap读写都优于synchronizedHashMap。
由于读不需要加锁，ConcurrentHashMap和ConcurrentSkipListMap读取时间都基本上不随线程数增加而增加，
而synchronizedHashMap和 synchronizedTreeMap， 因为读也要加锁，则随着线程数增加读取时间也增加。
特别是，8个线程下，ConcurrentSkipListMap的读写效率已经基本上接近synchronizedHashMap。如果线程数再增加，ConcurrentSkipListMap的性能应该会超过synchronizedHashMap。

===========================================================================================
测试程序

package learning.multithread.collection;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentSkipListMap;

/**
 * Set -Xms1024M to avoid JVM heap size increase during the test 
 */
public class ConcurrentMapTest {
    private static final int THREAD_NUM = 8;
    private static final int MAP_SIZE = 1000000;
    
    public static void main(String[] args) throws InterruptedException {
        List<Integer> list = new ArrayList<Integer>(MAP_SIZE);       
        for (int i = 0; i < MAP_SIZE; i++) {
            list.add(Integer.valueOf(i));
        }
        Collections.shuffle(list);
                
        singleThreadMapTest(new HashMap<Integer, Integer>(), list);
        //singleThreadMapTest(new TreeMap<Integer, Integer>(), list);
        
        //concurrentMapTest(Collections.synchronizedMap(new HashMap<Integer, Integer>()), list);
        //concurrentMapTest(new ConcurrentHashMap<Integer, Integer>(), list);
        //concurrentMapTest(Collections.synchronizedSortedMap(new TreeMap<Integer, Integer>()), list);
        //concurrentMapTest(new ConcurrentSkipListMap<Integer, Integer>(), list);
    }
    
    private static void singleThreadMapTest(Map<Integer, Integer> map, List<Integer> l) {
        //first run to load all to memories and set map initial size        
        mapReadWrite(map, l);
        mapReadWrite(map, l);
        map.clear();
        
        System.out.println("Now start test......");
        mapReadWrite(map, l.subList(0, (MAP_SIZE/4)));
        map.clear();
        mapReadWrite(map, l.subList(0, (MAP_SIZE/4)*2));
        map.clear();
        mapReadWrite(map, l.subList(0, (MAP_SIZE/4)*3));
        map.clear();
        mapReadWrite(map, l);
    }
    
    private static void mapReadWrite(Map<Integer, Integer> map, List<Integer> l) {        
        MapWriter mwHash = new MapWriter(map, l);
        mwHash.run();        
        MapReader mrHash = new MapReader(map, l.subList(0, (MAP_SIZE/10)));
        mrHash.run();
        System.out.println("Map Size = " + map.size());
    }
    
    private static void concurrentMapTest(Map<Integer, Integer> map, List<Integer> l) throws InterruptedException {        
        //first run to load all to memories and set map initial size    
        concurrentReadWrite(map, l);
        map.clear();
        concurrentReadWrite(map, l);
        map.clear();
        
        System.out.println("Now start test......");
        concurrentReadWrite(map, l);
        System.out.println("Map Size = " + map.size());
    }
    
    private static void concurrentReadWrite(Map<Integer, Integer> map, List<Integer> l)
            throws InterruptedException {
        Thread[] writerThreads = new Thread[THREAD_NUM];
        Thread[] readerThreads = new Thread[THREAD_NUM];
        
        int mapSize = MAP_SIZE/THREAD_NUM; 
        for (int i = 0; i < THREAD_NUM; ++i) {
            writerThreads[i] = new Thread(new MapWriter(map, l.subList(mapSize*i, mapSize*(i+1))));
        }
        for (int i = 0; i < THREAD_NUM; ++i) {
            writerThreads[i].start();
        }
        
        for (Thread t : writerThreads) {
            t.join();
        }
        
        for (int i = 0; i < THREAD_NUM; ++i) {
            readerThreads[i] = new Thread(new MapReader(map, l.subList(mapSize*i, mapSize*i+MAP_SIZE/10)));
        }
        for (int i = 0; i < THREAD_NUM; ++i) {
            readerThreads[i].start();
        }
        
        for (Thread t : readerThreads) {
            t.join();
        } 
    }
    
    private static class MapWriter implements Runnable {
        public MapWriter(Map<Integer, Integer> map, List<Integer> l) {
            this.map = map;
            this.l = l;
        }

        public void run() {
            long begin = System.currentTimeMillis();
            for(Integer i : l) {
                map.put(i, i);
            }
            long end = System.currentTimeMillis();
            
            System.out.println("Write time:" + (end - begin));            
        }

        private final Map<Integer, Integer> map;
        private final List<Integer> l;
    }
    
    private static class MapReader implements Runnable {
        public MapReader(Map<Integer, Integer> map, List<Integer> l) {
            this.map = map;
            this.l = l;
        }

        public void run() {
            long begin = System.currentTimeMillis();
            for (Integer i : l) {
                map.get(i);
            }
            long end = System.currentTimeMillis();
            
            System.out.println("Read time:" + (end - begin));
        }

        private final Map<Integer, Integer> map;
        private final List<Integer> l;
    }
}

Java多线程 -- Map容器性能比较