public class MapSortingMain {
  public static void main(String[] args) {
    // 設定したソート条件を持つマップを作成
    SortedMap > map = new TreeMap>(new Comparator() {
        public int compare(KeyRecord o1, KeyRecord o2) {
            return o1.getName().compareToIgnoreCase(o2.getName());
        }
      });
    // マップにデータを投入
    try{
      map.put(new KeyRecord("EFG"), Arrays.asList(4,5,6));
      Thread.sleep(2000);
      map.put(new KeyRecord("ABC"), Arrays.asList(2,3,4,5));
      Thread.sleep(2000);
      map.put(new KeyRecord("HIJ"), Arrays.asList(1,4,8,90,3));
      map.put(new KeyRecord("A2"), Arrays.asList(1,14,58,91,1));
      map.put(new KeyRecord("A4"), Arrays.asList(11,24,48,92,2));
      map.put(new KeyRecord("A1"), Arrays.asList(12,34,28,93,3));
      map.put(new KeyRecord("A3"), Arrays.asList(13,44,38,94,4));
    } catch (InterruptedException e){
    }
    // ソート済Mapを指定サイズに切り捨てる
    while (5 < map.size()){
      map.remove(map.lastKey());
    }
    // データをキー順番で取り出して表記
    for( Iterator it = map.keySet().iterator(); it.hasNext(); ) {
      KeyRecord entryKey = (KeyRecord) it.next();
      System.out.printf("%s(%s)\n", entryKey.getName(), entryKey.getCreateDate());
    }
  }
}

処理結果

A1(1409305245000)
A2(1409305245000)
A3(1409305245000)
A4(1409305245000)
ABC(1409305243000)