map集合解决双重for循环的性能问题

超、凢脫俗 2022-04-03 06:44 427阅读 0赞

最近做了一个项目，做到权限管理模块时，需要展示权限树，在controller层需要使用双重循环解决权限的父子嵌套关系。

## 原始代码 ##

@RequestMapping("/loadData")
    	@ResponseBody
    	public Object loadData() {
    		
    		AjaxResult ajaxResult=new AjaxResult();
    		
    		//获取权限树
    		try {
    			List<Permission> permissionTree=new ArrayList<Permission>();
    			
    			//所有权限
    			List<Permission> allPermission = permissionService.queryAllPermission();
    			
    			for (Permission permission : allPermission) {
    				//找到根权限
    				if(permission.getPid()==null) {
    					Permission root=permission;
    					//设置根权限默认打开
    					root.setOpen(true);
    					permissionTree.add(root);
    				}else {
    					//如果不是根权限，根据其pid找到其父权限，将其加入到父权限的chridren中、
    					for (Permission permission2 : allPermission) {
    						if(permission.getPid()==permission2.getId()) {
    							permission2.getChildren().add(permission);
    							//每个权限最多只有一个权限，所以找到后退出本循环
    							break;
    						}
    					}
    				}
    				
    			}
    			ajaxResult.setData(permissionTree);
    			ajaxResult.setSuccess(true);
    			ajaxResult.setMessage("权限树获得成功");
    		} catch (Exception e) {
    			e.printStackTrace();
    			ajaxResult.setSuccess(false);
    			ajaxResult.setMessage("加载权限树失败");
    		}
    		return ajaxResult;
    	}

假设有100中权限，则使用双重循环的时间复杂度为100\*100=10000；

## 使用map集合改进 ##

@RequestMapping("/loadData")
    	@ResponseBody
    	public Object loadData() {
    		
    		AjaxResult ajaxResult=new AjaxResult();
    		
    		//获取权限树
    		try {
    			List<Permission> permissionTree=new ArrayList<Permission>();
    			
    			//所有权限
    			List<Permission> allPermission = permissionService.queryAllPermission();
    			
    			Map<Integer,Permission> map=new HashMap<Integer,Permission>();
    			//100次
    			for (Permission permission : allPermission) {
    				map.put(permission.getId(), permission);
    			}
    			//100次
    			for (Permission permission : allPermission) {
    				Permission child=permission;
    				//找到根权限
    				if(child.getPid()==null) {
    					//设置根权限默认打开
    					child.setOpen(true);
    					permissionTree.add(child);
    				}else {
    					//如果不是根权限，找到他的父权限将其放入父权限的chridren中
    					Permission parent = map.get(child.getPid());
    					parent.getChildren().add(child);
    				}
    				
    			}
    			ajaxResult.setData(permissionTree);
    			ajaxResult.setSuccess(true);
    			ajaxResult.setMessage("权限树获得成功");
    		} catch (Exception e) {
    			e.printStackTrace();
    			ajaxResult.setSuccess(false);
    			ajaxResult.setMessage("加载权限树失败");
    		}
    		return ajaxResult;
    	}

时间复杂度为100+100=200；  
显然使用这种方式的效率是比双重循环快不少的

## 心得总结 ##

> 使用map<Integer,Permission>，利用map集合根据key值取数据的特点规避了使用双重循环，从而极大的减小了算法的时间复杂度。  
> 注意：  
> 1.使用这个技巧时需要注意是否有可用的key可以找到，这里使用了permission的id来作为map集合的key，如果没能找到合适的key那么也只能采用双重循环的方式解决  
> 2.数据库的表采用自关联的方式（权限permission中的id和pid，> 其中pid为父权限的id）