巧用Map缓存提升"翻译"速度

在业务编码中，很多情况都需要用到code2Name或者id2Name之间的“翻译”，在我的过往经历中发现不少开发人员都是直接双重循环实现这种“翻译”。如果一次“翻译”的数据量较多，性能就遇上瓶颈了，这时可以考虑使用Map缓存的方式提升速度。

示例
用户表（userId， levelNum）
级别表 (levelNum, levelName）
现在要将用户列表中每个用户的levelNum翻译成levelName展示。

代码如下：

package test;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class TranslateTest {
      public static void main(String[] args) {
           //初始化列表数据
           int num = 10000;
           List<User> userList = new ArrayList<User>();
           List<Level> levelList = new ArrayList<Level>();
           for(int i=0; i<num; i++) {
                 userList.add(new User(i, i));
                 levelList.add(new Level(i, "等级:" + i));
           }
           
           //使用双重循环翻译
           long startTime = System.currentTimeMillis();
           translateLoop(userList, levelList);
           System.out.println("translateLoop use: " + (System.currentTimeMillis() - startTime)  + " MS");
           clearTranslateResult(userList);
           
           //使用map缓存翻译
           startTime = System.currentTimeMillis();
           translateUseMap(userList, levelList);
           System.out.println("translateUseMap use: " + (System.currentTimeMillis() - startTime)  + " MS");
      }
      
      //清除翻译结果
      static void clearTranslateResult(List<User> userList) {
           for(User user : userList) {
                 user.setLevelName(null);
           }
      }
      
      static void translateLoop (List<User> userList, List<Level> levelList){
           for(User user : userList) {
                 for(Level level : levelList) {
                      if(user.getLevelNum() == level.getLevelNum()) {
                            user.setLevelName(level.getLevelName());
                            break;
                      }
                 }
           }
      }
      
      static void translateUseMap(List<User> userList, List<Level> levelList) {
           Map<Integer, String> levelNum2Name = new HashMap<Integer, String>();
           for(Level level : levelList) {
                 levelNum2Name.put(level.getLevelNum(), level.getLevelName());
           }
           for(User user : userList) {
                 user.setLevelName(levelNum2Name.get(user.getLevelNum()));
           }
      }
      
      static class Level {
           //级数
           private int levelNum;
           //级别名称
           private String levelName;
           
           public Level(int levelNum, String levelName) {
                 this.levelNum = levelNum;
                 this.levelName = levelName;
           }
           
           public int getLevelNum() {
                 return levelNum;
           }
           public void setLevelNum(int levelNum) {
                 this.levelNum = levelNum;
           }
           public String getLevelName() {
                 return levelName;
           }
           public void setLevelName(String levelName) {
                 this.levelName = levelName;
           }
      }
      
      static class User {
           private int userId;//用户ID
           private int levelNum;//级数
           
           public User(int userId, int levelNum) {
                 this.userId = userId;
                 this.levelNum = levelNum;
           }
           
           //翻译后的值
           private String levelName;
           
           public String getLevelName() {
                 return levelName;
           }
           public void setLevelName(String levelName) {
                 this.levelName = levelName;
           }
           public int getUserId() {
                 return userId;
           }
           public void setUserId(int userId) {
                 this.userId = userId;
           }
           public int getLevelNum() {
                 return levelNum;
           }
           public void setLevelNum(int levelNum) {
                 this.levelNum = levelNum;
           }
      }
}

结果
translateLoop use: 311 MS
translateUseMap use: 9 MS

将num加大到100000后测试结果：
translateLoop use: 75964 MS
translateUseMap use: 58 MS

总结
translateLoop使用了双重循环，时间复杂度是 O(nn)
translateUseMap，由于map的get方法通常情况下（hash不碰撞）时间复杂度是 O(1)，则总时间复杂度为 O(n + 1n)
我认为：程序员，即使只是实现业务代码，还是要有空间换时间，时间换空间的意识；即使平时用不上算法，还是要对常用的算法和时间复杂度有所了解。