All Permutations(Recursive)

该算法采用DFS递归的方法，每次从当前元素出发，依次与它后面的元素交换，到序列结尾时表示完成一次全排列，输出结果。注意，每次递归返回后再把元素交换回来，否则会出现重复序列。该算法时间复杂度为O(n!)，序列不是递增的。例如对“123”全排列的结果为：123 132 213 231 321 312。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

private void swap(StringBuilder sb, int i, int j) {
        char c = sb.charAt(i);
        sb.setCharAt(i, sb.charAt(j));
        sb.setCharAt(j, c);
}
public void nextPermutation(StringBuilder sb, int start) {
    if(start == sb.length())
        println(sb);
    for (int i = start; i < sb.length(); ++i) {
        swap(sb, start, i);
        nextPermutation(sb, start + 1);
        swap(sb, start, i);
    }
}

Linux系统结构

Linux系统结构如图所示，位于最内层的kernel管理计算机的硬件资源，提供硬件访问、内存管理、进程调度、文件管理、用户管理和网络等系统服务。为了保护系统，进程不能直接访问内核的内存空间和内核函数，当进程需要内核提供的服务时，通过内核与外界的接口（也就是系统调用）来实现。

用户态和内核态

进程运行的状态可以分为内核态和用户态，当进程处于内核态时，它可以访问内核的内存空间和硬件资源；当进程处于用户态时，进程只能访问用户空间的内存空间，不能访问内核内存空间和硬件资源，不能关闭中断。用户态到内核态的切换有三种方式：

1. 系统调用，当用户态通过系统调用申请使用系统服务时，进程由用户态切换到内核态
2. 异常，当CPU在执行运行在用户态下的程序时，发生了某些事先不可知的异常，这时会触发由当前运行进程切换到处理此异常的内核相关程序中，也就转到了内核态，比如缺页异常。
3. 外围设备中断，当外围设备完成用户请求的操作时，会向CPU发送相应的中断信号，如果此时进程处于用户态，将切换到内核态。

系统调用的实现

系统调用通过软件中断的方式实现，每个系统调用都有相应的系统调用号作为唯一的标识，内核维护一张系统调用表，表中的元素是系统调用函数的起始地址，而系统调用号就是系统调用在调用表的偏移量。在进行系统调用是只要指定对应的系统调用号，就可以明确的要调用哪个系统调用。对于参数传递，Linux是通过寄存器完成的。Linux最多允许向系统调用传递6个参数，分别依次由%ebx，%ecx，%edx，%esi，%edi和%ebp这个6个寄存器完成。

在用户态和内核态运行的进程使用的栈是不同的，分别叫做用户栈和内核栈，两者各自负责相应特权级别状态下的函数调用。当进行系统调用时，进程不仅要从用户态切换到内核态，同时也要完成栈切换，这样处于内核态的系统调用才能在内核栈上完成调用。系统调用返回时，还要切换回用户栈，继续完成用户态下的函数调用。

寄存器%esp（栈指针，指向栈顶）所在的内存空间叫做当前栈，比如%esp在用户空间则当前栈就是用户栈，否则是内核栈。栈切换主要就是%esp在用户空间和内核空间间的来回赋值。在Linux中，每个进程都有一个私有的内核栈，当从用户栈切换到内核栈时，需完成保存%esp以及相关寄存器的值（%ebx，%ecx…）并将%esp设置成内核栈的相应值。而从内核栈切换会用户栈时，需要恢复用户栈的%esp及相关寄存器的值以及保存内核栈的信息。一个问题就是用户栈的%esp和寄存器的值保存到什么地方，以便于恢复呢？答案就是内核栈，在调用int指令机型系统调用后会把用户栈的%esp的值及相关寄存器压入内核栈中，系统调用通过iret指令返回，在返回之前会从内核栈弹出用户栈的%esp和寄存器的状态，然后进行恢复。

自动内存管理的优缺点

优点

在C/C++等语言中，内存管理是程序员的责任，程序员需要在内存的分配和释放上花费大量的时间，手动内存管理过程中容易出现以下问题：

1. 悬垂指针问题（Dangling references，tries to access the original object, but the space has been reallocated to a new object, the result is unpredictable and not what was intended）
2. 内存泄露问题（Memory/Space Leaks， memory is allocated and no longer referenced but not released)
   包括Java在内的现代面向对象语言中都提供了自动内存管理机制，垃圾回收器保证正在使用的对象不会被回收从而解决悬垂指针问题；通过自动释放不再使用对象占用的内存空间来解决内存泄露问题。内存管理机制有助于程序员将精力集中在业务实现上并且可以写出更加可靠的代码。

缺点

自动内存管理机制的缺点在于，垃圾回收器本身需要CPU时间和其它资源，从一定程度上降低了性能。

垃圾回收器的职责

在JVM运行时数据区中，线程私有的虚拟机栈，本地方法栈和程序计数器随着线程的启动而创建，线程结束后资源就被回收了，所以一般不需要对线程私有的数据进行垃圾回收。JVM主要对各线程共享的方法区和堆进行垃圾回收，方法区（也叫永久代）中的垃圾主要包括废弃的常量和无用的类，由于永久代垃圾回收的效率较低，一般在大量使用反射、动态代理、CGLib等ByteCode框架、动态生成JSP以及OSGI这类频繁自定义ClassLoader是场景下使用，垃圾回收器的工作主要包括：

1. 分配内存
2. 保证所有被引用的对象保存在内存中
3. 回收从正在执行的代码中引用的对象出发不可达的对象占用的空间

JVM在执行Java程序时会将它管理的内存划分为若干个不同的数据区域，这些区域有各自的用途以及创建和销毁的时间。有的区域随着虚拟机进程的启动而存在，有的区域则依赖用户线程的启动和结束而创建和销毁。根据《Java虚拟机规范》的规定，Java虚拟机所管理的内存将包括以下几个运行时数据区域，其中方法区和堆由所有线程共享；虚拟机栈，本地方法栈和程序计数器是线程似有的。

堆

堆（heap）和方法区(Method Area)被JVM内的所有线程共享，堆中存放的是类的对象和数组。对大多数应用来说，Java堆是JVM管理的内存中最大的一块。堆在JVM启动时创建，几乎所有的对象实例和数组都从堆中分配内存。这里的堆并不是数据结构意义上的堆（heap，有序树），而是动态内存分配意义上的堆——用于管理动态生命周期的内存区域。
堆是垃圾回收器管理的主要区域，因此很多时候也被成为“GC堆”。由于垃圾回收器基本都采用分代收集算法，堆还可以细分为：新生代和老年代；再细致一点还可以分为Eden区、From Survivor区、To Survivor区等。无论怎么划分，堆中存放的都是对象实例，进一步划分的目的是为了更好地回收内存、更快地分配内存。
根据Java虚拟机规范，Java堆可以处于物理上不连续的内存空间中，只要逻辑上连续即可。当前主流虚拟机都是可扩展的，通过-Xmx和-Xms控制堆的大小。如果堆中没有内存完成实例分配，并且堆也无法再扩展时，将会抛出OutOfMemoryError异常。

方法区

方法区(Method Area)用于储存被虚拟机加载的类信息，常量，即时编译后的代码等，类似于其它语言中存放编译后代码的区域以及操作系统中线程的text字段。对于HotSpot来说，方法区也可以当做“永久代（Permanent Generation）”，因为分代收集也扩展到了该区域，垃圾收集器可以像管理Java堆一样管理方法区内存。JDK1.7的HotSpot中，已经把原本放在永久代的字符串常量池移除。
垃圾收集行为在方法区是比较少见的，但并不是说方法区的数据会永久存在。该区域内存回收的主要目的是针对常量池的回收和对类型的卸载，不过方法区内存回收的条件是非常苛刻的。
当方法区无法满足内存分配需求时，将抛出OutOfMemoryError异常。

JDK1.2～JDK1.6的实现中，Hotspot使用永久代实现方法区。

从JDK7开始移除永久代，JDK7中符号表被移动到Native Heap中，字符串常量和类引用被移动到Java Heap中。

JDK8中，方法区移到元空间（Metaspace），字符串常量移到Java Heap。元空间在本地堆内存（native heap）中，默认类的元数据分配只受本地内存大小限制。

运行时常量池

Java内存模型（Java Memory Model）是一组类似硬件体系结构内存模型的规范，这些规范描述了Java语言编写多线程程序的语义，这些语义可以解决多线程对共享变量读写时的可见性、原子性和有序性问题。

背景

1. 在Java之前的编程语言（例如C，C++）直接使用操作系统的内存模型，不同平台的差异性会导致程序出现运行结果不一致或者移植性问题。为了屏蔽不同平台的底层差异，实现“一次编写，到处运行（WORA，Write once， run anywhere）”，Java定义了一个内存模型（JMM，Java Memory Model）。
2. 在命令式编程中，有两种并发编程模型：共享内存和消息传递，Java中采用了共享内存的方式。Java内存模型将内存抽象成主内存和工作内存，内存模型规定了一个变量何时对一个变量可见，实例字段、静态字段这些线程间共享的变量存放在主内存中，被线程使用的共享变量副本、局部变量和方法参数存放在线程各自的本地工作内存中。对变量的修改都是在各线程内部的工作内存中进行的，各线程通过从主内存中读写共享变量实现线程间通信，Java内存模型通过控制主内存与各线程之间的交互提供变量可见性的保证。

重排序

为了提高程序的并行度，编译器和处理器会对指令进行重排序，重排序主要分为如下三种：

1. 编译器重排序：在不影响单线程语义的情况下重新安排语句的执行顺序
2. 指令级并行重排序（Instruction-Level Paralellism， ILP）：在指令不存在依赖的情况下，重新安排指令的执行顺序，以提高流水线效率。
3. 内存系统重排序：由于处理器使用缓存和读写缓冲区，为了提高命中率会重新对指令排序。

这些重排序可能导致一些内存可见性问题，JMM禁用一些特定的编译器重排序规则，并通过编译器编译时插入特定类型的内存屏障（memory barriers，intel称之为memory fence）指令来禁止特定的处理器重排序。JMM属于语言级的内存模型，它确保在不同的编译器和不同的处理器平台之上，通过禁止特定类型的编译器重排序和处理器重排序，为程序员提供一致的内存可见性保证。

由于写缓冲区仅对自己的处理器可见，它会导致处理器执行内存操作的顺序可能会与内存实际的操作执行顺序不一致。由于现代的处理器都会使用写缓冲区，因此现代的处理器都会允许对写-读操作重排序。

本文中ConcurrentHashMap源码分析基于jdk1.7，与jdk1.8中ConcurrentHashMap的实现有很大差别，在学完《Java并发编程实战》和《Linux程序设计》之后如果有时间再具体研究jdk1.8中新的锁和并发机制。（http://ifeve.com/jdk1-8-abstractqueuedsynchronizer/）

背景知识

与ConcurrentHashMap类似的Java Conllections还有Hashtable和HashMap，HashMap不是一个线程安全的类，key和value的值都可以是null，ConcurrentHashMap和HashMap都是线程安全的类，但是key和value的值都不能是null。Hashtable保证线程安全的做法是每个可调用的方法都是synchronized的。这意味着每个线程访问Hashtable时都会把整个Hashtable锁起来。ConcurrentHashMap则采用了分段锁（Segment）的机制，使得竞态条件只发生在Segment内，增加了并发度；同时，在HashMap.Entry的基础上进行改进，ConcurrentHashMap.Entry的value和next域都是volatile的，可以保证在多线程环境下对于其他线程的可见性。由于ConcurrentHashMap不是对整个表加锁，在执行size()这些全局性质的方法时需要遍历整个Segment数组。

HashEntry<K, V>类

HashEntry 用来封装散列映射表中的键值对

1
2
3
4
5
6

static final class HashEntry<K, V> {
        final int hash;
        final K key;
        volatile V value;
        volatile ConcurrentHashMap.HashEntry<K, V> next;
    }

在方法区中所占用的内存大小与在栈帧所占用的内存大小不同，因为在方法区中占用内存以字节为最小单位，但是在栈帧中以字为最小单位。如byte类型在方法区中它占用8位，为一个字节，但是在栈帧中以一个字，即32位来处理，其实就是当作一个int类型来处理。
基本数据的类型的大小是固定的，但引用类型对象的大小是可变的，一个空Object对象的大小是8byte，这个大小只是保存堆中一个没有任何属性的对象的大小。

1

Object ob = new Object();

它所占的空间为：4byte+8byte。4byte是上面部分所说的Java栈中保存引用的所需要的空间。而那8byte则是Java堆中对象的信息。因为所有的Java非基本类型的对象都需要默认继承Object对象，因此不论什么样的Java对象，其大小都必须是大于8byte。

1
2
3
4
5

class NewObject {  
int count;  
boolean flag;  
Object ob;  
}

HashMap

HashMap permits null key and null value, HashMap is equivalent to HashTabel except it is unsynchronized and permits nulls. Iteration over collection views requires time proportional to the “capacity” of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings).
An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table.The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. Thus, it’s very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.

Changes in JDK 1.8:The principal idea is that once the number of items in a hash bucket grows beyond a certain threshold, that bucket will switch from using a linked list of entries to a balanced tree. In the case of high hash collisions, this will improve worst-case performance from O(n) to O(log n).This technique has already been implemented in the latest version of the java.util.concurrent.ConcurrentHashMap class, which is also slated for inclusion in JDK 8 as part of JEP 155. Portions of that code will be re-used to implement the same idea in the HashMap and LinkedHashMap classes. Only the implementations will be changed; no interfaces or specifications will be modified. Some user-visible behaviors, such as iteration order, will change within the bounds of their current specifications.

1
2
3
4
5
6
7
8
9

//constructors
HashMap()
//Constructs an empty HashMap with the default initial capacity (16) and the default load factor (0.75).
HashMap(int initialCapacity)
//Constructs an empty HashMap with the specified initial capacity and the default load factor (0.75).
HashMap(int initialCapacity, float loadFactor)
//Constructs an empty HashMap with the specified initial capacity and load factor.
HashMap(Map<? extends K,? extends V> m)
//Constructs a new HashMap with the same mappings as the specified Map.