专栏名称: 朱小厮的博客

著有畅销书：《深入理解Kafka》和《RabbitMQ实战指南》。公众号主要用来分享Java技术栈、Golang技术栈、消息中间件（如Kafka、RabbitMQ）、存储、大数据以及通用型技术架构等相关的技术。

阿里巴巴工程师：Java 编程技巧之数据结构

朱小厮的博客 · 公众号 · · 2019-12-28 08:41

正文

点击上方“朱小厮的博客”，选择“ 设为星标”

后台回复” 1024 “获取公众号专属1024GB资料

来源：阿里巴巴中间件

导读

编码过程中踩过的坑多了，获得的编码经验也就多了，总结的编码技巧也就更多了。总结的编码技巧多了，凡事又能够举一反三，编码的速度自然就上来了。笔者从数据结构的角度，整理了一些 Java 编程技巧，以供大家学习参考。

使用HashSet判断主键是否存在

HashSet 实现 Set 接口，由哈希表（实际上是 HashMap ）实现，但不保证 set 的迭代顺序，并允许使用 null 元素。HashSet 的时间复杂度跟 HashMap 一致，如果没有哈希冲突则时间复杂度为 O(1) ，如果存在哈希冲突则时间复杂度不超过 O(n) 。所以，在日常编码中，可以使用 HashSet 判断主键是否存在。

案例：给定一个字符串(不一定全为字母)，请返回第一个重复出现的字符。

/** 查找第一个重复字符 */
public static char findFirstRepeatedChar(String string) {
    // 检查空字符串
    if (Objects.isNull(string) || string.isEmpty()) {
        return null;
    }

    // 查找重复字符
    char[] charArray = string.toCharArray();
    Set charSet = new HashSet<>(charArray.length);
    for (char ch : charArray) {
        if (charSet.contains(ch)) {
            return ch;
        }
        charSet.add(ch);
    }

    // 默认返回为空
    return null;
}

其中，由于 Set 的 add 函数有个特性——如果添加的元素已经再集合中存在，则会返回 false 。可以简化代码为：

if (!charSet.add(ch)) {
    return ch;
}

使用HashMap存取键值映射关系

简单来说，HashMap 由数组和链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的。如果定位到的数组位置不含链表，那么查找、添加等操作很快，仅需一次寻址即可，其时间复杂度为 O(1) ；如果定位到的数组包含链表，对于添加操作，其时间复杂度为 O(n) ——首先遍历链表，存在即覆盖，不存在则新增；对于查找操作来讲，仍需要遍历链表，然后通过key对象的 equals 方法逐一对比查找。从性能上考虑， HashMap 中的链表出现越少，即哈希冲突越少，性能也就越好。所以，在日常编码中，可以使用 HashMap 存取键值映射关系。

案例：给定菜单记录列表，每条菜单记录中包含父菜单标识（根菜单的父菜单标识为 null ），构建出整个菜单树。

/** 菜单DO类 */
@Setter
@Getter
@ToString




    

public static class MenuDO {
    /** 菜单标识 */
    private Long id;
    /** 菜单父标识 */
    private Long parentId;
    /** 菜单名称 */
    private String name;
    /** 菜单链接 */
    private String url;
}

/** 菜单VO类 */
@Setter
@Getter
@ToString
public static class MenuVO {
    /** 菜单标识 */
    private Long id;
    /** 菜单名称 */
    private String name;
    /** 菜单链接 */
    private String url;
    /** 子菜单列表 */
    private List childList;
}

/** 构建菜单树函数 */
public static List buildMenuTree(List menuList) {
    // 检查列表为空
    if (CollectionUtils.isEmpty(menuList)) {
        return Collections.emptyList();
    }

    // 依次处理菜单
    int menuSize = menuList.size();
    List rootList = new ArrayList<>(menuSize);
    Map, MenuVO> menuMap = new HashMap<>(menuSize);
    for (MenuDO menuDO : menuList) {
        // 赋值菜单对象
        Long menuId = menuDO.getId();
        MenuVO menu = menuMap.get(menuId);
        if (Objects.isNull(menu)) {
            menu = new MenuVO();
            menu.setChildList(new ArrayList<>());
            menuMap.put(menuId, menu);
        }
        menu.setId(menuDO.getId());
        menu.setName(menuDO.getName());
        menu.setUrl(menuDO.getUrl());

        // 根据父标识处理
        Long parentId = menuDO.getParentId();
        if (Objects.nonNull(parentId)) {
            // 构建父菜单对象
            MenuVO parentMenu = menuMap.get(parentId);
            if (Objects.isNull(parentMenu)) {
                parentMenu = new MenuVO();
                parentMenu.setId(parentId);
                parentMenu.setChildList(new ArrayList<>());
                menuMap.put(parentId, parentMenu);
            }
            
            // 添加子菜单对象
            parentMenu.getChildList().add(menu);
        } else {
            // 添加根菜单对象
            rootList.add(menu);
        }
    }

    // 返回根菜单列表
    return rootList;
}

使用 ThreadLocal 存储线程专有对象

ThreadLocal 提供了线程专有对象，可以在整个线程生命周期中随时取用，极大地方便了一些逻辑的实现。

常见的 ThreadLocal 用法主要有两种：

1、保存线程上下文对象，避免多层级参数传递；

2、保存非线程安全对象，避免多线程并发调用。

保存线程上下文对象，避免多层级参数传递

这里，以 PageHelper 插件的源代码中的分页参数设置与使用为例说明。

设置分页参数代码：

/** 分页方法类 */
public abstract class PageMethod {
    /** 本地分页 */
    protected static final ThreadLocal LOCAL_PAGE = new ThreadLocal();

    /** 设置分页参数 */
    protected static void setLocalPage(Page page) {
        LOCAL_PAGE.set(page);
    }

    /** 获取分页参数 */
    public static  Page getLocalPage() {
        return LOCAL_PAGE.get();
    }

    /** 开始分页 */
    public static  Page startPage(int pageNum, int pageSize, boolean count, Boolean reasonable, Boolean pageSizeZero) {
        Page page = new Page(pageNum, pageSize, count);
        page.setReasonable(reasonable);
        page.setPageSizeZero(pageSizeZero);
        Page oldPage = getLocalPage();
        if (oldPage != null && oldPage.isOrderByOnly()) {
            page.setOrderBy(oldPage.getOrderBy());
        }
        setLocalPage(page);
        return page;
    }
}

使用分页参数代码：

/** 虚辅助方言类 */
public abstract class AbstractHelperDialect extends AbstractDialect implements Constant {
    /** 获取本地分页 */
    public  Page getLocalPage() {
        return PageHelper.getLocalPage();
    }

    /** 获取分页SQL */
    @Override
    public String getPageSql(MappedStatement ms, BoundSql boundSql, Object parameterObject, RowBounds rowBounds, CacheKey pageKey) {
        String sql = boundSql.getSql();
        Page page = getLocalPage();
        String orderBy = page.getOrderBy();
        if (StringUtil.isNotEmpty(orderBy)) {
            pageKey.update(orderBy);
            sql = OrderByParser.converToOrderBySql(sql, orderBy);
        }
        if (page.isOrderByOnly()) {
            return sql;
        }
        return getPageSql(sql, page, pageKey);
    }
    ...
}

使用分页插件代码：

/** 查询用户函数 */
public PageInfo queryUser(UserQuery userQuery, int pageNum, int pageSize) {
 PageHelper.startPage(pageNum, pageSize);
 List userList = userDAO.queryUser(userQuery);
 PageInfo pageInfo = new PageInfo<>(userList);
 return pageInfo;
}

如果要把分页参数通过函数参数逐级传给查询语句，除非修改 MyBatis 相关接口函数，否则是不可能实现的。

保存非线程安全对象，避免多线程并发调用

在写日期格式化工具函数时，首先想到的写法如下：

/** 日期模式 */




    

private static final String DATE_PATTERN = "yyyy-MM-dd";

/** 格式化日期函数 */
public static String formatDate(Date date) {
    return new SimpleDateFormat(DATE_PATTERN).format(date);
}

其中，每次调用都要初始化 DateFormat 导致性能较低，把 DateFormat 定义成常量后的写法如下：

/** 日期格式 */
private static final DateFormat DATE_FORMAT = new SimpleDateFormat("yyyy-MM-dd");

/** 格式化日期函数 */
public static String formatDate(Date date) {
    return DATE_FORMAT.format(date);
}

由于 SimpleDateFormat 是非线程安全的，当多线程同时调用 formatDate 函数时，会导致返回结果与预期不一致。如果采用 ThreadLocal 定义线程专有对象，优化后的代码如下：

/** 本地日期格式 */
private static final ThreadLocal LOCAL_DATE_FORMAT = new ThreadLocal() {
    @Override
    protected DateFormat initialValue() {
        return new SimpleDateFormat("yyyy-MM-dd");
    }
};

/** 格式化日期函数 */
public static String formatDate(Date date) {
    return LOCAL_DATE_FORMAT.get().format(date);
}

这是在没有线程安全的日期格式化工具类之前的实现方法。在 JDK8 以后，建议使用 DateTimeFormatter 代替 SimpleDateFormat ，因为 SimpleDateFormat 是线程不安全的，而 DateTimeFormatter 是线程安全的。当然，也可以采用第三方提供的线程安全日期格式化函数，比如 apache 的 DateFormatUtils 工具类。

注意： ThreadLocal 有一定的内存泄露的风险，尽量在业务代码结束前调用 remove 函数进行数据清除。

使用 Pair 实现成对结果的返回

在 C/C++ 语言中， Pair （对）是将两个数据类型组成一个数据类型的容器，比如 std::pair 。

Pair 主要有两种用途：

1、把 key 和 value 放在一起成对处理，主要用于 Map 中返回名值对，比如 Map 中的 Entry 类；

2、当一个函数需要返回两个结果时，可以使用 Pair 来避免定义过多的数据模型类。

第一种用途比较常见，这里主要说明第二种用途。

定义模型类实现成对结果的返回

函数实现代码：

/** 点和距离类 */
@Setter
@Getter
@ToString
@AllArgsConstructor
public static class PointAndDistance {
    /** 点 */
    private Point point;
    /** 距离 */
    private Double distance;
}

/** 获取最近点和距离 */
public static PointAndDistance getNearestPointAndDistance(Point point, Point[] points) {
    // 检查点数组为空
    if (ArrayUtils.isEmpty(points)) {
        return null;
    }

    // 获取最近点和距离
    Point




    
 nearestPoint = points[0];
    double nearestDistance = getDistance(point, points[0]);
    for (int i = 1; i < points.length; i++) {
        double distance = getDistance(point, point[i]);
        if (distance < nearestDistance) {
            nearestDistance = distance;
            nearestPoint = point[i];
        }
    }

    // 返回最近点和距离
    return new PointAndDistance(nearestPoint, nearestDistance);
}

函数使用案例：

Point point = ...;
Point[] points = ...;
PointAndDistance pointAndDistance = getNearestPointAndDistance(point, points);
if (Objects.nonNull(pointAndDistance)) {
    Point point = pointAndDistance.getPoint();
    Double distance = pointAndDistance.getDistance();
    ...
}

使用 Pair 类实现成对结果的返回

在 JDK 中，没有提供原生的 Pair 数据结构，也可以使用 Map::Entry 代替。不过， Apache 的 commons-lang3 包中的 Pair 类更为好用，下面便以 Pair 类进行举例说明。

函数实现代码：

/** 获取最近点和距离 */
public static Pair, Double> getNearestPointAndDistance(Point point, Point[] points) {
    // 检查点数组为空
    if (ArrayUtils.isEmpty(points)) {
        return null;
    }

    // 获取最近点和距离
    Point nearestPoint = points[0];
    double nearestDistance = getDistance(point, points[0]);
    for (int i = 1; i < points.length; i++) {
        double distance = getDistance(point, point[i]);
        if (distance < nearestDistance) {
            nearestDistance = distance;
            nearestPoint = point[i];
        }
    }

    // 返回最近点和距离
    return Pair.of(nearestPoint, nearestDistance);
}

函数使用案例：

Point point = ...;
Point[] points = ...;
Pair, Double> pair = getNearestPointAndDistance(point, points);
if (Objects.nonNull(pair)) {
    Point point = pair.getLeft();
    Double distance = pair.getRight();
    ...
}

定义 Enum 类实现取值和描述

在 C++、Java 等计算机编程语言中，枚举类型（Enum）是一种特殊数据类型，能够为一个变量定义一组预定义的常量。在使用枚举类型的时候，枚举类型变量取值必须为其预定义的取值之一。

用 class 关键字实现的枚举类型

在 JDK5 之前， Java 语言不支持枚举类型，只能用类（class）来模拟实现枚举类型。

/** 订单状态枚举 */
public final class OrderStatus {
    /** 属性相关 */
    /** 状态取值 */
    private final int value;
    /** 状态描述 */
    private final String description;

    /** 常量相关 */
    /** 已创建(1) */
    public static final OrderStatus CREATED = new OrderStatus(1, "已创建");
    /** 进行中(2) */
    public static final OrderStatus PROCESSING = new OrderStatus(2, "进行中");
    /** 已完成(3) */
    public static final OrderStatus FINISHED = new OrderStatus(3, "已完成");

    /** 构造函数 */
    private OrderStatus(int value, String description) {
        this.value = value;
        this.description = description;
    }

    /** 获取状态取值 */
    public int getValue() {
        return value;
    }

    /** 获取状态描述 */
    public String getDescription() {
        return description;
    }
}

用 enum 关键字实现的枚举类型

JDK5 提供了一种新的类型—— Java 的枚举类型，关键字 enum 可以将一组具名的值的有限集合创建为一种新的类型，而这些具名的值可以作为常量使用，这是一种非常有用的功能。

/** 订单状态枚举 */
public enum OrderStatus {
    /** 常量相关 */
    /** 已创建(1) */
    CREATED(1, "已创建"),
    /** 进行中(2) */
    PROCESSING(2, "进行中"),
    /** 已完成(3) */
    FINISHED(3, "已完成");

    /** 属性相关 */
    /** 状态取值 */
    private final int value;
    /** 状态描述 */
    private final String description;

    /** 构造函数 */
    private OrderStatus(int value, String description) {
        this.value = value;
        this.description = description;
    }

    /** 获取状态取值 */
    public int getValue() {
        return value;
    }

    /** 获取状态描述 */
    public String getDescription() {
        return description;
    }
}

其实，Enum 类型就是一个语法糖，编译器帮我们做了语法的解析和编译。通过反编译，可以看到 Java 枚举编译后实际上是生成了一个类，该类继承了 java.lang.Enum ，并添加了 values()、valueOf() 等枚举类型通用方法。

定义 Holder 类实现参数的输出

在很多语言中，函数的参数都有输入（in）、输出（out）和输入输出（inout）之分。在 C/C++ 语言中，可以用对象的引用（&）来实现函数参数的输出（out）和输入输出（inout）。但在 Java 语言中，虽然没有提供对象引用类似的功能，但是可以通过修改参数的字段值来实现函数参数的输出（out）和输入输出（inout）。这里，我们叫这种输出参数对应的数据结构为Holder（支撑）类。

Holder 类实现代码：

/** 长整型支撑类 */
@Getter
@Setter
@ToString
public class LongHolder {
    /** 长整型取值 */
    private long value;

    /** 构造函数 */
    public LongHolder() {}

    /** 构造函数 */
    public LongHolder(long value) {
        this.value = value;
    }
}

Holder 类使用案例：

/** 静态常量 *//** 页面数量 */private static final int PAGE_COUNT = 100;/** 最大数量 */private static final int MAX_COUNT = 1000;

/** 处理过期订单 */public void handleExpiredOrder() {  LongHolder minIdHolder = new LongHolder(0L);    for (int pageIndex = 0; pageIndex < PAGE_COUNT; pageIndex++) {        if (!handleExpiredOrder(pageIndex, minIdHolder)) {          break;        }    }}

/** 处理过期订单 */private boolean handleExpiredOrder(int pageIndex, LongHolder minIdHolder) {  // 获取最小标识  Long minId = minIdHolder.getValue();

  // 查询过期订单(按id从小到大排序)  List orderList = orderDAO.queryExpired(minId, MAX_COUNT);  if (CollectionUtils.isEmpty(taskTagList)) {    return false;  }

  // 设置最小标识  int orderSize = orderList.size();  minId = orderList.get(orderSize - 1).getId();  minIdHolder.setValue(minId);

  // 依次处理订单   for (OrderDO order : orderList) {       ...    }

  // 判断还有订单  return orderSize >= PAGE_SIZE;}

其实，可以实现一个泛型支撑类，适用于更多的数据类型。

定义 Union 类实现数据体的共存

在 C/C++ 语言中，联合体（union），又称共用体，类似结构体（struct）的一种数据结构。联合体（union）和结构体（struct）一样，可以包含很多种数据类型和变量，两者区别如下：

1、结构体（struct）中所有变量是“共存”的，同时所有变量都生效，各个变量占据不同的内存空间；

2、联合体（union）中是各变量是“互斥”的，同时只有一个变量生效，所有变量占据同一块内存空间。

当多个数据需要共享内存或者多个数据每次只取其一时，可以采用联合体（union）。

在Java语言中，没有联合体（union）和结构体（struct）概念，只有类（class）的概念。众所众知，结构体（struct）可以用类（class）来实现。其实，联合体（union）也可以用类（class）来实现。但是，这个类不具备“多个数据需要共享内存”的功能，只具备“多个数据每次只取其一”的功能。

这里，以微信协议的客户消息为例说明。根据我多年来的接口协议封装经验，主要有以下两种实现方式。

使用函数方式实现 Union

Union 类实现:

/** 客户消息类 */
@ToString
public class CustomerMessage {

    /** 属性相关 */
    /** 消息类型 */
    private String msgType;
    /** 目标用户 */
    private String toUser;

    /** 共用体相关 */
    /** 新闻内容 */
    private News news;
    ...

    /** 常量相关 */
    /** 新闻消息 */
    public static final String MSG_TYPE_NEWS = "news";
    ...

    /** 构造函数 */
    public CustomerMessage() {}

    /** 构造函数 */
    public CustomerMessage(String toUser) {
        this.toUser = toUser;
    }

    /** 构造函数 */
    public CustomerMessage(String toUser, News news) {
        this.toUser = toUser;
        this.msgType = MSG_TYPE_NEWS;
        this.news = news;
    }

    /** 清除消息内容 */
    private void removeMsgContent() {
        // 检查消息类型
        if (Objects.isNull(msgType)) {
            return;
        }

        // 清除消息内容
        if (MSG_TYPE_NEWS.equals(msgType)) {
            news = null;
        } else if (...) {
        ...
        }
        msgType = null;
    }

    /** 检查消息类型 */
    private void checkMsgType(String msgType) {
        // 检查消息类型
        if (Objects.isNull(msgType)) {
            throw new IllegalArgumentException("消息类型为空");
        }

        // 比较消息类型
        if (!Objects.equals(msgType, this.msgType)) {
            throw new IllegalArgumentException("消息类型不匹配");
        }
    }

    /** 设置消息类型函数 */
    public void setMsgType(String msgType) {
        // 清除消息内容
        removeMsgContent();

        // 检查消息类型
        if (Objects.isNull(msgType)) {
            throw new IllegalArgumentException("消息类型为空");
        }

        // 赋值消息内容
        this.msgType = msgType;
        if (MSG_TYPE_NEWS.equals(msgType)) {
            news = new News();
        } else if (...) {
        ...
              } else {
            throw new IllegalArgumentException("消息类型不支持");
        }
    }

    /** 获取消息类型 */
    public String getMsgType() {
        // 检查消息类型
        if (Objects.isNull(msgType)) {
            throw new IllegalArgumentException("消息类型无效");
        }

        // 返回消息类型
        return this.msgType;
    }

    /** 设置新闻 */
    public void setNews(News news) {
        // 清除消息内容
        removeMsgContent();

        // 赋值消息内容
        this.msgType = MSG_TYPE_NEWS;
        this.news = news;
    }

    /** 获取新闻 */
    public News getNews() {
        // 检查消息类型
        checkMsgType(MSG_TYPE_NEWS);

        // 返回消息内容
        return this.news;
    }
    
    ...
}

Union 类使用:

String accessToken = ...;
String toUser = ...;
List articleList = ...;
News news = new News(articleList);
CustomerMessage customerMessage = new CustomerMessage(toUser, news);
wechatApi.sendCustomerMessage(accessToken, customerMessage);

主要优缺点:

优点：更贴近 C/C++ 语言的联合体（union）；
缺点：实现逻辑较为复杂，参数类型验证较多。

使用继承方式实现 Union