chaojun-zhang / javafamily Goto Github PK

View Code? Open in Web Editor NEW

0.0 1.0 0.0 154 KB

记录学习点滴，分享技术干货

Java 17.24% Scala 82.76%

java netty spark flink druid algorithms-datastructures hbase hdfs yarn scala

javafamily's Introduction

javafamily's People

Watchers

javafamily's Issues

概述

Java并发包里面所有的阻塞锁和同步的抽象模板类AbstractQueuedSynchronizer，主要依赖FIFO等待队列来实现，所有底层的重入锁和同步类都是从这个类派生的，所以理解这个类最关键，不过这篇文章主要结合重入锁进行开始分析

设计要点

AQS内部维护了一个阻塞队列，名字叫CLH（取自三个人的第一个字母),先来看下这个类的几个重要类

Node
队列的节点，每个节点内部持有一个线程属性，和对应的前驱和后续节点，还有个节点的标志是否是共享模式还是排他模式

static final class Node {
        /** Marker to indicate a node is waiting in shared mode */
        static final Node SHARED = new Node(); //表示是一个共享节点
        /** Marker to indicate a node is waiting in exclusive mode */
        static final Node EXCLUSIVE = null; //表示是一个排他节点
        volatile int waitStatus; //代表的是后续节点的等待状态，不是当前节点
        volatile Node prev; //链表的前驱节点
        volatile Node next;//链表的后续节点 
        volatile Thread thread; //代表当前节点对应的线程
        Node nextWaiter; 等待节点

AbstractQueuedSynchronizer
这个是所有并发包的基础类，最重要也就是下面几个属性

public abstract class AbstractQueuedSynchronizer  extends AbstractOwnableSynchronizer 
 implements java.io.Serializable {
        private transient volatile Node head;//等待队列的头节点
        private transient volatile Node tail;//等待队列的尾结点
        private volatile int state;//同步状态
   
       private transient Thread exclusiveOwnerThread;//这个是父类的属性，代表是当前拥有排他的线程
    }

由于这个类里面其实是个模板类，所以必须要结合子类，才能读懂里面的代码，先从简单的子类重入锁类开始吧

ReetrantLock
这个重入锁有2种模式，公平模式和非公平模式，有FairSync和NonfairSync实现，这2个都是继承Sync类，而Sync又继承AbstractQueuedSynchronizer，而Sync类本身又是一个模板类，本身即实现了AQS的tryRelease模板方法，同时提供了lock模板方法。

先看下类UML图

分析下FairSync的lock方法

    static final class FairSync extends Sync {
       final void lock() {
           acquire(1);//这里调用了父类的acquire方法
       }

看下父类的acquire方法

 public final void acquire(int arg) {
     if (!tryAcquire(arg) && 
         acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
         selfInterrupt();
 }

//这里调用了tryAcquire方法，这个方法其实是个模板方法，所以还是回到子类看这个实现，继续看子类
FairSync.tryAcquire

        protected final boolean tryAcquire(int acquires) {
            final Thread current = Thread.currentThread();//获取当前线程
            int c = getState();//获取同步状态，如果是0，那么说明
            if (c == 0) {
                if (!hasQueuedPredecessors() &&
                    compareAndSetState(0, acquires)) {
                    setExclusiveOwnerThread(current);
                    return true;
                }
            }
            else if (current == getExclusiveOwnerThread()) {
                int nextc = c + acquires;
                if (nextc < 0)
                    throw new Error("Maximum lock count exceeded");
                setState(nextc);
                return true;
            }
            return false;
        }

可以看到其逻辑如下

获取当前线程
获取当前同步状态
如果当前同步状态为0，说明还没有线程获取锁
- 继续判断是否有等待的节点，如果没有继续等待的节点，并且设置同步状态为1成功，同时设置当前线程为排他线程
- 如果同步状态不为0，说明有线程持有锁了，判断是否是当前线程获取了锁，如果是，对同步状态加1操作
- 否则返回false

看到这里如果tryAcquire返回false,接着调用acquireQueued(addWaiter(Node.EXCLUSIVE))，这个方法有点难懂，需要先从addWaiter开始。

	private Node addWaiter(Node node){
      Node node = new Node(Thread.currentThread(), mode);
        // Try the fast path of enq; backup to full enq on failure
        Node pred = tail;
        if (pred != null) {
            node.prev = pred;
            if (compareAndSetTail(pred, node)) {
                pred.next = node;
                return node;
            }
        }
        enq(node);
        return node; 
      }

这个就是典型的添加节点到队列的逻辑，使用CAS加死循环，保证多线程的原子性等，入队的方法看enq(node)这部分代码

   private Node enq(final Node node) {
     for (;;) {
           Node t = tail;
           if (t == null) { // Must initialize 
               if (compareAndSetHead(new Node()))//创建head节点
                   tail = head; 
           } else {
               node.prev = t;
               if (compareAndSetTail(t, node)) {
                   t.next = node;
                   return t;
               }
           }
       }
   }

这里首先判断tail是否为空，如果为空，那么说明还没有初始化链表，也就是先cas创建head节点，然后设置tail等于head,否则如果已经初始化过，那么先设置node的前驱节点为tail,并cas设置tail为自己，如果设置成功，那么设置tail的next为自，不成功说明有别的线程设置成功，那么继续循环，直到成功为止。

addWaiter最后返回node作为acquireQueued的方法入口参数，并传入一个参数（仍是1），看看它里面做了什么操作

    final boolean acquireQueued(final Node node, int arg) {
        boolean failed = true;
        try {
            boolean interrupted = false;
            for (;;) {
                final Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    failed = false;
                    return interrupted;
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                    parkAndCheckInterrupt())
                    interrupted = true;
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

这里也是一个死循环，除非进入if(p == head &&tryAcquire(arg))这个判定条件，而p为node.predcessor()得到，这个方法返回node节点的前一个节点，也就是说只有当前一个节点是head的时候，进一步尝试通过tryAcquire(arg)来征用才有机会成功。tryAcquire(arg)这个方法我们前面介绍过，成立的条件为：锁的状态为0，且通过CAS尝试设置状态成功或线程的持有者本身是当前线程才会返回true，我们现在来详细拆分这部分代码。

如果这个条件成功后，发生的几个动作包含：
- 首先调用setHead(Node)的操作，这个操作内部会将传入的node节点作为AQS的head所指向的节点。线程属性设置为空（因为现在已经获取到锁，不再需要记录下这个节点所对应的线程了），再将这个节点的perv引用赋值为null。
- 进一步将的前一个节点的next引用赋值为null。
  在进行了这样的修改后，队列的结构就变成了以下这种情况了，通过这样的方式，就可以让执行完的节点释放掉内存区域，而不是无限制增长队列，也就真正形成FIFO了：

如果这个判定条件失败
会首先判定：“shouldParkAfterFailedAcquire(p , node)”，这个方法内部会判定前一个节点的状态是否为：“Node.SIGNAL”，若是则返回true，若不是都会返回false，不过会再做一些操作：判定节点的状态是否大于0，若大于0则认为被“CANCELLED”掉了（我们没有说明几个状态的值，不过大于0的只可能被CANCELLED的状态），因此会从前一个节点开始逐步循环找到一个没有被“CANCELLED”节点，然后与这个节点的next、prev的引用相互指向；如果前一个节点的状态不是大于0的，则通过CAS尝试将状态修改为“Node.SIGNAL”，自然的如果下一轮循环的时候会返回值应该会返回true。
如果这个方法返回了true，则会执行：“parkAndCheckInterrupt()”方法，它是通过LockSupport.park(this)将当前线程挂起到WATING状态，它需要等待一个中断、unpark方法来唤醒它，通过这样一种FIFO的机制的等待，来实现了Lock的操作。

相应的，可以自己看看FairSync实现类的lock方法，其实区别不大，有些细节上的区别可能会决定某些特定场景的需求，你也可以自己按照这样的思路去实现一个自定义的锁。
接下来简单看看unlock()解除锁的方式，如果获取到了锁不释放，那自然就成了死锁，所以必须要释放，来看看它内部是如何释放的。同样从排它锁（ReentrantLock）中的unlock()方法开始，请先看下面的代码：

public void unlock(){
	sync.release(1);
}

public final boolean release(int arg) {
    if (tryRelease(arg)) {
         Node h = head;
         if (h != null && h.waitStatus != 0)
             unparkSuccessor(h);
         return true;
     }
     return false;
 }
protected final boolean tryRelease(int releases) {
     int c = getState() - releases;
     if (Thread.currentThread() != getExclusiveOwnerThread())
          throw new IllegalMonitorStateException();
      boolean free = false;
      if (c == 0) {
          free = true;
          setExclusiveOwnerThread(null);
      }
      setState(c);
      return free;
}

这个动作可以认为就是一个设置锁状态的操作，而且是将状态减掉传入的参数值（参数是1），如果结果状态为0，就将排它锁的Owner设置为null，以使得其它的线程有机会进行执行。
在排它锁中，加锁的时候状态会增加1（当然可以自己修改这个值），在解锁的时候减掉1，同一个锁，在可以重入后，可能会被叠加为2、3、4这些值，只有unlock()的次数与lock()的次数对应才会将Owner线程设置为空，而且也只有这种情况下才会返回true。
成功释放锁owner线程后，会继续把head节点的下一个节点的线程唤起，如果下一个节点为空，或者是下一个节点的waitStatus大于0，则需要从tail节点开始往前查找节点的waitstatus小于等于0，找到后调用LockSupport.unpark()进行唤起。

至此整个FairSync的代码分析完了，非公平锁的唯一区别就是先直接设置同步状态，如果设置成功，那么些如当前线程为排他线程。

 static final class NonfairSync extends Sync {
        private static final long serialVersionUID = 7316153563782823691L;

        /**
         * Performs lock.  Try immediate barge, backing up to normal
         * acquire on failure.
         */
        final void lock() {
            if (compareAndSetState(0, 1))
                setExclusiveOwnerThread(Thread.currentThread());
            else
                acquire(1);
        }

        protected final boolean tryAcquire(int acquires) {
            return nonfairTryAcquire(acquires);
        }
    }

这里compareAndSetState(0, 1) 就是直接设置为1，如果设置不成功，在调用acquire(1)，其实就是进入排队了，另外tryAcquire则是调用父类的nonfairTryAcquire，不过这里为啥要放在父类，更合理的是把nonfairTryAcquire这个方法内部逻辑直接放在NonfairSync的tryAcquire的方法里面，更加符合OO原则，别的逻辑和FairSync一样了，就不在分析了。

补充

关于Lock及AQS的一些补充：

Lock的操作不仅仅局限于lock()/unlock()，因为这样线程可能进入WAITING状态，这个时候如果没有unpark()就没法唤醒它，可能会一直“睡”下去，可以尝试用tryLock()、tryLock(long , TimeUnit)来做一些尝试加锁或超时来满足某些特定场景的需要。例如有些时候发现尝试加锁无法加上，先释放已经成功对其它对象添加的锁，过一小会再来尝试，这样在某些场合下可以避免“死锁”哦。
lockInterruptibly() 它允许抛出InterruptException异常，也就是当外部发起了中断操作，程序内部有可能会抛出这种异常，但是并不是绝对会抛出异常的，大家仔细看看代码便清楚了。
newCondition()操作，是返回一个Condition的对象，Condition只是一个接口，它要求实现await()、awaitUninterruptibly()、awaitNanos(long)、await(long , TimeUnit)、awaitUntil(Date)、signal()、signalAll()方法，AbstractQueuedSynchronizer中有一个内部类叫做ConditionObject实现了这个接口，它也是一个类似于队列的实现，具体可以参考源码。大多数情况下可以直接使用，当然觉得自己比较牛逼的话也可以参考源码自己来实现。
在AQS的Node中有每个Node自己的状态（waitStatus），我们这里归纳一下，分别包含:
- SIGNAL 从前面的代码状态转换可以看得出是前面有线程在运行，需要前面线程结束后，调用unpark()方法才能激活自己，值为：-1
- CANCELLED 当AQS发起取消或fullyRelease()时，会是这个状态。值为1，也是几个状态中唯一一个大于0的状态，所以前面判定状态大于0就基本等价于是CANCELLED的意思。
- CONDITION 线程基于Condition对象发生了等待，进入了相应的队列，自然也需要Condition对象来激活，值为-2。
- PROPAGATE 读写锁中，当读锁最开始没有获取到操作权限，得到后会发起一个doReleaseShared()动作，内部也是一个循环，当判定后续的节点状态为0时，尝试通过CAS自旋方式将状态修改为这个状态，表示节点可以运行。
  状态0 初始化状态，也代表正在尝试去获取临界资源的线程所对应的Node的状态

验证二叉搜索树

递归遍历

class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root==null) return true;
        return helper(root.left,Long.MIN_VALUE,root.val) && helper(root.right,root.val,Long.MAX_VALUE);
    }

    private boolean helper(TreeNode node ,long low,long high){
        if (node ==null) return true;
        if (node.val<=low || node.val>= high) return false;
        return helper(node.left,low,node.val) && helper(node.right,node.val,high);
        
    }
}

中序遍历法
当前遍历的元素必须大于上一个元素

class Solution {
  public boolean isValidBST(TreeNode root) {
    Stack<TreeNode> stack = new Stack();
    double inorder = - Double.MAX_VALUE;

    while (!stack.isEmpty() || root != null) {
      while (root != null) {
        stack.push(root);
        root = root.left;
      }
      root = stack.pop();
      // If next element in inorder traversal
      // is smaller than the previous one
      // that's not BST.
      if (root.val <= inorder) return false;
      inorder = root.val;
      root = root.right;
    }
    return true;
  }
}

细说Java BitSet

概述

JAVA中BitSet就是“位图”数据结构，根据“位图”的语义，数据的存在性可以使用bit位上的1或0来表示；一个bit具有2个值：0和1，正好可以用来表示false和true, 对于数据的判重，通常使用HashMap来存储，不过hashmap需要消耗较多的内存，在大数据场景中不太适合；

BitSet原理

JAVA中，一个long型数字占用64位空间，根据上述“位图”的概念，那么一个long型数字（4个字节）就可以保存64个数字的“存在性”状态，比如50个数字{0,1,10,...63}，判定“15”是否存在，那么我们通常会首先将这些数字使用数组或者hashmap保存，然后再去判定，那么保存这些这些数据需要占用64 * 64位；如果使用位图，那么一个long型数字即可。（如果换成50个字符串，那么其节约的空间可能更大）。

BitSet只面向数字比较，比如set(int a,boolean value)方法，将数字a在bitSet中设定为true或者false；此后可以通过get(int a)方法检测结果。对于string类型的数据，如果像使用BitSet，那么可以将其hashcode值映射在bitset中。

首先我们需要知道：1，1<<64，1<<128，1<<192...等，这些数字的计算结果是相等的（位运算）；这也是一个long数字，只能表达连续的(或者无冲突的)64个数字的状态，即如果把数字1在long中用位表示，那么数字64将无法通过同一个long数字中位表示--冲突；BitSet内部，是一个long[]数组，数组的大小由bitSet接收的最大数字决定，这个数组将数字分段表示[0,63],[64,127],[128,191]...。即long[0]用来存储[0,63]这个范围的数字的“存在性”，long[1]用来存储[64,127]，依次轮推，这样就避免了位运算导致的冲突。

BitSet内部的long[]数组是基于向量的，即随着set的最大数字而动态扩展。数组的最大长度计算：

(maxValue - 1) >> 6 + 1

BitSet中set方法伪代码：

Java代码

public void set(int number) {  
    int index = number >> 6;//找到number需要映射的数组的index。  
    if(index + 1 > length) {  
        ensureCapacity(index + 1);//重新扩展long[]数组  
    }   
    long[index] |= (1L << number);//冲突解决  
}

使用BitSet：

本例中使用bitSet做String字符串的存在性校验。
Java代码

BitSet bitSet = new BitSet(Integer.MAX_VALUE);//hashcode的值域  
//0x7FFFFFFF  
String url = "http://baidu.com/a";  
int hashcode = url.hashCode() & 0x7FFFFFFF;  
bitSet.set(hashcode);  
  
System.out.println(bitSet.cardinality());//着色位的个数  
System.out.println(bitSet.get(hashcode));//检测存在性  
bitSet.clear(hashcode);

BitSet与Hashcode冲突

因为BitSet API只能接收int型的数字，即只能判定int数字是否在bitSet中存在。所以，对于String类型，我们通常使用它的hashcode，但这有一种隐患，java中hashcode存在冲突问题，即不同的String可能得到的hashcode是一样的（即使不重写hashcode方法），如果我们不能很好的解决这个问题，那么就会出现“数据抖动”---不同的hashcode算法、运行环境、bitSet容量，会导致判断的结果有所不同。比如A、B连个字符串，它们的hashcode一样，如果A在BitSet中“着色”(值为true)，那么检测B是否在BitSet存在时，也会得到true。

这个问题该如何解决或者缓解呢？

调整hashcode生成算法：我们可以对一个String使用多个hashcode算法，生成多个hashcode，然后在同一个BitSet进行多次“着色”，在判断存在性时，只有所有的着色位为true时，才判定成功。

String url = "http://baidu.com/a";  
int hashcode1 = url.hashCode() & 0x7FFFFFFF;  
bitSet.set(hashcode1);  
  
int hashcode2 = (url + "-seed-").hashCode() & 0x7FFFFFFF;  
bitSet.set(hashcode2);  
System.out.println(bitSet.get(hashcode1) && bitSet.get(hashcode2));  
//也可以在两个不同的bitSet上进行2次“着色”，这样冲突性更小。但会消耗双倍的内存

其实我们能够看出，这种方式降低了误判的概率。但是如果BitSet中存储了较多的数字，那么互相覆盖着色，最终数据冲突的可能性会逐渐增加，最终仍然有一定概率的判断失误。所以在hashcode算法的个数与实际String的个数之间有一个权衡，我们建议: “hashcode算法个数 * String字符串的个数” < Integer.MAX_VALUE * 0.8

多个BitSet并行保存：

改良1)中的实现方式，我们仍然使用多个hashcode生成算法，但是每个算法生成的值在不同的BitSet中着色，这样可以保持每个BitSet的稀疏度(降低冲突的几率)。在实际结果上，比1)的误判率更低，但是它需要额外的占用更多的内存，毕竟每个BitSet都需要占用内存。这种方式，通常是缩小hashcode的值域，避免内存过度消耗。

BitSet bitSet1 = new BitSet(Integer.MAX_VALUE);//127M  
BitSet bitSet2 = new BitSet(Integer.MAX_VALUE);  
  
String url = "http://baidu.com/a";  
int hashcode1 = url.hashCode() & 0x7FFFFFFF;  
bitSet1.set(hashcode1);  
  
int hashcode2 = (url + "-seed-").hashCode() & 0x7FFFFFFF;  
bitSet2.set(hashcode2);  
  
System.out.println(bitSet1.get(hashcode1) && bitSet2.get(hashcode2));

是否有必要完全避免误判？

如果做到100%的正确判断率，在原理上说BitSet是无法做的，BitSet能够保证“如果判定结果为false，那么数据一定是不存在；但是如果结果为true，可能数据存在，也可能不存在(冲突覆盖)”,即“false == YES，true == Maybe”。有人提出将冲突的数据保存在类似于BTree的额外数据结构中，事实上这种方式增加了设计的复杂度，而且最终仍然没有良好的解决内存占用较大的问题。

BloomFilter(布隆姆过滤器)

BloomFilter 的设计**和BitSet有较大的相似性，目的也一致，它的核心**也是使用多个Hash算法在一个“位图”结构上着色，最终提高“存在性”判断的效率。请参见Guava BloomFilter。如下为代码样例：

Charset charset = Charset.forName("utf-8");  
BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(charset),2<<21);//指定bloomFilter的容量  
String url = "www.baidu.com/a";  
bloomFilter.put(url);  
System.out.println(bloomFilter.mightContain(url));

内存消耗

据上所述，BitSet可以有效的降低内存的使用量，但是它的内存使用量是有内部long数组的大小决定，所以在创建BitSet时指定的值域非常重要，过大的值域将会导致OOM（比如指定Long.MAX_VALUE）,在一个BitMap上存储Integer.MAX_VALUE个“着色”（注意，BitSet只能对正数操作），大概消耗128M内存。
常用位工具操作类
https://github.com/HelloMan/JavaFamily/blob/master/src/main/java/bitset/BitUtils.java

二叉树遍历-速记法

先序遍历

栈S;
p= root;
while(p不空 || S不空){
    while(p不空){
        访问p节点；
        p的右子树入S;
        p = p的左子树;
    }
    p = S栈顶弹出;
}

后序遍历

栈S;
p= root;
while(p不空 || S不空){
    while(p不空){
        访问p节点；
        p的左子树入S;
        p = p的右子树;
    }
    p = S栈顶弹出;
}
结果序列逆序;

中序遍历

栈S;
p= root;
while(p不空 || S不空){
    while(p不空){
        p入S;
        p = p的左子树;
    }
    p = S栈顶弹出;
    访问p;
    p = p的右子树;
}

Java OOM归类

除了程序计数器外，虚拟机内存的其他几个运行时区域都有发生OutOfMemoryError(OOM)异常的可能

内存模型

Error 1- Java heap space

// Java program to illustrate 
// Heap error 
import java.util.*; 

public class Heap { 
    static List<String> list = new ArrayList<String>(); 
    public static void main(String args[]) throws Exception { 
        Integer[] array = new Integer[10000 * 10000]; 
    } 
}

解决方案
- 检查是否存在大对象分配，或者大数组分配
- jmap dump下来在使用mat工具分析看是否有内存泄漏
- 加大-Xmx内存
- 还有一点容易被忽略，检查是否有大量的自定义的 Finalizable 对象，也有可能是框架内部提供的，考虑其存在的必要性
-

Error 2 GC Overhead limit exceeded
这个主要说明了JVM的GC一直在运行，并且程序已经运行很慢。通常98%的时间在做GC，那么这个时候会抛出这个异常

// Java program to illustrate 
// GC Overhead limit exceeded 
import java.util.*; 
  
public class Wrapper { 
public static void main(String args[]) throws Exception 
    { 
        Map m = new HashMap(); 
        m = System.getProperties(); 
        Random r = new Random(); 
        while (true) { 
            m.put(r.nextInt(), "randomValue"); 
        } 
    } 
}

如果你用java -Xmx100m -XX:+UseParallelGC 来运行上面的代码，那么这个错误就会抛出

Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded
at java.lang.Integer.valueOf(Integer.java:832)
at Wrapper.main(error.java:9)

Sun 官方对此的定义：超过98%的时间用来做GC并且回收了不到2%的堆内存时会抛出此异常。

解决方法
1、检查项目中是否有大量的死循环或有使用大内存的代码，优化代码。
2、添加参数 -XX:-UseGCOverheadLimit 禁用这个检查，其实这个参数解决不了内存问题，只是把错误的信息延后，最终出现 java.lang.OutOfMemoryError: Java heap space。
3、dump内存，检查是否存在内存泄露，如果没有，加大内存。

Error 3 - Permgen space is thrown
java内存分为不同的区域，包括permgen area都是在JVM启动的时候指定的，这个通常是说方法区的内存太小导致的。比如加载的class超过了这个区域指定的大小

// Java program to illustrate 
// Permgen Space error 
import javassist.ClassPool; 
  
public class Permgen { 
    static ClassPool classPool = ClassPool.getDefault(); 
  
public static void main(String args[]) throws Exception 
    { 
        for (int i = 0; i < 1000000000; i++) { 
            Class c = classPool.makeClass(com.saket.demo.Permgen" + i).toClass(); 
            System.out.println(c.getName()); 
        } 
    } 
}

可以通过修改以下参数调整

java -XX:MaxPermSize=512m com.saket.demo.Permgen(这个已经在JAVA8 中废弃了)

Error 4 - Metaspace
java 类元数据是分配在native 内存中的，如果这个部分的内存超出，也会抛出OOM。

// Java program to illustrate 
// Metaspace error 
import java.util.*; 
  
public class Metaspace { 
    static javassist.ClassPool cp = javassist.ClassPool.getDefault(); 
  
public static void main(String args[]) throws Exception 
    { 
        for (int i = 0; i < 100000; i++) { 
            Class c = cp.makeClass("com.saket.demo.Metaspace" + i).toClass(); 
        } 
    } 
}

这段代码持续生成新类并且加载到元数据空间中，直到完全用完元数据空间，然后就会抛出java.lang.OutOfMemoryError: Metaspace。

解决方法
因为该OOM原因比较简单，解决方法有如下几种：
1、检查是否永久代空间或者元空间设置的过小（ -XX:MaxMetaspaceSize）
2、检查代码中是否存在大量的反射操作
3、dump之后通过mat检查是否存在大量由于反射生成的代理类
4、放大招，重启JVM

Error 5 – Requested array size exceeds VM limit :
主要表示应用尝试分配一个数组大于堆的大小，就会报出这个错误，举个栗子，比如在512的内存对空间中，尝试分配一个1024M的数组就会抛出这样的错误
Error 6 – Request size bytes for reason. Out of swap space?
java.lang.OutOfMemoryError: Out of swap space 通常是由以下的原因造成的：
- The operating system is configured with insufficient swap space.（操作系统的swap space不足）
- Another process on the system is consuming all memory resources.（别的进程占用所有的内存资源）
Error 7 : reason stack_trace_with_native_method

// Java program to illustrate 
// new native thread error 
import java.util.*; 
  
public class GFG { 
public static void main(String args[]) throws Exception 
    { 
        while (true) { 
            new Thread(new Runnable() 
            { 
                public void run() 
                { 
                    try
                    { 
                        Thread.sleep(1000000000); 
        } 
        catch (InterruptedException e) 
        { 
        } 
    } 
            }).start(); 
   } 
  } 
}

Error 8 Map failed
Caused by: java.lang.OutOfMemoryError: Map failed
这个一般是由于程序使用了FileChannelImpl这个类导致的，里面用到了底层的内存映射文件，当map file个数增长，系统的启动参数上加上关闭手动GC导致的（-XX:+DisableExplicitGC），导致map file个数达到了操作系统的max_map_count后直接OOM了。
Java的FilechannelImpl在使用时，如果发现map第一次出现OOM时，会调用System.gc去回收，但是我们又在启动参数上关闭了系统System.gc的能力。最后导致map失败。
解决方法：
-XX:+DisableExplicitGC这个参数不能随便关闭，原有是有些系统或者框架使用了DirectByteBuffer和FileChannel.map。这些占用的内存达到了最大临界值的时候，需要依赖调用System.gc来强制释放。

如果这个参数关闭了，那么内存释放就无效了,看到在下面第一次出现OutofMemoryError的时候，会调用System.gc(),然后等待100ms后，再次进行map操作，如果还是失败了，那就会抛出Map failed 。

	    try {
           var7 = this.map0(var6, var13, var15);
        } catch (OutOfMemoryError var30) {
            System.gc();

            try {
                Thread.sleep(100L);
            } catch (InterruptedException var29) {
                Thread.currentThread().interrupt();
            }

            try {
                var7 = this.map0(var6, var13, var15);
            } catch (OutOfMemoryError var28) {
                throw new IOException("Map failed", var28);
            }
        }

LeetCode干货收藏

https://leets.android543.com/index.html

二叉树遍历- 颜色标记法

官方题解中介绍了三种方法来完成树的中序遍历，包括：

递归
借助栈的迭代方法
莫里斯遍历

在树的深度优先遍历中（包括前序、中序、后序遍历），递归方法最为直观易懂，但考虑到效率，我们通常不推荐使用递归。

栈迭代方法虽然提高了效率，但其嵌套循环却非常烧脑，不易理解，容易造成“一看就懂，一写就废”的窘况。而且对于不同的遍历顺序（前序、中序、后序），循环结构差异很大，更增加了记忆负担。

因此，我在这里介绍一种“颜色标记法”（瞎起的名字……），兼具栈迭代方法的高效，又像递归方法一样简洁易懂，更重要的是，这种方法对于前序、中序、后序遍历，能够写出完全一致的代码。

核心**如下：

使用颜色标记节点的状态，新节点为白色，已访问的节点为灰色。
如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子节点依次入栈。
如果遇到的节点为灰色，则将节点的值输出。

使用这种方法实现的中序遍历如下：

class Solution {
    class ColorNode {
        TreeNode node;
        String color;
        
        public ColorNode(TreeNode node,String color){
            this.node = node;
            this.color = color;
        }
    }
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null) return new ArrayList<Integer>();
            
        List<Integer> res = new ArrayList<>();
        Stack<ColorNode> stack = new Stack<>();
        stack.push(new ColorNode(root,"white"));
        
        while(!stack.empty()){
            ColorNode cn = stack.pop();
            
            if(cn.color.equals("white")){
                if(cn.node.right != null) {
                  stack.push(new ColorNode(cn.node.right,"white"));
                }
                stack.push(new ColorNode(cn.node,"gray"));
                if(cn.node.left != null){
                    stack.push(new ColorNode(cn.node.left,"white"));
                }
            }else{
                res.add(cn.node.val);
            }
        }
        
        return res;
    }
}