Java programming techniques for data structures

takeaway

Ouyang Xiu, one of the eight masters of the Tang and Song dynasties, wrote in His book The Old Man Selling Oil:

Weng took a gourd and put it on the ground, covered its mouth with money, and xu dipped the oil with a ladle. The money went into the hole, but the money was not wet. He said, “I have no one but my hand.”

The same is true of the “old driver” who writes the code, and the reason why “old driver” is called “old driver” is that “nobody but the hand.” In the process of coding step over the pit more, the coding experience will be more, summed up the coding skills will be more. Summary of the coding skills, and everything can be extrapolated, the speed of coding on the natural. From the perspective of data structure, the author sorted out some Java programming skills for everyone to learn reference.

1. Use HashSet to check whether the primary key exists

HashSet implements the Set interface, which is supported by a hash table (actually a HashMap), but does not guarantee the iteration order of the Set and allows null elements. The time complexity of a HashSet is the same as that of a HashMap. If there are no hash conflicts, the time complexity is O(1); if there are hash conflicts, the time complexity does not exceed O(n). So, in everyday coding, you can use a HashSet to determine whether a primary key exists.

Example: Given a string (not necessarily all letters), return the first recurring character.

Public static Character findFirstRepeatedChar(String String) {// Check the empty Stringif (Objects.isNull(string) || string.isEmpty()) {
        returnnull; Char [] charArray = string.tochararray (); Set charSet = new HashSet<>(charArray.length);for (char ch : charArray) {
        if (charSet.contains(ch)) {
            returnch; } charSet.add(ch); } // Return null by defaultreturn null;
}Copy the code

The Set add function returns false if the added element already exists in the collection. The code can be simplified as:

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

2. Use HashMap to access key-value mappings

Simply put, a HashMap is made up of arrays, the body of a HashMap, and linked lists, which are designed to resolve hash conflicts. If the location of the array does not contain a linked list, then the search, add and other operations are very fast, only need one address, its time complexity is O(1); If the array to be located contains a linked list, the time complexity of the add operation is O(n) — the list is first traversed, the existence is overwritten, the non-existence is added; For lookups, you still need to traverse the linked list and compare the lookups one by one through the Equals method of the key object. In terms of performance, the fewer linked lists in a HashMap, that is, the fewer hash collisions, the better the performance. So, in everyday coding, you can use hashMaps to access key-value mappings.

Example: Given a list of menu records, each menu record contains the parent menu identifier (the parent menu identifier of the root menu is NULL), building the entire menu tree.

/** MenuDO class */ @setter@getter@toString public static class MenuDO {/** MenuDO class */ private Long id; /** Private Long parentId; /** menu name */ private String name; /** menu link */ private String url; } @setter@getter@toString public static class MenuVO {/** private Long id; /** menu name */ private String name; /** menu link */ private String url; Private List<MenuVO> childList; private List<MenuVO> childList; } public static List<MenuVO> buildMenuTree(List<MenuDO> menuList) {// Check List is emptyif (CollectionUtils.isEmpty(menuList)) {
        returnCollections.emptyList(); } int menuSize = menulist.size (); List<MenuVO> rootList = new ArrayList<>(menuSize); Map<Long, MenuVO> menuMap = new HashMap<>(menuSize);for(MenuDO MenuDO: menuList) {// Assign menu object 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)) {// build the parentMenu object MenuVO parentMenu = menumap.get (parentId);if(Objects.isNull(parentMenu)) { parentMenu = new MenuVO(); parentMenu.setId(parentId); parentMenu.setChildList(new ArrayList<>()); menuMap.put(parentId, parentMenu); } // Add a submenu object parentmenu.getChildList ().add(menu); }else{// Add the root menu object rootList.add(menu); }} // Return to the root menu listreturn rootList;
}Copy the code

3. Use ThreadLocal to store thread-specific objects

ThreadLocal provides thread-specific objects that can be accessed at any time throughout a thread’s life cycle, making it much easier to implement logic.

There are two common uses of ThreadLocal:

Save thread context objects to avoid multi-level parameter passing;
Save non-thread-safe objects to avoid concurrent calls from multiple threads.

3.1. Save thread context objects to avoid multi-level parameter passing

Here, the PageHelper plug-in in the source code of the page parameter setting and use as an example.

Set paging parameter code:

/** protected static final ThreadLocal<Page> LOCAL_PAGE = new ThreadLocal<Page>(); /** Set paging parameters */ protected static voidsetLocalPage(Page page) { LOCAL_PAGE.set(page); } public static <T> Page<T>getLocalPage() {
        returnLOCAL_PAGE.get(); } public static <E> Page<E> startPage(int pageNum, int pageSize, Boolean count, Boolean reasonable, Boolean pageSizeZero) { Page<E> page = new Page<E>(pageNum, pageSize, count); page.setReasonable(reasonable); page.setPageSizeZero(pageSizeZero); Page<E> oldPage = getLocalPage();if(oldPage ! = null && oldPage.isOrderByOnly()) { page.setOrderBy(oldPage.getOrderBy()); }setLocalPage(page);
        returnpage; }}Copy the code

Use the paging parameter code:

Public abstract class AbstractHelperDialect extends AbstractDialect implements Constant {/** get local paging */ public <T> Page<T>getLocalPage() {
        returnPageHelper.getLocalPage(); } @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;
        }
        returngetPageSql(sql, page, pageKey); }... }Copy the code

Using the paging plug-in code:

Public PageInfo<UserDO> queryUser(UserQuery UserQuery, int pageNum) int pageSize) { PageHelper.startPage(pageNum, pageSize); List<UserDO> userList = userDAO.queryUser(userQuery); PageInfo<UserDO> pageInfo = new PageInfo<>(userList);return pageInfo;
}Copy the code

If you want to pass paging parameters to a query step by step through function parameters, it is not possible to do so unless you modify MyBatis related interface functions.

3.2. Save non-thread-safe objects to avoid multi-threaded concurrent calls

When writing the date formatter function, the first thing that comes to mind is the following:

/** Date pattern */ private static final String DATE_PATTERN ="yyyy-MM-dd"; Public static String formatDate(Date Date) {return new SimpleDateFormat(DATE_PATTERN).format(date);
}Copy the code

DateFormat is initialized on each call, resulting in poor performance.

/ / private static final DateFormat DATE_FORMAT = new SimpleDateFormat("yyyy-MM-dd"); Public static String formatDate(Date Date) {return DATE_FORMAT.format(date);
}Copy the code

Because SimpleDateFormat is not thread-safe, when multiple threads call the formatDate function at the same time, the results returned are not as expected. If ThreadLocal is used to define thread-specific objects, the optimized code looks like this:

Private static final ThreadLocal<DateFormat> LOCAL_DATE_FORMAT = new ThreadLocal<DateFormat>() {@override  protected DateFormatinitialValue() {
        return new SimpleDateFormat("yyyy-MM-dd"); }}; Public static String formatDate(Date Date) {return LOCAL_DATE_FORMAT.get().format(date);
}Copy the code

This was implemented before there were thread-safe date formatting utility classes. After JDK8, it is recommended to use DateTimeFormatter instead of SimpleDateFormat, because SimpleDateFormat is thread-safe, whereas DateTimeFormatter is thread-safe. Of course, you can also use thread-safe date formatting functions provided by third parties, such as Apache’s DateFormatUtils utility class.

Note: ThreadLocal has some risk of memory leakage, so try to call the remove function to clean data before the business code ends.

4. Use Pair to return paired results

In C/C++, a Pair is a container that combines two data types into a single data type, such as STD :: Pair.

Pair has two main uses:

A pair of keys and values is used to return a pair of name values in a Map, such as the Entry class in a Map.
When a function needs to return two results, you can use Pair to avoid defining too many data model classes.

The first use is more common, and the second is mainly described here.

4.1. Define model classes to implement the return of the results

Function implementation code:

Constructor public static class PointAndDistance {/** Point */ private Point  point; /** distance */ private Double distance; } / * * the closest Point and distance * / public static PointAndDistance getNearestPointAndDistance (Point Point, Point [] points) {/ / checkpoint array is emptyif (ArrayUtils.isEmpty(points)) {
        returnnull; } 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]; }} // Returns the nearest point and distancereturn new PointAndDistance(nearestPoint, nearestDistance);
}Copy the code

Function use case:

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

4.2. Return pairs of results using the Pair class

In the JDK, no native Pair data structure is provided, and Map::Entry can be used instead. However, the Pair class in Apache’s Commons-Lang3 package is more useful, as illustrated below.

Function implementation code:

/ * * the closest Point and distance * / public static Pair < Point, Double > getNearestPointAndDistance (Point Point, Point [] points) {/ / checkpoint array is emptyif (ArrayUtils.isEmpty(points)) {
        returnnull; } 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]; }} // Returns the nearest point and distancereturn Pair.of(nearestPoint, nearestDistance);
}Copy the code

Function use case:

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

5. Define the value and description of the Enum class

In computer programming languages such as C++ and Java, an enumerated type (Enum) is a special data type that defines a set of predefined constants for a variable. When using an enumerated type, the value of an enumerated type variable must be one of its predefined values.

5.1. Enumeration types implemented with the class keyword

Prior to JDK5, the Java language did not support enumerated types and could only be simulated using classes to implement enumerated types.

/** OrderStatus enumeration */ public final class OrderStatus {/** attribute related */ /** status value */ private final int value; /** State description */ private final String Description; Public static final OrderStatus CREATED = new OrderStatus(1, 1)"Created"); / / Public static final OrderStatus PROCESSING = new OrderStatus(2,"In progress"); / / Public static final OrderStatus FINISHED = new OrderStatus(3,"Done"); /** Constructor */ private OrderStatus(int Value, String description) {this.value = value; this.description = description; } /** Get the status value */ public intgetValue() {
        returnvalue; } /** Get the status description */ public StringgetDescription() {
        returndescription; }}Copy the code

5.2. Enumeration types implemented with the enum keyword

JDK5 provides a new type — Java enumerated types. The keyword enum can create a new type from a limited set of named values that can be used as constants, a very useful feature.

/** createStatus (1) */ createStatus (1) */ createStatus (1) */ createStatus (1)"Created"), /** in progress (2) */ PROCESSING(2,"In progress"), /** FINISHED(3) */ FINISHED(3)"Done"); /** Attribute related */ /** status value */ private final int value; /** State description */ private final String Description; /** Constructor */ private OrderStatus(int Value, String description) {this.value = value; this.description = description; } /** Get the status value */ public intgetValue() {
        returnvalue; } /** Get the status description */ public StringgetDescription() {
        returndescription; }}Copy the code

In fact, the Enum type is a syntax sugar, and the compiler does the parsing and compiling for us. Through decompilation, you can see that when Java enumerations are compiled, they actually generate a class that inherits java.lang.enum and adds common methods for enumeration types such as Values () and valueOf().

6. Define the output of the Holder class implementation parameters

In many languages, function parameters are in, out, and inout. In C/C++, a reference to an object (&) can be used to implement out and inout of function parameters. However, in the Java language, although there is no similar function for object reference, you can modify the field value of the parameter to realize the output (out) and input and output (inout) of function parameters. Here, we call the data structure corresponding to this output parameter the Holder (support) class.

Holder class implementation code:

@getter@setter@toString Public class LongHolder {private long value; /** constructor */ publicLongHolder() {} /** constructor */ public LongHolder(long value) {this.value = value; }}Copy the code

Holder class use case:

Private static final int PAGE_COUNT = 100; private static final int PAGE_COUNT = 100; Private static final int MAX_COUNT = 1000; /** Process overdue orders */ public voidhandleExpiredOrder() {
    LongHolder minIdHolder = new LongHolder(0L);
    for (int pageIndex = 0; pageIndex < PAGE_COUNT; pageIndex++) {
        if(! handleExpiredOrder(pageIndex, minIdHolder)) {break; }}} /** Handle overdue orders */ private Boolean handleExpiredOrder(int pageIndex, Long minId = minidholder.getValue (); List<OrderDO> 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); // Process orders in turnfor(OrderDO order : orderList) { ... } // There are still ordersreturn orderSize >= PAGE_SIZE;
}Copy the code

In fact, you can implement a generic support class for more data types.

7. Define the Union class to realize the coexistence of data bodies

In C/C++, a union is a data structure similar to a struct. A union, like a struct, can contain many types of data and variables. The differences are as follows:

All variables in a struct are “co-existing” and all variables are in effect at the same time, each variable occupies different memory space;
In a union, each variable is “mutually exclusive”, only one variable is in effect at the same time, and all variables occupy the same memory space.

When multiple data needs to share memory or multiple data needs to be fetched only for a moment at a time, a union can be used.

In the Java language, there are no unions or structs, only classes. As we all know, structs can be implemented using classes. In fact, unions can also be implemented using classes. However, this class does not have “multiple data needs to share memory” functionality, only “multiple data at a time” functionality.

Here, take wechat protocol customer messages as an example. According to my years of experience in interface protocol encapsulation, there are mainly the following two implementation methods.

7.1. Implement Union in a functional way

The Union class implements:

@toString Public Class CustomerMessage {/** attribute */ /** message type */ private String msgType; /** target user */ private String toUser; /** private News News */ private News News; . Public static final String MSG_TYPE_NEWS = public static final String MSG_TYPE_NEWS ="news"; . /** constructor */ publicCustomerMessage() {} /** Constructor */ public CustomerMessage(String toUser) {this.touser = toUser; } /** Constructor */ public CustomerMessage(String toUser, News News) {this.toUser = toUser; this.msgType = MSG_TYPE_NEWS; this.news = news; } /** Clear message content */ private voidremoveMsgContent() {// Check the message typeif (Objects.isNull(msgType)) {
            return; } // Clear the message contentif (MSG_TYPE_NEWS.equals(msgType)) {
            news = null;
        } else if(...). {... } msgType = null; } /** Check message type */ private void checkMsgType(String msgType) {// Check message typeif (Objects.isNull(msgType)) {
            throw new IllegalArgumentException("Message type is empty"); } // Compare message typesif(! Objects.equals(msgType, this.msgType)) { throw new IllegalArgumentException("Message type mismatch"); }} /** Sets the message type function */ public voidsetMsgType(String MsgType) {// Remove message content removeMsgContent(); // Check the message typeif (Objects.isNull(msgType)) {
            throw new IllegalArgumentException("Message type is empty"); } this.msgType = msgType;if (MSG_TYPE_NEWS.equals(msgType)) {
            news = new News();
        } else if (...) {
            ...
        } else {
            throw new IllegalArgumentException("Message type not supported"); }} /** Get the message type */ public StringgetMsgType() {// Check the message typeif (Objects.isNull(msgType)) {
            throw new IllegalArgumentException("Message type invalid"); } // Return the message typereturnthis.msgType; } /** Set the news */ public voidsetNews(News News) {// Remove message content removeMsgContent(); This. msgType = MSG_TYPE_NEWS; this.news = news; } /** Get News */ public NewsgetNews() {// Check the message type checkMsgType(MSG_TYPE_NEWS); // Returns the message contentreturnthis.news; }... }Copy the code

The Union class uses:

String accessToken = ... ; String toUser = ... ; List<Article> articleList = ... ; News news = new News(articleList); CustomerMessage customerMessage = new CustomerMessage(toUser, news); wechatApi.sendCustomerMessage(accessToken, customerMessage);Copy the code

Main advantages and disadvantages:

Advantages: More close to C/C++ language union;
Disadvantages: more complex implementation logic, more parameter type verification.

7.2. Implement Union using inheritance

The Union class implements:

/** CustomerMessage class */ @getter@setter@tostring public abstract class CustomerMessage {/** attribute dependent */ /** message type */ private String msgType; /** target user */ private String toUser; Public static final String MSG_TYPE_NEWS = public static final String MSG_TYPE_NEWS ="news"; . /** constructor */ public CustomerMessage(String msgType) {this.msgType = msgType; } /** Constructor */ public CustomerMessage(String msgType, String toUser) {this.msgType = msgType; this.toUser = toUser; }} /** News client message class */ @getter@setter@toString (callSuper =true) public class NewsCustomerMessage extends CustomerMessage {/** attribute */ /** News content */ private News News; /** constructor */ publicNewsCustomerMessage() { super(MSG_TYPE_NEWS); } /** Constructor */ public NewsCustomerMessage(String toUser, News News) {super(MSG_TYPE_NEWS, toUser); this.news = news; }}Copy the code

The Union class uses:

String accessToken = ... ; String toUser = ... ; List<Article> articleList = ... ; News news = new News(articleList); CustomerMessage customerMessage = new NewsCustomerMessage(toUser, news); wechatApi.sendCustomerMessage(accessToken, customerMessage);Copy the code

Main advantages and disadvantages:

Advantages: Using virtual base class and subclass to split, each subclass object concept is clear;
Disadvantages: Very different from C/C++ union, but generally the same functionality.

In C/C++, a union does not include the current data type of the union. However, in the Java union implemented above, the corresponding data type of the union is already included. So, Java union is not really a union in the strict sense, just a class that takes one of many data at a time.

8. Use generics to mask type differences

In C++, there is a useful template feature that allows you to write generic versions with parameterized types that the compiler automatically generates specific versions for different types. In the Java language, there is a similar feature called generics. While classes and methods are typically written with concrete types, using generics makes it possible to parameterize the types and write more general code.

Many people believe that C++ templates and Java generics are equivalent concepts, but the implementation mechanisms are completely different. A C++ template is a set of macro instructions. The compiler creates a copy of the template code for each type. The implementation of Java generics is based on the concept of “type erasure”, which is essentially a syntactic sugar for type restriction.

8.1. A generic class

Using the support class as an example, define a generic support class for generics:

Public class GenericHolder<T> {/** GenericHolder */ private T value; /** constructor */ publicGenericHolderPublic GenericHolder(T value) {this.value = value; }}Copy the code

8.2. Generic interfaces

Define generic data provider interface:

Public DataProvider<T> {public T getData(); }Copy the code

8.3. Generic methods

To define a shallow copy function for generics:

Public static <T> T shallowCopy(Objectsource, Class<T> clazz) throws BeansException {// Judge source objectif (Objects.isNull(source)) {
        returnnull; } // create target object T target; try { target = clazz.newInstance(); } catch (Exception e) { throw new BeansException("New class instance exception", e); } // Copy the object property beanutils.copyProperties (source, target); // Return the target objectreturn target;
}Copy the code

8.4. Generic wildcards

The generic wildcard is usually “?” Instead of a specific type argument, we can call “?” As the parent of all types. When the specific type is uncertain, use the generic wildcard “?” ; You can use the generic wildcard “? “when you do not need the specific functionality of the type, but only the functionality of the Object class. .

/** Prints the value function */ public static voidprintValue(GenericHolder<? > holder) { System.out.println(holder.getValue()); Public static void main(String[] args) {public static void main(String[] args) {printValue(new GenericHolder<>(12345));
    printValue(new GenericHolder<>("abcde"));
}Copy the code

In the Java specification, the generic wildcard “? “is not recommended. , the above function can be changed to:

*/ public static <T> voidprintValue(GenericHolder<T> holder) {
    System.out.println(holder.getValue());
}Copy the code

8.5. Upper and lower bounds of generics

When using generics, we can also impose upper and lower bounds on the type arguments passed in. For example, type arguments can only be passed in the parent or subclass of a type. The declaration of upper and lower bounds of generics must be accompanied by the declaration of generics.

Extends:

The upper bound wildcard is “extends” and can accept its specified type or its subclasses as generic arguments. In a special form, you can specify not only that it is a subclass of a type, but also that it implements some interface. For example, a List
indicates that this is A List of concrete subclasses of A, and the objects held must be either A or subclasses of A. For a List
list. You cannot add objects of A or subclasses of A, but only get objects of A.

Lower bound wildcard (super) :

The lower bound wildcard is “super”, which can accept its specified type or its parent class as a generic parameter. For example, a List
indicates that this is A List of some concrete parent of A, and the object saved must be either A or A’s superclass. For a List
list, can add A or A subclass Object, but can only get Object objects.

PECS (Producer Extends Consumer Super) Principle: When providing data as a Producer (reading outwardly), an upper bound wildcard Extends is appropriate. As consumer data, the lower bound wildcard (super) is appropriate.

In everyday coding, an upper bound wildcard (extends) is used to qualify the parent class of a generic type. Example code is as follows:

@getter@setter@toString Public class NumberHolder<T extends Number> {/** private T value; /** constructor */ publicNumberHolder() {} /** constructor */ public NumberHolder(T value) {this.value = value; }} public static <T extends Number> voidprintValue(GenericHolder<T> holder) {
    System.out.println(holder.getValue());
}Copy the code

Afterword.

The author has been working in the communication industry for more than 10 years, and has access to more than 100 kinds of northbound interface protocols of all kinds of network management and equipment, involving transmission, switching, access, power supply, environment and other professions. He has contacted CORBA, HTTP/HTTPS, WebService, Socket TCP/UDP, serial port RS232/485 and other interfaces. Summarized a set of interface protocol encapsulation “methodology”. It is a very important step in the encapsulation of interface protocol to transform the data format of interface protocol document into Java data structure such as enumeration, structure and union.

Author: Chen Changyi, Hua Ming Changyi, technical expert of AmAP

The original link

This article is the original content of the cloud habitat community, shall not be reproduced without permission.