`JVM`内存区域（二）

1. 对象的创建

1.1

Java是一种面向对象的语言，在使用java的日常，我们常常和对象打交道。在JVM内存区域中也存在专门的堆内存来存储管理对象。因此就堆内存和对象之间的关系，做简单的阐述。

虚拟机遇到一条new指令后，虚拟机就会新建一个对象，整个过程虚拟机大致会做如下工作：

检查对象对应的类是否被加载、解析和初始化过
为对象在堆内存上分配内存
初始化新分配的内存为零值
虚拟机对对象进行必要的设置（信息存放对象头）

在上面的工作都完成之后，从虚拟机的角度来看，一个新的对象已经产生了。但从java程序角度来看，对象创建才刚刚开始——<init>方法还没执行，所有的字段都还为零。执行完new指令后接着执行init方法，把对象按照程序员的意图进行初始化，这样一个真正可用对象才算完全产生出来。

1.2

虚拟机遇到一条new指令后，首先会去检查该对象对应的类是否被加载、解析和初始化过（通常称为类加载过程），如果类没有加载进来，则首先进行类加载。类加载也是一个重要的过程，后面的博客会详细介绍。

在类加载通过虚拟机的检查后，虚拟机会首先在堆内存中为新生对象分配空间。值得注意的是，对象所需要的内存空间大小在类加载后是可以完全确定的（如何确定的本文第2节会介绍）。

在为对象分配堆上内存空间的时候，存在两个主要的问题：

a. 内存块连续性的问题
b. 多线程同步的问题

a. 线程运行过程中，需要经常向堆内存申请内存分配，但是通常来讲申请的内存需要是连续的（例如新建数组）。内存中有空闲区和占用区。根据空闲区和占用区的位置之间的不同，可以分为两种内存分配方式：

指针碰撞 bump the pointer: 堆内存是规整的，一边是占用区，另一边是空闲区；中间采用指针指示，需要申请新的内存时候，只需要将指示器指针移动一定的距离即可
空闲列表：如果堆内存不是规整的，即占用区和空闲去交错分布；因此通操作系统的存储管理一样，虚拟机需要维护一个空闲去列表记录哪些空闲区可用；在申请内存分配的时候，从空闲区寻找到一个大小合适的区域分配出去。

采用何种方式进行内存分配取决于堆内存的规整性；而堆内存的规整性取决于虚拟机采用的垃圾回收算法是否带有压缩整理功能决定的。因此在使用Serial，ParNew等带Compact过程的垃圾回收器，虚拟机内存分配采用bump the pointer;而在使用CMS这种基于Mark-Sweep算法的垃圾回收器时，通常采用空闲列表这种方式。

b. 除了以何种方式从堆内存空间分配空间以外，还存在另一个线程安全的问题；当多个线程申请内存分配的时候，可能虚拟机正在使用内存指针给线程A分配内存的时候，线程B用采用原来的内存指针来进行内存分配了。这是典型的多线程问题，解决方法有两种：

对分配内存空间进行同步处理，保证分配操作是线程安全的、原子性的；实际上虚拟机采用的是WCAS（Compare and Set）配上失败重试的方法保证指针更新操作的原子性；
线程封闭的方式；把内存分配的动作按照线程划分在不同的空间中进行，即每个线程在堆中预先分配一小块内存称为本地线程分配缓冲（Thread Local Allocation Buffer TLAB）。哪个线程需要分配内存，就在对应的TLAB上分配，只有TLAB用完并分配新的TLAB的时候，才需要同步锁定。同步需要额外的花销。

1.3

以下代码片段来自于http://hg.openjdk.java.net/jdk7/jdk7/hotspot/archive/9b0ca45cd756.zip/src/上下载openjdk7的源代码中的bytecodeInterpreter.cpp文件。


CASE(_new): {//遇到new指令
      u2 index = Bytes::get_Java_u2(pc+1);//根据下一个pc找到一个index，其实就是new SomeClass()中的SomeClass
      constantPoolOop constants = istate->method()->constants();//获取方法区的常量池
      if (!constants->tag_at(index).is_unresolved_klass()) {//如果需要新建对象的类被解析过
        // Make sure klass is initialized and doesn't have a finalizer
        oop entry = constants->slot_at(index).get_oop();//根据index在常量池中找到对应oop(ordinary object pointer),oop指向加载解析过的类对象的指针
        assert(entry->is_klass(), "Should be resolved klass");
        klassOop k_entry = (klassOop) entry;
        assert(k_entry->klass_part()->oop_is_instance(), "Should be instanceKlass");
        instanceKlass* ik = (instanceKlass*) k_entry->klass_part();
        if ( ik->is_initialized() && ik->can_be_fastpath_allocated() ) {
          size_t obj_size = ik->size_helper();//确定对象的大小的；第2节会介绍；
          oop result = NULL;
          // If the TLAB isn't pre-zeroed then we'll have to do it
          bool need_zero = !ZeroTLAB;//是否需要将内存区域0值化
          if (UseTLAB) {//判断是否是TLAB的方式
            result = (oop) THREAD->tlab().allocate(obj_size);
          }
          
          //以下是内存分配多线程同步的CAS加失败重试的方案
          if (result == NULL) {//result为NULl，表示不是采用TLAB解决内存分配多线程的问题
            need_zero = true;
            // Try allocate in shared eden
            //直接在堆内存中的eden代中分配
      retry:
            HeapWord* compare_to = *Universe::heap()->top_addr();
            HeapWord* new_top = compare_to + obj_size;
            if (new_top <= *Universe::heap()->end_addr()) {
              //Atomic::cmpxchg_ptr是一个采用CAS的原子操作，用于将compare_to指针更新；
              if (Atomic::cmpxchg_ptr(new_top, Universe::heap()->top_addr(), compare_to) != compare_to) {
                goto retry;
              }
              result = (oop) compare_to;//内存分配成功
            }
          }
          if (result != NULL) {
            // Initialize object (if nonzero size and need) and then the header
            if (need_zero ) {
              HeapWord* to_zero = (HeapWord*) result + sizeof(oopDesc) / oopSize;
              obj_size -= sizeof(oopDesc) / oopSize;
              if (obj_size > 0 ) {
                memset(to_zero, 0, obj_size * HeapWordSize);//内存初始化为零
              }
            }
            //以下在设置对象头
            if (UseBiasedLocking) {//根据是否启用偏向锁来设置Mark Word
              result->set_mark(ik->prototype_header());
            } else {
              result->set_mark(markOopDesc::prototype());
            }
            result->set_klass_gap(0);
            result->set_klass(k_entry);//设置类信息
            SET_STACK_OBJECT(result, 0);//将result指针如虚拟机栈中，保存在局部变量表中；
            UPDATE_PC_AND_TOS_AND_CONTINUE(3, 1);//更新程序计数器，继续下一个操作；
          }
        }
      }
  	//如果类没有被解析；则会进行一系列复杂的类加载、内存分配等操作；这是一种较慢的情况；
      // Slow case allocation
      CALL_VM(InterpreterRuntime::_new(THREAD, METHOD->constants(), index),
              handle_exception);
      SET_STACK_OBJECT(THREAD->vm_result(), 0);
      THREAD->set_vm_result(NULL);
      UPDATE_PC_AND_TOS_AND_CONTINUE(3, 1);
    }

2. 对象的内存布局

在HotSpot虚拟机中，对象在内存中存储的布局可以分为3个区域，对象头（Header）、实例数据(Instance Data)和对齐填充(Padding)。

对象头包含两种信息：

第一部分用于存储对象本身的运行时数据。如哈希码、GC分代年龄、锁状态标志、线程持有的锁、偏向线程ID、偏向时间戳等；这部分数据的长度在32bit(32位虚拟机)或者64bit(64位虚拟机)，被称为”Mark Word”。根据对象所处的状态不同，Mark Word存储的内容也不同；
第二部分是类型指针，即对象指向它的类元数据的指针，虚拟机可以通过这个来确定对象是那个类的实例。（并不是所有的虚拟机实现都必须在对象数据上保留类型指针，也就是查找对象的类元数据并非一定要经过对象本身，第3节介绍的基于句柄方式的对象定位，就不要通过对象而可以找到对应的类元数据）

另外如果对象是一个Java数组的话，还需要在对象头必须有一块用于记录数组长度的数据，因为虚拟机需要通过对象的元数据信息确定对象的大小，而从类元数据中却无法确定数组的大小。

实例数据存放了对象真正意义上的有效信息，也就是程序中定义的各类型的字段内容。无论是从父类继承下来的，还是在子类中定义的，都需要记录下来。

对齐填充并不是必然存在的，由于HotSpot的自动内存管理系统要求对象的起始地址必须是8字节的整数倍，也就是说对象的大小必须是8字节的整数倍，因此当对象实例数据部分没有对齐的时候，就需要对其填充来补全。

3. 对象的访问定位

在java语言规范中，java需要通过虚拟机栈上的reference数据来操作堆上的具体对象。在虚拟机规范中，由于reference类型只是一个指向对象的引用，并没有定义如何通过这种引用去定位、方位堆上的对象的具体位置。目前主流的访问方式有使用句柄和直接指针两种

句柄方式；堆上会划分一块内存作为句柄池，引用存储的是对象在句柄池中的句柄地址，而句柄中包含了对象和其对应的类型数据各具体信息的地址信息；
直接地址；引用存储的直接就是对象的堆内存地址，而采用这种方式的话，对象中必须要设置如何访问对应的类型数据的相关信息；

各自的优缺点如下：

句柄方式

优点：句柄方式在对象被移动时（GC时移动对象是非常普遍的）只改变句柄中的实例数据指针，而引用本身不用改变
缺点：中间加了一层，访问变慢；

直接指针：

优点：访问速度快
缺点：对象频繁移动，对引用的修改

参考：《深入理解Java虚拟机》

`JVM`内存区域（一）

1. 运行时内存区域分类

JVM运行时内存区域主要包含：

程序计数器
栈
堆
方法区
其中属于线程私有的是程序计数器、栈；属于共享的是堆，方法区。

2. 运行时内存区域含义

程序计数器

程序计数器是一块较小的内存空间，他可以当做当前线程执行的字节码的行号指示器。
栈
- java虚拟机栈
  
  和大多数程序语言一样，每个java方法在jvm解释执行时都会创建一个栈帧存储局部变量、操作数栈、动态链接、方法出口信息。
  每一个方法的调用到执行返回，都对应一个栈帧在虚拟机栈中入栈和出栈的过程。
  局部变量表存放了编译时期确定的各种基本数据类型（boolean、byte、char、short、int、float、long、double）、对象引用类型（reference类型）。其中long和double会占据两个局部变量槽（slot）,其余的占据一个slot
- 本地方法栈
  
  本地方法调用形成的栈，类似于java虚拟机栈；
堆

所有的对象实例以及数组都要在堆上分配。
方法区

和堆内存一样，是各个线程共享的内存区域，用于存储已经被虚拟机加载的类信息，常量，静态变量，即时编译器编译后的代码等数据。
- 运行时常量池（runtime constant pool）
  
  运行时常量池是方法区的一部分。Class文件里面除了包含类版本、字段、方法、接口等描述信息外，还有一项就是常量表（符号表 constant pool table），用于存放编译时期（源码到字节码）产生的各种字面量和符号引用，例如 public int a = 2中的a，这部分内容在类加载后会进入方法区的运行时常量池。
  运行时常量池相对于class文件的常量表的区别：
  - 常量表必须符合class文件严格的规范才会被虚拟机加载；而运行时常量池则是由不同的虚拟机厂商自由发挥实现的；
  - 运行时常量池具有动态性，常量并非只有在编译时期产生，也就是并非置入class文件中常量表的内容才能进入方法区中的运行时常量池，运行期间也可能有新的常量进入池中，这种特性就是常用的string.inter()方法。
直接内存（Direct Memory）

直接内存不是虚拟机运行时数据的一部分，java语言提供一些接口能够使用native函数直接分配堆外内存（通常意义下虚拟机管理的内存以外的内存），参见NIO。

Union-Find算法

发表于 2017-09-30 更新于 2025-09-24 分类于数据结构与算法

1.简介

Union-Find算法又称并查集算法，是一种作用于并查集数据结构的算法。包含两个主要的操作：

Find 用于查找某个元素属于哪个集合，可以用来确定两个元素是否在同一个集合中；
Union 用于合并两个不同的集合；

2.原理

并查集数据结构是一种树形结构，树形结构对于有规律的数据组织方式，进行修改和查找十分高效。
具体结构如下图一所示：

图一

图二

图一展示了并查集的树形结构，每一棵独立的树都代表一个独立的集合，在同一棵树下的所有节点自然就是属于同一个集合。
图二表示了并查集的存储结构，并查集数据结构采用数据对树进行存储，元素i的值id[i]存储的是其在树形结构上对应的父节点的标号，而根节点元素root的值id[root]是本身的标号，即root = id[root];

有了上述的树形结构和数据的组织形式后，一些基本的操作就变得简单了。

root(x) 返回元素x所在树的根节点，从当前元素x的父节点id[i]不断的向上递推求父节点，直到id[i] == i成立。
connected(x, y)判断x和y元素是否是连通的（直接或间接）,只需要判断两个节点是否有相同的根节点（即是否在同一棵树中）；
count(x) 获取元素x所在集合（树）的元素（节点）的个数,以根节点来分别统计每棵树的节点的数目；
find(x) 返回元素x的根节点
union(x,y) 将元素x和y连通，将x所在的树的拼接到y所在树种，（反之亦可）即将x的根节点父节点设置为y的根节点。

上述的操作基本上覆盖了并查集数据结构以及算法中的大部分操作，由此可以写出一个基本的并查集算法雏形：

class UnionFind {
	
	private int[] id;
	
	public UnionFind(int size) {
		id = new int[size];
		for (int i = 0; i < size; i++) {
			id[i] = i;
		}
	}
	
	public boolean connected(int i, int j) {
		return root(i) == root(j);
	}
	
	private int root(int i) {
		int root;
		while ((root = id[i]) != i)
			i = id[i];	
		return root;
	}
	
	public int find(int i) {
		return root(i);
	}
	
	public void union(int i, int j) {
		int rootI, rootJ;
		if ((rootI = root(i)) == (rootJ = root(j)))
			return;
     id[rootI] = rootJ;//将i节点所在树移接到j节点所在树
	}
	
	@Override
	public String toString() {
		// TODO Auto-generated method stub
		Map<Integer, List<Integer>> group = new HashMap<>();
		for (int i = 0 ; i < this.id.length; i++) {
			int root = root(i);
			if (group.get(root) == null) {
				List<Integer> tmp = new ArrayList<>();
				tmp.add(i);
				group.put(root, tmp);
			} else 
				group.get(root).add(i);
		}
		return group.toString();
	}
}

3.改进

对上述Union-Find的两个主要操作find和union的时间复杂度进行分析易得出

union(i,j) — O(1)
find(i) — O(h) 其中h是节点i所在树的高度

由于在进行对两个节点进行union操作的时候，我们总是不加选择的将节点i所在的树拼接到节点j所在的树下，这样可能会导致某一棵树特别的瘦高，即其h很大，几乎可以接近于n，从而可能导致find操作可能需要遍历整个集合。

图三

由于这个原因，我们需要不断的调整树，使其变得稍微矮胖一些，如图四。

图四

为了将树摊平，存在两个改进的地方：

带权的union操作即在进行union操作的时候，可以先判断节点所在树的大小，将size小的树接到size大的树；
路径压缩即在进行find操作的时候，在找到根节点后，循环将该路径下的所有节点都拼接到根节点下，如图五所示；

图五

图六

改进后union-find


class UnionFind {
	
	private Map<Integer, Integer> memSize;
	private int[] id;
	
	public UnionFind(int size) {
		memSize = new HashMap<>();
		id = new int[size];
		for (int i = 0; i < size; i++) {
			id[i] = i;
			memSize.put(i, 1);
		}
	}
	
	public boolean connected(int i, int j) {
		return root(i) == root(j);
	}
	
	private int root(int i) {
		int root;
		while ((root = id[i]) != i) {
			//优化二：路径压缩，将当前非root节点i 拼接到爷节点下面，将爷节点作为自己的父节点
			//这样为后续查找节点i的root节点压缩路径深度，节约了时间。
			id[i] = id[id[i]];
			i = id[i];	
		}
    
    //或者另一种路径压缩方式
    /* while (id[i] != i) {
      id[i] = root;
      i = id[i];
    } */
    
		return root;
	}
	
	public int find(int i) {
		return root(i);
	}
	
	public void union(int i, int j) {
		int rootI, rootJ;
		if ((rootI = root(i)) == ( rootJ = root(j)))
			return;
		int iSize, jSize;
		//优化一：带权union, 小树接大树，避免新树过高；
		if ((iSize = memSize.get(rootI)) > (jSize = memSize.get(rootJ))) {
			id[rootJ] = rootI;
			memSize.put(rootI, iSize + jSize);
		} else {
			id[rootI] = rootJ;
			memSize.put(rootJ, iSize + jSize);
		}
	}
	
	@Override
	public String toString() {
		// TODO Auto-generated method stub
		Map<Integer, List<Integer>> group = new HashMap<>();
		for (int i = 0 ; i < this.id.length; i++) {
			int root = root(i);
			if (group.get(root) == null) {
				List<Integer> tmp = new ArrayList<>();
				tmp.add(i);
				group.put(root, tmp);
			} else 
				group.get(root).add(i);
		}
		return group.toString();
	}
}

4.应用

Percolation.
Games (Go, Hex).
Dynamic connectivity.
Least common ancestor.
Equivalence of finite state automata.
Hoshen-Kopelman algorithm in physics.
Hinley-Milner polymorphic type inference.
Kruskal’s minimum spanning tree algorithm.
Compiling equivalence statements in Fortran.
Morphological attribute openings and closings.
Matlab’s bwlabel() function in image processing.

5.References

[1] Algorithms - Robert Sedgewick, Kevin Wayne

1. IO复用

进程需要这样一种功能：内核一旦发现进程指定的一个或多个IO条件（事件）就绪（输入准备好被读取或者输出准备好被输出），它通知进程，这个就叫做I/O复用。

IO复用的典型使用场景

客户处理多个描述符号（通常是交互式输入和网络套接字）时候，必须使用I/O复用，例如实际的网络聊天，进程既要等待用户的输入，又要处理来自网络套接字的输入，采用I/O复用可以大幅度提高并发度和节省资源；
TCP服务器既要处理监听套接字，又要处理已经连接的套接字，这时候需要I/O复用以提高并发性能；实际上常见的并发连接的客户数多，但是每个连接的任务轻（CPU时间短）比如多人在线聊天室；连接并发数多，但是每个连接不都是长期处于活跃状态，可能是偶尔I/O一些数据，这时候需要I/O复用，让系统别被这些Lazy的客户端拖垮；
如果一个服务器需要同时处理多个服务或协议，一般使用IO复用；

其实，不难看出I/O复用的目的是为了让计算机的资源得到尽可能最大化的利用，提高并行化程度达到这种目的的一种有效途径。

I/O复用在某种程度上和操作系统的中断处理机制何其的相似。

操作系统作为计算机的核心软件，管理着众多的硬件设备，具有极大的并发性能，我们可以同时听音乐，同时拷文件，同时跑程序等等；如此高的并发能力得益与中断机制给操作系统带来的异步能力，当某个硬件设备特定的事件发生时（比如磁盘就绪），就引发一个硬件中断，操作系统能捕获到这些中断，将当前运行的进程挂起，然后转而执行该中断对应的中断处理程序。

这种机制有点贪心的思想，操作系统总是尽可能的少等待，有活就干，没活就离开；这种机制中，众多硬件设备就类似与IO复用里面的众多Lazy的客户，他们需要与服务器（这里是操作系统）保持连接（做到随叫随到），但是又总是需要操作系统。中断是操作系统运行的动力源泉，这是一个典型的异步模型。I/O复用依赖于内核提供的异步能力，其抽象程度与操作系统和硬件设备的模型相似，这样能充分利用计算机的资源（软件充分利用操作系统，操作系统充分利用硬件）。

2. I/O模型

阻塞IO
非阻塞IO
IO复用
信号驱动IO
异步IO

应用程序典型的I/O包含两个不同的阶段：

以输入为例

IO请求就绪阶段 应用程序向内核发出请求，检查硬件设备是否准备好数据（例如等待数据从网络到达、用户键盘敲击）；若硬件设备就绪，产生中断；
IO实际读写阶段 内核捕获处理中断，然后内核空间将数据拷贝到用户的进程空间中，CPU切换到用户态；

这两个阶段的产生主要是由于计算机目前的体系结构决定的（最顶层用户程序运行在用户态，中间层内核工作在内核态，最底层是硬件）；这两个阶段都有可能产生阻塞，在内核与硬件之间，应付这种阻塞采用了基于事件的中断机制以提高并发性；而在内核与用户进程之间，异步IO机制也将为用户进程并发程度提高带来曙光。

2.1 阻塞IO

最普遍的IO模型都是阻塞模型，这种模型在IO的的第一阶段（向内核发出I/O请求的系统调用）时，被阻塞直到I/O就绪，再执行实际I/O操作；

2.2 非阻塞IO

进程通知内核，进程所发起的IO请求在I/O未就绪的条件下，也不能把进程阻塞（挂起），而是返回一个错误；该模型可能需要进程不断的去轮询某个FD是否IO就绪，这样的轮询模型比较少见，轮询会额外的浪费大量的CPU资源。

2.3 IO复用

该模型本质上属于非阻塞模型I/O，常见的是select和poll机制。对于普通的非阻塞模型，一个进程或者线程始终轮询同一个FD，这样效率较低，特别是对于同时需要处理很多FD的程序；

而IO复用模型，可以让进程或者线程同时管理（轮询）多个FD，以select为例，select能够管理许多FD上的不同事件，select调用在所有FD都没有IO事件(就绪、可读、可写等)产生时会阻塞，虽然select调用会阻塞，但是其管理轮询的FD不是阻塞的，因此该模型依然算是非阻塞IO模型；

该模型通常和阻塞IO模型+多线程作对比，在典型的socket服务器端，该模型和阻塞IO模型+多线程可以实现相同的功能，大多数情况下效果性能也不会差太离谱；

但是考虑在某些特定的场景下，例如客户端连接数目众多，但是每个连接今次进行IO次数比较多，IO的数据比较少（典型的就是多人在线聊天，大量的客户端同服务器保持连接，但是每一个连接“走走停停”，隔一会来几个字节的数据），在阻塞IO模型+多线程模型中，每一个连接对应于一个线程，大量的长连接会很快消耗掉计算机中（也可能是线程池）中所有线程资源，从而拒绝了额外的新的客户连接请求，但是此时计算机的CPU却是闲置的，因为很多线程其实是在阻塞状态，因此这种场景下，该模型没有很好的提高系统的并发性；

而采用I/O复用模型，用一个或多个线程去select或者poll检查多个连接上的IO事件，当IO事件(可读、可写等)发生，就利用新开线程池中的线程来处理IO，由于每一次的IO的任务很轻，并且IO数据已经来到了内核或者进程的缓冲区，这样新开的线程很快就会被线程池回收，这样当新来的客户连接请求进来，系统仍然有足够的线程资源来处理请求，极大的提高了该场景下系统的吞吐量，IO复用模型要远优于阻塞IO模型+多线程；

实际应用中，辨证的选择IO复用模型和阻塞IO模型+多线程。

2.4 信号驱动IO

进程不会阻塞在第一阶段，当IO就绪时，内核会通过信号的形式通知进程；

2.5 异步IO

进程在整个IO过程（IO请求和IO读写阶段）都不会阻塞，而是在IO完成后由内核通知进程；

2.6 同步IO与异步IO

在某些术语中，阻塞和非阻塞用于区分IO的第一个阶段，即IO的请求阶段；
同步和异步用于区分IO的第二个阶段，即IO的读写阶段；

因此，按照这个来重新分类上述五种IO模型，就可以分为

同步IO
- 阻塞IO (最普遍的同步阻塞BIO)
- 非阻塞IO （Java NIO，需要轮询，不停的轮询某个FD是否就绪）
- IO复用 (Java NIO的Select机制，同时监听多个FD，虽然单个FD不阻塞，但是当所有FD都没有就绪时，select调用会阻塞；一个阻塞换来多个不阻塞)
- 信号驱动IO (同同步非阻塞IO，不用轮询，而是直接接收内核发来的IO信号)
异步IO （Java AIO， IO的两个阶段都不会阻塞，进程只需要发起IO请求，在IO完成两个阶段后，由内核负责通知进程，期间进程都不会挂起）

2.7 5种IO模型的Java示例

（1）阻塞IO + 多线程



package iomodel;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.Reader;
import java.net.ServerSocket;
import java.net.Socket;
import java.util.concurrent.Executor;
import java.util.concurrent.Executors;

public class BIODemo {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Executor pools = Executors.newFixedThreadPool(5);
		try {
			ServerSocket sS = new ServerSocket(8888);
			for (;;) {
				Socket s = sS.accept();//blocking
				pools.execute(new BIOWorker(s));
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

}

class BIOWorker implements Runnable {
	Socket client = null;

	public BIOWorker(Socket client) {
		super();
		this.client = client;
	}

	@Override
	public void run() {
		// TODO Auto-generated method stub
		try {
			BufferedReader is = new BufferedReader(new InputStreamReader(client.getInputStream()));
			String line = null;
			while ((line = is.readLine()) != null)//blocking
				System.out.println(line);
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
}

（2）非阻塞IO模型

package iomodel;

import java.io.IOException;
import java.net.InetSocketAddress;
import java.net.ServerSocket;
import java.nio.ByteBuffer;
import java.nio.channels.ServerSocketChannel;
import java.nio.channels.SocketChannel;
import java.nio.charset.Charset;
import java.nio.charset.CharsetDecoder;
public class NBIODemo {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		try {
			Charset ascii = Charset.forName("us-ascii");
			CharsetDecoder decoder = ascii.newDecoder();
			ServerSocketChannel ssc = ServerSocketChannel.open();
			ssc.configureBlocking(false);
			ServerSocket ss = ssc.socket();
			ss.bind(new InetSocketAddress("localhost", 8888));

			SocketChannel sC = null;

			while ((sC = ssc.accept()) == null)
				System.out.println("i am pooling for new connection!");// poll until new connection was established.non-blocking
			sC.configureBlocking(false);

			ByteBuffer buffer = ByteBuffer.allocate(1024);
		
			while (true) {//pool for reading
				int r = sC.read(buffer);//non-blocking
				System.out.println("i am pooling for new data!");
				if (r > 0) {
					buffer.flip();
					System.err.println("recv " + r +" bytes from " + sC);
					System.err.print(decoder.decode(buffer));
					buffer.compact();
				}
			}

		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

}

（3）I/O复用

package iomodel;

import java.io.IOException;
import java.net.InetSocketAddress;
import java.net.ServerSocket;
import java.nio.ByteBuffer;
import java.nio.channels.SelectionKey;
import java.nio.channels.Selector;
import java.nio.channels.ServerSocketChannel;
import java.nio.channels.SocketChannel;
import java.nio.charset.Charset;
import java.nio.charset.CharsetDecoder;
import java.util.Iterator;
import java.util.Set;
import java.util.concurrent.Executor;
import java.util.concurrent.Executors;

public class MultiplexingIODemo {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Executor pool = Executors.newFixedThreadPool(5);
		try {
			Selector selector = Selector.open();
			ServerSocketChannel ssc = ServerSocketChannel.open();
			ssc.configureBlocking(false);// listening socket channel is
											// non-blocking for accept()

			ServerSocket ss = ssc.socket();
			ss.bind(new InetSocketAddress("localhost", 8888));

			ssc.register(selector, SelectionKey.OP_ACCEPT);

			for (;;) {

				// System.out.println("I am selecting..");
				selector.select();// may block until there occurred at least one
									// IO event.

				Set<SelectionKey> selectKeys = selector.selectedKeys();
				Iterator<SelectionKey> iterator = selectKeys.iterator();

				while (iterator.hasNext()) {
					SelectionKey key = iterator.next();
					if ((key.readyOps() & SelectionKey.OP_ACCEPT) == SelectionKey.OP_ACCEPT) {
						ServerSocketChannel ssc1 = (ServerSocketChannel) key.channel();
						SocketChannel sc = ssc1.accept();
						sc.configureBlocking(false);
						sc.register(selector, SelectionKey.OP_READ);
						iterator.remove();
						System.out.println("Got connection from " + sc);
					} else if ((key.readyOps() & SelectionKey.OP_READ) == SelectionKey.OP_READ) {
						SocketChannel sc = (SocketChannel) key.channel();
						if (key.attachment() == null) {
							ByteBuffer buff = ByteBuffer.allocate(1024);
							key.attach(buff);
							System.out.println("first recv data from " + sc);
						}
						pool.execute(new IOWorker(sc, (ByteBuffer) key.attachment()));
						iterator.remove();
					}
				}
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

}

class IOWorker implements Runnable {
	ByteBuffer buffer = null;
	SocketChannel sC = null;
	Charset gb2312 = Charset.forName("gb2312");
	CharsetDecoder decoder = gb2312.newDecoder();

	public IOWorker(SocketChannel sC, ByteBuffer buffer) {
		super();
		this.sC = sC;
		this.buffer = buffer;

	}

	@Override
	public void run() {
		// TODO Auto-generated method stub
		int r;
		try {
			r = this.sC.read(buffer);
			if (r > 0) {
				System.err.println("recv " + r + " new bytes from " + sC);
				buffer.flip();
				// get first byte
				// decode bytes stream
				for (; buffer.hasRemaining();) {
					byte fisrt = buffer.get(0);
					if (Byte.toUnsignedInt(fisrt) <= 127) {// 高字节的大小判断
						fisrt = buffer.get();
						System.err.println("[to " + sC.socket().getPort() + " ] "+ (char) fisrt);
					} else if (buffer.remaining() >= 2) {
						byte[] b = new byte[2];
						b[0] = buffer.get();
						b[1] = buffer.get();
						String s = new String(b, "gbk");
						System.err.println("[to " + sC.socket().getPort() + " ] " + s);
					} else
						break;
				}
				buffer.compact();
			}

		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

}

（4）异步I/O

package iomodel;

import java.io.File;
import java.io.IOException;
import java.net.InetSocketAddress;
import java.nio.ByteBuffer;
import java.nio.channels.AsynchronousFileChannel;
import java.nio.channels.AsynchronousServerSocketChannel;
import java.nio.channels.AsynchronousSocketChannel;
import java.nio.channels.CompletionHandler;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.nio.file.StandardOpenOption;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.Future;
public class AIODemo {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		try {
			AsynchronousFileChannel aFC = AsynchronousFileChannel.open(Paths.get("a.txt"), StandardOpenOption.READ);
			System.out.println("main " + Thread.currentThread().getId());
			ByteBuffer buffer = ByteBuffer.allocate((int) new File("a.txt").length());
			Future<Integer> result = aFC.read(buffer, 0);	
			while (!result.isDone()) {
				System.out.println("i am doing other useful work...");
			}
			buffer.flip();
			System.out.println(result.get());
		
			System.out.println("read is done");
			
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (ExecutionException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
	}

}

class FileReadHandler implements CompletionHandler<Integer, AsynchronousFileChannel> {
	
	@Override
	public void completed(Integer result, AsynchronousFileChannel attachment) {
		System.out.println("new connection from " + result);
	}

	@Override
	public void failed(Throwable exc, AsynchronousFileChannel attachment) {
		// TODO Auto-generated method stub
		
	}
	
}

3. 总结

几种IO模型的优缺点，模型的阻塞、非阻塞以及同步、异步指的是什么？
select模型与阻塞+多线程模型的区别以及使用场景；

4. References

[1] 史蒂文斯，芬纳，鲁道夫.UNIX网络编程卷一[M].北京:人民邮电出版社,2015:122-148

Java getClass() VS instanceof VS ==

发表于 2017-07-19 更新于 2025-09-24 分类于 Java

含义

getClass() 返回调用对象object的运行时类(runtime class)，一个Class实例。
a instanceof T 返回a是否是T类型的实例或者T类型的子类型的实例
a == b 判断a和b引用的是否是同一个对象

区分

getClass()的文档介绍如下：

Returns the runtime class of this Object.
The returned Class object is the object that is locked by static synchronized methods of the represented class.

The returned Class object is the object that is locked by static synchronized methods of the represented class
这句话的意思是在说明一个事实：

T.class = a.getClass()

返回的Class对象是该对象(Class对象)表示的类中的静态同步方法锁住的那个对象。

java中当同步关键字加在静态方法前面，当某个线程进入该方法时，必须是已经获得了该类对象(T.class)的锁。

下面两个写法效果相同：

1 2	public static synchronized void foo() { }

public static void foo() {
  synchronized(T.class) {
  }
}

另外，java中的同步关键字的加锁粒度一般发生在普通对象和类对象上，封锁范围一般可以是代码块、一个方法、整个类的所有方法等。

instanceof是一个操作符，返回值是false或true。

instanceof不仅可以判断对象是否是某个类T或其子类的实例，还可以判断是否是某个接口I或其子接口I的实现类的实例。

==操作符是判断两个引用对应的对象是否是同一个。

equal()方法是自定义的判断的两个引用对应的对象是否逻辑相等。

堆和堆的应用：堆排序和优先队列

发表于 2017-07-07 更新于 2025-09-24 分类于数据结构与算法

1.堆

堆(Heap)是一种重要的数据结构，是实现优先队列(Priority Queues)

首选的数据结构。由于堆有很多种变体，包括二项式堆、斐波那契堆等，但是这里只考虑最常见的就是二叉堆（以下简称堆）。

堆是一棵满足一定性质的二叉树，具体的讲堆具有如下性质：父节点的键值总是不大于它的孩子节点的键值（小顶堆）, 堆可以分为小顶堆和大顶堆，这里以小顶堆为例，其主要包含的操作有：

insert()
extractMin
peek(findMin)
delete(i)

由于堆是一棵形态规则的二叉树，因此堆的父节点和孩子节点存在如下关系：

设父节点的编号为 i, 则其左孩子节点的编号为2*i+1, 右孩子节点的编号为2*i+2
设孩子节点的编号为i, 则其父节点的编号为(i-1)/2

由于二叉树良好的形态已经包含了父节点和孩子节点的关系信息，因此就可以不使用链表而简单的使用数组来存储堆。

要实现堆的基本操作，涉及到的两个关键的函数

siftUp(i, x) ：将位置i的元素x向上调整，以满足堆得性质，常常是用于insert后，用于调整堆；
siftDown(i, x)：同理，常常是用于delete(i)后，用于调整堆；

具体的操作如下：

private void siftUp(int i) {
	int key = nums[i];
	for (; i > 0;) {
		int p = (i - 1) >>> 1;
		if (nums[p] <= key)
			break;
		nums[i] = nums[p];
		i = p;
	}
	nums[i] = key;
}

private void siftDown(int i) {
		int key = nums[i];
		for (;i < nums.length / 2;) {
			int child = (i << 1) + 1;
			if (child + 1 < nums.length && nums[child] > nums[child+1])
				child++;
			if (key <= nums[child])
				break;
			nums[i] = nums[child];
			i = child;
		}
		nums[i] = key;
  }

可以看到siftUp和siftDown不停的在父节点和子节点之间比较、交换；在不超过logn的时间复杂度就可以完成一次操作。

有了这两个基本的函数，就可以实现上述提及的堆的基本操作。

首先是如何建堆，实现建堆操作有两个思路:

一个是不断地insert（insert后调用的是siftUp）
另一个将原始数组当成一个需要调整的堆，然后自底向上地
在每个位置i调用siftDown(i)，完成后我们就可以得到一个满足堆性质的堆。这里考虑后一种思路：

通常堆的insert操作是将元素插入到堆尾，由于新元素的插入可能违反堆的性质，因此需要调用siftUp操作自底向上调整堆；堆移除堆顶元素操作是将堆顶元素删除，然后将堆最后一个元素放置在堆顶，接着执行siftDown操作，同理替换堆顶元素也是相同的操作。

建堆

// 建立小顶堆
private void buildMinHeap(int[] nums) {
	int size = nums.length;
	for (int j = size / 2 - 1; j >= 0; j--)
		siftDown(nums, j, size);
}

那么建堆操作的时间复杂度是多少呢？答案是O(n)。虽然siftDown的操作时间是logn，但是由于高度在递减的同时，每一层的节点数量也在成倍减少，最后通过数列错位相减可以得到时间复杂度是O(n)。

extractMin
由于堆的固有性质，堆的根便是最小的元素，因此peek操作就是返回根nums[0]元素即可；
若要将nums[0]删除，可以将末尾的元素nums[n-1]覆盖nums[0],然后将堆得size = size-1，调用siftDown(0)调整堆。时间复杂度为logn。

peek
同上

delete(i)

删除堆中位置为i的节点，涉及到两个函数siftUp和siftDown，时间复杂度为logn,具体步骤是，

将元素last覆盖元素i，然后siftDown
检查是否需要siftUp

注意到堆的删除操作，如果是删除堆的根节点，则不用考虑执行siftUp的操作；若删除的是堆的非根节点，则要视情况决定是siftDown还是siftUp操作，两个操作是互斥的。


public int delete(int i) {
	int key = nums[i];
	//将last元素移动过来，先siftDown; 再视情况考虑是否siftUp
	int last = nums[i] = nums[size-1];
	size--;
	siftDown(i);
	//check #i的node的键值是否确实发生改变（是否siftDown操作生效）,若发生改变，则ok,否则为确保堆性质，则需要siftUp 
	if (i < size && nums[i] == last) {
		System.out.println("delete siftUp");
		siftUp(i);
	}	
     return key;
}

case 1 :

删除中间节点i21，将最后一个节点复制过来；

这里写图片描述

由于没有进行siftDown操作，节点i的值仍然为6，因此为确保堆的性质，执行siftUp操作；

这里写图片描述

case 2

删除中间节点i，将值为11的节点复制过来，执行siftDown操作；
这里写图片描述

由于执行siftDown操作后，节点i的值不再是11，因此就不用再执行siftUp操作了，因为堆的性质在siftDown操作生效后已经得到了保持。

这里写图片描述

可以看出，堆的基本操作都依赖于两个核心的函数siftUp和siftDown；较为完整的Heap代码如下：

class Heap {
	private final static int N = 100; //default size
	private int[] nums;
	private int size;
	
	public Heap(int[] nums) {
		this.nums = nums;
		this.size = nums.length;
		heapify(this.nums);
	}
	
	public Heap() {
		this.nums = new int[N];
	}
	
	/**
	 * heapify an array, O(n)
	 * @param nums An array to be heapified. 
	 */
	private void heapify(int[] nums) {
		for (int j = (size - 1) >> 1; j >= 0; j--)
			siftDown(j);
	}
	
	/**
	 * append x to heap
	 * O(logn)
	 * @param x
	 * @return
	 */
	public int insert(int x) {
		if (size >= this.nums.length)
			expandSpace();
		size += 1;
		nums[size-1] = x;
		siftUp(size-1);
		return x;
	}
	
	/**
	 * delete an element located in i position.
	 * O(logn)
	 * @param i
	 * @return
	 */
	public int delete(int i) {
		rangeCheck(i);
		int key = nums[i];
		//将last元素覆盖过来,先siftDown; 再视情况考虑是否siftUp;
		int last = nums[i] = nums[size-1];
		size--;
		siftDown(i);
		//check #i的node的键值是否确实发生改变,若发生改变，则ok,否则为确保堆性质，则需要siftUp; 
		if (i < size && nums[i] == last) 
			siftUp(i);
		return key;
	}
	
	/**
	 * remove the root of heap, return it's value, and adjust heap to maintain the heap's property. 
	 * O(logn)
	 * @return
	 */
	public int extractMin() {
		rangeCheck(0);
		int key = nums[0], last = nums[size-1];
		nums[0] = last;
		size--;
		siftDown(0);
		return key;
	}
	/**
	 * return an element's index, if not exists, return -1;
	 * O(n)
	 * @param x
	 * @return
	 */
	public int search(int x) {
		for (int i = 0; i < size; i++)
			if (nums[i] == x)
				return i;
		return -1;
	}
	/**
	 * return but does not remove the root of heap.
	 * O(1)
	 * @return
	 */
	public int peek() {
		rangeCheck(0);
		return nums[0];
	}
	
	private void siftUp(int i) {
		int key = nums[i];
		for (; i > 0;) {
			int p = (i - 1) >>> 1;
			if (nums[p] <= key)
				break;
			nums[i] = nums[p];
			i = p;
		}
		nums[i] = key;
	}
	
	private void siftDown(int i) {
		int key = nums[i];
		for (;i < size / 2;) {
			int child = (i << 1) + 1;
			if (child + 1 < size && nums[child] > nums[child+1])
				child++;
			if (key <= nums[child])
				break;
			nums[i] = nums[child];
			i = child;
		}
		nums[i] = key;
	}
	
	private void rangeCheck(int i) {
		if (!(0 <= i && i < size))
			throw new RuntimeException("Index is out of boundary");	
	}
	
	private void expandSpace() {
		this.nums = Arrays.copyOf(this.nums, size * 2);
	}
	
	@Override
	public String toString() {
		// TODO Auto-generated method stub
		StringBuilder sb = new StringBuilder();
		sb.append("[");
		for (int i = 0; i < size; i++)
			sb.append(String.format((i != 0 ? ", " : "") + "%d", nums[i]));
		sb.append("]\n");
		return sb.toString();
	}
}

2.堆的应用：堆排序

运用堆的性质，我们可以得到一种常用的、稳定的、高效的排序算法————堆排序。堆排序的时间复杂度为O(n*log(n))，空间复杂度为O(1)，堆排序的思想是：
对于含有n个元素的无序数组nums, 构建一个堆(这里是小顶堆)heap，然后执行extractMin得到最小的元素，这样执行n次得到序列就是排序好的序列。
如果是降序排列则是小顶堆；否则利用大顶堆。

Trick

由于extractMin执行完毕后，最后一个元素last已经被移动到了root，因此可以将extractMin返回的元素放置于最后，这样可以得到sort in place的堆排序算法。

具体操作如下：

int[] n = new int[] {1,9,5,6,8,3,1,2,5,9,86};
Heap h = new Heap(n);
for (int i = 0; i < n.length; i++)
	n[n.length-1-i] = h.extractMin();

当然，如果不使用前面定义的heap，则可以手动写堆排序，由于堆排序设计到建堆和extractMin，两个操作都公共依赖于siftDown函数，因此我们只需要实现siftDown即可。(trick:由于建堆操作可以采用siftUp或者siftDown，而extractMin是需要siftDown操作，因此取公共部分，则采用siftDown建堆)。

这里便于和前面统一，采用小顶堆数组进行降序排列。


public void heapSort(int[] nums) {
		int size = nums.length;
		buildMinHeap(nums);
		while (size != 0) {
			// 交换堆顶和最后一个元素
			int tmp = nums[0];
			nums[0] = nums[size - 1];
			nums[size - 1] = tmp;
			size--;
			siftDown(nums, 0, size);
		}
	}

	// 建立小顶堆
	private void buildMinHeap(int[] nums) {
		int size = nums.length;
		for (int j = size / 2 - 1; j >= 0; j--)
			siftDown(nums, j, size);
	}

	private void siftDown(int[] nums, int i, int newSize) {
		int key = nums[i];
		while (i < newSize >>> 1) {
			int leftChild = (i << 1) + 1;
			int rightChild = leftChild + 1;
			// 最小的孩子，比最小的孩子还小
			int min = (rightChild >= newSize || nums[leftChild] < nums[rightChild]) ? leftChild : rightChild;
			if (key <= nums[min])
				break;
			nums[i] = nums[min];
			i = min;
		}
		nums[i] = key;
	}

3.堆的应用：优先队列

优先队列是一种抽象的数据类型，它和堆的关系类似于，List和数组、链表的关系一样；我们常常使用堆来实现优先队列，因此很多时候堆和优先队列都很相似，它们只是概念上的区分。
优先队列的应用场景十分的广泛：
常见的应用有：

Dijkstra’s algorithm（单源最短路问题中需要在邻接表中找到某一点的最短邻接边，这可以将复杂度降低。）
Huffman coding（贪心算法的一个典型例子，采用优先队列构建最优的前缀编码树(prefixEncodeTree)）
Prim’s algorithm for minimum spanning tree
Best-first search algorithms

这里简单介绍上述应用之一：Huffman coding。

Huffman编码是一种变长的编码方案，对于每一个字符，所对应的二进制位串的长度是不一致的，但是遵守如下原则：

出现频率高的字符的二进制位串的长度小
不存在一个字符c的二进制位串s是除c外任意字符的二进制位串的前缀

遵守这样原则的Huffman编码属于变长编码，可以无损的压缩数据，压缩后通常可以节省20%-90%的空间，具体压缩率依赖于数据的固有结构。

Huffman编码的实现就是要找到满足这两种原则的 字符-二进制位串 对照关系，即找到最优前缀码的编码方案（前缀码：没有任何字符编码后的二进制位串是其他字符编码后位串的前缀）。
这里我们需要用到二叉树来表达最优前缀码，该树称为最优前缀码树
一棵最优前缀码树看起来像这样：

这里写图片描述

算法思想：用一个属性为freqeunce关键字的最小优先队列Q,将当前最小的两个元素x,y合并得到一个新元素z（z.frequence = x.freqeunce + y.frequence）,
然后插入到优先队列中Q中，这样执行n-1次合并后，得到一棵最优前缀码树（这里不讨论算法的证明）。

一个常见的构建流程如下：

这里写图片描述

树中指向某个节点左孩子的边上表示位0,指向右孩子的边上的表示位1，这样遍历一棵最优前缀码树就可以得到对照表。

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * 
 *                            root 
 *                            /   \ 
 *                    --------- ---------- 
 *                    |c:freq | | c:freq | 
 *                    --------- ----------
 * 
 *
 */
public class HuffmanEncodeDemo {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Node[] n = new Node[6];
		float[] freq = new float[] { 9, 5, 45, 13, 16, 12 };
		char[] chs = new char[] { 'e', 'f', 'a', 'b', 'd', 'c' };
		HuffmanEncodeDemo demo = new HuffmanEncodeDemo();
		Node root = demo.buildPrefixEncodeTree(n, freq, chs);
		Map<Character, String> collector = new HashMap<>();
		StringBuilder sb = new StringBuilder();
		demo.tranversalPrefixEncodeTree(root, collector, sb);
		System.out.println(collector);
		String s = "abcabcefefefeabcdbebfbebfbabc";
		StringBuilder sb1 = new StringBuilder();
		for (char c : s.toCharArray()) {
			sb1.append(collector.get(c));
		}
		System.out.println(sb1.toString());
	}

	public Node buildPrefixEncodeTree(Node[] n, float[] freq, char[] chs) {
		PriorityQueue<Node> pQ = new PriorityQueue<>(new Comparator<Node>() {
			public int compare(Node o1, Node o2) {
				return o1.item.freq > o2.item.freq ? 1 : o1.item.freq == o2.item.freq ? 0 : -1;
			};
		});
		Node e = null;
		for (int i = 0; i < chs.length; i++) {
			n[i] = e = new Node(null, null, new Item(chs[i], freq[i]));
			pQ.add(e);
		}

		for (int i = 0; i < n.length - 1; i++) {
			Node x = pQ.poll(), y = pQ.poll();
			Node z = new Node(x, y, new Item('$', x.item.freq + y.item.freq));
			pQ.add(z);
		}
		return pQ.poll();
	}
	
	/**
	 * tranversal  
	 * @param root
	 * @param collector
	 * @param sb
	 */
	public void tranversalPrefixEncodeTree(Node root, Map<Character, String> collector, StringBuilder sb) {
		// leaf node
		if (root.left == null && root.right == null) {
			collector.put(root.item.c, sb.toString());
			return;
		}
		Node left = root.left, right = root.right;
		tranversalPrefixEncodeTree(left, collector, sb.append(0));
		sb.delete(sb.length() - 1, sb.length());
		tranversalPrefixEncodeTree(right, collector, sb.append(1));
		sb.delete(sb.length() - 1, sb.length());
	}
	
}

class Node {
	public Node left, right;
	public Item item;

	public Node(Node left, Node right, Item item) {
		super();
		this.left = left;
		this.right = right;
		this.item = item;
	}

}

class Item {
	public char c;
	public float freq;

	public Item(char c, float freq) {
		super();
		this.c = c;
		this.freq = freq;
	}
}

输出如下：

1 2	{a=0, b=101, c=100, d=111, e=1101, f=1100} 010110001011001101110011011100110111001101010110011110111011011100101110110111001010101100

4 堆的应用：海量实数中（一亿级别以上）找到TopK（一万级别以下）的数集合。

A:通常遇到找一个集合中的TopK问题，想到的便是排序，因为常见的排序算法例如快排算是比较快了，然后再取出K个TopK数，时间复杂度为O(nlogn)，当n很大的时候这个时间复杂度还是很大的；
B:另一种思路就是打擂台的方式,每个元素与K个待选元素比较一次，时间复杂度很高：O(k*n)，此方案明显逊色于前者。

对于一亿数据来说，A方案大约是26.575424*n；

C:由于我们只需要TopK，因此不需要对所有数据进行排序，可以利用堆得思想，维护一个大小为K的小顶堆，然后依次遍历每个元素e, 若元素e大于堆顶元素root，则删除root，将e放在堆顶，然后调整，时间复杂度为logK；若小于或等于，则考察下一个元素。这样遍历一遍后，最小堆里面保留的数就是我们要找的topK，整体时间复杂度为O(k+n*logk)约等于O(n*logk)，大约是13.287712*n（由于k与n数量级差太多），这样时间复杂度下降了约一半。

A、B、C三个方案中，C通常是优于B的，因为logK通常是小于k的，当K和n的数量级相差越大，这种方式越有效。

以下为具体操作：

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.io.UnsupportedEncodingException;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;
public class TopKNumbersInMassiveNumbersDemo {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] topK = new int[]{50001,50002,50003,50004,50005};
		genData(1000 * 1000 * 1000, 500, topK);
		long t = System.currentTimeMillis();
		findTopK(topK.length);
		System.out.println(String.format("cost:%fs", (System.currentTimeMillis() - t) * 1.0 / 1000));
	}
	
	public static void genData(int N, int maxRandomNumer, int[] topK) {
		File f = new File("data.txt");
		int k = topK.length;
		Set<Integer> index = new TreeSet<>();
		for (;;) {
			index.add((int)(Math.random() * N));
			if (index.size() == k)
				break;
		}
		System.out.println(index);
		int j = 0;
		try {
			PrintWriter pW = new PrintWriter(f, "UTF-8");
			for (int i = 0; i < N; i++)
				if(!index.contains(i))
					pW.println((int)(Math.random() * maxRandomNumer));
				else
					pW.println(topK[j++]);
			pW.flush();
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (UnsupportedEncodingException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	public static void findTopK(int k) {
		int[] nums = new int[k];
		//read
		File f = new File("data.txt");
		try {
			Scanner scanner = new Scanner(f);
			for (int j = 0;j < k; j++)
				nums[j] = scanner.nextInt();
			heapify(nums);
			//core
			while (scanner.hasNextInt()) {
				int a = scanner.nextInt();
				if (a <= nums[0])
					continue;
				else {
					nums[0] = a;
					siftDown(0, k, nums);
				}
			}
			System.out.println(Arrays.toString(nums));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
	}
	
	//O(n), minimal heap
	public static void heapify(int[] nums) {
		int size = nums.length;
		for (int j = (size - 1) >> 1; j >= 0; j--)
			siftDown(j, size, nums);
	}
	
	private static void siftDown(int i, int n, int[] nums) {
		int key = nums[i];
		for (;i < (n >>> 1);) {
			int child = (i << 1) + 1;
			if (child + 1 < n && nums[child] > nums[child+1])
				child++;
			if (key <= nums[child])
				break;
			nums[i] = nums[child];
			i = child;
		}
		nums[i] = key;
	}
}

ps:大致测试了一下，10亿个数中找到top5需要140秒左右，应该是很快了。

5 总结

堆是基于树的满足一定约束的重要数据结构，存在许多变体例如二叉堆、二项式堆、斐波那契堆（很高效）等。
堆的几个基本操作都依赖于两个重要的函数siftUp和siftDown，堆的insert通常是在堆尾插入新元素并siftUp调整堆，而extractMin是在
删除堆顶元素，然后将最后一个元素放置堆顶并调用siftDown调整堆。
二叉堆是常用的一种堆，其是一棵二叉树；由于二叉树良好的性质，因此常常采用数组来存储堆。
堆得基本操作的时间复杂度如下表所示：

heapify	insert	peek	extractMin	delete(i)
`O(n)`	`O(logn)`	`O(1)`	`O(logn)`	`O(logn)`

二叉堆通常被用来实现堆排序算法，堆排序可以sort in place，堆排序的时间复杂度的上界是O(nlogn)，是一种很优秀的排序算法。由于存在相同键值的两个元素处于两棵子树中，而两个元素的顺序可能会在后续的堆调整中发生改变，因此堆排序不是稳定的。降序排序需要建立小顶堆，升序排序需要建立大顶堆。
堆是实现抽象数据类型优先队列的一种方式，优先队列有很广泛的应用，例如Huffman编码中使用优先队列利用贪心算法构建最优前缀编码树。
堆的另一个应用就是在海量数据中找到TopK个数，思想是维护一个大小为K的二叉堆，然后不断地比较堆顶元素，判断是否需要执行替换对顶元素的操作，采用
此方法的时间复杂度为n*logk，当k和n的数量级差距很大的时候，这种方式是很有效的方法。

6 references

[1] https://en.wikipedia.org/wiki/Heap_(data_structure)

[2] https://en.wikipedia.org/wiki/Heapsort

[3] https://en.wikipedia.org/wiki/Priority_queue

[4] https://www.cnblogs.com/swiftma/p/6006395.html

[5] Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest, Clifford Stein.算法导论[M].北京:机械工业出版社,2015:245-249

[6] Jon Bentley.编程珠玑[M].北京:人民邮电出版社,2015:161-174

LCS问题

发表于 2017-06-20 更新于 2025-09-24 分类于数据结构与算法

1. 简介

LCS通常是指Longest Common Subsequence, 但是也可代指Longest Common Substring。子串是一种特殊的子序列，子串和子序列的区别就是字串要求是组成子串的
各字符是连续的，而子序列仅仅要求各字符的下标是递增的即可。举个例子，如helloworld， world是子串(也是子序列)， hw不是子串是子序列。

LCS问题就是在若干(这里是两个)字符串中，找到最长的一个字符串p, 这个p是那些字符串的子串(子序列)。LCS问题的意义之一就是去衡量若干字符串的相似度，例如在生物信息学
中有DNA序列的问题，比如序列a = "ATGATAGATAGATAG"，序列b="TGGGCCGAGAAGCGAGA"，需要一种去衡量a、b相似度的方法，那么最长公共子序列就可以作为一种衡量方法。
除此之外，在软件开发领域中的版本控制系统（典型的就是Git），比较同一个文件不同时刻的差异的时候，就需要利用到这个方法。

例如下图就是Git上面的两次不同时刻对同一个文件的快照的对比图，我们可以看到，系统把两次的差异标示出来了。而原来位置、内容相同的部分没有标示。这个就可以通过
LCS问题的解决，来找到最长的公共子序列部分，就是作为公共的、未发生改变部分；剩下的就是改变的部分，应该标示出来。

这里写图片描述

同理基于这个，我们还可以简单的比较两篇文章的相似度来检查雷同、抄袭的情况，这么看来，LCS问题的还是和我们日常比较相关的。

解决LCS问题依靠暴力(brute force)的求解时间复杂度是指数级别的，因此不太现实，由于问题的本身的最优解具有最优子结构特征，因此原问题的求解可以化为多个子问题的求解；另外子问题的求解存在重叠的情况，这恰好是适合动态规划求解的问题的第二个特征：存在重叠的子问题求解过程，因此适合利用动态规划来求解，这个也是较常见的解决LCS问题的方法,时间复杂度为O(n*m)，动态规划易于编写，但是时间复杂度较高；另外更高级的还存在一种线性复杂度的O(n+m)的解法，就是Suffix Tree，不过这种方法的缺点是程序难以编制。因此在日常的编码中，动态规划已经够用了。

2. 最长公共子串问题

设dp[i][j]表示s[0~~i]和t[0~~j]的最长公共子串的长度，对于两个字符串的最长公共子串问题的最优解，最优解存在如下结构：

dp[i][j] = 1 (i == 0 || j == 0)
dp[i][j] = dp[i-1][j-1] + 1;(s[i] == t[j] && i > 0 && j > 0);
dp[i][j] = 0;(s[i] != t[j])

上述等式建立了原问题和子问题的关系（此类证明可用反证法），剩下的就是编码了。

public static List<String> findLongestLCS(String s, String t) {
   char[] schs = s.toCharArray();
   char[] tchs = t.toCharArray();
   int m = s.length(), n = t.length();
   int[][] dp = new int[m][n];
   int maxSize = 0;
   List<Integer> indexs = new ArrayList<>();//存储最长公共子串的在原始串中结束位置

   for (int i = 0; i < m; i++)
     for (int j = 0; j < n; j++) {
       if (schs[i] == tchs[j]) {
         if (i == 0 || j == 0)
           dp[i][j] = 1;
         else
           dp[i][j] = dp[i - 1][j - 1] + 1;

         if (dp[i][j] > maxSize) {
           maxSize = dp[i][j];
           indexs.clear();//找到更优的解，前面存储的下标值全部作废
           indexs.add(i);
         } else if (dp[i][j] == maxSize)
           indexs.add(i);
        } else
          dp[i][j] = 0;
    }
   List<String> ret = new ArrayList<>();
   for (Integer i : indexs)
     ret.add(s.substring(i + 1 - maxSize, i + 1));
   return ret;
 }

改进：上面的版本时间复杂度是O(n*m),空间复杂度也是O(n*m);但是观察dp二维数组发现，发现有优化的余地。由于在计算dp[i][j]的时候只使用到了dp[i-1][j-1]，因此dp二维数组可以使用一个一位数组和两个临时变量即可完成，这样就把空间复杂度降低到O(min(n, m))。

改进版本


// 内存改进版本, 只存储one row,新增两个临时变量空间复杂度O(min(m, n))
	public static List<String> findLongestLCS0(String s, String t) {
		String tmp = s;
		if (s.length() > t.length()) {
			s = t;
			t = tmp;
		}

		char[] schs = s.toCharArray();
		char[] tchs = t.toCharArray();
		int m = s.length(), n = t.length();

		int[] dp = new int[m];
  //prev存储dp[i-1][j-1]，cur存储dp[i][j]
		int prev = 0, cur = 0;
		int maxSize = 0;
		List<Integer> indexs = new ArrayList<>();

		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				if (schs[j] == tchs[i]) {
					if (i == 0 || j == 0)
						dp[j] = 1;
					else {
						cur = dp[j];
						dp[j] = prev + 1;
						prev = cur;
					}

					if (dp[j] > maxSize) {
						maxSize = dp[j];
						indexs.clear();
						indexs.add(j);
					} else if (dp[j] == maxSize)
						indexs.add(j);
				} else {
					cur = dp[j];
					dp[j] = 0;
					prev = cur;
				}
		List<String> ret = new ArrayList<>();
		for (Integer j : indexs)
			ret.add(s.substring(j + 1 - maxSize, j + 1));
		return ret;
	}

如果上面的dp数组很稀疏(0值很多)，当字符串很大时，也还可以继续优化，采用hashmap的方式存储非0值，这样在字符串大且dp数组稀疏的时候，可以进一步优化。


// 内存改进版1 用hashtable存储每一行dp的非0值
	public static List<String> findLongestLCS1(String s, String t) {
		String tmp = s;
		if (s.length() > t.length()) {
			s = t;
			t = tmp;
		}

		char[] schs = s.toCharArray();
		char[] tchs = t.toCharArray();
		int m = s.length(), n = t.length();

		Map<Integer, Integer> dp = new HashMap<>();
		int prev = 0, cur = 0;
		int maxSize = 0;
		List<Integer> indexs = new ArrayList<>();

		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++) {
				Integer tmpj = dp.get(j);
				if (schs[j] == tchs[i]) {
					if (i == 0 || j == 0)
						dp.put(j, 1);
					else {
						cur = tmpj == null ? 0 : tmpj;
						dp.put(j, prev + 1);
						prev = cur;
					}

					tmpj = dp.get(j);
					if (tmpj > maxSize) {
						maxSize = tmpj;
						indexs.clear();
						indexs.add(j);
					} else if (tmpj == maxSize)
						indexs.add(j);
				} else {
					//非0值不存储， 优化稀疏情况。
					cur = tmpj == null ? 0 : tmpj;
					dp.remove(j);
					prev = cur;
				}
			}
		System.out.println(indexs);
		List<String> ret = new ArrayList<>();
		for (Integer j : indexs)
			ret.add(s.substring(j + 1 - maxSize, j + 1));
		return ret;
	}

3. 最长公共子序列问题

同样的最长公共子序列也可以利用刻画最优解的结构来利用DP求解。
对于字符串s和t，和上面一样dp[i][j]存储的值依然是s[0~~i]和t[0~~j]的最长公共子序列的长度。

最优解的结构

dp[i][j] = 1 (i == 0 || j == 0 && s[i] == t[j])
dp[i][j] = 0 (i == 0 || j == 0 && s[i] != t[j])
dp[i][j] = dp[i-1][j-1] + 1(i > 0 && j > 0 && s[i] == t[j])
dp[i][j] = max(dp[i-1][j], dp[i][j-1])(i > 0 && j > 0 && s[i] != t[j])

具体证明参见《算法讨导论》,也是利用反证法。

由于计算的时候只使用到了dp[i-1][j-1]、dp[i-1][j]和dp[i][j-1]，则可以运用上上文中的思路，进行空间优化。


//只需要求解长度，可以进行空间优化
	public static int longestLCS(String s, String t) {
		String tmp = s;
		if (s.length() > t.length()) {
			s = t;
			t = tmp;
		}
		
		char[] schs = s.toCharArray();
		char[] tchs = t.toCharArray();
		int m = s.length(), n = t.length(), prev = 0, cur;
		int[] dp = new int[m];

		for (int j = 0; j < n; j++)
			for (int i = 0; i < m; i++) {
				if (schs[i] == tchs[j]) {
					if (i == 0 || j == 0) 
						dp[i] = 1;
					else {
						cur = dp[i];
						dp[i] = prev + 1;//prev ---> dp[i-1][j-1]
						prev = cur;
					}	
				} else {
					cur = dp[i];
					int aa = i == 0 ? 0 : dp[i-1], bb = j == 0 ? 0 : dp[i];
					dp[i] = Math.max(aa, bb);
					prev = cur;
				}
			}	
		return dp[m-1];
	}

但是由于有些时候，我们需要知道这些最长公共子序列，因此我们还需要在求解的过程保存额外的信息(上文中保存的是下标值)。为了得到最长公共子序列，我们可以
沿着求解反方向去得到最长公共子序列。具体的做法就是，给定一个dp[i][j]我们可以判断出，它是由dp[i][j-1]还是dp[i-1][j]还是dp[i-1][j-1]得来的，知道了这个以后我们就知道了求解方向了，这样可以逆着回退到起点dp[0][0]。


public static String longestLCSWithReconstructionLCS(String a, String b) {
	char[] achs = a.toCharArray();
	char[] bchs = b.toCharArray();
	int m = a.length(), n = b.length();
	int[][] dp = new int[m][n];
	StringBuilder sb = new StringBuilder();

	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++) {
			if (achs[i] == bchs[j]) {
				if (i == 0 || j == 0)
					dp[i][j] = 1;
				else
					dp[i][j] = dp[i - 1][j - 1] + 1;
			} else {
				int aa = i == 0 ? 0 : dp[i - 1][j], bb = j == 0 ? 0 : dp[i][j - 1];
				dp[i][j] = Math.max(aa, bb);
			}
		}	
	// 重构最长公共子序列
	int i = m - 1, j = n - 1;
	while (i >= 0 && j >= 0) {
		//判断方向
		if (achs[i] == bchs[j]) {//如果相等，必然是子序列的一部分
			sb.append(achs[i]);
			i--;j--;
		} else {//如果不相等，则需要判断求解方向，然后逆行。
			if (dp[i - 1][j] >= dp[i][j - 1])
				i--;
			else
				j--;
		}
	}
	return sb.reverse().toString();
}

我们可以在O(n)的时间重构得到最长公共子序列,由于我们需要在最后逆行构造最长公共子序列，因此是不能将二维数组dp优化成一位数组dp,因为优化以后我们是没法
在O(1)的时间判断出由dp[i][j-1]还是dp[i-1][j]还是dp[i-1][j-1]得来的，重构最长公共子序列也就无从谈起了。

4. References

[1] Longest_common_subsequence_problem

[2] Suffix Tree

[3] Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest, Clifford Stein.算法导论[M].北京:机械工业出版社,2015:222-226

Java动态代理简述

发表于 2017-04-16 更新于 2025-09-24 分类于 Java

一、代理简介

代理一词含义十分宽泛，例如金融领域的股票发行代理、营销领域的销售代理、以及计算机领域中的代理设计模式等。尽管代理一词被使用的领域如此广泛，但是代理一词的大致的抽象含义是相似的或者说是相同的。代理是一个被委托人委托其执行如下活动：参加活动、行驶权力、执行任务等。这样理解的话，计算机中某个对象或组件的代理就非常好理解了。

计算机领域中代理的概念是一个十分重要的概念，常见的有代理服务器、代理设计模式等。在软件开发发展成熟的今天，每个工程的代码量也越来越庞大，带来的一个问题就是一次小小的需求修改就会引起很大的变化，从而可能引进新的BUG.
因此程序员对需求修改都深恶痛绝，而代理设计模式在某种程度上可以缓解这种问题。代理设计模式可以实现在不破坏原有代码的情况下，对原有代码添加额外的功能，从而实现以低的侵入完成原有系统功能的扩展，这种设计也符合里氏替换原则（对修改关闭，对扩展开放）。

二、Java语言的代理

编程语言中的代理分为静态代理和动态代理

静态代理：在编译时期就已经确定了静态代理的类型或者说是是在编译时期的时候生成代理的类（class）
动态代理：在运行时期确定代理的类型或者是说在运行时期生成代理的类（class）

像大多数其他语言一样，Java可以轻松的实现静态代理。具体来讲有两种形式：

静态代理

匿名内部类的形式

abstract class AbstractProxy {
	AbstractProxy real;
	public AbstractProxy() {
		// TODO Auto-generated constructor stub
	}
	public AbstractProxy(AbstractProxy real) {
		this.real = real;
	};
	//被代理的方法
	public abstract void foolbar(String str);
}

//某个被代理类
class RealClass extends AbstractProxy {
	public RealClass() {
		super();
	}
	public RealClass(AbstractProxy real) {
		super(real);
		// TODO Auto-generated constructor stub
	}

	@Override
	public void foolbar(String str) {
		// TODO Auto-generated method stub
		System.out.println("out>>" + str);
	}
	
}

final AbstractProxy realObj = new RealClass();
AbstractProxy proxy = new AbstractProxy() {
	@Override
	public void foolbar(String str) {
		// TODO Auto-generated method stub
		System.out.println("you are proxied by me!");
		realObj.foolbar(str);
	}
};

该形式可以实现一个代理，看似是在运行时生成的一个匿名内部类，但是通过测试发现匿名内部类是在编译时期生成的类，这个可以通过匿名内部类类文件来观察，因此其属于静态代理。这种形式的代理看起来不太正常，而且一个代理类只能代理一个接口或者一个抽象类，如果代理多个就必须新增加多个匿名内部类。

继承被代理类或者实现被代理接口
这种形式的代理设计类似于设计模式中的装饰器模式或者适配器模式，具体看代码：


//被代理的接口
interface IReal {
	public void doSomeThing(String str);
}

//某个被代理的类
class RealClass implements IReal {

	@Override
	public void doSomeThing(String str) {
		// TODO Auto-generated method stub
		System.out.println("doSomeThing " + str);
	}
	
}


class ProxyClass implements IReal {
	IReal realObj;
	
	public ProxyClass(IReal realObj) {
		this.realObj = realObj;	
	}

	@Override
	public void doSomeThing(String str) {
		// TODO Auto-generated method stub
		System.out.println("you are proxied by me!");
		realObj.doSomething();
	}
}

RealClass realObj = new RealClass();
RealClass proxy = new ProxyClass(realObj);

这种形式的代理类型需要在编译时期确定，因此属于静态类型。从某种程度上来看，这种形式和装饰器模式、适配器模式的设计思路相似。缺点同第一种形式一样，如果多个需要代理多个接口就需要重写代理类，让其实现多个被代理的接口；同时在类型转换的时候也会很麻烦。

动态代理

java的动态代理是运行时动态的根据需要被代理的接口列表interfaces生成一个代理类，该代理类实现了接口列表interfaces中的所有方法，然后在方法的内部实际是讲该方法的调用转发给了实现了InvocationHandler接口的对象，顾名思义，该对象让包含代理时被代理方法的代理逻辑。

用法举例：编写一个代理类实现拦截某个被代理方法
具体的使用代码：

interface IProxied1 {
	public void proxiedMethod1(String str);
}

interface IProxied2 {
	public void proxiedMethod2(String str);
}

class Proxied implements IProxied1, IProxied2 {

	@Override
	public void proxiedMethod2(String str) {
		// TODO Auto-generated method stub
		System.out.println("proxiedMethod2 " + str);
	}

	@Override
	public void proxiedMethod1(String str) {
		// TODO Auto-generated method stub
		System.out.println("proxiedMethod1 " + str);
	}
	
}

class Interceptor implements InvocationHandler {
	Object proxied;
	public Interceptor() {
		// TODO Auto-generated constructor stub
	}
	
	public Interceptor(Object proxied) {
		// TODO Auto-generated constructor stub
		this.proxied = proxied;
	}
	@Override
	public Object invoke(Object proxy, Method method, Object[] args) throws Throwable {
		// TODO Auto-generated method stub
		System.out.println("I am watching...");
		//判断是否拦截
		if(method.getName().equals("proxiedMethod1")) {
			System.out.println("you are intercepted!!!!!");
			return null;
		}
		return method.invoke(proxied, args);
	}
	
}

执行代码


public class DynamicProxyDemo {
	public static void main(String[] str) {
		IProxied1 proxiedObj = new Proxied();
		Object proxyObj = Proxy.newProxyInstance(IProxied1.class.getClassLoader(), new Class<?>[]{IProxied1.class, IProxied2.class}, new Interceptor(proxiedObj));
		((IProxied1)proxyObj).proxiedMethod1("Hello, World!");
		System.out.println("-------");
		((IProxied2)proxyObj).proxiedMethod2("Hello, World!");
	}
}

输出如下：


I am watching...
you are intercepted!!!!!
-------
I am watching...
proxiedMethod2 Hello, World!

比较静态代理和动态代理

一般来讲，静态代理是硬编码去实现一个代理类，如果需要被代理的接口有变动，则需要重新编码代理类；静态绑定的过程将代理类的代理逻辑和代理类的生成绑定到一起了，
所以修改起来不是很方便（解耦不彻底）。其实我们最关注的是代理类的代理逻辑，因此如果将代理的生成自动化（因为代理类的生成的规则是general的，可以泛化。先实现被代理的接口、然后方法转发，就是这么简单。），
而将代理逻辑分离出来，所有的代理逻辑全部发生在这里；通过这样的解耦，代码可维护性会增强、侵入性会减小，这就是动态代理的思想。

具体来讲区别如下图：

静态代理

这里写图片描述

静态代理的代理类多处出现代理逻辑的代码，并且同时静态代理的代理类需要自己硬编码。

动态代理

动态代理的代理类类似于一个方法路由，对被代理对象的任何被代理方法的调用，都会被该路由转发到InvocationHandler代理逻辑处理类中，从而将代理类的生成和代理类的代理逻辑分开。
Java动态代理生成的代理类是直接在内存中按照class文件格式生成了一个二进制文件，然后类加载器加载该二进制类文件，最后实例化一个代理类的实例。

三、Java动态代理源码分析

前面已经介绍了Java动态代理的基本用法，主要涉及到如下几个类和方法如下：（JDK7）

java.lang.reflect.Proxy
- public static Object newProxyInstance(ClassLoader loader, Class<?>[] interfaces, InvocationHandler h) throws IllegalArgumentException
- public static Class<?> getProxyClass(ClassLoader loader, Class<?>... interfaces) throws IllegalArgumentException
sun.misc.ProxyGenerator
- public static byte[] generateProxyClass(final String name, Class[] interfaces)
java.lang.reflect.InvocationHandler
- public Object invoke(Object proxy, Method method, Object[] args) throws Throwable;

具体源代码如下：


/**
 * Returns an instance of a proxy class for the specified interfaces
 * that dispatches method invocations to the specified invocation
 * handler.  This method is equivalent to:
 * <pre>
 *     Proxy.getProxyClass(loader, interfaces).
 *         getConstructor(new Class[] { InvocationHandler.class }).
 *         newInstance(new Object[] { handler });
 * </pre>
 *
 * <p>{@code Proxy.newProxyInstance} throws
 * {@code IllegalArgumentException} for the same reasons that
 * {@code Proxy.getProxyClass} does.
 *
 * @param   loader the class loader to define the proxy class
 * @param   interfaces the list of interfaces for the proxy class
 *          to implement
 * @param   h the invocation handler to dispatch method invocations to
 * @return  a proxy instance with the specified invocation handler of a
 *          proxy class that is defined by the specified class loader
 *          and that implements the specified interfaces
 * @throws  IllegalArgumentException if any of the restrictions on the
 *          parameters that may be passed to {@code getProxyClass}
 *          are violated
 * @throws  NullPointerException if the {@code interfaces} array
 *          argument or any of its elements are {@code null}, or
 *          if the invocation handler, {@code h}, is
 *          {@code null}
 */
public static Object newProxyInstance(ClassLoader loader,
                                      Class<?>[] interfaces,
                                      InvocationHandler h)
    throws IllegalArgumentException
{
    if (h == null) {
        throw new NullPointerException();
    }

    /*
     * Look up or generate the designated proxy class.
     */
    Class<?> cl = getProxyClass(loader, interfaces);

    /*
     * Invoke its constructor with the designated invocation handler.
     */
    try {
        Constructor cons = cl.getConstructor(constructorParams);
        return cons.newInstance(new Object[] { h });
    } catch (NoSuchMethodException e) {
        throw new InternalError(e.toString());
    } catch (IllegalAccessException e) {
        throw new InternalError(e.toString());
    } catch (InstantiationException e) {
        throw new InternalError(e.toString());
    } catch (InvocationTargetException e) {
        throw new InternalError(e.toString());
    }
}


/**
    * Returns the {@code java.lang.Class} object for a proxy class
    * given a class loader and an array of interfaces.  The proxy class
    * will be defined by the specified class loader and will implement
    * all of the supplied interfaces.  If a proxy class for the same
    * permutation of interfaces has already been defined by the class
    * loader, then the existing proxy class will be returned; otherwise,
    * a proxy class for those interfaces will be generated dynamically
    * and defined by the class loader.
    *
    * <p>There are several restrictions on the parameters that may be
    * passed to {@code Proxy.getProxyClass}:
    *
    * <ul>
    * <li>All of the {@code Class} objects in the
    * {@code interfaces} array must represent interfaces, not
    * classes or primitive types.
    *
    * <li>No two elements in the {@code interfaces} array may
    * refer to identical {@code Class} objects.
    *
    * <li>All of the interface types must be visible by name through the
    * specified class loader.  In other words, for class loader
    * {@code cl} and every interface {@code i}, the following
    * expression must be true:
    * <pre>
    *     Class.forName(i.getName(), false, cl) == i
    * </pre>
    *
    * <li>All non-public interfaces must be in the same package;
    * otherwise, it would not be possible for the proxy class to
    * implement all of the interfaces, regardless of what package it is
    * defined in.
    *
    * <li>For any set of member methods of the specified interfaces
    * that have the same signature:
    * <ul>
    * <li>If the return type of any of the methods is a primitive
    * type or void, then all of the methods must have that same
    * return type.
    * <li>Otherwise, one of the methods must have a return type that
    * is assignable to all of the return types of the rest of the
    * methods.
    * </ul>
    *
    * <li>The resulting proxy class must not exceed any limits imposed
    * on classes by the virtual machine.  For example, the VM may limit
    * the number of interfaces that a class may implement to 65535; in
    * that case, the size of the {@code interfaces} array must not
    * exceed 65535.
    * </ul>
    *
    * <p>If any of these restrictions are violated,
    * {@code Proxy.getProxyClass} will throw an
    * {@code IllegalArgumentException}.  If the {@code interfaces}
    * array argument or any of its elements are {@code null}, a
    * {@code NullPointerException} will be thrown.
    *
    * <p>Note that the order of the specified proxy interfaces is
    * significant: two requests for a proxy class with the same combination
    * of interfaces but in a different order will result in two distinct
    * proxy classes.
    *
    * @param   loader the class loader to define the proxy class
    * @param   interfaces the list of interfaces for the proxy class
    *          to implement
    * @return  a proxy class that is defined in the specified class loader
    *          and that implements the specified interfaces
    * @throws  IllegalArgumentException if any of the restrictions on the
    *          parameters that may be passed to {@code getProxyClass}
    *          are violated
    * @throws  NullPointerException if the {@code interfaces} array
    *          argument or any of its elements are {@code null}
    */
   //根据一组接口列表interfaces，返回一个由类加载器loader加载的实现了所有interfaces的类对象
   //如果实现接口列表interfaces的类已经被加载过了；则直接返回缓存的类对象
   public static Class<?> getProxyClass(ClassLoader loader,
                                        Class<?>... interfaces)
       throws IllegalArgumentException
   {
       if (interfaces.length > 65535) {
           throw new IllegalArgumentException("interface limit exceeded");
       }

       Class<?> proxyClass = null;

       /* collect interface names to use as key for proxy class cache */
       String[] interfaceNames = new String[interfaces.length];

       // for detecting duplicates
       Set<Class<?>> interfaceSet = new HashSet<>();

       //验证接口列表的接口对于参数给定的类加载器loader是否是可见的；
       //同时检查接口列表interfaces的合法性（无重复的接口、必须是接口类型）
       for (int i = 0; i < interfaces.length; i++) {
           /*
            * Verify that the class loader resolves the name of this
            * interface to the same Class object.
            */
           String interfaceName = interfaces[i].getName();
           Class<?> interfaceClass = null;
           try {
               interfaceClass = Class.forName(interfaceName, false, loader);
           } catch (ClassNotFoundException e) {
           }
           if (interfaceClass != interfaces[i]) {
               throw new IllegalArgumentException(
                   interfaces[i] + " is not visible from class loader");
           }

           /*
            * Verify that the Class object actually represents an
            * interface.
            */
           if (!interfaceClass.isInterface()) {
               throw new IllegalArgumentException(
                   interfaceClass.getName() + " is not an interface");
           }

           /*
            * Verify that this interface is not a duplicate.
            */
           if (interfaceSet.contains(interfaceClass)) {
               throw new IllegalArgumentException(
                   "repeated interface: " + interfaceClass.getName());
           }
           interfaceSet.add(interfaceClass);

           interfaceNames[i] = interfaceName;
       }

       /*
        * Using string representations of the proxy interfaces as
        * keys in the proxy class cache (instead of their Class
        * objects) is sufficient because we require the proxy
        * interfaces to be resolvable by name through the supplied
        * class loader, and it has the advantage that using a string
        * representation of a class makes for an implicit weak
        * reference to the class.
        */
       List<String> key = Arrays.asList(interfaceNames);

       /*
        * Find or create the proxy class cache for the class loader.
        */
       Map<List<String>, Object> cache;
       synchronized (loaderToCache) {
           cache = loaderToCache.get(loader);
           if (cache == null) {
               cache = new HashMap<>();
               loaderToCache.put(loader, cache);
           }
           /*
            * This mapping will remain valid for the duration of this
            * method, without further synchronization, because the mapping
            * will only be removed if the class loader becomes unreachable.
            */
       }

       /*
        * Look up the list of interfaces in the proxy class cache using
        * the key.  This lookup will result in one of three possible
        * kinds of values:
        *     null, if there is currently no proxy class for the list of
        *         interfaces in the class loader,
        *     the pendingGenerationMarker object, if a proxy class for the
        *         list of interfaces is currently being generated,
        *     or a weak reference to a Class object, if a proxy class for
        *         the list of interfaces has already been generated.
        */
       synchronized (cache) {
           /*
            * Note that we need not worry about reaping the cache for
            * entries with cleared weak references because if a proxy class
            * has been garbage collected, its class loader will have been
            * garbage collected as well, so the entire cache will be reaped
            * from the loaderToCache map.
            */
           do {
               //cache 的key是接口名数组生成的list；value是一个代理类对象的弱引用
               Object value = cache.get(key);
               if (value instanceof Reference) {
                   proxyClass = (Class<?>) ((Reference) value).get();
               }
               if (proxyClass != null) {
                   // proxy class already generated: return it
                   return proxyClass;
                   //如果是一个标志符号，则说明有另外的线程正在创建代理类；则该线程挂起等待
               } else if (value == pendingGenerationMarker) {
                   // proxy class being generated: wait for it
                   try {
                       cache.wait();
                   } catch (InterruptedException e) {
                       /*
                        * The class generation that we are waiting for should
                        * take a small, bounded time, so we can safely ignore
                        * thread interrupts here.
                        */
                   }
                   continue;//被唤醒后；继续check是否存在类对象
               } else {
                   /*
                    * No proxy class for this list of interfaces has been
                    * generated or is being generated, so we will go and
                    * generate it now.  Mark it as pending generation.
                    */
                   //不存在代理类的时候，需要自己去生成代理类；生成代理类之前先置一个状态标志对象pendingGenerationMarker
                   cache.put(key, pendingGenerationMarker);
                   break;
               }
           } while (true);
       }

       try {
           String proxyPkg = null;     // package to define proxy class in

           /*
            * Record the package of a non-public proxy interface so that the
            * proxy class will be defined in the same package.  Verify that
            * all non-public proxy interfaces are in the same package.
            */
           for (int i = 0; i < interfaces.length; i++) {
               int flags = interfaces[i].getModifiers();
               if (!Modifier.isPublic(flags)) {
                   String name = interfaces[i].getName();
                   int n = name.lastIndexOf('.');
                   String pkg = ((n == -1) ? "" : name.substring(0, n + 1));
                   if (proxyPkg == null) {
                       proxyPkg = pkg;
                   } else if (!pkg.equals(proxyPkg)) {
                       throw new IllegalArgumentException(
                           "non-public interfaces from different packages");
                   }
               }
           }

           if (proxyPkg == null) {     // if no non-public proxy interfaces,
               proxyPkg = "";          // use the unnamed package
           }

           {
               /*
                * Choose a name for the proxy class to generate.
                */
               long num;
               synchronized (nextUniqueNumberLock) {
                   num = nextUniqueNumber++;
               }
               String proxyName = proxyPkg + proxyClassNamePrefix + num;
               /*
                * Verify that the class loader hasn't already
                * defined a class with the chosen name.
                */

               /*
                * Generate the specified proxy class.
                */
               //重点在这里；调用ProxyGenerator的静态方法去生成一个代理类，得到类文件的字节数组
               byte[] proxyClassFile = ProxyGenerator.generateProxyClass(
                   proxyName, interfaces);
               try {
                   //用类加载器加载二进制类文件，得到代理类对象
                   proxyClass = defineClass0(loader, proxyName,
                       proxyClassFile, 0, proxyClassFile.length);
               } catch (ClassFormatError e) {
                   /*
                    * A ClassFormatError here means that (barring bugs in the
                    * proxy class generation code) there was some other
                    * invalid aspect of the arguments supplied to the proxy
                    * class creation (such as virtual machine limitations
                    * exceeded).
                    */
                   throw new IllegalArgumentException(e.toString());
               }
           }
           // add to set of all generated proxy classes, for isProxyClass
           proxyClasses.put(proxyClass, null);

       } finally {
           /*
            * We must clean up the "pending generation" state of the proxy
            * class cache entry somehow.  If a proxy class was successfully
            * generated, store it in the cache (with a weak reference);
            * otherwise, remove the reserved entry.  In all cases, notify
            * all waiters on reserved entries in this cache.
            */
           synchronized (cache) {
               if (proxyClass != null) {
                   //加入缓存
                   cache.put(key, new WeakReference<Class<?>>(proxyClass));
               } else {
                   cache.remove(key);
               }
               cache.notifyAll();//不管创建代理类是否成功，唤醒在cache上面等待的线程
           }
       }
       return proxyClass;
   }

/**
 * Generate a class file for the proxy class.  This method drives the
 * class file generation process.
 */
 //根据得到的方法信息、类信息；按照JVM的规范动态的生成一个代理类的二进制文件
 //该过程比较复杂涉及到许多JVM的指令
private byte[] generateClassFile() {

    /* ============================================================
     * Step 1: Assemble ProxyMethod objects for all methods to
     * generate proxy dispatching code for.
     */

    /*
     * Record that proxy methods are needed for the hashCode, equals,
     * and toString methods of java.lang.Object.  This is done before
     * the methods from the proxy interfaces so that the methods from
     * java.lang.Object take precedence over duplicate methods in the
     * proxy interfaces.
     */
    addProxyMethod(hashCodeMethod, Object.class);
    addProxyMethod(equalsMethod, Object.class);
    addProxyMethod(toStringMethod, Object.class);

    /*
     * Now record all of the methods from the proxy interfaces, giving
     * earlier interfaces precedence over later ones with duplicate
     * methods.
     */
    for (int i = 0; i < interfaces.length; i++) {
        Method[] methods = interfaces[i].getMethods();
        for (int j = 0; j < methods.length; j++) {
            addProxyMethod(methods[j], interfaces[i]);
        }
    }

    /*
     * For each set of proxy methods with the same signature,
     * verify that the methods' return types are compatible.
     */
    for (List<ProxyMethod> sigmethods : proxyMethods.values()) {
        checkReturnTypes(sigmethods);
    }

    /* ============================================================
     * Step 2: Assemble FieldInfo and MethodInfo structs for all of
     * fields and methods in the class we are generating.
     */
    try {
        methods.add(generateConstructor());

        for (List<ProxyMethod> sigmethods : proxyMethods.values()) {
            for (ProxyMethod pm : sigmethods) {

                // add static field for method's Method object
                fields.add(new FieldInfo(pm.methodFieldName,
                    "Ljava/lang/reflect/Method;",
                     ACC_PRIVATE | ACC_STATIC));

                // generate code for proxy method and add it
                methods.add(pm.generateMethod());
            }
        }

        methods.add(generateStaticInitializer());

    } catch (IOException e) {
        throw new InternalError("unexpected I/O Exception");
    }

    if (methods.size() > 65535) {
        throw new IllegalArgumentException("method limit exceeded");
    }
    if (fields.size() > 65535) {
        throw new IllegalArgumentException("field limit exceeded");
    }

    /* ============================================================
     * Step 3: Write the final class file.
     */

    /*
     * Make sure that constant pool indexes are reserved for the
     * following items before starting to write the final class file.
     */
    cp.getClass(dotToSlash(className));
    cp.getClass(superclassName);
    for (int i = 0; i < interfaces.length; i++) {
        cp.getClass(dotToSlash(interfaces[i].getName()));
    }

    /*
     * Disallow new constant pool additions beyond this point, since
     * we are about to write the final constant pool table.
     */
    cp.setReadOnly();

    ByteArrayOutputStream bout = new ByteArrayOutputStream();
    DataOutputStream dout = new DataOutputStream(bout);

    try {
        /*
         * Write all the items of the "ClassFile" structure.
         * See JVMS section 4.1.
         */
                                    // u4 magic;
        dout.writeInt(0xCAFEBABE);
                                    // u2 minor_version;
        dout.writeShort(CLASSFILE_MINOR_VERSION);
                                    // u2 major_version;
        dout.writeShort(CLASSFILE_MAJOR_VERSION);

        cp.write(dout);             // (write constant pool)

                                    // u2 access_flags;
        dout.writeShort(ACC_PUBLIC | ACC_FINAL | ACC_SUPER);
                                    // u2 this_class;
        dout.writeShort(cp.getClass(dotToSlash(className)));
                                    // u2 super_class;
        dout.writeShort(cp.getClass(superclassName));

                                    // u2 interfaces_count;
        dout.writeShort(interfaces.length);
                                    // u2 interfaces[interfaces_count];
        for (int i = 0; i < interfaces.length; i++) {
            dout.writeShort(cp.getClass(
                dotToSlash(interfaces[i].getName())));
        }

                                    // u2 fields_count;
        dout.writeShort(fields.size());
                                    // field_info fields[fields_count];
        for (FieldInfo f : fields) {
            f.write(dout);
        }

                                    // u2 methods_count;
        dout.writeShort(methods.size());
                                    // method_info methods[methods_count];
        for (MethodInfo m : methods) {
            m.write(dout);
        }

                                     // u2 attributes_count;
        dout.writeShort(0); // (no ClassFile attributes for proxy classes)

    } catch (IOException e) {
        throw new InternalError("unexpected I/O Exception");
    }

    return bout.toByteArray();
}

通过反编译生成的动态代理类的文件，可以得到


final class $Proxy0
  extends Proxy
  implements IReal
{
  private static Method m1;
  private static Method m3;
  private static Method m2;
  private static Method m0;
  
  public $Proxy0(InvocationHandler paramInvocationHandler)
  {
    super(paramInvocationHandler);
  }
  
  public final boolean equals(Object paramObject)
  {
    try
    {
      return ((Boolean)this.h.invoke(this, m1, new Object[] { paramObject })).booleanValue();
    }
    catch (Error|RuntimeException localError)
    {
      throw localError;
    }
    catch (Throwable localThrowable)
    {
      throw new UndeclaredThrowableException(localThrowable);
    }
  }
  
  public final void doSomeThing(String paramString)
  {
    try
    {
      this.h.invoke(this, m3, new Object[] { paramString });//方法的转发;反射调用InvocationHandler的invoke方法
      return;
    }
    catch (Error|RuntimeException localError)
    {
      throw localError;
    }
    catch (Throwable localThrowable)
    {
      throw new UndeclaredThrowableException(localThrowable);
    }
  }
  
  public final String toString()
  {
    try
    {
      return (String)this.h.invoke(this, m2, null);
    }
    catch (Error|RuntimeException localError)
    {
      throw localError;
    }
    catch (Throwable localThrowable)
    {
      throw new UndeclaredThrowableException(localThrowable);
    }
  }
  
  public final int hashCode()
  {
    try
    {
      return ((Integer)this.h.invoke(this, m0, null)).intValue();
    }
    catch (Error|RuntimeException localError)
    {
      throw localError;
    }
    catch (Throwable localThrowable)
    {
      throw new UndeclaredThrowableException(localThrowable);
    }
  }
  
  static
  {
    try
    {
      m1 = Class.forName("java.lang.Object").getMethod("equals", new Class[] { Class.forName("java.lang.Object") });
      m3 = Class.forName("trick.IReal").getMethod("doSomeThing", new Class[] { Class.forName("java.lang.String") });
      m2 = Class.forName("java.lang.Object").getMethod("toString", new Class[0]);
      m0 = Class.forName("java.lang.Object").getMethod("hashCode", new Class[0]);
      return;
    }
    catch (NoSuchMethodException localNoSuchMethodException)
    {
      throw new NoSuchMethodError(localNoSuchMethodException.getMessage());
    }
    catch (ClassNotFoundException localClassNotFoundException)
    {
      throw new NoClassDefFoundError(localClassNotFoundException.getMessage());
    }
  }
}

java动态代理的应用在框架中十分广泛，例如Spring框架用动态代理来实现AOP、Struts2框架利用动态代理实现拦截器。
AOP中的代理逻辑点又称为切面的切入点(cut point)。另外，实现AOP概念的方式是动态代理，但动态代理的形式有很多种，JDK提供的这种只是其中一种，还有涉及到类加载器加载类前、加载类后植入字节码等形式。

在日常开发中我们经常会批量操作数据，因此很多高级语言除了提供数组，还给我们提供很多高级的、抽象的数据类型来让我们处理批量数据时得心应手。由于这些轮子对于程序的性能是比较关键的轮子，因此很多语言都内置的提供了比较精致的实现。在java中，这种实现被称为集合框架。集合框架包含的接口、类十分丰富，而且功能强大，因此理解并熟悉java集合框架，对于写出正确高效的程序是十分有必要的。java集合框架中包含两个重要的类LinkedHashMap与HashMap，它们常常被用于按key-value存储、操作数据，对于常见的操作都是常数的时间复杂度，因此被广泛使用，虽然这两个类的作用类似，但是他们的实现和使用场景稍微不同。

2. 二者的区别

HashMap与LinkedHashMap都实现了Map接口，二者的存储形式都是采用**bucket加链表**的形式来进行存储的。二者的主要区别:

HashMap由于是按照key的hash值映射到对应的bucket中，无法保证遍历HashMap时的顺序是预期的顺序
LinkedHashMap在HashMap的基础上加以改进，却可以保证遍历的顺序要么是插入item的顺序或者LRU访问的顺序

这是因为LinkedHashMap维护了一个双向链表来记录数据插入的顺序，因此在迭代遍历生成的迭代器的时候，是按照双向链表的路径进行遍历的。

如果选择LRU访问的顺序，LinkedHashMap对于访问过的item会将其移动到双链表的末尾，这样保证最近访问过的item是处于链表末端，因此较老其不经常使用的item会处于链表前端。这个特性恰好符合LRU的思想，因此LinkedHashMap可以用来实现**LRU Cache**。Android提供的SDK的LruCache类便是利用LinkedHashMap实现了基于Lru规则的缓存功能。

另外可以发现在java8中HashMap和LinkedHashMap有了改动，据说在某些Hash碰撞严重时，性能也不会太差。java8之前的Map实现的问题是当出现某个bucket的后面的链表太长了，也就是说发生hash冲突的item太多了，这样会导致访问操作退化到了O(n)。

java8的改进便是当bucket的链表长度大于阈值的时候，会将链表重新组织为一颗红黑树，这样在hash碰撞严重的时候性能还是可以保证到log(n).改进前后的示意图如下所示：

这里写图片描述

在使用LinkedHashMap和HashMap的时候应该注意Key的hash值是怎么取得，如果不同的key经常出现相同的hash值，则会频繁出现冲突，降低性能。

同时，由于改进后的HashMap会在某个bucket后的链表长度超过某个阈值时，重新将连边组织为一颗红黑树，因此在java8上的key最好实现Comparable接口来保证key是可以通过compareTo进行比较的，因为这样会简化建立红黑树的判断流程，提高效率。当然如果不实现Comparable接口的话，也会有相应的方法保证hash值冲突的item形成一颗平衡的红黑树。

3. 源码阅读

此处选取几个关键的地方进行源码分析：

对于HashMap重点关注这几个方法

1	final void treeifyBin(Node<K,V>[] tab, int hash)

1	public V put(K key, V value)

1	final void treeify(Node<K,V>[] tab)

1	static int tieBreakOrder(Object a, Object b)


public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
           boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
//通过hash找到对应的桶，如果桶空则直接新建一个链表节点置于桶中并成为链表头
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
else {//桶不为空，则从桶内存放的链表头开始查找
    Node<K,V> e; K k;
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))//运气好的话，在链表头就找到了，注意此处key的匹配规则，首先是 == 匹配，然后再是调用equals方法匹配
        e = p;
    else if (p instanceof TreeNode)//如果该桶内存放的不再是链表，而是一颗树，则按树的规则去执行。
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    else {
        for (int binCount = 0; ; ++binCount) {//按链表顺序查找，并记录链表的节点数目
            if ((e = p.next) == null) {//如果查找到了链表尾，认为匹配到key,则新建一个节点
                p.next = newNode(hash, key, value, null);
                //java8改进的地方！！！！如果桶内链表的长度大于了阈值则树形化该链表
                if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                    treeifyBin(tab, hash);
                break;
            }
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))//匹配到一个存在的item
                break;
            p = e;
        }
    }
    //如果成功匹配了key，则此次put操作仅仅是修改value而没有插入新的节点
    if (e != null) { // existing mapping for key
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
            e.value = value;
        afterNodeAccess(e);//访问元素e的回调，注意比较LinkedHashMap在此处的实现。
        return oldValue;
    }
}
++modCount;
if (++size > threshold)//如果真个hashmap的长度超过了阈值，就说明可能会出现严重的hash冲突此时就应该resize()，rehash。
    resize();
afterNodeInsertion(evict);//插入元素e的回调，注意比较LinkedHashMap在此处的实现。
return null;
}


/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//如果Hash表的桶数小于可以树形化的阈值，则只是扩大桶数，进行再Hash
//我估计在设计的时候权衡了重建一颗红黑树和再Hash的cost，当桶的数量很少的时候，再hash划算一些
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
    TreeNode<K,V> hd = null, tl = null;
    do {
        //从链表头hd,将每一个节点转化为一个树节点且继续保持链表的顺序
        TreeNode<K,V> p = replacementTreeNode(e, null);
        if (tl == null)
            hd = p;
        else {
            p.prev = tl;
            tl.next = p;
        }
        tl = p;
    } while ((e = e.next) != null);
    if ((tab[index] = hd) != null)
        hd.treeify(tab);//最终树形化链表在这里完成
}
}


/**
 * Forms tree of the nodes linked from this node.
 * @return root of tree
 */
final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    //以当前对象作为root，开始构建一颗红黑树
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null;
        if (root == null) {
            x.parent = null;
            x.red = false;
            root = x;
        }
        else {
            K k = x.key;//当前树节点x包含的key
            int h = x.hash;//当前树节x点的hash值
            Class<?> kc = null;//x节点包含的key的类
            //从红黑树的根节点开始寻找合适的插入的位置，然后再平衡该树。
            for (TreeNode<K,V> p = root;;) {
                int dir, ph;
                K pk = p.key;
                //正常来讲，由于HashMap是树形化一个桶内的链表，因此
                //每个链表的节点的hashCode()返回的值应该是一样的。
                //因此这里两个分支(ph = p.hash) > h 和 ph < h应该都不会被执行
                //这里会直接进入分支3进行判断
                if ((ph = p.hash) > h)//分支1
                    dir = -1;
                else if (ph < h)//分支2
                    dir = 1;
                   //分支3 当两个节点的hash值相等的时候（事实上绝大部分都是这样的情况）
                    //则反射判断x节点的key的类是否是实现了Comparable接口，如果实现了则利用compareTo方法进行比较判断，从而决定插入的位置；
                    //如果没有实现Comparable接口或者实现了Comparable接口但是compareTo比较的结果还是一致，则利用tieBreakOrder来决定大小。
                    //因为红黑树的节点都要有大小区分的，不能出现大小相同的节点，因此无论采用哪种量化方式，一定得比较个大小出来。
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);//当俩节点hashCode返回值相等且没有实现comparable接口，在这种尴尬僵持的局面，就需要调用tieBreakOrder方法
                //来一较高低了。因此java8中对于HashMap的文档中建议Key要实现Comparable接口，这样此处就不会进入到如此尴尬僵持的局面，会提高些许性能，毕竟后面
                //打破僵局是需要付出代价的

                TreeNode<K,V> xp = p;
                //直到走到叶节点，则进行插入
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;//如果该节点x比父亲节点p小，则作为节点p的左孩子
                    else
                        xp.right = x;
                    root = balanceInsertion(root, x);//红黑树都有的操作，插入节点后需要进行调整以继续保证红黑树的性质
                    break;
                }
            }
        }
    }
    moveRootToFront(tab, root);//保证桶内存放的是红黑树的根节点root
}

/**
 * Forms tree of the nodes linked from this node.
 * @return root of tree
 */
final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    //以当前对象作为root，开始构建一颗红黑树
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null;
        if (root == null) {
            x.parent = null;
            x.red = false;
            root = x;
        }
        else {
            K k = x.key;//当前树节点x包含的key
            int h = x.hash;//当前树节x点的hash值
            Class<?> kc = null;//x节点包含的key的类
            //从红黑树的根节点开始寻找合适的插入的位置，然后再平衡该树。
            for (TreeNode<K,V> p = root;;) {
                int dir, ph;
                K pk = p.key;
                //正常来讲，由于HashMap是树形化一个桶内的链表，因此
                //每个链表的节点的hashCode()返回的值应该是一样的。
                //因此这里两个分支(ph = p.hash) > h 和 ph < h应该都不会被执行
                //这里会直接进入分支3进行判断
                if ((ph = p.hash) > h)//分支1
                    dir = -1;
                else if (ph < h)//分支2
                    dir = 1;
                   //分支3 当两个节点的hash值相等的时候（事实上绝大部分都是这样的情况）
                    //则反射判断x节点的key的类是否是实现了Comparable接口，如果实现了则利用compareTo方法进行比较判断，从而决定插入的位置；
                    //如果没有实现Comparable接口或者实现了Comparable接口但是compareTo比较的结果还是一致，则利用tieBreakOrder来决定大小。
                    //因为红黑树的节点都要有大小区分的，不能出现大小相同的节点，因此无论采用哪种量化方式，一定得比较个大小出来。
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);//当俩节点hashCode返回值相等且没有实现comparable接口，在这种尴尬僵持的局面，就需要调用tieBreakOrder方法
                //来一较高低了。因此java8中对于HashMap的文档中建议Key要实现Comparable接口，这样此处就不会进入到如此尴尬僵持的局面，会提高些许性能，毕竟后面
                //打破僵局是需要付出代价的

                TreeNode<K,V> xp = p;
                //直到走到叶节点，则进行插入
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;//如果该节点x比父亲节点p小，则作为节点p的左孩子
                    else
                        xp.right = x;
                    root = balanceInsertion(root, x);//红黑树都有的操作，插入节点后需要进行调整以继续保证红黑树的性质
                    break;
                }
            }
        }
    }
    moveRootToFront(tab, root);//保证桶内存放的是红黑树的根节点root
}


/**
 * Tie-breaking utility for ordering insertions when equal
 * hashCodes and non-comparable. We don't require a total
 * order, just a consistent insertion rule to maintain
 * equivalence across rebalancings. Tie-breaking further than
 * necessary simplifies testing a bit.
 */
static int tieBreakOrder(Object a, Object b) {
    int d;
    if (a == null || b == null ||
        (d = a.getClass().getName().
         compareTo(b.getClass().getName())) == 0)//先利用两对象的类名的大小比较，若仍然陷入僵局，则调用
        //System.identityHashCode()的方法该方法会返回对象唯一的真实的hash值无论对象的类是否重写了hashCode方法
        d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
             -1 : 1);
    return d;
}

以上部分简要的分析了HashMap的改进处的源码。

对于LinkedHashMap,主要阅读分析其如何保证迭代的顺序、具有LRU的性质
LinkedHashMap是HashMap的子类，只是稍加改造便使得其具有链表的顺序性质。

1
2
3


public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>


/**
* The head (eldest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> head;//维护的双向链表的
/**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> tail;//维护的双向链表的表尾

/**
* The iteration ordering method for this linked hash map: <tt>true</tt>
* for access-order, <tt>false</tt> for insertion-order.
*
* @serial
*/
final boolean accessOrder;//是访问顺序还是插入顺序

主要关注以下几个方法：

1	Node<K,V> newNode(int hash, K key, V value, Node<K,V> e)

1 2	private void linkNodeLast(LinkedHashMap.Entry<K,V> p)

1
2
3


void afterNodeAccess(Node<K,V> e)

1
2
3


void afterNodeInsertion(boolean evict)

1
2
3


protected boolean removeEldestEntry(Map.Entry<K,V> eldest)

//这个方法是HashMap的hook方法，只是简单的扩展了HashMap的Node类，就完成了LinkedHashMap的大部分功能
//不得不说类的设计很巧妙
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
    new LinkedHashMap.Entry<K,V>(hash, key, value, e);//将节点e
linkNodeLast(p);//将该Entry链接到LinkedHashMap维护的双向链表的表尾
return p;
}

/**
* HashMap.Node subclass for normal LinkedHashMap entries.
*/
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
    super(hash, key, value, next);
}
}

// link at the end of list
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;//tail是维护的双链表的表尾
tail = p;
//接下就是简单的链表链接操作
if (last == null)
    head = p;
else {
    p.before = last;
    last.after = p;
}
}

由于LinkedHashMap没有重写put方法，因此它复用了HashMap的put方法，只是简单重写了**hook方法**newNode。因此put方法不用分析了。到此应该就可以去看迭代器的实现了，讲道理的话应该是按照双向链表的顺序来迭代的。


abstract class LinkedHashIterator {
LinkedHashMap.Entry<K,V> next;
LinkedHashMap.Entry<K,V> current;
int expectedModCount;

LinkedHashIterator() {
    next = head;//head存放的是双向链表的表头
    expectedModCount = modCount;
    current = null;
}

public final boolean hasNext() {
    return next != null;
}

final LinkedHashMap.Entry<K,V> nextNode() {
    LinkedHashMap.Entry<K,V> e = next;
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    if (e == null)
        throw new NoSuchElementException();
    current = e;
    next = e.after;//依次迭代
    return e;
}
}

自此已经大致清楚了LinkedHashMap是如何简单的改造了HashMap而拥有了顺序的迭代。

LinkedHashMap不仅仅遍历是有序的，而且还可以选择是何种顺序，是插入顺序还是访问顺序。

acceeOrder的定义了遍历是何种顺序，该值默认是false,若想为true,需要显示的指定。


void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
//如果是访问顺序，则将节点e放在链表尾部
if (accessOrder && (last = tail) != e) {
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    p.after = null;
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a != null)
        a.before = b;
    else
        last = b;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
    tail = p;
    ++modCount;
}
}

这样无论是put还是get操作都会导致该元素e会被放在链表尾部。这样链表表头部分的元素的访问时间就相对久远了，这个特性就恰恰比较符合LRU的思想。因此当LinkiedHashMap的元素个数超过一定的阈值时（因为缓存的容量是有限的），就需要删除某些缓存item了。在LinkedHashMap中就有这样的CallBack来完成这个目的。


void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
//如果该LinkedHashMap允许删除老元素，则移除老元素
if (evict && (first = head) != null && removeEldestEntry(first)) {
    K key = first.key;
    removeNode(hash(key), key, null, false, true);
}
}

LinkedHashMap默认是不移除老元素，因此要实现Lru需要重写该方法。


protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
}

通常会这么重写

private static final int MAX_ENTRIES = 100;

protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_ENTRIES;
}

可以看出来LinkedHashMap只是稍微加以改进，就具备了额外的功能。这种类的设计十分精致，值得借鉴。
HashMap预留了几个关键的hook方法给扩展类(此处是LinkedHashMap)，例如newNode(),afterAccess() afterInsertion()等。这样就是策略和机制分离了，便于扩展类添加更丰富的功能。当然我们也可以按照需要扩展HashMap,从而改变其某些行为。

但是HashMap类中的TreeNode怎么会去继承子类LinkedHashMap的Entry，难道仅仅是为了少些几行代码？我觉得这个设计不是很好。毕竟父类不应该去获取子类的某些信息，有点本末倒置。

/**
* Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
* extends Node) so can be used as extension of either regular or
* linked node.
*/
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {

4. Best Practices

在使用HashMap时应该尽量保证key的hashCode返回值分布均匀性；在java8上使用时key应该尽量实现comparable接口。
LinkedHashMap和HashMap性能的比较:在基本的put get remove操作，两者的性能几乎相近，由于LinkedHashMap维护着一个双向链表，因此性能可能稍微差一点点。但是在迭代遍历的时候，因为LinkedHashMap遍历的所有的插入的元素，而HashMap是遍历的整个HashMap（包括一些空桶），因此LinkedHashMap的性能稍微优于HashMap。
LinkedHashMap可以保持任意的Map的顺序信息，就像这样使用：


void foo(Map m) {
        Map copy = new LinkedHashMap(m);
        ...
  }

常用算法策略之回溯法

发表于 2017-03-12 更新于 2025-09-24 分类于数据结构与算法

1.回溯法简介

回溯法，又称试探法，是常用的，基本的优选搜索方法。常用于解决这一类问题：给定一定约束条件F（该约束条件常用于后面的剪枝）下求问题的一个解或者所有解。

回溯法其实是暴力枚举的一种改进，因为其会聪明的filter掉不合适的分支，大大减少了无谓的枚举。若某问题的枚举都是可行解得话，也就是没有剪枝发生，那么回溯法和暴力枚举并无二异。

该回溯法先从解空间中选取任意一个可能满足约束条件F的点x1,然后从满足F的解空间中继续选择一个点x2，直到所找到的点构成一个解S或者找不到满足约束条件F的点时，开始回溯。回溯到上一层节点f，再另选满足F的解空间中的一点，继续试探。

整个过程类似于一个递归树，因此回溯法常常采用DFS的方法来实现。不考虑约束条件F，整个递归树的任一根节点root到叶子节点leaf的路径path都是无约束条件F的原问题的一个解。

现在考虑约束条件F，实际就是在每次向下深入的时候，利用约束条件F来判断当前遍历的节点是否有必要继续搜索下去,若无必要则马上回溯；有必要则继续深入，这一个过程类似于约束条件F剪去了多余的递归分支。

回溯法解决的问题的一般特征：能够利用约束条件F去快速判断构成一个完整解的一些局部候选信息partial candidates是否可能最终构成一个正确的、完整的解。

2.回溯法的基本步骤

明确问题的解空间S和约束条件F.
利用深度优先搜索，试探可能构成一个完整解的候选节点，利用约束条件F进行剪枝
2.1. 找到递归的base case
2.2. 利用约束条件F判断是否剪枝，一旦剪枝，则开始回溯（返回）
当递归到叶节点的时候，即得到原问题在约束条件F下的一个解，若要得到所有的可行解，则还需要考察根节点的其他分支。

回溯法注意事项：

递归状态的存储和更新
回溯点的处理（是否应该清除该回溯点之前对递归状态产生的side effect）
解的搜集

3.回溯法之经典问题

回溯法之经典问题：N皇后问题

public class NQueensDemo {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		NQueensDemo demo = new NQueensDemo();
		demo.solution(8);
	}

	public void solution(int n) {
		List<int[]> collector = new ArrayList<>();
		for (int j = 0; j < n; j++)
			dfs(0, j, new int[n], new int[n], new int[n], new int[n * 2 - 1], new int[n * 2 - 1], collector, n);
		System.out.println("numbers of solution " + collector.size());
		print(collector, n);
	}

	public void dfs(int i, int j, int[] solution, int[] occupiedRow, int[] occupiedCol, int[] occupiedTopBottom,
			int[] occupiedBottomTop, List<int[]> collector, int size) {
		solution[i] = j;
		if (i >= size - 1) {
			collector.add(solution.clone());
			return;
		}

		// 8个方向
		occupiedRow[i] = 1;
		occupiedCol[j] = 1;
		occupiedTopBottom[size - 1 + (i - j)] = 1;// 左上到右下的斜线 (i+d, j+d) 关系为i-j,
													// 范围为 -size + 1 ~ size - 1,
													// 所以左右各加size - 1归到区间
													// 0~2size - 2, 关系为 size - 1
													// + (i - j), 分配的数组大小为 2size
													// - 1
		occupiedBottomTop[i + j] = 1;// 左下到右上的斜线(i-d, j+d)和(i+d, j-d) 关系为 i+j
										// 分配的数组大小为 2size - 1

		// 寻找下一个皇后放置的位置
		i = i + 1;
		for (int n = 0; n < size; n++) {
			if (occupiedRow[i] == 0 && occupiedCol[n] == 0 && occupiedTopBottom[size - 1 + (i - n)] == 0
					&& occupiedBottomTop[i + n] == 0)
				dfs(i, n, solution, occupiedRow, occupiedCol, occupiedTopBottom, occupiedBottomTop, collector, size);
		}

		// 回溯后, clear flag，恢复原状
		i = i - 1;
		occupiedRow[i] = 0;
		occupiedCol[j] = 0;
		occupiedTopBottom[size - 1 + (i - j)] = 0;
		occupiedBottomTop[i + j] = 0;
	}

	public void print(List<int[]> collector, int n) {
		for (int[] s : collector) {
			System.out.println();
			for (int i = 0; i < n; i++) {
				System.out.println();
				for (int j = 0; j < n; j++) {
					if (j == s[i])
						System.out.print(1 + "  ");
					else
						System.out.print(0 + "  ");
				}
			}
		}
	}

}

4.回溯法之经典问题：Sudoku（数独）


public class Solution {
   public final char base = '1';
	public void solveSudoku(char[][] board) {
		int filledNum = 0;// 统计已填的数目，作为DFS搜索结束的条件
		int m = 0, n = 0;
		int[][] rowCount = new int[9][9], colCount = new int[9][9], subBoxCount = new int[9][9];

		for (m = 0; m < 9; m++)
			for (n = 0; n < 9; n++)
				if (board[m][n] != '.') {
					rowCount[m][board[m][n] - base] += 1;
					colCount[n][board[m][n] - base] += 1;
					subBoxCount[m / 3 * 3 + n / 3][board[m][n] - base] += 1;
					filledNum++;
				}

		boolean found = false;
		for (m = 0; m < 9; m++) {// 找到第一个待填的方格
			for (n = 0; n < 9; n++)
				if (board[m][n] == '.') {
					found = true;
					break;
				}
			if (found)
				break;
		}

		for (int num = 0; num < 9; num++)
			if (rowCount[m][num] == 0 && colCount[n][num] == 0 && subBoxCount[m / 3 * 3 + n / 3][num] == 0)
				if (dfs(m, n, (char) (num + base), board, rowCount, colCount, subBoxCount, filledNum))
					break;
	}

	public boolean dfs(int i, int j, char c, char[][] board, int[][] rowCount, int[][] colCount, int[][] subBoxCount,
			int filledNum) {

		int number = c - base;// 0~8代表1~9
		board[i][j] = c;
		rowCount[i][number] += 1;
		colCount[j][number] += 1;
		subBoxCount[i / 3 * 3 + j / 3][number] += 1;
		filledNum += 1;

		// bas case
		if (filledNum >= 81)
			return true;

		int m = i, n = j;
		boolean found = false;
		// 找到下一个待填方格
		for (; m < 9; m++) {
			for (; n < 9; n++) {
				if (board[m][n] == '.') {
					found = true;
					break;
				}
			}
			if (found)
				break;
			else
				n = 0;
		}

		for (int num = 0; num < 9; num++) {
			if (rowCount[m][num] == 0 && colCount[n][num] == 0 && subBoxCount[m / 3 * 3 + n / 3][num] == 0) {
				if (dfs(m, n, (char) (num + base), board, rowCount, colCount, subBoxCount, filledNum))
					return true;
			}
		}

		// failed 该格子无论填啥都无解,所以clear所做的更改
		board[i][j] = '.';
		rowCount[i][number] -= 1;
		colCount[j][number] -= 1;
		subBoxCount[i / 3 * 3 + j / 3][number] -= 1;
		filledNum -= 1;

		return false;
	}
}

JVM内存区域（二）

1. 对象的创建

1.1

1.2

1.3

2. 对象的内存布局

3. 对象的访问定位

JVM内存区域（一）

1. 运行时内存区域分类

2. 运行时内存区域含义

1.简介

2.原理

3.改进

4.应用

5.References

1. IO复用

2. I/O模型

2.1 阻塞IO

2.2 非阻塞IO

2.3 IO复用

2.4 信号驱动IO

2.5 异步IO

2.6 同步IO与异步IO

2.7 5种IO模型的Java示例

3. 总结

4. References

含义

区分

1.堆

2.堆的应用：堆排序

3.堆的应用：优先队列

4 堆的应用：海量实数中（一亿级别以上）找到TopK（一万级别以下）的数集合。

5 总结

6 references

1. 简介

2. 最长公共子串问题

3. 最长公共子序列问题

4. References

一、代理简介

二、Java语言的代理

静态代理

动态代理

比较静态代理和动态代理

静态代理

动态代理

三、Java动态代理源码分析

See Also

1. 简介

2. 二者的区别

3. 源码阅读

4. Best Practices

1.回溯法简介

2.回溯法的基本步骤

3.回溯法之经典问题

4.回溯法之经典问题：Sudoku（数独）

`JVM`内存区域（二）

`JVM`内存区域（一）