chaojun-zhang / javafamily Goto Github PK
View Code? Open in Web Editor NEW记录学习点滴,分享技术干货
记录学习点滴,分享技术干货
递归遍历
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;
}
}
先序遍历
栈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的右子树;
}
除了程序计数器外,虚拟机内存的其他几个运行时区域都有发生OutOfMemoryError(OOM)异常的可能
// 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 对象,也有可能是框架内部提供的,考虑其存在的必要性
-
// 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内存,检查是否存在内存泄露,如果没有,加大内存。
// 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 中废弃了)
// 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 通常是由以下的原因造成的:
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();
}
}
}
如果这个参数关闭了,那么内存释放就无效了,看到在下面第一次出现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);
}
}
官方题解中介绍了三种方法来完成树的中序遍历,包括:
递归
借助栈的迭代方法
莫里斯遍历
在树的深度优先遍历中(包括前序、中序、后序遍历),递归方法最为直观易懂,但考虑到效率,我们通常不推荐使用递归。
栈迭代方法虽然提高了效率,但其嵌套循环却非常烧脑,不易理解,容易造成“一看就懂,一写就废”的窘况。而且对于不同的遍历顺序(前序、中序、后序),循环结构差异很大,更增加了记忆负担。
因此,我在这里介绍一种“颜色标记法”(瞎起的名字……),兼具栈迭代方法的高效,又像递归方法一样简洁易懂,更重要的是,这种方法对于前序、中序、后序遍历,能够写出完全一致的代码。
核心**如下:
使用颜色标记节点的状态,新节点为白色,已访问的节点为灰色。
如果遇到的节点为白色,则将其标记为灰色,然后将其右子节点、自身、左子节点依次入栈。
如果遇到的节点为灰色,则将节点的值输出。
使用这种方法实现的中序遍历如下:
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;
}
}
Java并发包里面所有的阻塞锁和同步的抽象模板类AbstractQueuedSynchronizer,主要依赖FIFO等待队列来实现,所有底层的重入锁和同步类都是从这个类派生的,所以理解这个类最关键,不过这篇文章主要结合重入锁进行开始分析
AQS内部维护了一个阻塞队列,名字叫CLH(取自三个人的第一个字母),先来看下这个类的几个重要类
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; 等待节点
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;//这个是父类的属性,代表是当前拥有排他的线程
}
由于这个类里面其实是个模板类,所以必须要结合子类,才能读懂里面的代码,先从简单的子类重入锁类开始吧
分析下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;
}
可以看到其逻辑如下
看到这里如果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,我们现在来详细拆分这部分代码。
相应的,可以自己看看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的一些补充:
JAVA中BitSet就是“位图”数据结构,根据“位图”的语义,数据的存在性可以使用bit位上的1或0来表示;一个bit具有2个值:0和1,正好可以用来表示false和true, 对于数据的判重,通常使用HashMap来存储,不过hashmap需要消耗较多的内存,在大数据场景中不太适合;
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
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做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 API只能接收int型的数字,即只能判定int数字是否在bitSet中存在。所以,对于String类型,我们通常使用它的hashcode,但这有一种隐患,java中hashcode存在冲突问题,即不同的String可能得到的hashcode是一样的(即使不重写hashcode方法),如果我们不能很好的解决这个问题,那么就会出现“数据抖动”---不同的hashcode算法、运行环境、bitSet容量,会导致判断的结果有所不同。比如A、B连个字符串,它们的hashcode一样,如果A在BitSet中“着色”(值为true),那么检测B是否在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
改良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 的设计**和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
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.