set.contains时间复杂度

对于 Java 的 Set 接口的实现类，比如 HashSet 和 TreeSet，它们的 contains 方法的时间复杂度为 O(1) 或 O(log n)。

对于 HashSet，contains 方法的平均时间复杂度为 O(1)。HashSet 使用哈希表来存储元素，通过计算元素的哈希码来确定存储位置，因此在大多数情况下，可以直接通过哈希码来快速定位元素。

对于 TreeSet，contains 方法的时间复杂度为 O(log n)。TreeSet 使用红黑树来存储元素，红黑树是一种自平衡二叉搜索树，因此在最坏情况下，需要遍历树的高度，时间复杂度为 O(log n)。

需要注意的是，这里提到的时间复杂度是在平均情况下或最坏情况下的估计值，具体的性能还会受到元素数量、哈希函数的质量等因素的影响。

相关问题

set和优先队列的时间复杂度

Set数据结构，通常实现为哈希表或红黑树等，它的常见操作如插入（add）、删除（remove）和查找（contains）的时间复杂度大部分情况下都是O(1)。这是因为内部的数据结构设计使得查找、插入和删除操作能够迅速定位元素，尤其是对于无序的集合。

优先队列（Priority Queue），也叫做堆（Heap），它是一种特殊的树形数据结构，满足堆性质，即每个节点的值都大于或等于（最大堆）或小于或等于（最小堆）其子节点的值。常见的实现有二叉堆。对于基本操作，如插入（enqueue）和删除（dequeue）顶部元素（最小堆）或底部元素（最大堆），时间复杂度通常是O(log n)，因为每次修改堆都需要调整部分结构以保持堆的性质。查询操作，虽然不需要完全重建堆，但也需要线性时间O(n)，但实际应用中查询往往不是最频繁的操作。

public AjaxResult importData(MultipartFile file, SysDept sysDept) throws Exception { ExcelUtil<SysDept> util = new ExcelUtil<>(SysDept.class); List<SysDept> sysDeptList = util.importExcel(file.getInputStream(), 1); sysDept.setDeptType(Constants.DEPT_BANK); sysDept.setDelFlag(Constants.STATUS_VALID); List<SysDept> depts = deptService.selectDeptList(sysDept); // 创建机构名称集合 List<String> deptNames = new ArrayList<>(); // 创建机构编号集合 List<String> deptNum = new ArrayList<>(); // 创建父部门编号map Map<String, SysDept> parentNum = new HashMap<>(); for (SysDept dept : depts) { deptNames.add(dept.getDeptName()); deptNum.add(dept.getDeptNum()); parentNum.put(dept.getDeptNum(), dept); } for (SysDept dept : sysDeptList) { if (deptNames.contains(dept.getDeptName()) || deptNum.contains(dept.getDeptNum())) { throw new ServiceException("机构已存在!"); } // 添加父部门id if (parentNum.get(dept.getParentNum()) != null) { dept.setParentId(parentNum.get(dept.getParentNum()).getDeptId()); deptNames.add(dept.getDeptName()); parentNum.put(dept.getDeptNum(), dept); deptNum.add(dept.getDeptNum()); } else { throw new ServiceException("添加" + dept.getDeptName() + "失败！经办机构不存在!"); } dept.setDeptType(Constants.DEPT_BANK); dept.setCreateBy(getUserId()); dept.setStatus(Constants.STATUS_VALID); dept.setDelFlag(Constants.STATUS_VALID); //存储用户信息 SysUser user = new SysUser(); user.setUserName(dept.getUserName()); user.setPassword(SecurityUtils.encryptPassword(dept.getPassword())); user.setPhonenumber(dept.getPhonenumber()); user.setRoleIds(dept.getRoleIds()); user.setUserType(Constants.USER_TYPE_BANK); user.setCreateBy(getUserId()); user.setStatus(Constants.STATUS_VALID); user.setDelFlag(Constants.STATUS_VALID); if (!userService.checkUserNameUnique(user)) { throw new ServiceException(ADD_USER + user.getUserName() + ACCOUNT_ALREADY_EXISTS); } else if (StringUtils.isNotEmpty(user.getPhonenumber()) && !userService.checkPhoneUnique(user)) { throw new ServiceException(ADD_USER + user.getUserName() + PHONE_EXISTS); } userService.insertUser(user); //存储部门信息 dept.setUserId(user.getUserId()); deptService.insertDept(dept); //更新用户信息 user.setDeptId(dept.getDeptId()); userService.updateUser(user); } return success(); }重构这段代码 将其认知复杂度从16降低到允许的15。

为了将代码的认知复杂度从16降低到15，可以考虑进行以下重构：

1. 将创建机构名称集合、创建机构编号集合和创建父部门编号map的部分代码提取为单独的方法，以减少importData方法中的代码量。
2. 将判断机构是否存在的部分代码提取为单独的方法，以减少importData方法中的代码量。
3. 将存储用户信息、存储部门信息和更新用户信息的部分代码提取为单独的方法，以减少importData方法中的代码量。

重构后的代码如下：

public AjaxResult importData(MultipartFile file, SysDept sysDept) throws Exception {
    ExcelUtil<SysDept> util = new ExcelUtil<>(SysDept.class);
    List<SysDept> sysDeptList = util.importExcel(file.getInputStream(), 1);
    sysDept.setDeptType(Constants.DEPT_BANK);
    sysDept.setDelFlag(Constants.STATUS_VALID);

    List<SysDept> depts = deptService.selectDeptList(sysDept);
    Map<String, SysDept> parentNum = createParentNumMap(depts);
    List<String> deptNames = createDeptNames(depts);
    List<String> deptNum = createDeptNum(depts);

    for (SysDept dept : sysDeptList) {
        if (isDeptExist(deptNames, deptNum, dept)) {
            throw new ServiceException("机构已存在!");
        }

        if (parentNum.get(dept.getParentNum()) != null) {
            dept.setParentId(parentNum.get(dept.getParentNum()).getDeptId());
            deptNames.add(dept.getDeptName());
            parentNum.put(dept.getDeptNum(), dept);
            deptNum.add(dept.getDeptNum());
        } else {
            throw new ServiceException("添加" + dept.getDeptName() + "失败！经办机构不存在!");
        }

        storeUserInfoAndDeptInfo(dept);
    }

    return success();
}

private Map<String, SysDept> createParentNumMap(List<SysDept> depts) {
    Map<String, SysDept> parentNum = new HashMap<>();
    for (SysDept dept : depts) {
        parentNum.put(dept.getDeptNum(), dept);
    }
    return parentNum;
}

private List<String> createDeptNames(List<SysDept> depts) {
    List<String> deptNames = new ArrayList<>();
    for (SysDept dept : depts) {
        deptNames.add(dept.getDeptName());
    }
    return deptNames;
}

private List<String> createDeptNum(List<SysDept> depts) {
    List<String> deptNum = new ArrayList<>();
    for (SysDept dept : depts) {
        deptNum.add(dept.getDeptNum());
    }
    return deptNum;
}

private boolean isDeptExist(List<String> deptNames, List<String> deptNum, SysDept dept) {
    return deptNames.contains(dept.getDeptName()) || deptNum.contains(dept.getDeptNum());
}

private void storeUserInfoAndDeptInfo(SysDept dept) {
    SysUser user = createSysUser(dept);
    if (userService.checkUserNameUnique(user)) {
        if (StringUtils.isNotEmpty(user.getPhonenumber()) && userService.checkPhoneUnique(user)) {
            userService.insertUser(user);
            dept.setUserId(user.getUserId());
            deptService.insertDept(dept);
            user.setDeptId(dept.getDeptId());
            userService.updateUser(user);
        } else {
            throw new ServiceException(ADD_USER + user.getUserName() + PHONE_EXISTS);
        }
    } else {
        throw new ServiceException(ADD_USER + user.getUserName() + ACCOUNT_ALREADY_EXISTS);
    }
}

private SysUser createSysUser(SysDept dept) {
    SysUser user = new SysUser();
    user.setUserName(dept.getUserName());
    user.setPassword(SecurityUtils.encryptPassword(dept.getPassword()));
    user.setPhonenumber(dept.getPhonenumber());
    user.setRoleIds(dept.getRoleIds());
    user.setUserType(Constants.USER_TYPE_BANK);
    user.setCreateBy(getUserId());
    user.setStatus(Constants.STATUS_VALID);
    user.setDelFlag(Constants.STATUS_VALID);
    return user;
}