精华内容
下载资源
问答
  • 最近项目中有5个导入模块,想复制粘贴,加上最近对注解和反射有点想用的的冲动,写了个粗略的动态导入: ...2、外键关联字段,如属于哪个部门 ,dept_id(导入的是中文名称,需要将对应的id查询出来) 3、...

    最近项目中有5个导入模块,不想复制粘贴,加上最近对注解和反射有点想用的的冲动,写了个粗略的动态导入:

    PS:以下内容过长,容易引起舒适度不爽,请做好心理准备

    一、需求分析:

    0、导入的数据列头是中文,所以需要用反射 + 注解进行对应

    1、基础字段,如user 的 name 、age;

    2、外键关联字段,如属于哪个部门 ,dept_id(导入的是中文名称,需要将对应的id查询出来)

    3、外键内关联字段 , 如部门属于哪个事业部,business_unit_id, 这个是和 2相关的,当然还可能出现第3个互相关联字段,假设有权限表,其根据部门来设置的,后面代码有会有具体讲解(此处是最麻烦的,注解配置项会很多,达到了11个)

    4、验证功能,如user 的身份证号、手机号、各种信息长度等

    5、外联字段可能需要同时导入id和name

    6、将每一行,出错的列都统计处理,并返回

    二、外键关联字段实现思路:

    1、对于基础字段来说,动态导入很简单,只需要有 @FiledMappingAnnotation(cnName="表头") 就可以了,当然需要加入限制,如下:

     @FiledMappingAnnotation(cnName = "密码", validate = RegexConst.NO_EMPTY_STR,advice = "必填,长度6-32位且不能有空格",length = 32)

    2、以下着重对外键关联字段说明思路

       ① 如果只是单独的外键关联,不与其他字段发生关系,则需要配置该字段关联的表的serviceImpl来查询数据,达到根据中文名称获取id,以下是一个例子:

    @FiledMappingAnnotation(cnName = "职务", pkName = "name", pkCode = "id", actionFiled = "0", beanName = "hospitalQuarterDictServiceImpl",advice = "非必填,必须为已有职务才能使用",length = 100)

    后面注解中详细讲解每一个的含义

       ② 如果需要与其他字段发生关联关系,则需要更加复杂的实现,需要将字段进行分级处理,高等级的字段,实现 2,低等级的字段通过高等级的字段查询自己的值,如:  

    @FiledMappingAnnotation(cnName = "医院名称", pkName = "name", pkCode = "id",
                actionFiled = "0",validate = RegexConst.NOT_NULL,beanName = "hospitalServiceImpl",
                fieldLevel = "height",advice = "必填,且必须为已有医院",length = 50)
                private Long hospitalId;   ---医院是高等级字段

     @FiledMappingAnnotation(cnName = "科室名称",contingencyName = "name",contingencyCode = "id",
                actionFiled = "0",validate = RegexConst.NOT_NULL, beanName = "hospitalDeptServiceImpl"
                ,fieldLevel = "low",heightField = "hospitalId",correlationField = "hospitalId",
                advice = "必填,且必须为已有科室",length = 50)
                 private Integer deptId;     --- 科室是低等级字段

    PS:此处的高低等级针对导入时的一种实现策略,可能中间还有更加复杂的,高、中、低三等,甚至存在 高、中、中、低等。

    三、代码实现:

    1、注解类

    package com.ih.common.util.annotation;
    
    import java.lang.annotation.ElementType;
    import java.lang.annotation.Retention;
    import java.lang.annotation.RetentionPolicy;
    import java.lang.annotation.Target;
    
    /**
     * 导入时,用于映射中英文字段,包括当前table表的外联表字段值
     */
    @Target(ElementType.FIELD)
    @Retention(RetentionPolicy.RUNTIME)
    public @interface FiledMappingAnnotation {
        /**
         * 是否name 和 id一起导入
         * @return
         */
        String moreoverName() default "";
        /**
         * 列的中文名称
         /
        String cnName();
    
        /**
         * 外联表的name字段 -- 导入的外联表字段在其他表的数据库(实体)名称 如 张三 关联user表 name ,如费用、关联Fee表 fee
         * @return
         */
        String pkName() default "";
    
        /**
         * 外联表的code字段  -- 导入的外联表名称对应的 需要插入当前表中的 id或者其他属性 如 id,code
         * @return
         */
        String pkCode() default "";
        /**
         * mid/low 查询自关联表的字段名称 --表中存在内关联字段的时候,中、低等级配置的,与高、中等级在关联表中的字段,
         * 如: user 属于医院下的科室,此时科室为低,医院为高,其关联表为科室表,科室的名称关联的字段是 name
         * @return
         */
        String contingencyName() default "";
    
        /**
         * mid/low 查询自关联表的id 
         * @return
         */
        String contingencyCode() default "";
        /**
         * 外联表 字段作用范围
         * -1 -> 自己基础字段
         * 0 -> 关联字段
         * @return
         */
        String actionFiled() default "-1";
    
        /**
         * 校验规则,正则表达式
         * @return
         */
        String validate() default "";
    
        /**
         * 用于是否启用、性别之类的映射关系
         * @return
         */
        FiledMappingEnum[] state() default {};
    
        /**
         * 关联字段-只能为string
         * 是将多关联分级处理了
         * 见下面fieldLevel
         * @return
         */
        String correlationField() default "";
    
        /**
         * 描述关联字段的等级高级
         * height -- 名称必须唯一的
         * mid -- 仅当该节点有父子关系的时候配置
         * low
         * 如医院 -> 科室 -> 人员
         * height - mid - low
         * 如 院区<- 医院 -> 科室
         *    low - height - low
         * @return
         */
        String fieldLevel() default "";
    
        /**
         * 外联表对象service bean
         * @return
         */
        String beanName() default "";
    
        /**
         * height/mid 等级在中间表的外键 与 contingencyName contingencyCode在同一张表中,用于高等级查询低等级
         * @return
         */
        String heightField() default "";
    
        /**
         * 限制长度
         * @return
         */
        long length() default 0L;
    
        /**
         * 验证出错的信息提示
         * @return
         */
        String message() default "数据格式错误";
    
        /**
         * 导入错误的建议
         * @return
         */
        String advice() default "修改数据";
    }
    

    2、枚举类

    package com.ih.common.util.annotation;
    
    public enum FiledMappingEnum {
        MALE("男","0"),FAMALE("女","1"),ENABLE("启用",1),DISABLE("停用",0),NONE("none",null),BUILDAUTHORITY("是",1),BUILDAUTHORITYNO("否",0),MANAGER("是",1),MANAGERNO("否",0);
    
        private String name;
        private Object value;
    
        FiledMappingEnum(String name,Object value) {
            this.name = name;
            this.value = value;
        }
    
        public Object getValue() {
            return value;
        }
    
        public String getName() {
            return name;
        }
    }

    3、正则表达式常量类(大部分都是网上直接摘抄的)

    package com.ih.common.util.annotation;
    
    public class RegexConst {
        /**
         * 校验非必填属性不填值和填值,用@Length限制
         */
        public static final String EMPTY_OR_NOT = "^$|^[\\s\\S]*(\\s*\\S+)([\\s\\S]*)$";
        /**
         * 登录账号,密码等不允许有空格
         */
        public static final String NO_EMPTY_STR = "^\\S{0,32}$";
        /**
         * 不能为空,可以有空格在任意地方,可以用@NotNull @NotEmpty @NotBlank 替换
         * (?=^.{0,30}$)(^([\s\S]*(\s*\S+)([\s\S]*))$)  //可以加长度限制,没有@Length灵活,重复太多
         */
        public static final String NOT_NULL = "^[\\s\\S]*(\\s*\\S+)([\\s\\S]*)$";
    
        /**
         * 如英文名字之类的,开头、结尾不允许为空,中间可以为空
         */
        public static final String BEGIN_NOT_NULL = "^[\\S]+(\\s*\\S+)*([\\S]*)$";
    
        public static final String CAN_NULL_AND_BEGIN_NOT_NULL = "^$|^[\\S]+(\\s*\\S+)*([\\S]*)$";
    
        /**
         * 比率相关 可以为空 不超过100
         */
        public static final String RATE = "^$|^0$|^100$|^(([1-9][0-9])|([1-9]))(\\.[0-9]{1,2})?$";
        /**
         * 速率
         */
        public static final String VELOCITY = "^(0|[1-9][0-9]{0,8})(\\.[0-9]{1,2})?$";
        /**
         * 速率 可以为空
         */
        public static final String VELOCITY_CAN_NO = "^(0|[1-9][0-9]{0,8})(\\.[0-9]{1,2})?$";
        /**
         * 不超过366天
         */
        public static final String YEAR = "^([0-9]|[1-9][0-9]|[1-2][0-9]{2}|3[0-5][0-9]|36[0-6])$";
        /**
         * 中文名称
         */
        public static final String CHINES_ENAME = "^[\\u0391-\\uFFE5]+$";
        /**
         *  非中文-验证的时候去除英文提示信息
         */
        public static final String NOT_CHINES_ENAME = "^[^\\u0391-\\uFFE5]*[^\\u0391-\\uFFE5]+?";
        /**
         * 性别
         */
        public static final String SEX = "^[男女]$";
        /**
         * 电话号码
         */
        public static final String PHONE_NUM = "^1[3|4|5|6|7|8|9][0-9]\\d{8}$";
        /**
         * 可以为空的电话
         */
        public static final String CONTACT_PHONE_NUM = "^$|^1[3|4|5|6|7|8|9][0-9]\\d{8}$";
        /**
         * 邮箱
         */
        public static final String EMAIL = "^[a-zA-Z0-9_.-]+@[a-zA-Z0-9-]+(\\.[a-zA-Z0-9-]+)*\\.[a-zA-Z0-9]{2,6}$";
        /**
         * 价格
         */
        public static final String PRICE = "^(0|[1-9][0-9]{0,8})(\\.[0-9]{1,2})?$";
        /**
         * 15或者18位身份证号
         */
        public static final String ID_CARD = "^[1-9]\\d{5}\\d{2}((0[1-9])|(10|11|12))(([0-2][1-9])|10|20|30|31)\\d{2}[0-9]$||^[1-9]\\d{5}(18|19|([23]\\d))\\d{2}((0[1-9])|(10|11|12))(([0-2][1-9])|10|20|30|31)\\d{3}[0-9Xx]$";
        /**
         * 出生日期
         */
        public static final String BIRTH_DAY = "^(([0-9]{3}[1-9]|[0-9]{2}[1-9][0-9]{1}|[0-9]{1}[1-9][0-9]{2}|[1-9][0-9]{3})-(((0[13578]|1[02])-(0[1-9]|[12][0-9]|3[01]))|((0[469]|11)-(0[1-9]|[12][0-9]|30))|(02-(0[1-9]|[1][0-9]|2[0-8]))))$|^((([0-9]{2})(0[48]|[2468][048]|[13579][26])|((0[48]|[2468][048]|[13579][26])00))-02-29)$";
    
    }
    

    4、上下文对象

    package com.ih.common.util.annotation;
    
    import org.springframework.beans.BeansException;
    import org.springframework.context.ApplicationContext;
    import org.springframework.context.ApplicationContextAware;
    import org.springframework.stereotype.Component;
    
    @Component
    public class SpringContextUtil implements ApplicationContextAware {
        private static ApplicationContext applicationContext;
    
        @Override
        public void setApplicationContext(ApplicationContext applicationContext){
            SpringContextUtil.applicationContext = applicationContext;
        }
        public static ApplicationContext getApplicationContext(){
            return applicationContext;
        }
    
        public static Object getBean(String name) throws BeansException {
            return applicationContext.getBean(name);
        }
    }
    

    5、导入类

    package com.ih.common.util.util;
    
    import com.baomidou.mybatisplus.mapper.EntityWrapper;
    import com.ih.common.util.annotation.FiledMappingAnnotation;
    import com.ih.common.util.annotation.FiledMappingEnum;
    import com.ih.common.util.annotation.RegexConst;
    import com.ih.common.util.annotation.SpringContextUtil;
    import com.ih.common.util.base.UploadErrorMessage;
    import org.apache.commons.lang.StringUtils;
    import org.apache.poi.hssf.usermodel.HSSFWorkbook;
    import org.apache.poi.ss.usermodel.Cell;
    import org.apache.poi.ss.usermodel.Row;
    import org.apache.poi.ss.usermodel.Sheet;
    import org.apache.poi.ss.usermodel.Workbook;
    import org.apache.poi.xssf.usermodel.XSSFWorkbook;
    import org.springframework.stereotype.Component;
    import org.springframework.util.CollectionUtils;
    import org.springframework.web.multipart.MultipartFile;
    
    import java.lang.reflect.Field;
    import java.lang.reflect.InvocationTargetException;
    import java.lang.reflect.Method;
    import java.math.BigDecimal;
    import java.text.SimpleDateFormat;
    import java.util.*;
    
    /**
     * 通过反射动态解析excel
     */
    @Component
    public class ImportExcelUtils<T> {
        /**
         * 存放注解数据
         */
        private Map<String, Map<String, Object>> annotationMap;
        /**
         * 存放外键关联的数据 key为beanName,value为table的数据
         */
        private Map<String, List<Map<String, Object>>> dataMap;
        /**
         * 存放Class注解解析的数据,并和表格比较是否全部存在
         */
        private List<Map<String, Object>> recordList;
        /**
         * 存放未通过的数据
         */
        private List<UploadErrorMessage> allErrorList;
        /**
         * 存放验证通过的数据的索引
         */
        private List<Integer> dataRownumList;
        /**
         * 存放验证通过的数据
         */
        private List<T> entityList;
        /**
         * 存放所有的数据,因为需要验证重复的
         */
        private List<T> allDataList;
    
        /**
         * 存放所有的数据的索引,备用
         */
        private List<Integer> allDataRowNumList;
    
        Integer integer;
        /**
         * 存放无外联映射的数据索引
         */
        private Map<String, Object> heighLevelFieldValueMap;
        private Map<String, Object> midLevelFieldValueMap;
    
        public List<T> parseExcel(MultipartFile file,Class clazz) throws Exception {
            initStoreDataStructer();
            String fileName = file.getOriginalFilename();
            boolean isExcel2003 = true;
            if (fileName.matches("^.+\\.(?i)(xlsx)$")) {
                isExcel2003 = false;
            }
            Workbook wb = null;
            if (isExcel2003) {
                wb = new HSSFWorkbook(file.getInputStream());
            } else {
                wb = new XSSFWorkbook(file.getInputStream());
            }
            return parseExcel(clazz,wb,true);
        }
    
        /**
         * 初始化一些存储数据结构,每一个导入的结构必须是最新的
         */
        private void initStoreDataStructer() {
            allErrorList = new ArrayList<>();
            dataRownumList = new ArrayList<>();
            heighLevelFieldValueMap = new HashMap<>();
            midLevelFieldValueMap = new HashMap<>();
            entityList = new ArrayList<>();
            allDataList = new ArrayList<>();
            allDataRowNumList = new ArrayList<>();
            integer = 0;
        }
    
        public List<T> parseExcel(Class clazz, Workbook workbook,boolean isInit) throws Exception {
            if(!isInit){
                initStoreDataStructer();
            }
            Sheet sheet = workbook.getSheetAt(0);
            Row row = sheet.getRow(0);
            if (row == null) {
                return entityList;
            }
            //获取列总数
            int lastCellNum = row.getPhysicalNumberOfCells();
            getAnnotationMsg(clazz);
            //存储header是否在表格中
            getRecordList(lastCellNum, row);
            int lastRowNum = sheet.getLastRowNum();
            List<Map<String, Object>> tempStoreList;
            Set<String> fieldLevelSet = new HashSet<>();
            for (int i = 1; i <= lastRowNum; i++) {
                T object = (T) clazz.newInstance();
                Row currentRow = sheet.getRow(i);
                if (isAllRowEmpty(currentRow, row)) {
                    continue;
                }
                tempStoreList = new ArrayList<>();
                for (int j = 0; j < recordList.size(); j++) {
                    Map<String, Object> objectMap = recordList.get(j);
                    if ((Boolean) objectMap.get("isExist")) {
                        Map<String,Object> map = new HashMap<>();
                        map.put("rowNum",i + 1);
                        Cell cell = currentRow.getCell(j);
                        List<Map<String, Object>> data = dataMap.get(objectMap.get("beanName"));
                        //先对字段进行校验,校验不通过,则没有必要继续往下执行
                        boolean validateCondition = validateCellDataByValidateCondition(objectMap, cell, i + 1,data);
                        if(!validateCondition){
                            integer++;
                            if(j < recordList.size() - 1){
                                continue;
                            }else if (j == recordList.size() - 1){
                                setSelfCorrelationFieldValue(tempStoreList, object, fieldLevelSet);
                            }
                        }else {
                            //需要判断fieldLevel 如果不为null,表示是内关联的字段,暂时存起来,当循环的length为 recordList.size() - 1时执行
                            Object fieldLevel = objectMap.get("fieldLevel");
                            if (fieldLevel != null && ("mid".equals(fieldLevel) || "low".equals(fieldLevel))) {
                                fieldLevelSet.add(fieldLevel.toString());
                                objectMap.put("cell", cell);
                                objectMap.put("index", i + 1);
                                tempStoreList.add(objectMap);
                            } else {
                               setData(cell, objectMap, data, object,integer,i + 1);
                            }
                            if (j == recordList.size() - 1) {
                                setSelfCorrelationFieldValue(tempStoreList, object, fieldLevelSet);
                            }
                        }
                    }else if (j == recordList.size() - 1){
                        setSelfCorrelationFieldValue(tempStoreList, object, fieldLevelSet);
                    }
                }
                allDataList.add(object);
                allDataRowNumList.add(i + 1);
                if(integer == 0){
                    entityList.add(object);
                    dataRownumList.add(i + 1);
                }
            }
            return entityList;
        }
        /**
         * 通过配置的正则表达式校验 Cell数据是否满足条件
         * 如果校验不通过,则直接将信息放到最大的异常list里面
         * @param objectMap
         * @param cell
         * @param rowNum
         * @param data
         */
        private boolean validateCellDataByValidateCondition(Map<String, Object> objectMap, Cell cell,Integer rowNum,List<Map<String,Object>> data) {
            Object cnName = objectMap.get("cnName");
            String simpleName = getSimpleName(objectMap);
            UploadErrorMessage uploadErrorMessage = new UploadErrorMessage(rowNum,cnName.toString(),null,objectMap.get("advice").toString());
            if("Double,BigDecimal,Long,Integer,Date".contains(simpleName)){
                //获取值之前先判断类型是否匹配
                boolean typeMatches = typeMatches(cell, simpleName);
                if(!typeMatches){
                    uploadErrorMessage.setErrorInfo("不支持的数据类型");
                    allErrorList.add(uploadErrorMessage);
                    return false;
                }
            }
            Object value = getValueByFieldType(cell, simpleName);
            boolean validateData = validateData(objectMap, value,data);
            if(!validateData){
                uploadErrorMessage.setErrorInfo("数据验证失败");
                allErrorList.add(uploadErrorMessage);
                return false;
            }
            return true;
        }
    
        private Object validateDataPkValueIsExist(List<Map<String,Object>> data,String pkName,Object values) {
            if(values == null){
                return values;
            }
            Object id = null;
            for (int k = 0; k < data.size(); k++) {
                //外联表字段映射 其实就是name列的名字
                if (values.equals(data.get(k).get(pkName))) {
                    Object obj = data.get(k).get("id");
                    if (obj != null && obj instanceof Integer) {
                        id = Integer.parseInt(data.get(k).get("id").toString());
                    } else if (obj != null && obj instanceof Long) {
                        id = Long.parseLong(data.get(k).get("id").toString());
                    }
                    break;
                }
            }
            return id;
        }
    
        /**
         * 处理自关联字段的值
         *
         * @param tempStoreList
         * @return
         */
        private void setSelfCorrelationFieldValue(List<Map<String, Object>> tempStoreList, T object, Set<String> fieldLevelSet) throws ClassNotFoundException, InstantiationException, IllegalAccessException, InvocationTargetException {
            //判断有几个等级
            if (fieldLevelSet.size() == 1) {
                setHeightOrMidValue(tempStoreList, "low", heighLevelFieldValueMap, object);
            }
            if (fieldLevelSet.size() == 2) {
                setHeightOrMidValue(tempStoreList, "mid", heighLevelFieldValueMap, object);
                setHeightOrMidValue(tempStoreList, "low", midLevelFieldValueMap, object);
            }
        }
    
        private void setHeightOrMidValue(List<Map<String, Object>> tempStoreList, String level, Map<String, Object> fieldValueMap, T instance) throws ClassNotFoundException, InvocationTargetException, InstantiationException, IllegalAccessException {
            for (int i = 0; i < tempStoreList.size(); i++) {
                Map<String, Object> map = tempStoreList.get(i);
                Object contingencyName = map.get("contingencyName");
                Object contingencyCode = map.get("contingencyCode");
                Object heightField = map.get("heightField");
                Object correlationField = map.get("correlationField");
                Cell cell = (Cell) map.get("cell");
                Field field = (Field) map.get("field");
                String simpleName = getSimpleName(map);
                Object values = getValueByFieldType(cell, simpleName);
                List<Map<String, Object>> data = dataMap.get(map.get("beanName"));
                //如果是查询mid的值,需要将关联的字段拿出来作为条件判断
                if (level.equals(map.get("fieldLevel"))) {
                    for (int j = 0; j < data.size(); j++) {
                        Map<String, Object> dataTempMap = data.get(j);
                        Object selfNameValue = dataTempMap.get(contingencyName);
                        Object heightFieldValue = dataTempMap.get(heightField);
                        Object heightValue = fieldValueMap.get(correlationField);
                        //查出来的数据库数据中 根据名称获取的数据不能为空且关联字段的数据不能为空,最后根据cell值和关联字段自己的值进行比较
                        if (selfNameValue != null && heightFieldValue != null && selfNameValue.toString().equals(values)
                                && heightFieldValue.equals(heightValue)) {
                            field.setAccessible(true);
                            //满足情况下都需要设置值了
                            Object contingencyCodeValue = dataTempMap.get(contingencyCode);
                            if (contingencyCodeValue instanceof Integer) {
                                field.set(instance, Integer.parseInt(contingencyCodeValue.toString()));
                            } else if (contingencyCodeValue instanceof Long) {
                                field.set(instance, Long.parseLong(contingencyCodeValue.toString()));
                            }
                            if ("mid".equals(level)) {
                                midLevelFieldValueMap.put(field.getName(), contingencyCodeValue);
                            }
                            break;
                        } else if (j == data.size() - 1) { //找不到,就放到错误list
                            UploadErrorMessage uploadErrorMessage = new UploadErrorMessage(Integer.parseInt(map.get("index").toString()),map.get("cnName").toString(),"找不到数据",map.get("advice").toString());
                            allErrorList.add(uploadErrorMessage);
                        }
                    }
                }
            }
        }
        /**
         * 验证excel是否全部为空
         *
         * @param row      当前行
         * @param firstRow 第一行标题行
         * @return
         */
        private boolean isAllRowEmpty(Row row, Row firstRow) {
            if (row == null) {
                return true;
            }
            int count = 0;
            //单元格数量
            int rowCount = firstRow.getLastCellNum() - firstRow.getFirstCellNum();
            //判断多少个单元格为空
            for (int c = 0; c < rowCount; c++) {
                Cell cell = row.getCell(c);
                if (cell == null || cell.getCellType() == Cell.CELL_TYPE_BLANK || StringUtils.isEmpty((cell + "").trim())) {
                    count += 1;
                }
            }
            if (count == rowCount) {
                return true;
            }
            return false;
        }
    
        /**
         * 根据中文header获取对应的配置信息
         * 并且标识字段是否在实体类中存在
         */
        private void getRecordList(int lastCellNum, Row row) {
            recordList = new ArrayList<>();
            for (int i = 0; i < lastCellNum; i++) {
                String cellValue = row.getCell(i).getStringCellValue();
                Map<String, Object> filedProperty = annotationMap.get(cellValue);
                if (filedProperty == null) {
                    filedProperty = new HashMap<>();
                    filedProperty.put("isExist", false);
                } else {
                    filedProperty.put("isExist", true);
                }
                recordList.add(filedProperty);
            }
        }
    /**
     * 获取注解数据
     */
        private void getAnnotationMsg(Class clazz) throws InvocationTargetException, IllegalAccessException, NoSuchFieldException {
            annotationMap = new HashMap<>();
            dataMap = new HashMap<>();
            Map<String, Field> tempFieldMap = new HashMap<>();
            Field[] declaredFields = clazz.getDeclaredFields();
            for (Field field : declaredFields) {
                tempFieldMap.put(field.getName(), field);
            }
            //将需要映射的字段注解全部加载出来
            //根据依赖外联表的serviceBean将数据查询出来
            for (int i = 0; i < declaredFields.length; i++) {
                FiledMappingAnnotation annotation = declaredFields[i].getAnnotation(FiledMappingAnnotation.class);
                if (annotation == null) {
                    continue;
                }
                String cnName = annotation.cnName();
                String pkName = annotation.pkName();
                String pkCode = annotation.pkCode();
                String validate = annotation.validate();
                String actionFiled = annotation.actionFiled();
                String beanName = annotation.beanName();
                FiledMappingEnum[] state = annotation.state();
                String fieldLevel = annotation.fieldLevel();
                String contingencyCode = annotation.contingencyCode();
                String contingencyName = annotation.contingencyName();
                String correlationField = annotation.correlationField();
                String heightField = annotation.heightField();
                String message = annotation.message();
                String advice = annotation.advice();
                long length = annotation.length();
                Map<String, Object> tempMap = new HashMap<>();
                if (StringUtils.isNotEmpty(fieldLevel)) {
                    tempMap.put("fieldLevel", fieldLevel);
                    tempMap.put("contingencyCode", contingencyCode);
                    tempMap.put("contingencyName", contingencyName);
                    tempMap.put("correlationField", correlationField);
                    tempMap.put("heightField", heightField);
                }
                String moreoverName = annotation.moreoverName();
                if(StringUtils.isNotEmpty(moreoverName)){
                    Field field = clazz.getDeclaredField(moreoverName);
                    tempMap.put("moreoverName",field);
                }
                tempMap.put("cnName", cnName);
                tempMap.put("pkName", pkName);
                tempMap.put("pkCode", pkCode);
                tempMap.put("field", declaredFields[i]);
                tempMap.put("actionFiled", actionFiled);
                tempMap.put("validate", validate);
                tempMap.put("beanName", beanName);
                tempMap.put("state", state);
                tempMap.put("message", message);
                tempMap.put("length", length);
                tempMap.put("advice", advice);
                getTableData(beanName);
                annotationMap.put(cnName, tempMap);
            }
        }
    
    /**
    *  Ps : 此处是根据关联表配置的beanName通过反射查询数据,此处是用的MybatisPlus的selectMaps,如果没有该方法,可以自己写一个查询关联表所有数据的方法,如果需要通用,最好在baseServiceImpl里面统一定义
    *
    */
        private void getTableData(String beanName) throws InvocationTargetException, IllegalAccessException {
            if (!dataMap.containsKey(beanName) && StringUtils.isNotEmpty(beanName)) {
                Object bean = SpringContextUtil.getBean(beanName);
                Class<?> dependenceClass = bean.getClass();
                Method[] methods = dependenceClass.getMethods();
                Method method1 = null;
                for (Method method : methods) {
                    if ("selectMaps".equals(method.getName())) {
                        method1 = method;
                    }
                }
                method1.setAccessible(true);
                EntityWrapper entityWrapper = new EntityWrapper();
                List<Map<String, Object>> list = (List<Map<String, Object>>) method1.invoke(bean, entityWrapper);
                dataMap.put(beanName, list);
            }
        }
    
        /**
         * 对数据进行一系列的判断
         * 包括类型是否匹配,是否为空,是否满足正则表达式,状态类(性别、是否启用)是否满足等
         * @param objectMap
         * @param value
         * @return
         */
        private boolean validateData(Map<String, Object> objectMap, Object value,List<Map<String,Object>> data) {
            String validate = objectMap.get("validate").toString();
            String pkName = objectMap.get("pkName").toString();
            long length = Long.parseLong(objectMap.get("length").toString());
            if(CollectionUtils.isEmpty(data)){ //这是非关联字段
                if (value == null && StringUtils.isEmpty(validate)) {
                    //此处说明不校验,数据正确
                    return true;
                } else if (value == null && StringUtils.isNotEmpty(validate)) {
                    //此处说明需要校验,将值设置为空字符串,测试是否可以为空串
                    String str;
                    if(RegexConst.NO_EMPTY_STR.equals(validate)){
                        str = " ";
                    }else {
                        str = "";
                    }
                    return str.matches(validate);
                }
                //如果校验规则不为空,并且数据不满足,就中断当前行的操作
                if (StringUtils.isNotEmpty(validate) && (!value.toString().trim().matches(validate) || value.toString().length() > length)) {
                    return false;
                }
                //如果是state 需要判断数据是否在可选范围内
                FiledMappingEnum[] stateArr = (FiledMappingEnum[]) objectMap.get("state");
                if(stateArr != null && stateArr.length > 0){
                    Object stateTypeMatches = validateStateTypeMatches(objectMap, value);
                    if(stateTypeMatches == null){
                        return false;
                    }
                }
            }else if(!CollectionUtils.isEmpty(data)){ //关联字段
                if(StringUtils.isNotEmpty(validate) && StringUtils.isNotEmpty(pkName)){
                    return  validateDataPkValueIsExist(data,pkName,value) != null;
                }else if(StringUtils.isEmpty(validate) && value != null && ( value != null && StringUtils.isNotEmpty(value.toString()))){
                    return  validateDataPkValueIsExist(data,pkName,value) != null;
                }
            }
            return true;
        }
    
        /**
         * 经过上面的验证后,value到此不会为空
         * @param objectMap
         * @param value
         */
        private Object validateStateTypeMatches(Map<String, Object> objectMap,Object value) {
            Object stateValue = null;
            FiledMappingEnum[] stateArr = (FiledMappingEnum[]) objectMap.get("state");
            if(stateArr != null && stateArr.length > 0){
                for(FiledMappingEnum filedMappingEnum : stateArr){
                    if(filedMappingEnum.getName().equals(value)){
                        stateValue = filedMappingEnum.getValue();
                        break;
                    }
                }
            }
            return stateValue;
        }
    
        /**
         * 如果字段是bean本身的数据,直接用本身的字段类型,如果字段是关联的其他表或者表格中数据与实体数据类型不符的,
         * 如id,将类型定位string,
         * 如果是日期,但是bean中是string ,转为Date,用于获取表格中数据
         * 如state 将类型转为string
         * @param objectMap 字段注解数据
         * @return
         */
        private String getSimpleName(Map<String, Object> objectMap) {
            Field field = (Field) objectMap.get("field");
            String actionFiled = objectMap.get("actionFiled").toString();
            FiledMappingEnum[] state = (FiledMappingEnum[]) objectMap.get("state");
            //获取字段类型
            String simpleName = field.getType().getSimpleName();
            simpleName = "-1".equals(actionFiled) ? simpleName : "String";
            if (RegexConst.BIRTH_DAY.equals(objectMap.get("validate").toString())) {
                simpleName = "Date";
            }else if(state != null && state.length > 0){
                simpleName = "String";
            }
            return simpleName;
        }
    
        //只负责设置数据就可以,前面已经做了数据类型校验和正则匹配
        private void setData(Cell cell, Map<String, Object> objectMap, List<Map<String, Object>> data, T object,Integer integer,Integer rowNum){
            try{
                String simpleName = getSimpleName(objectMap);
                Object values = getValueByFieldType(cell, simpleName);
                //查询数据,根据作用字段获取值
                String pkName = objectMap.get("pkName").toString();
                Field field = (Field) objectMap.get("field");
                String actionFiled = objectMap.get("actionFiled").toString();
                field.setAccessible(true);
                switch (actionFiled) {
                    case "-1"://是自己的字段,只需要判断数据类型
                        Object typeMatches = validateStateTypeMatches(objectMap, values);
                        if(typeMatches != null){
                            values = typeMatches;
                        }
                        field.set(object, values);
                        break;
                    case "0": //作用于id.根据cell值获取id
                        Object id = validateDataPkValueIsExist(data, pkName, values);
                        if(id != null){
                            field.set(object, id);
                            heighLevelFieldValueMap.put(field.getName(), id);
                            if(objectMap.get("moreoverName") != null){
                                Field fieldMoreoverName = (Field)objectMap.get("moreoverName");
                                fieldMoreoverName.setAccessible(true);
                                fieldMoreoverName.set(object, values);
                            }
                            break;
                        }
                }
            }catch (Exception e){
                integer++;
                UploadErrorMessage uploadErrorMessage = new UploadErrorMessage(rowNum,objectMap.get("cnName").toString(),"数据设置异常",objectMap.get("advice").toString());
                allErrorList.add(uploadErrorMessage);
                e.printStackTrace();
            }
        }
        /**
         * 对于数字类型的数据需要做类型匹配,放置出现转换异常,以error方式返回告知用户
         /
        private boolean typeMatches(Cell cell, String simpleName) {
            if(cell == null){
                return true;
            }
            int cellType = cell.getCellType();
            switch (cellType){
                case Cell.CELL_TYPE_NUMERIC:
                    if(!"Double,BigDecimal,Long,Integer,Date".contains(simpleName)){
                        return false;
                    }
                    break;
                case Cell.CELL_TYPE_STRING:
                    if(!"String".equals(simpleName)){
                        return false;
                    }
                    break;
            }
            return true;
        }
    
        /**
         * 获取cell值,如果数据与定义的类型不符,出现异常,捕获并设置为空,
         * 原因:后续有正则的validate,如果是必填数据,必定有相应的validate规则,如果非必填数据,错误了,直接设置为null
         * @param cell
         * @param simpleName
         * @return
         */
        private Object getValueByFieldType(Cell cell, String simpleName) {
            Object value = null;
            if (cell == null) {
                return null;
            }
            try {
                switch (simpleName) {
                    case "String":
                        cell.setCellType(Cell.CELL_TYPE_STRING);
                        value = cell.getStringCellValue();
                        break;
                    case "BigDecimal":
                        cell.setCellType(Cell.CELL_TYPE_NUMERIC);
                        value = new BigDecimal(cell.getNumericCellValue() + "");
                        break;
                    case "Long":
                        cell.setCellType(Cell.CELL_TYPE_NUMERIC);
                        Double cellValue = cell.getNumericCellValue();
                        value = cellValue.longValue();
                        break;
                    case "Integer":
                        cell.setCellType(Cell.CELL_TYPE_NUMERIC);
                        Double numericCellValue = cell.getNumericCellValue();
                        value = numericCellValue.intValue();
                        break;
                    case "Double":
                        cell.setCellType(Cell.CELL_TYPE_NUMERIC);
                        value = cell.getNumericCellValue();
                        break;
                    case "Date":
                        Date dateCellValue = cell.getDateCellValue();
                        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd");
                        value = simpleDateFormat.format(dateCellValue);
                        break;
                }
            } catch (Exception e) {
                value = null;
            }
            return value;
        }
        public List<Integer> getDataRownumList() {
            return this.dataRownumList;
        }
    
        public List<UploadErrorMessage> getFinalException() {
            return this.allErrorList;
        }
    
        public List<Integer> getAllDataRowNumList() {
            return allDataRowNumList;
        }
    
        public List<T> getAllDataList() {
            return allDataList;
        }
    }
    
    

    6、实体配置(较全,基本覆盖了上述的配置)

    package com.ih.entity;

    import com.baomidou.mybatisplus.enums.IdType;
    import com.baomidou.mybatisplus.annotations.TableId;
    import com.baomidou.mybatisplus.annotations.TableField;
    import com.baomidou.mybatisplus.activerecord.Model;
    import com.baomidou.mybatisplus.annotations.TableName;
    import com.fasterxml.jackson.databind.annotation.JsonSerialize;
    import com.fasterxml.jackson.databind.ser.std.ToStringSerializer;
    import com.ih.common.util.annotation.FiledMappingAnnotation;
    import com.ih.common.util.annotation.FiledMappingEnum;
    import com.ih.common.util.annotation.RegexConst;
    import org.hibernate.validator.constraints.Length;
    import org.springframework.beans.BeanUtils;

    import javax.validation.constraints.Pattern;
    import java.io.Serializable;
    import java.util.List;


    @TableName("hospital_user")
    public class HospitalUser extends Model<HospitalUser> {

        private static final long serialVersionUID = 1L;

        /**
         * 主键
         */
        @TableId(value = "id", type = IdType.AUTO)
        private Long id;
        /**
         * 医院代码
         */
        @TableField("hospital_id")
        @FiledMappingAnnotation(cnName = "医院名称", pkName = "name", pkCode = "id",
                actionFiled = "0",validate = RegexConst.NOT_NULL,beanName = "hospitalServiceImpl",
                fieldLevel = "height",advice = "必填,且必须为已有医院",length = 50)
        @JsonSerialize(using = ToStringSerializer.class)
        private Long hospitalId;
        /**
         * 医院name
         */
        private String hospitalName;
        /**
         * 科室name
         */
        private String deptName;
        /**
         * 科室代码
         */
        @TableField("dept_id")
        @FiledMappingAnnotation(cnName = "科室名称",contingencyName = "name",contingencyCode = "id",
                actionFiled = "0",validate = RegexConst.NOT_NULL, beanName = "hospitalDeptServiceImpl"
                ,fieldLevel = "low",heightField = "hospitalId",correlationField = "hospitalId",
                advice = "必填,且必须为已有科室",length = 50)
        private Integer deptId;
        /**
         * 人员代码
         */
        @TableField("user_code")
        private String userCode;
        /**
         * 姓名
         */
        @FiledMappingAnnotation(cnName = "姓名", validate = RegexConst.BEGIN_NOT_NULL,advice = "必填,且长度不能超过20位",length = 20)
        @Length(max = 20,message = "姓名必填,且长度不能超过20位")
        @Pattern(regexp = RegexConst.BEGIN_NOT_NULL,message = "姓名必填,且长度不能超过20位")
        private String name;
        /**
         * 性别
         */
        @FiledMappingAnnotation(cnName = "性别", validate = RegexConst.SEX, length = 2, state = {FiledMappingEnum.MALE,FiledMappingEnum.FAMALE},advice = "必填,可选男、女")
        private String sex;
        /**
         * 身份证号
         */
        @TableField("id_card")
        @FiledMappingAnnotation(cnName = "身份证号", validate = RegexConst.ID_CARD,advice = "必填,输入15或者18位身份证号",length = 20)
        @Pattern(regexp = RegexConst.ID_CARD,message = "请输入有效的15、18位身份证")
        private String idCard;
        /**
         * 登录账号
         */
        @FiledMappingAnnotation(cnName = "登录账号", validate = RegexConst.NO_EMPTY_STR,advice = "必填,长度不能超过50位且不能有空格",length = 50)
        @Length(max = 50,message = "请输入50位以内登录账号")
        @Pattern(regexp = RegexConst.NO_EMPTY_STR,message = "请输入有效的50位以内账号")
        private String account;
        /**
         * 密码
         */
        @FiledMappingAnnotation(cnName = "密码", validate = RegexConst.NO_EMPTY_STR,advice = "必填,长度6-32位且不能有空格",length = 32)
        @Length(max = 32,min = 6,message = "请输入6-32位密码")
        @Pattern(regexp = RegexConst.NO_EMPTY_STR,message = "请输入有效的6-32位密码")
        private String password = "123456";
       
         * 职称
         */
        @FiledMappingAnnotation(cnName = "职称", pkName = "name", pkCode = "id",moreoverName = "jobTitleName", actionFiled = "0", beanName = "hospitalJobTitleDictServiceImpl",advice = "非必填,必须为已有职称才能使用",length = 100)
        @TableField("job_title_id")
        private Integer jobTitleId;
        /**
         * 职称名称 前端展示
         */
        private String jobTitleName;
        /**
         * 学历
         */
        @FiledMappingAnnotation(cnName = "学历", pkName = "name", pkCode = "id", actionFiled = "0", beanName = "hospitalEductionDictServiceImpl",advice = "非必填,必须为已有学历才能使用",length = 100)
        @TableField("education_id")
        private Integer educationId;

        /**
         * 手机号
         */
        @TableField("phone_number")
        @FiledMappingAnnotation(cnName = "电话号码", validate = RegexConst.PHONE_NUM,advice = "必填,输入正确的11位电话号码",length = 11)
        @Pattern(regexp = RegexConst.PHONE_NUM,message = "请输入有效的电话号码")
        private String phoneNumber;
        /**
         * 邮件地址
         */
        @FiledMappingAnnotation(cnName = "邮件地址", validate = RegexConst.EMAIL,advice = "必填,长度不能超过50位",length = 50)
        @Length(max = 50,message = "请输入50位以内邮件地址")
        @Pattern(regexp = RegexConst.EMAIL,message = "请输入50位以内有效的邮件地址")
        private String email;
        /**
         * 擅长
         */
        @FiledMappingAnnotation(cnName = "擅长", validate = RegexConst.EMPTY_OR_NOT,advice = "长度不能超过100,且输入值不能全为空格",length = 100)
        @Length(max = 100,message = "请输入100位以内擅长信息")
        @Pattern(regexp = RegexConst.EMPTY_OR_NOT,message = "请输入100位以内有效擅长信息")
        private String adept;
        /**
         * 简介
         */
        @FiledMappingAnnotation(cnName = "简介", validate = RegexConst.EMPTY_OR_NOT,advice = "长度不能超过200,且输入值不能全为空格",length = 200)
        @Length(max = 200,message = "请输入200位以内简介信息")
        @Pattern(regexp = RegexConst.EMPTY_OR_NOT,message = "请输入200位以内简介信息")
        private String intro;
        
        /**
         * 是否启用
         */
        @FiledMappingAnnotation(cnName = "是否启用", state = {FiledMappingEnum.DISABLE,FiledMappingEnum.ENABLE},advice = "必填,可选项启用、停用",length =3)
        private Integer state;
        /**
         * 备注
         */
        @FiledMappingAnnotation(cnName = "备注", validate = RegexConst.EMPTY_OR_NOT,length = 100,advice = "长度不能超过100,且输入值不能全为空格")
        @Length(max = 100,message = "请输入100位以内备注")
        @Pattern(regexp = RegexConst.EMPTY_OR_NOT,message = "请输入100位以内有效备注")
        private String remark;

        /**
         * 出生日期
         */
        @FiledMappingAnnotation(cnName = "出生日期", validate = RegexConst.BIRTH_DAY,length = 20,advice = "必填,请输入2018/12/20格式的日期")
        @Pattern(regexp = RegexConst.BIRTH_DAY,message = "请输入2018/12/20格式的日期")
        private String birthday;

        /**
         * 工作类别
         */
        @TableField("job_type_id")
        @FiledMappingAnnotation(cnName = "工作类别", pkName = "dictName", pkCode = "id", actionFiled = "0",
                beanName = "dictServiceImpl",length = 50,advice = "非必填,必须为已有工作类别才能使用")
        private Integer jobTypeId;

        /**
         * 城市名称
         */
        @FiledMappingAnnotation(cnName = "城市名称", validate = RegexConst.EMPTY_OR_NOT)
        private String cityName;
    }
     

    展开全文
  • 数据结构-并查集

    2021-01-12 14:56:42
    并查集(Disjoint-Set)是一种可以动态维护若干个重叠的集合,并支持合并与查询两种操作的一种数据结构。 就是维护多个集合之间的关系,集合的合并和查询定位(哪个元素属于哪些集合等查询操作),所以并查集主要...

    简介

    并查集(Disjoint-Set)是一种可以动态维护若干个不重叠的集合,并支持合并与查询两种操作的一种数据结构。
    就是维护多个集合之间的关系,集合的合并和查询定位(哪个元素属于哪些集合等查询操作),所以并查集主要包括两种操作:

    合并(Union):合并两个集合;
    查询(Find):查询元素属于哪些集合。

    由上面的概念,我们可以知道并查集主要解决以下几个个问题:

    合并两个或多个集合;
    判断某一个元素或者多个元素是否属于某个集合

    分析

    慢union,快find

    我们可以用数组来表示数据结构(并查集表示的是多个集合之间的关系,使用map不能直观的描述多个集合的关系),数组的下标代表元素,存储的内容代表所在的集合,如下:

    在这里插入图片描述
    此时假如我们需要将元素2合并到元素1所在集合,则直接使arr[2]=arr[1]就行了

    在这里插入图片描述
    假如我们要将1集合加入到3集合,也就是元素1和元素2加入到3的集合中,则需要将元素1和元素2所在的集合做更改,arr[1]=3,arr[2]=3,合并的时间复杂度为O(n)

    在这里插入图片描述

    这时判断元素1和元素2是否在同一个集合只需要判断数组内值是否相等即可arr[1]==arr[2],相等则说明属于同一个集合,时间复杂度为O(1)
    示例代码如下(慢union,快):

    package com.example.demo;
    
    public class Test {
    
        private static int[] arr = new int[]{0,1,2,3,4,5,6,7};
    
        public static void main(String[] args) throws Exception {
            System.out.println("元素所在集合初始:" );
            arrToString(arr);
            System.out.println("将元素2合并到元素1所在集合");
            union(2,1);
            arrToString(arr);
            System.out.println("将元素1、2合并到3所在集合");
            union(1,3);
            arrToString(arr);
        }
    
        /**
         * 查看元素属于哪个集合
         * 时间复杂度为 O(1)
         * @param index
         * @return
         */
        public static int find(int index){
            return arr[index];
        }
    
        /**
         * 判断两个元素是否属于同一个集合
         * @param first
         * @param second
         * @return
         */
        public static boolean isTogether(int first, int second){
            return find(first) == find(second);
        }
    
        /**
         * 时间复杂度为 O(n)
         * 将first元素所在集合合并到second元素所在集合
         * @param first
         * @param second
         */
        public static void union(int first, int second){
            int m1 = find(first);
            int m2 = find(second);
    
            for(int i = 0; i < arr.length;i++){
                if(arr[i] == m1 ){
                    arr[i] = m2;
                }
            }
    
        }
    
        public static void arrToString(int[] arr){
            if(null == arr || arr.length <= 0){
                return;
            }
            System.out.print("数组元素:");
            for(int i = 0 ; i < arr.length ; i ++){
                System.out.print(i + " " );
            }
            System.out.println("");
            System.out.print("所在集合:");
            for(int c : arr){
                System.out.print(c + " ");
            }
            System.out.println("");
        }
    
    }
    

    输出:
    元素所在集合初始:
    数组元素:0 1 2 3 4 5 6 7
    所在集合:0 1 2 3 4 5 6 7
    将元素2合并到元素1所在集合
    数组元素:0 1 2 3 4 5 6 7
    所在集合:0 1 1 3 4 5 6 7
    将元素1、2合并到3所在集合
    数组元素:0 1 2 3 4 5 6 7
    所在集合:0 3 3 3 4 5 6 7

    上面的方法union时间复杂度是O(n),每次合并都需要把需要合并的集合遍历一遍,当集合内数据很大时肯定是不行的,我们需要对union进行优化

    快union,慢find

    我们将上面的关系转化为树形结构,改成树形结构时我们需要对数组进行小调整,数组下标依然表示元素,数组内容需要变为父集合。

    上面我们将2加入1,则元素2的父集合就是1所在的集合,1加入3则元素1的父集合就是3所在的集合,稍做调整后的数组结为arr[2]=arr[1],arr[1]=arr[3],如图:

    在这里插入图片描述
    树形结构如下图:

    在这里插入图片描述
    这个时候假如我们将3集合合并到4集合,其实只需要把领头的元素3加入到4集合,元素1,2,3的关系保持不变就可以了,只需要操作一步就完成了合并操作。这个时候数据结构就从数组转变成了树形结构,成功的将union时间复杂度变为了O(1)

    在这里插入图片描述
    再来看find(1),需要找到顶部元素所在集合(也就是元素4所在集合)即可,时间复杂度取决于树的深度
    示例代码:

    package com.example.demo;
    
    public class Test2 {
    
        private static int[] arr = new int[]{0,3,1,3,4,5,6,7};
    
        public static void main(String[] args) throws Exception {
            System.out.println("元素所在集合初始:");
            arrToString(arr);
            System.out.println("将元素3所在集合合并到元素4所在集合");
            union(3, 4);
            arrToString(arr);
        }
    
        /**
         * 查看元素属于哪个集合
         * 时间复杂度为 O(1)
         * @param index
         * @return
         */
        public static int find(int index){
            // 判断自己是不是顶部节点 没有父集合就是顶部元素
            while(index != arr[index]){
                //如果不是顶部元素  则往上查找  知道找到顶部元素为止
                //顶部元素所在的集合就是该元素所在的集合
                index = arr[index];
            }
            return index;
        }
    
        /**
         * 判断两个元素是否属于同一个集合
         * @param first
         * @param second
         * @return
         */
        public static boolean isTogether(int first, int second){
            return find(first) == find(second);
        }
    
        /**
         * 时间复杂度为 O(n)
         * 将first元素所在集合合并到second元素所在集合
         * @param first
         * @param second
         */
        public static void union(int first, int second){
            int firstRoot = find(first);
            int secondRoot = find(second);
            // 如果所属集合相等则不操作
            if(firstRoot == secondRoot){
                return ;
            }
            // 否则将first元素所在集合的顶部元素所在的父集合指向元素second顶部元素所在的集合,则完成了合并
            arr[firstRoot] = secondRoot;
        }
    
        public static void arrToString(int[] arr){
            if(null == arr || arr.length <= 0){
                return;
            }
            System.out.print("数组元素:");
            for(int i = 0 ; i < arr.length ; i ++){
                System.out.print(i + " " );
            }
            System.out.println("");
            System.out.print("所在集合:");
            for(int c : arr){
                System.out.print(c + " ");
            }
            System.out.println("");
        }
    
    }
    

    输出:
    元素所在集合初始:
    数组元素:0 1 2 3 4 5 6 7
    所在集合:0 3 1 3 4 5 6 7
    将元素3所在集合合并到元素4所在集合
    数组元素:0 1 2 3 4 5 6 7
    所在集合:0 3 1 4 4 5 6 7

    快速union,快速find,基于重量

    上面的例子中我们要找到2所在的集合需要把整个集合都遍历一遍,这是因为每次合并时都是往父一级追加,形成了线性链表,上面的优化导致了find方法时间复杂度为集合深度。为了再次优化find方法,我们需要优化树结构的生成规则。既然两个元素合并到一个元素,以上面的例子举例,元素3合并到元素4和元素4合并到元素3其实是一个效果,但是显然元素4合并到元素3更为合理。也就是谁元素多谁为主,元素少的集合合并到元素多的集合中,这样就能降低树的深度提高find效率了

    在这里插入图片描述

    示例代码:

    package com.example.demo;
    
    public class Test3 {
    
        private static int[] arr    = new int[]{0,3,1,3,4,5,6,7};
        private static int[] weight = new int[]{1,1,0,2,1,1,1,1};
    
        public static void main(String[] args) throws Exception {
            System.out.println("元素所在集合初始:");
            arrToString(arr);
            System.out.println("将元素3所在集合和元素4所在集合合并");
            union(3, 4);
            arrToString(arr);
        }
    
        /**
         * 查看元素属于哪个集合
         * 时间复杂度为 O(1)
         * @param index
         * @return
         */
        public static int find(int index){
            // 判断自己是不是顶部节点 没有父集合就是顶部元素
            while(index != arr[index]){
                //如果不是顶部元素  则往上查找  知道找到顶部元素为止
                //顶部元素所在的集合就是该元素所在的集合
                index = arr[index];
            }
            return index;
        }
    
        /**
         * 判断两个元素是否属于同一个集合
         * @param first
         * @param second
         * @return
         */
        public static boolean isTogether(int first, int second){
            return find(first) == find(second);
        }
    
        /**
         * 时间复杂度为 O(n)
         * 将first元素所在集合合并到second元素所在集合
         * @param first
         * @param second
         */
        public static void union(int first, int second){
            int firstRoot = find(first);
            int secondRoot = find(second);
            // 如果所属集合相等则不操作
            if(firstRoot == secondRoot){
                return ;
            }
            // 取出所在集合元素个数
            int fweight = weight[firstRoot];
            int sweight = weight[secondRoot];
            if(fweight < sweight){
                //若second所在集合元素个数大于first所在集合元素个数
                // 则将first元素加入second元素所在集合
                arr[firstRoot] = secondRoot;
                weight[secondRoot] = sweight + fweight ;
            }else{
                // 于上面相反
                arr[secondRoot] = firstRoot;
                weight[firstRoot] = fweight + sweight;
    
            }
    
        }
    
        public static void arrToString(int[] arr){
            if(null == arr || arr.length <= 0){
                return;
            }
            System.out.print("数组元素:");
            for(int i = 0 ; i < arr.length ; i ++){
                System.out.print(i + " " );
            }
            System.out.println("");
            System.out.print("所在集合:");
            for(int c : arr){
                System.out.print(c + " ");
            }
            System.out.println("");
            System.out.print("集合重量:");
            for(int c : weight){
                System.out.print(c + " ");
            }
            System.out.println("");
        }
    
    }
    

    元素所在集合初始:
    数组元素:0 1 2 3 4 5 6 7
    所在集合:0 3 1 3 4 5 6 7
    集合高度:1 1 0 2 1 1 1 1
    将元素3所在集合合并到元素4所在集合
    数组元素:0 1 2 3 4 5 6 7
    所在集合:0 3 1 3 3 5 6 7
    集合重量:1 1 0 3 1 1 1 1

    观察上面输出可以看到元素4加入了集合3

    快速union,快速find,基于高度(基于秩)

    对于上述改进方法,只是单纯的判断集合内元素的个数大小来决定如何合并集合,如果数据结构是如下图时:

    在这里插入图片描述
    假如按照元素个数谁大合并到谁那则会出现下面的情况

    在这里插入图片描述

    集合5加入了集合3,树的高度变为了4,极端情况下find的时间复杂度会无限接近o(n)(无限接近线性链表的结构)。假如我们按照树的高度来判断合并到哪个集合,上述情况合并会得到:

    在这里插入图片描述
    示例代码:

    package com.example.demo;
    
    public class Test4 {
    
        private static int[] arr    = new int[]{0,3,3,3,3,5,5,6};
        private static int[] height = new int[]{1,1,1,2,1,3,2,1};
    
        public static void main(String[] args) throws Exception {
            System.out.println("元素所在集合初始:");
            arrToString(arr);
            System.out.println("将元素3所在集合和元素5所在集合合并");
            union(3, 5);
            arrToString(arr);
        }
    
        /**
         * 查看元素属于哪个集合
         * 时间复杂度为 O(1)
         * @param index
         * @return
         */
        public static int find(int index){
            // 判断自己是不是顶部节点 没有父集合就是顶部元素
            while(index != arr[index]){
                //如果不是顶部元素  则往上查找  知道找到顶部元素为止
                //顶部元素所在的集合就是该元素所在的集合
                index = arr[index];
            }
            return index;
        }
    
        /**
         * 判断两个元素是否属于同一个集合
         * @param first
         * @param second
         * @return
         */
        public static boolean isTogether(int first, int second){
            return find(first) == find(second);
        }
    
        /**
         * 时间复杂度为 O(n)
         * 将first元素所在集合合并到second元素所在集合
         * @param first
         * @param second
         */
        public static void union(int first, int second){
            int firstRoot = find(first);
            int secondRoot = find(second);
            // 如果所属集合相等则不操作
            if(firstRoot == secondRoot){
                return ;
            }
            // 取出所在集合元素个数
            int fheight = height[firstRoot];
            int sheight = height[secondRoot];
            if(fheight < sheight){
                //若second所在集合高度大于first所在集合高度
                // 则将first元素加入second元素所在集合
                // 高度取决于最高的集合 所以最大高度并不会改变
                arr[firstRoot] = secondRoot;
            }else if(fheight == sheight){
                //若second所在集合高度和first所在集合高度  相等
                // 则将first元素加入second元素所在集合
                // 高度+1
                arr[firstRoot] = secondRoot;
                height[secondRoot] = sheight + 1;
            }else{
                //若second所在集合高度小于first所在集合高度
                // 则将second元素加入first元素所在集合
                // 高度不变
                arr[secondRoot] = firstRoot;
            }
    
        }
    
        public static void arrToString(int[] arr){
            if(null == arr || arr.length <= 0){
                return;
            }
            System.out.print("数组元素:");
            for(int i = 0 ; i < arr.length ; i ++){
                System.out.print(i + " " );
            }
            System.out.println("");
            System.out.print("所在集合:");
            for(int c : arr){
                System.out.print(c + " ");
            }
            System.out.println("");
            System.out.print("集合高度:");
            for(int c : height){
                System.out.print(c + " ");
            }
            System.out.println("");
        }
    
    }
    

    输出:
    元素所在集合初始:
    数组元素:0 1 2 3 4 5 6 7
    所在集合:0 3 3 3 3 5 5 6
    集合高度:1 1 1 2 1 3 2 1
    将元素3所在集合和元素5所在集合合并
    数组元素:0 1 2 3 4 5 6 7
    所在集合:0 3 3 5 3 5 5 6
    集合高度:1 1 1 2 1 3 2 1

    最大高度还是3没有变化

    路径压缩

    针对基于重量的优化,我们可以将叶子节点直接指向父元素的父元素所在集合,这样也能压缩树的高度,提高find性能。这种方法实际上没有改变树的结构,只是直接越级查找了
    示例代码:

    package com.example.demo;
    
    public class Test32 {
    
        private static int[] arr    = new int[]{0,3,1,3,4,5,6,7};
        private static int[] weight = new int[]{1,1,0,2,1,1,1,1};
    
        public static void main(String[] args) throws Exception {
            System.out.println("元素所在集合初始:");
            arrToString(arr);
            System.out.println("将元素3所在集合和元素4所在集合合并");
            union(3, 4);
            arrToString(arr);
        }
    
        /**
         * 查看元素属于哪个集合
         * 时间复杂度为 O(1)
         * @param index
         * @return
         */
        public static int find(int index){
            // 判断自己是不是顶部节点 没有父集合就是顶部元素
            while(index != arr[index]){
                //如果不是顶部元素  则往上查找  知道找到顶部元素为止
                // 这里查找采用路径压缩法,越过一级往上查找
                index = arr[arr[index]];
            }
            return index;
        }
    
        /**
         * 判断两个元素是否属于同一个集合
         * @param first
         * @param second
         * @return
         */
        public static boolean isTogether(int first, int second){
            return find(first) == find(second);
        }
    
        /**
         * 时间复杂度为 O(n)
         * 将first元素所在集合合并到second元素所在集合
         * @param first
         * @param second
         */
        public static void union(int first, int second){
            int firstRoot = find(first);
            int secondRoot = find(second);
            // 如果所属集合相等则不操作
            if(firstRoot == secondRoot){
                return ;
            }
            // 取出所在集合元素个数
            int fweight = weight[firstRoot];
            int sweight = weight[secondRoot];
            if(fweight < sweight){
                //若second所在集合元素个数大于first所在集合元素个数
                // 则将first元素加入second元素所在集合
                arr[firstRoot] = secondRoot;
                weight[secondRoot] = sweight + fweight;
            }else{
                // 于上面相反
                arr[secondRoot] = firstRoot;
                weight[firstRoot] = fweight + sweight;
    
            }
    
        }
    
        public static void arrToString(int[] arr){
            if(null == arr || arr.length <= 0){
                return;
            }
            System.out.print("数组元素:");
            for(int i = 0 ; i < arr.length ; i ++){
                System.out.print(i + " " );
            }
            System.out.println("");
            System.out.print("所在集合:");
            for(int c : arr){
                System.out.print(c + " ");
            }
            System.out.println("");
            System.out.print("集合重量:");
            for(int c : weight){
                System.out.print(c + " ");
            }
            System.out.println("");
        }
    
    }
    

    输出:
    元素所在集合初始:
    数组元素:0 1 2 3 4 5 6 7
    所在集合:0 3 1 3 4 5 6 7
    集合重量:1 1 0 2 1 1 1 1
    将元素3所在集合和元素4所在集合合并
    数组元素:0 1 2 3 4 5 6 7
    所在集合:0 3 1 3 3 5 6 7
    集合重量:1 1 0 3 1 1 1 1

    应用场景:

    并查集在很多场景都可以使用,比如地图寻址,im的群查找合并,数据统计等

    原文:https://gper.club/articles/7e7e7f7ff4g59gc7g69

    展开全文
  • (2) 以下数据结构中不属于线性数据结构的是(C) A. 队列 B. 线性表 C. 二叉树 D. 栈 (3) 在一棵二叉树上第5层的结点数最多是(B) 注:由公式2k-1得 A. 8 B. 16 C. 32 D. 15 (4) 下面描述中,符合结构化程序设计风格的...
  •  (48)在以下网络威胁中,哪个不属于信息泄露  A) 数据窃听 B) 流量分析 C) 拒绝服务攻击 D) 偷窃用户帐号  Key: C  (49)在公钥密码体制中,用于加密的密钥为  A)公钥 B)私钥 C) 公钥与私钥 D) 公钥...
  • (2) 以下数据结构中不属于线性数据结构的是______。(C) A. 队列 B. 线性表 C. 二*树 D. 栈 (3) 在一棵二*树上第5层的结点数最多是______。(B) A. 8 B. 16 C. 32 D. 15 (4) 下面描述中,符合结构化程序设计风格的是__...
  • ASP.NET的网页代码模型及生命周期

    热门讨论 2009-07-28 14:22:11
    Web开发像软件开发,Web应用实际上是没有状态的,这就说明Web应用程序自动指示序列中的请求是否来自相同的浏览器或客户端,也无法判断浏览器是否一直在浏览一个页面或者一个站点,也无法判断用户执行了哪个操作...
  • 2.3.6 以下属于数据链路层功能的是? 2.3.7 IEEE802.3u标准是指? 2.3.8 如果要将两计算机通过双绞线直接连接,正确的线序是? 2.3.9 在V.35和V.24规程中,控制信号RTS表示? 2.4.0 路由器作为网络互连设备,...
  • 会计理论考试题

    2012-03-07 21:04:40
    1.计算机感染病毒后会产生各种现象,以下不属于病毒现象的是__D__。 A、文件占用的空间变大 B、发生异常蜂鸣声 C、屏幕显示异常图形 D、机内的电扇不转 2. Windows98支持下面___C__网络协议。 A、Net BEUI B、IPX...
  • Egret 的 童话 与 现实

    2021-01-03 14:33:25
    哪个社区都是如此?NodeJS的兴起也是因为搞JS的人『喜欢JS那一套东西』,所以balabalabala…… 但是这里面有一个本质的区别:NodeJS是充分挖掘了JS本身的特质和功能,让JS可以做更多的...
  • (1)进程调度属于低级处理机管理,即确定系统中哪个进程将获得CPU;而作业调度属于高级处理机管理,即确定系统中哪些作业将获得CPU。 (2)进程是一个具有一定独立功能的程序关于某个数据集合的一次运行...
  • 《数据结构 1800题》

    热门讨论 2012-12-27 16:52:03
    13.以下哪个数据结构不是多型数据类型(D )【中山大学 1999 一、3(1分)】 A.栈 B.广义表 C.有向图 D.字符串 14.以下数据结构中,(A )是非线性数据结构【中山大学 1999 一、4】 A.树 B.字符串 C.队 ...
  • 3.2 动态数据:包括输入数据和输出数据。 3.3 数据库描述:给出使用数据库的名称和类型。 3.4 数据词典 3.5 数据采集 4 功能需求 4.1功能划分 4.2功能描述 5 性能需求 5.1 数据精确度 5.2 时间特性:如响应...
  • Java局域网通信——飞鸽传书源代码 28个目标文件 内容索引:JAVA源码,媒体网络,飞鸽传书 Java局域网通信——飞鸽传书源代码,大家都知道VB版、VC版还有Delphi版的飞鸽传书软件,但是Java版的确实多,因此这个Java...
  • JAVA上百实例源码以及开源项目

    千次下载 热门讨论 2016-01-03 17:37:40
     Java局域网通信——飞鸽传书源代码,大家都知道VB版、VC版还有Delphi版的飞鸽传书软件,但是Java版的确实多,因此这个Java文件传输实例可错过,Java网络编程技能的提升很有帮助。 Java聊天程序,包括服务端和...
  • java源码包---java 源码 大量 实例

    千次下载 热门讨论 2013-04-18 23:15:26
     Java局域网通信——飞鸽传书源代码,大家都知道VB版、VC版还有Delphi版的飞鸽传书软件,但是Java版的确实多,因此这个Java文件传输实例可错过,Java网络编程技能的提升很有帮助。 Java聊天程序,包括服务端和...
  • java源码包2

    千次下载 热门讨论 2013-04-20 11:28:17
     Java局域网通信——飞鸽传书源代码,大家都知道VB版、VC版还有Delphi版的飞鸽传书软件,但是Java版的确实多,因此这个Java文件传输实例可错过,Java网络编程技能的提升很有帮助。 Java聊天程序,包括服务端和...
  • java源码包3

    千次下载 热门讨论 2013-04-20 11:30:13
     Java局域网通信——飞鸽传书源代码,大家都知道VB版、VC版还有Delphi版的飞鸽传书软件,但是Java版的确实多,因此这个Java文件传输实例可错过,Java网络编程技能的提升很有帮助。 Java聊天程序,包括服务端和...
  • Java局域网通信——飞鸽传书源代码 28个目标文件 内容索引:JAVA源码,媒体网络,飞鸽传书 Java局域网通信——飞鸽传书源代码,大家都知道VB版、VC版还有Delphi版的飞鸽传书软件,但是Java版的确实多,因此这个Java...
  • Java局域网通信——飞鸽传书源代码 28个目标文件 内容索引:JAVA源码,媒体网络,飞鸽传书 Java局域网通信——飞鸽传书源代码,大家都知道VB版、VC版还有Delphi版的飞鸽传书软件,但是Java版的确实多,因此这个Java...
  • java源码包

    2015-12-01 16:29:37
     Java局域网通信——飞鸽传书源代码,大家都知道VB版、VC版还有Delphi版的飞鸽传书软件,但是Java版的确实多,因此这个Java文件传输实例可错过,Java网络编程技能的提升很有帮助。 Java聊天程序,包括服务端和...

空空如也

空空如也

1 2
收藏数 21
精华内容 8
关键字:

以下哪个不属于动态分析