打印杨辉三角

构造杨辉三角逻辑并不难,主要打印格式的对齐比较困难.

public class Main {

	/**
	 * 计算行应该占得宽度
	 * 每个数字额外加了一个空格,数字的宽度加空格的宽度
	 * @param lastIntegers
	 * @return
	 */
	static int width_of(int[] lastIntegers) {
		int width = 0;
		int length = 0;
		for (int lastInteger : lastIntegers) {
			if (lastInteger > 0) {
				width += numWidth(lastInteger);
				length++;
			}
		}
		width += length;
		return width;
	}

	static int numWidth(int num) {
		int count = 0;
		while (num > 0) {
			num = num / 10;
			count++;
		}
		return count;
	}

	public static void main(String[] args) {
		int n = 10;
		int[][] result = new int[n][n];
		result[0][0] = 1;
		result[1][0] = 1;
		result[1][1] = 1;
		//构造杨辉三角
		for (int i = 2; i < n; i++) {
			result[i][0] = 1;
			result[i][i] = 1;
			for (int j = 1; j <= i - 1; j++) {
				result[i][j] = result[i - 1][j - 1] + result[i - 1][j];
			}
		}
		int maxWidth = width_of(result[n - 1]);
		for (int i = 0; i < n; i++) {
			int[] temp = result[i];
			int temp_width = width_of(temp);
			int wihteBlankLength = (maxWidth - temp_width) / 2;
			for (int k = 0; k < wihteBlankLength; k++) {
				System.out.print(" ");
			}
			for (int j = 0; j < temp.length; j++) {
				if (temp[j] > 0)
					System.out.print(String.format("%d", temp[j]) + " ");
			}
			System.out.println();
		}
	}

}

JAVA 引用学习

JDK1.2 之前,Java 中引用的定义很传统:如果 reference 类型的数据存储的数值代表的是另一块内存的起始地址,就称这块内存代表一个引用。

JDK1.2 以后,Java 对引用的概念进行了扩充,将引用分为强引用、软引用、弱引用、虚引用四种(引用强度逐渐减弱)

1.强引用

以前我们使用的大部分引用实际上都是强引用,这是使用最普遍的引用。如果一个对象具有强引用,那就类似于必不可少的生活用品,垃圾回收器绝不会回收它。当内存空间不足,Java 虚拟机宁愿抛出 OutOfMemoryError 错误,使程序异常终止,也不会靠随意回收具有强引用的对象来解决内存不足问题。

2.软引用(SoftReference)

如果一个对象只具有软引用,那就类似于可有可无的生活用品。如果内存空间足够,垃圾回收器就不会回收它,如果内存空间不足了,就会回收这些对象的内存。只要垃圾回收器没有回收它,该对象就可以被程序使用。软引用可用来实现内存敏感的高速缓存。

软引用可以和一个引用队列(ReferenceQueue)联合使用,如果软引用所引用的对象被垃圾回收,JAVA 虚拟机就会把这个软引用加入到与之关联的引用队列中。

3.弱引用(WeakReference)

如果一个对象只具有弱引用,那就类似于可有可无的生活用品。弱引用与软引用的区别在于:只具有弱引用的对象拥有更短暂的生命周期。在垃圾回收器线程扫描它所管辖的内存区域的过程中,一旦发现了只具有弱引用的对象,不管当前内存空间足够与否,都会回收它的内存。不过,由于垃圾回收器是一个优先级很低的线程, 因此不一定会很快发现那些只具有弱引用的对象。

弱引用可以和一个引用队列(ReferenceQueue)联合使用,如果弱引用所引用的对象被垃圾回收,Java 虚拟机就会把这个弱引用加入到与之关联的引用队列中。

4.虚引用(PhantomReference)

“虚引用”顾名思义,就是形同虚设,与其他几种引用都不同,虚引用并不会决定对象的生命周期。如果一个对象仅持有虚引用,那么它就和没有任何引用一样,在任何时候都可能被垃圾回收。

虚引用主要用来跟踪对象被垃圾回收的活动。

虚引用与软引用和弱引用的一个区别在于: 虚引用必须和引用队列(ReferenceQueue)联合使用。当垃圾回收器准备回收一个对象时,如果发现它还有虚引用,就会在回收对象的内存之前,把这个虚引用加入到与之关联的引用队列中。程序可以通过判断引用队列中是否已经加入了虚引用,来了解被引用的对象是否将要被垃圾回收。程序如果发现某个虚引用已经被加入到引用队列,那么就可以在所引用的对象的内存被回收之前采取必要的行动。

特别注意,在程序设计中一般很少使用弱引用与虚引用,使用软引用的情况较多,这是因为软引用可以加速 JVM 对垃圾内存的回收速度,可以维护系统的运行安全,防止内存溢出(OutOfMemory)等问题的产生。

继续阅读“JAVA 引用学习”

斐波那契数列


import java.util.HashMap;
import java.util.Map;

public class Fibonacci {

	// F(0)=0, F(1)=1, n>1时,F(n)=F(n-1)+F(n-2)。
	public static int fibonacci(int n) {
		if (n == 0 || n == 1) {
			return n;
		}
		return fibonacci(n - 1) + fibonacci(n - 2);
	}

	/**
	 * 缓存执行结果
	 */
	static Map<Integer, Integer> cacheList = new HashMap<>();
	static {
		cacheList.put(0, 0);
		cacheList.put(1, 1);
	}

	public static int fibonacciUseCache(int n) {
		int r = cacheList.containsKey(n) ? cacheList.get(n) : 0;
		if (r == 0) {
			r = fibonacci(n - 1) + fibonacci(n - 2);
		}
		cacheList.put(n, r);
		return r;
	}

	/**
	 * 动态规划:从底部开始解决问题,将所有小问题解决掉,然后合并成一个整体解决方案,从而解决掉整个大问题;
	 * 递归:从顶部开始将问题分解,通过解决掉所有分解的小问题来解决整个问题;
	 * 
	 * @param n
	 * @return
	 */
	public static int fibonacciDynamic(int n) {
		int current = 0;
		int next = 1;
		int temp;
		for (int i = 0; i < n; i++) {
			temp = current;
			current = next;
			next += temp;
		}
		return current;
	}

	public static int fibonacciDynamic2(int n) {
		int a = 1; // n-1
		int b = 0; // n-2
		for (int i = 0; i < n; i++) {
			if (i > 1) {
				int newA = a + b;
				int newB = a;
				b = newB;
				a = newA;
			}
		}
		return a + b;
	}

	/**
	 * 尾调用优化
	 * @param n
	 * @param curr
	 * @param next
	 * @return
	 */
	public static int fibonacciWithNext(int n, int curr, int next) {
		if (n == 0) {
			return 0;
		}
		if(n==1){
			return next;
		}
		return fibonacciWithNext(n - 1, next, curr + next);
	}

	public static void main(String[] args) {
		System.out.println(fibonacciUseCache(15));
		System.out.println(fibonacciDynamic(15));
		System.out.println(fibonacciDynamic2(15));
		System.out.println(fibonacciWithNext(15, 0, 1));
	}

}


ThreadLocal可能引起的内存泄露

threadlocal里面使用了一个存在弱引用的map,当释放掉threadlocal的强引用以后,map里面的value却没有被回收.而这块value永远不会被访问到了. 所以存在着内存泄露.
** 最好的做法是将调用threadlocal的remove方法.**: 把当前ThreadLocal从当前线程的ThreadLocalMap中移除。(包括key,value)

/**
 * Remove the entry for key.
 */
private void remove(ThreadLocal<?> key) {
    Entry[] tab = table;
    int len = tab.length;
    int i = key.threadLocalHashCode & (len-1);
    for (Entry e = tab[i];
         e != null;
         e = tab[i = nextIndex(i, len)]) {
        if (e.get() == key) {
            e.clear();// 将entry的对threadlocal的引用赋值为null
            expungeStaleEntry(i);//将 entry的value赋值为null
            return;
        }
    }
}

在threadlocal的生命周期中,都存在这些引用. 看下图: 实线代表强引用,虚线代表弱引用

继续阅读“ThreadLocal可能引起的内存泄露”

StampedLock 学习

StampedLock是并发包里面jdk8版本新增的一个锁,
该锁提供了三种模式的读写控制,三种模式分别如下:

      写锁writeLock,是个排它锁或者叫独占锁,同时只有一个线程可以获取该锁,当一个线程获取该锁后,其它请求的线程必须等待,当目前没有线程持有读锁或者写锁的时候才可以获取到该锁,请求该锁成功后会返回一个stamp票据变量用来表示该锁的版本,当释放该锁时候需要unlockWrite并传递参数stamp。
      悲观读锁readLock,是个共享锁,在没有线程获取独占写锁的情况下,同时多个线程可以获取该锁,如果已经有线程持有写锁,其他线程请求获取该读锁会被阻塞。这里讲的悲观其实是参考数据库中的乐观悲观锁的,这里说的悲观是说在具体操作数据前悲观的认为其他线程可能要对自己操作的数据进行修改,所以需要先对数据加锁,这是在读少写多的情况下的一种考虑,请求该锁成功后会返回一个stamp票据变量用来表示该锁的版本,当释放该锁时候需要unlockRead并传递参数stamp。
      乐观读锁tryOptimisticRead,是相对于悲观锁来说的,在操作数据前并没有通过CAS设置锁的状态,如果当前没有线程持有写锁,则简单的返回一个非0的stamp版本信息,获取该stamp后在具体操作数据前还需要调用validate验证下该stamp是否已经不可用,也就是看当调用tryOptimisticRead返回stamp后到到当前时间间是否有其他线程持有了写锁,如果是那么validate会返回0,否者就可以使用该stamp版本的锁对数据进行操作。由于tryOptimisticRead并没有使用CAS设置锁状态所以不需要显示的释放该锁。该锁的一个特点是适用于读多写少的场景,因为获取读锁只是使用与或操作进行检验,不涉及CAS操作,所以效率会高很多,但是同时由于没有使用真正的锁,在保证数据一致性上需要拷贝一份要操作的变量到方法栈,并且在操作数据时候可能其他写线程已经修改了数据,而我们操作的是方法栈里面的数据,也就是一个快照,所以最多返回的不是最新的数据,但是一致性还是得到保障的。

一个小的案例:
继续阅读“StampedLock 学习”

HTTPS数字证书与验证

数字证书作用
我们知道HTTPS比HTTP安全,它的安全在于通信过程被加密。然而加密算法是用对称加密,也就是说,客户端和服务端采用一个相同的密钥。为了让双方得到这个密钥,前期就有一个很重要的工作:协商密钥。
现在我们简单模拟一下通信过程:

客户端:hi,我准备跟你(xx.com)建立HTTPS通信。
服务端:好的,我就是xx.com,这是我的证书,你验证一下。
客户端:验证通过了,你的确是xx.com,我把密钥发给你,下面的通信咱们就加密了。
服务端:s&&(*3u247(
客户端:(&DY&#%%&#
上述只是简化后的过程, 我们可以看到协商密钥中有一个很重要的步骤:服务端要证明自己是xx.com。如何证明?证书+链式验证!
继续阅读“HTTPS数字证书与验证”

关于ThreadLocal的一些反思

ThreadLocal 是一个用于提供线程局部变量的工具类,它主要用于将私有线程和该线程存放的副本对象做一个映射,各个线程之间的变量互不干扰,在高并发场景下,可以实现无状态的调用,特别适用于各个线程依赖不通的变量值完成操作的场景。例如Spring 中的单例Bean在多线程调用的时候,并行计算的时候各个线程缓存自己的中间计算结果等场景。

ThreadLocal 是解决线程安全问题一个很好的思路,它通过为每一个线程提供一个独立的变量副本,从而隔离了多个线程对数据的访问冲突。在很多情况下,ThreadLocal 比直接使用 synchronized 同步机制解决线程安全问题更简单,更方便,且结果程序拥有更高的并发性。

class PrintRunnable extends Runnable {
  val number = new ThreadLocal[Double]

  override def run(): Unit = {
    number.set(Math.random())
    println(number.get())
  }
}

object SimpleApp {
  def main(args: Array[String]): Unit = {
    val printRunnable = new PrintRunnable

    val thread1 = new Thread(printRunnable)
    val thread2 = new Thread(printRunnable)

    thread1.start()
    thread2.start()

    thread1.join()
    thread2.join()
  }
}
0.5157676349493098
0.37557496403907353

但是在父子线程要传递一些变量的时候会发现数据不能共享,需要 InheritableThreadLocal 来实现父子线程变量的传递。

class PrintRunnable extends Runnable {
  val number = new ThreadLocal[Double]

  override def run(): Unit = {
    number.set(Math.random())
    println(number.get())
    
    val childThread = new Thread(new Runnable {
      override def run(): Unit = {
        println(number.get())
      }
    })
    childThread.start()
    childThread.join()
  }
}

object SimpleApp {
  def main(args: Array[String]): Unit = {
    val printRunnable = new PrintRunnable

    val thread1 = new Thread(printRunnable)
    val thread2 = new Thread(printRunnable)

    thread1.start()
    thread2.start()

    thread1.join()
    thread2.join()
  }
}
0.5475226099407153
0.8376546404552231
null
null

正确的做法:

class PrintRunnable extends Runnable {
  val number = new InheritableThreadLocal[Double]

  override def run(): Unit = {
    number.set(Math.random())
    println(number.get())

    val childThread = new Thread(new Runnable {
      override def run(): Unit = {
        println(number.get())
      }
    })
    childThread.start()
    childThread.join()
  }
}

object SimpleApp {
  def main(args: Array[String]): Unit = {
    val printRunnable = new PrintRunnable

    val thread1 = new Thread(printRunnable)
    val thread2 = new Thread(printRunnable)

    thread1.start()
    thread2.start()

    thread1.join()
    thread2.join()
  }
}
0.006425375134899158
0.021932306310074368
0.006425375134899158
0.021932306310074368

在子线程中不能修改父线程的变量:

class PrintRunnable extends Runnable {
  val number = new InheritableThreadLocal[Double]

  override def run(): Unit = {
    number.set(Math.random())
    println(number.get())

    val childThread = new Thread(new Runnable {
      override def run(): Unit = {
        println(number.get())
        number.set(0.1)
      }
    })
    childThread.start()
    childThread.join()
    println(number.get())
  }
}

object SimpleApp {
  def main(args: Array[String]): Unit = {
    val printRunnable = new PrintRunnable
    val thread1 = new Thread(printRunnable)
    thread1.start()
    thread1.join()
  }
}
0.7413853012849937
0.7413853012849937
0.7413853012849937

但是现实开发中我们更多的是使用线程池管理线程,线程复用怎么解决ThreadLocal变量的传递或者跨线程池传递。如下面场景:分布式跟踪系统,日志收集记录系统上下文,Session级Cache,应用容器或上层框架跨应用代码给下层SDK传递信息。
可以看一下这个开源项目transmittable-thread-local

关于缓存的反思

目前缓存的解决方案一般有两种:

内存缓存(如 Ehcache) —— 速度快,进程内可用

集中式缓存(如 Redis)—— 可同时为多节点提供服务

使用内存缓存时,一旦应用重启后,由于缓存数据丢失,缓存雪崩,给数据库造成巨大压力,导致应用堵塞

使用内存缓存时,多个应用节点无法共享缓存数据

使用集中式缓存,由于大量的数据通过缓存获取,导致缓存服务的数据吞吐量太大,带宽跑满。现象就是 Redis 服务负载不高,但是由于机器网卡带宽跑满,导致数据读取非常慢

在遭遇问题1、2 时,很多人自然而然会想到使用 Redis 来缓存数据,因此就难以避免的导致了问题3的发生。

当发生问题 3 时,又有很多人想到 Redis 的集群,通过集群来降低缓存服务的压力,特别是带宽压力。

但其实,这个时候的 Redis 上的数据量并不一定大,仅仅是数据的吞吐量大而已。

个人觉得: 可以使用2级缓存,优先使用本地,再使用redis或者memcache的缓存,本地防止OOM可以做一些淘汰机制,刷新到redis或者memcahe中,当然这种情况就需要一些精巧的机制保证2级缓存的一致性。

节点间数据同步的方案 —— Redis Pub/Sub 和 JGroups 。当某个节点的缓存数据需要更新时,会通过 Redis 的消息订阅机制或者是 JGroups 的组播来通知集群内其他节点。当其他节点收到缓存数据更新的通知时,它会清掉自己内存里的数据,然后重新从 Redis 中读取最新数据。

为什么不用 Ehcache 的集群方案?

对 Ehcache 比较熟悉的人还会问的就是这个问题,Ehcache 本身是提供集群模式的,可以在多个节点同步缓存数据。但是 Ehcache 的做法是将整个缓存数据在节点间进行传输。如咱们前面的说的,一个页面需要读取 50K 的缓存数据,当这 50K 的缓存数据有更新时,那么需要在几个节点间传递整个 50K 的数据。这也会造成应用节点间大量的数据传输,这个情况完全不可控。

补充:当然这个单个数据传输量本身没有差别,但是 ehcache 利用 jgroups 来同步数据的做法,在实际测试过程中发现可靠性还是略低,而且 jgroups 的同步数据在云主机上无法使用。

订阅和通知模式传输的仅仅是缓存的 key 而已,因此相比 Ehcache 的集群模式,使用通知机制要传输的数据极其小,对节点间的数据通信完全不会产生大的影响。

Zookeeper 单一视图

Zookeeper 集群由多个节点构成,写入数据时只要多数节点确认就算成功,那些没有确认的节点此时存放的就是老数据。Zookeeper 的“单一视图(single system image)”保证说的是客户端如果读到了新数据,则再也不会读到老数据。如果重新连接连上了老的节点,怎么能保证不会读到老的数据?

真相很直接很残酷:老的节点会拒绝新客户端的连接。

zxid

Zookeeper 会为每个消息打上递增的 zxid(zookeeper transactioin id),客户端会维护一个 lastZxid,存放最后一次读取数据对应的 zxid,当客户端连接时,节点会判断 lastZxid 是不是比自己的 zxid 更大,如果是,说明节点的数据比客户端老,拒绝连接。

参考文章
https://www.cnblogs.com/ucarinc/p/8068409.html