ARTS打卡第十二周

Algorithm：141. 环形链表 https://leetcode-cn.com/problems/linked-list-cycle/submissions/

给定一个链表，判断链表中是否有环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 示例 1： 输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。 示例 2： 输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。 示例 3： 输入：head = [1], pos = -1 输出：false 解释：链表中没有环。 进阶： 你能用 O(1)（即，常量）内存解决此问题吗？

解法一：用hashSet缓存遍历过的节点，遇到相同节点表示有环。时间复杂度O(n)，空间复杂度O(n)

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { Set<ListNode> set = new HashSet<>(); while(head != null) { if(set.contains(head)) return true; set.add(head); head = head.next; } return false; } }

解法二（进阶）：将遍历过的节点指向一个特殊节点，最后如果又回到这个特殊节点，就表示有环。时间复杂度O(n)，空间复杂度O(1). 这个算法的弊端是破话了原链表。

public boolean hasCycle(ListNode head) { ListNode special = new ListNode(-1); ListNode p = head; ListNode q = head == null ? null : head.next; while(q != null && q != special) { p.next = special; p = q; q = q.next; } return q == special; }

解法三（进阶）：快慢指针，快指针比慢指针多移动一步，如果有环，最终快指针会追上慢指针。时间复杂度O(n)，空间复杂度O(1).

public boolean hasCycle(ListNode head) { ListNode fast = head == null ? null : head.next; ListNode slow = head; while(fast != null && fast != slow) { if(fast.next == null) return false; fast = fast.next.next; slow = slow.next; } return fast != null && fast == slow; }

Review: What Is MLAG Networking？

原文链接：http://www.fiber-optic-cable-sale.com/mlag-networking-wiki.html

MLAG，全称是Multi-Chassis Link Aggregation Group（多机架链路聚合组），是一种链路聚合技术，Juniper将其称为MC-LAG，Cisco将其称为mLACP 。

MLAG既可以增加带宽，又可以增强可靠性。MLAG从LAG发展而来，但相比于LAG的链路冗余，MLAG提供节点级别的冗余；相比于STP（Spanning Tree Protocol），HA MLAG不需要浪费端口就能防止拓扑环路。

参考资料： https://en.wikipedia.org/wiki/MC-LAG 详解交换机虚拟化技术VRRP、堆叠、M-LAG及其区别-信锐技术

Tip: 使用Jersey的Response返回JDK自带数据类型的集合

例如，我们想返回一个String类型的list。

List<String> stringList = Arrays.asList("a", "b", "c");

比较方便的做法是用一个POJO类型包装一下：

@Data @XmlRootElement @XmlAccessorType(XmlAccessType.FIELD) public class StringListVO implements Serializable { private List<String> data; } #然后在代码里直接返回这个POJO对象 StringListVO stringListVO = new StringListVO(); stringListVO.setData(stringList); return ResponseUtil.success(stringListVO);

这种做法有一个坑要注意，就是POJO类不能定义有参构造方法，否则就会抛出MessageBodyWriter not found 异常

一些尝试

我们无法直接将List<String> 放到Response的entity里，也就是说像下面的写法都是不行的，都会抛出MessageBodyWriter not found 异常：

#写法一： return Response.ok(stringList).build(); #写法二： GenericEntity<List<String>> entity = new GenericEntity<List<String>>(stringList){}; return Response.ok(entity).build(); 如果是`String[]`数组，将其直接放到Response里，是可以的，只不过显示效果是这样的： [ { "type": "string", "value": "a" }, { "type": "string", "value": "b" }, { "type": "string", "value": "c" }, ]

如果我们想把StringListVO搞得更通用一些，定义成范型，就像这样：

@Data @XmlRootElement @XmlAccessorType(XmlAccessType.FIELD) public class ListVO<T> implements Serializable { private List<T> data; } #然后在代码里返回这个POJO对象 ListVO<T> stringListVO = new ListVO<>(); stringListVO.setData(stringList); GenericEntity<ListVO<String>> entity = new GenericEntity<ListVO<String>>(stringListVO){}; return Response.ok(entity).build();

这样也是不行的，而且没有异常输出。

Share: 分析源码，学会正确使用 Java 线程池

https://my.oschina.net/editorial-story/blog/3107684

异常处理

通过new Thread 方式创建的线程，Runnable 接口不允许抛出异常，异常只会发送到 System.err 。可以通过设置 UncaughtExceptionHandler 来捕获异常。通过 execute 方法提交到线程池，可以继承 ThreadPoolExecutor 重写其 afterExecute 方法处理异常。通过 submit 方法提交到线程池，其异常只有在调用返回的 Future 的 get 方法的时候，异常才会抛出来，抛出ExecutionException异常，那么调用它的getCause方法就可以拿到最原始的异常对象了。

线程数设置

CPU密集型，建议核心线程数设为CPU核数+1，最大线程数设为CPU核数*2；IO密集型，建议核心线程数设为CPU核数4，最大线程数设为CPU核数5；

如何正确关闭一个线程池

shutdown 方法优雅关闭，会拒绝新任务，但已添加到线程池的任务仍然会执行； shutdownNow 方法立即关闭，会拒绝新任务，并丢弃已经在线程池队列中的任务，同时设置每个线程的中断标记；

建议：先调用shutdown 方法拒绝新任务，然后调用awaitTermination方法设置超时时间。当awaitTermination方法返回false时，表示超时了，此时可以尝试调用 shutdownNow 方法，这就要求提交到线程池的任务能够响应中断，做一些资源回收的工作。

线程池中的其他有用方法

prestartAllCoreThreads 是ThreadPoolExecutor 类的方法，用来预先创建所有的核心线程，避免第一次调用时创建线程的开销。 setCorePoolSize方法和setMaximumPoolSize方法，在线程池创建完毕之后更改其线程数。建议的一种临时扩容的方法：

起一个定时轮询线程（守护类型），定时检测线程池中的线程数，具体来说就是调用getActiveCount方法。当发现线程数超过了核心线程数大小时，可以考虑将CorePoolSize和MaximumPoolSize的数值同时乘以2，当然这里不建议设置很大的线程数，因为并不是线程越多越好的，可以考虑设置一个上限值，比如50、100之类的。同时，去获取队列中的任务数，具体来说是调用getQueue方法再调用size方法。当队列中的任务数少于队列大小的二分之一时，我们可以认为现在线程池的负载没有那么高了，因此可以考虑在线程池先前有扩容过的情况下，将CorePoolSize和MaximumPoolSize还原回去，也就是除以2。

其他注意事项

线程池中的队列是共享的，所以会有很多锁。如果想提高性能，可以创建一个单线程的线程池列表，用这个线程池列表来实现多线程，这就是Netty EventLoop的思路。也可以使用Disruptor。

任何情况下都不应该使用可伸缩线程池（线程的创建和销毁开销是很大的），这个似乎有些绝对，但绝大多数情况下是不应该用的。典型例子就是 Executors.newCachedThreadPool，线程数量不可控，创建和销毁开销大，这种线程池应该用在使用频率很低并且性能不敏感的场景，且最好自定义线程数量。

任何情况下都不应该使用无界队列，单测除外。有界队列常用的有ArrayBlockingQueue和LinkedBlockingQueue，前者基于数组实现，后者基于链表。从性能表现上来看，LinkedBlockingQueue的吞吐量更高但是性能并不稳定，实际情况下应当使用哪一种建议自行测试之后决定。顺便说一句，Executors的newFixedThreadPool采用的是LinkedBlockingQueue。

推荐自行实现RejectedExecutionHandler，JDK自带的都不是很好用，你可以在里面实现自己的逻辑。如果需要一些特定的上下文信息，可以在Runnable实现类中添加一些自己的东西，这样在RejectedExecutionHandler中就可以直接使用了