Ernest

由浅入深地讨论了几种应用中常见的排序算法的思想和实现方法，并对几种算法做了性能测试。 阅读原文 »

The post 排序 appeared first on 头条 - 伯乐在线.

在这个系列的第一部分里，我简单的介绍了非常优秀的Google collections和Guava类库，并简要的解释了作为Java程序员，如果使用Guava库来减少项目中大量的样板代码。在这篇博文中我们将深入挖掘Guava提供的更高级的特性。

我们将深入挖掘Guava库，并了解一下优雅的CharMatcher类、Joiner以及Splitter类，以及在处理Java基本类型时Guava给我们带来的别的工具类。

The Guava CharMatcher

CharMatcher 可以非常方便地添加到你的java工具箱中。有些人形容它：“像打了兴奋剂的StringUtils”:p

你可以使用预先设定好的常量，比如CharMatcher.WHITESPACE, CharMatcher.JAVA_DIGIT 或者CharMatcher.ASCII,此外你还有很多简便的工厂方法如CharMatcher.is(‘aaa’), CharMatcher.isNot(‘bbb’), CharMatcher.oneOf(‘abcd’).negate()，甚至更复杂一些比如：

CharMatcher.inRange('a', 'z').or(inRange('A', 'Z'));

当然你可以继承它然后实现方法 matches(char c)。你可以把 Google Collection中都创造实现一遍(当然下次我们会覆盖到)！

如果你想从字符串中得到所有的数字，那么你可以这样：

String string = CharMatcher.DIGIT.retainFrom("some text 89983 and more");

如果你想把字符串中的数据都去掉，可以如下：

String string = CharMatcher.DIGIT.removeFrom("some text 89983 and more");

还有好多匹配的方法：

matchesAllOf(CharSequence)
matchesAnyOf(CharSequence)
matchesNoneOf(CharSequence)

除了indexIn, lastIndexIn and countIn这些方法，还有很多trimming, replacing and collapsing相关的方法.

更多信息查看Java doc

Joiner and Splitter

目前Joiner还是Collections 的一部分，Splitter 已经加入了Guava (不过一旦Collections 发布1.0版本，那么它们会一起加入到Guava)。

可以这么使用Joiner：

String[] subdirs = { "usr", "local", "lib" };
String directory = Joiner.on("/").join(subdirs);

或者这样：

int[] numbers = { 1, 2, 3, 4, 5 };
 String numbersAsString = Joiner.on(";").join(Ints.asList(numbers));

得益于Guava对基本型的支持，可以很方便这么处理：

String numbersAsStringDirectly = Ints.join(";", numbers);

对于字符串，我们可以直接进行分割，但是这样做多少有些奇怪， Splitter 提供了更多的操作，而且更加健壮。字符创分割通常返回的是一个数组而 Splitter 返回的是一个迭代 Iterable。

Iterable split = Splitter.on(",").split(numbsAsString);

你可以简单地分割字符串：

String[] splitRegular = testString.split(",");

但是当需要处理下面这样的字符串时：

String testString = "foo , what,,,more,";

输出结果是：

‘foo ‘
‘ what’
”
”
‘more

这样的结果也许还可以，但是Splitter允许我们对分割结果做更多的控制：

Iterable<String> split = Splitter.on(",").omitEmptyStrings().trimResults().split(testString);

得到的结果是 foo’,’what’,’more’

Joiner和Splitter都是可配置的，甚至你可以把Joiner使用在map中。

Working with primitives cont’d

在博客的第一部分，我简单提到了基本型的用法。Guava已经提供了诸如Ints.compare(a, b)和Ints.toArray(list)。

让我介绍Guava 关于基本型提供的更多的一些用法吧。

假如我有一个整型数字数组，我们想知道数组中是否有特定的整型数字。传统的写法如下：

int[] array = { 1, 2, 3, 4, 5 };
 int a = 4;
 boolean hasA = false;
 for (int i : array) {
 if (i == a) {
 hasA = true;
 }
 }

使用Guava，我们可以如下：

boolean contains = Ints.contains(array, a);

同样，其他类型的基本型数组也可以这么来做。我们甚至可以直接对数组做如下的事：

int indexOf = Ints.indexOf(array, a);
int max = Ints.max(array);
int min = Ints.min(array);
int[] concat = Ints.concat(array, array2);

在这个系列的下一章我们将关注下 Google Collections library包的更高级特性如：Functions, Filtering and Ordering!欢迎继续收看，请与我们分享你的看法。

相关文章

• Guava 教程(4)：条件，多重映射和分片
• Guava 教程(3)：Java 的函数式编程，通过 Google Collections 过滤和调用
• Guava 教程1-使用 Google Collections,Guava,static imports 编写漂亮代码
• Google Guava的5个鲜为人知的特性
• Guava 是个风火轮之基础工具(3)
• Guava 是个风火轮之基础工具(2)
• Guava 是个风火轮之基础工具(1)
• 为什么手机制造商总是跟不上Android更新的节奏
• 每周学点设计模式——策略模式（上）
• Java EE7和Maven工程入门（7）

最近去面试时，在一家小公司面试时，公司小BOSS给我出了一道算法题： 一个人爬楼梯，一步可以迈一级，二级，三级台阶，如果楼梯有N级，要求编写程序，求总共有多少种走法。 这个问题应该是一个很老的题目了，用中学数学来说，就是一个排列组合问题。当时拿到这个题目之后，首先想到使用递归的思想去解决这个问题： N级楼梯问题可以划分为：N-1级楼梯，N-2级楼梯，N-3级楼梯的走法之和。 阅读原文 »

The post 面试算法题: 爬楼梯问题，N级楼梯有多少种走法？ appeared first on 头条 - 伯乐在线.

镜像链接：谷歌镜像 | 亚马逊镜像

相关日志

• 2015/04/05 -- 刘军洛：美联储加息谎言和大萧条 ( 镜像链接： 亚马逊镜像 | 谷歌镜像 )
• 2015/04/04 -- 真相很残忍：55岁以上人员撑起美国3月惨淡非农就业 ( 镜像链接： 亚马逊镜像 | 谷歌镜像 )
• 2015/04/03 -- 《纽约时报》奥巴马签署行政命令惩罚外国黑客 ( 镜像链接： 亚马逊镜像 | 谷歌镜像 )
• 2015/04/02 -- 《华尔街日报》奥巴马宣布针对海外网络攻击的制裁计划 ( 镜像链接： 亚马逊镜像 | 谷歌镜像 )
• 2015/04/02 -- 博谈网：中国人蜂拥来美生美国公民 ( 镜像链接： 亚马逊镜像 | 谷歌镜像 )
• 2015/04/02 -- 美国经济正在呈现裂纹 ( 镜像链接： 亚马逊镜像 | 谷歌镜像 )
• 2015/04/01 -- 曹长青：谁会是2016美国总统？ ( 镜像链接： 亚马逊镜像 | 谷歌镜像 )
• 2014/09/21 -- 高大上的美国蓝领生活 ( 镜像链接： 亚马逊镜像 | 谷歌镜像 )
• 2014/06/09 -- 《纽约时报》收入不平等的恶性循环 ( 镜像链接： 亚马逊镜像 | 谷歌镜像 )
• 2012/09/12 -- 美帝小小餐馆服务员过的是什么生活… ( 镜像链接： 亚马逊镜像 | 谷歌镜像 )

容器是Java语言学习中重要的一部分。泥瓦匠我的感觉是刚开始挺难学的，但等你熟悉它，接触多了，也就“顺理成章”地知道了。Java的容器类主要由两个接口派生而出：Collection和Map。

一、Collection vs Collections

首先，Collection 和 Collections 是两个不同的概念。之所以放在一起，是为了更好的比较。Collection是容器层次结构中根接口。而Collections是一个提供一些处理容器类静态方法的类。

JDK不提供Collection接口的具体实现，而是提供了更加具体的子接口（如Set和List）实现。

那Collection接口存在有何作用呢？存在即是道理。

原因在于：所有容器的实现类（如ArrayList实现了List接口，HashSet实现了Set接口）提供了两个‘标准’的构造函数来实现：1、一个无参的构造方法（void）2、一个带有Collection类型单参数构造方法，用于创建一个具有其参数相同元素新的Collection及其实现类等。实际上：因为所有通用的容器类遵从Collection接口，用第二种构造方法是允许容器之间相互的复制。

二、Collection的类层次结构

下面的图是关于Collection的类的层次结构。

Set：

一个不包括重复元素（包括可变对象）的Collection，是一种无序的集合。Set不包含满 a.equals(b) 的元素对a和b，并且最多有一个null。实现Set的接口有：EnumSet、HashSet、TreeSet等。下图是Set的JDK源码UML图。

List：

一个有序的Collection（也称序列），元素可以重复。确切的讲，列表通常允许满足 e1.equals(e2) 的元素对 e1 和 e2，并且如果列表本身允许 null 元素的话，通常它们允许多个 null 元素。实现List的有：ArrayList、LinkedList、Vector、Stack等。下图是List的JDK源码UML图。

Queue：

一种队列则是双端队列，支持在头、尾两端插入和移除元素，主要包括：ArrayDeque、LinkedBlockingDeque、LinkedList。另一种是阻塞式队列，队列满了以后再插入元素则会抛出异常，主要包括ArrayBlockQueue、PriorityBlockingQueue、LinkedBlockingQueue。虽然接口并未定义阻塞方法，但是实现类扩展了此接口。下图是Queue的JDK源码UML图。

三、Map的类的层次结构

下面的图是Map的层次结构图

Map：

是一个键值对的集合。也就是说，一个映射不能包含重复的键，每个键最多映射到一个值。该接口取代了Dictionary抽象类。实现map的有：HashMap、TreeMap、HashTable、Properties、EnumMap。下图是Map的JDK源码UML图。

四、容器接口的小结

五、代码样例

对HashMap，HashSet，LinkedList，ArrayList，TreeMap，TreeSet的例子如下：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

@SuppressWarnings("unchecked")
public class CollectionAll
{

    public static void main(String[] args)
    {
        printLists();

        printSets();

        printMaps();
    }

    private static void printLists()
    {
        List<String> a1 = new ArrayList<String>();
        a1.add("List");
        a1.add("Set");
        a1.add("Queue");
        a1.add("Map");
        System.out.println("ArrayList Elements:");
        System.out.print("\t" + a1 + "\n");

        List<String> l1 = new LinkedList<String>();
        l1.add("List");
        l1.add("Set");
        l1.add("Queue");
        l1.add("Map");
        System.out.println("LinkedList Elements:");
        System.out.print("\t" + l1 + "\n");
    }
    @SuppressWarnings("rawtypes")
    private static void printSets()
    {
        Set h1 = new HashSet<String>();
        h1.add("List");
        h1.add("Set");
        h1.add("Queue");
        h1.add("Map");
        System.out.println("HashSet Elements:");
        System.out.print("\t" + h1 + "\n");

        Set t1 = new TreeSet<String>();
        t1.add("List");
        t1.add("Set");
        t1.add("Queue");
        t1.add("Map");
        System.out.println("TreeSet Elements:");
        System.out.print("\t" + t1 + "\n");
    }

    private static void printMaps()
    {
        Map<String, String> h1 = new HashMap<String, String>();
        h1.put("List", "ArrayList");
        h1.put("Set", "HashSet");
        h1.put("Queue", "PriorityQueue");
        h1.put("Map", "HashMap");
        System.out.println("HashMap Elements:");
        System.out.print("\t" + h1 + "\n");

        Map<String, String> t1 = new TreeMap<String,String>();
        t1.put("List", "ArrayList");
        t1.put("Set", "HashSet");
        t1.put("Queue", "PriorityQueue");
        t1.put("Map", "HashMap");
        System.out.println("TreeMap Elements:");
        System.out.print("\t" + t1 + "\n");

    }
}

控制台打印如下：

ArrayList Elements:
    [List, Set, Queue, Map]
LinkedList Elements:
    [List, Set, Queue, Map]
HashSet Elements:
    [Map, Queue, Set, List]
TreeSet Elements:
    [List, Map, Queue, Set]
HashMap Elements:
    {Map=HashMap, Queue=PriorityQueue, Set=HashSet, List=ArrayList}
TreeMap Elements:
    {List=ArrayList, Map=HashMap, Queue=PriorityQueue, Set=HashSet}

六、总结

异同点

出处：http://blog.csdn.net/softwave/article/details/4166598

Vector和ArrayList

1，vector是线程同步的，所以它也是线程安全的，而arraylist是线程异步的，是不安全的。如果不考虑到线程的安全因素，一般用arraylist效率比较高。
2，如果集合中的元素的数目大于目前集合数组的长度时，vector增长率为目前数组长度的100%,而arraylist增长率为目前数组长度的50%.如过在集合中使用数据量比较大的数据，用vector有一定的优势。
3，如果查找一个指定位置的数据，vector和arraylist使用的时间是相同的，都是0(1),这个时候使用vector和arraylist都可以。而如果移动一个指定位置的数据花费的时间为0(n-i)n为总长度，这个时候就应该考虑到使用linklist,因为它移动一个指定位置的数据所花费的时间为0(1),而查询一个指定位置的数据时花费的时间为0(i)。

ArrayList 和Vector是采用数组方式存储数据，此数组元素数大于实际存储的数据以便增加和插入元素，都允许直接序号索引元素，但是插入数据要设计到数组元素移动等内存操作，所以索引数据快插入数据慢，Vector由于使用了synchronized方法（线程安全）所以性能上比ArrayList要差，LinkedList使用双向链表实现存储，按序号索引数据需要进行向前或向后遍历，但是插入数据时只需要记录本项的前后项即可，所以插入数度较快！

Aarraylist和Linkedlist

1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。

2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。

3.对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。

这一点要看实际情况的。若只对单条数据插入或删除，ArrayList的速度反而优于LinkedList。但若是批量随机的插入删除数据，LinkedList的速度大大优于ArrayList. 因为ArrayList每插入一条数据，要移动插入点及之后的所有数据。

HashMap与TreeMap

1、HashMap通过hashcode对其内容进行快速查找，而TreeMap中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用TreeMap（HashMap中元素的排列顺序是不固定的）。HashMap中元素的排列顺序是不固定的）。

2、  HashMap通过hashcode对其内容进行快速查找，而TreeMap中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用TreeMap（HashMap中元素的排列顺序是不固定的）。集合框架”提供两种常规的Map实现：HashMap和TreeMap (TreeMap实现SortedMap接口)。

3、在Map 中插入、删除和定位元素，HashMap 是最好的选择。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。使用HashMap要求添加的键类明确定义了hashCode()和 equals()的实现。 这个TreeMap没有调优选项，因为该树总处于平衡状态。

hashtable与hashmap

1、历史原因:Hashtable是基于陈旧的Dictionary类的，HashMap是Java 1.2引进的Map接口的一个实现 。

2、同步性:Hashtable是线程安全的，也就是说是同步的，而HashMap是线程序不安全的，不是同步的 。

3、值：只有HashMap可以让你将空值作为一个表的条目的key或value 。

可能感兴趣的文章

• HBase数据迁移（2）- 使用bulk load 工具从TSV文件中导入数据
• 使用Specs进行单元测试
• Java垃圾回收精粹 — Part1
• 10个精妙的Java编码最佳实践
• Lucene五分钟教程
• 从Java代码到字节码（1）
• 5步避免Java堆空间错误
• Java 8新特性探究（十）StampedLock将是解决同步问题的新宠
• 管理堆空间：使用JVMTI循环类实例
• 正确使用Java事件通知

感谢网友【张超盟】的投稿

1. 前言

AQS(AbstractQueuedSynchronizer)是 java.util.concurrent的基础。J.U.C中宣传的封装良好的同步工具类Semaphore、CountDownLatch、ReentrantLock、ReentrantReadWriteLock、FutureTask等虽然各自都有不同特征，但是简单看一下源码，每个类内部都包含一个如下的内部类定义：

 abstract static class Sync extends AbstractQueuedSynchronizer 

同时每个类内部都包含有这样一个属性，连属性名都一样！注释已经暗示了，该类的同步机制正是通过这个AQS的子类来完成的。不得不感叹：“每个强大的同步工具类，内心都有一把同样的锁！”

     /** All mechanics via AbstractQueuedSynchronizer subclass */
    private final Sync sync;

几种同步类提供的功能其实都是委托sync来完成。有些是部分功能，有些则是全部功能。 本文中就是想尝试比较分析下在几个同步工具类下面定义的AQS的子类如何来实现工具类要求的功能。当然包括两部分，一部分是这些工具类如何使用其Sync这种类型的同步器，也就是工具类向外提供的方法中，如何使用sync这个句柄；第二部分，就是工具类中自己定义的内部类Sync继承自AQS，那到底override了哪些方法来做到以父类AQS为基础，提供受委托工具类的功能要求。

关于第一部分，sync如何被其工具类使用，请允许我无耻的在一个文章中把一个类所有代码贴出来。

      public void acquire() throws InterruptedException {
        sync.acquireSharedInterruptibly(1);
}
    public void acquireUninterruptibly() {
        sync.acquireShared(1);
    }
    public boolean tryAcquire() {
        return sync.nonfairTryAcquireShared(1) >= 0;
    }
    public boolean tryAcquire(long timeout, TimeUnit unit)
        throws InterruptedException {
        return sync.tryAcquireSharedNanos(1, unit.toNanos(timeout));
    }
    public void release() {
        sync.releaseShared(1);
    }
    public void acquire(int permits) throws InterruptedException {
        if (permits < 0) throw new IllegalArgumentException();
        sync.acquireSharedInterruptibly(permits);
    }
    public void acquireUninterruptibly(int permits) {
        if (permits < 0) throw new IllegalArgumentException();
        sync.acquireShared(permits);
    }
    public boolean tryAcquire(int permits) {
        if (permits < 0) throw new IllegalArgumentException();
        return sync.nonfairTryAcquireShared(permits) >= 0;
    }
    public boolean tryAcquire(int permits, long timeout, TimeUnit unit)
        throws InterruptedException {
        if (permits < 0) throw new IllegalArgumentException();
        return sync.tryAcquireSharedNanos(permits, unit.toNanos(timeout));
    }
    public void release(int permits) {
        if (permits < 0) throw new IllegalArgumentException();
        sync.releaseShared(permits);
    }
    public int availablePermits() {
        return sync.getPermits();
    }
    public int drainPermits() {
        return sync.drainPermits();
    }
    protected void reducePermits(int reduction) {
	if (reduction < 0) throw new IllegalArgumentException();
        sync.reducePermits(reduction);
    }
    public final boolean hasQueuedThreads() {
        return sync.hasQueuedThreads();
    }
    public final int getQueueLength() {
        return sync.getQueueLength();
    }
    protected Collection<Thread> getQueuedThreads() {
        return sync.getQueuedThreads();
    }

所幸方法很多，总的代码行不多，因为每个方法都是一个风格，就是换个名直接调用sync的对应方法。这是Semaphore中对sync的使用。是不是觉得写这个代码的作者比写这个文章的作者还要无耻？在其他几个工具类中，没有这么夸张，b但基本上也是这个风格，即以一个helper的方式向外面的封装类提供功能支持。所以第一个问题，在文章中说到这里，后面涉及到也只会简单描述。 主要是求索第二个问题，即每个工具类中自己定义的Sync到底是什么样子，有哪些不同的特征，其实也就是代码上看这些Sync类对父类AQS做了哪些修改。

2. AQS简介

要介绍子类的特征，父类总得大致介绍下。AQS的原理、设计等比较系统的东西，在这里就不想涉及了。可以参照《深入浅出 Java Concurrency》系列的深入浅出 Java Concurrency (7): 锁机制 part 2 AQS一节，谢谢这个系列，作者讲的确实非常的深入浅出！要想了解更多，可以参考Doug Lea大师的原著The java.util.concurrent Synchronizer Framework。最简单的办法其实就是的耐心把AbstractQueuedSynchronizer源码前面注释的javadoc完整的读一遍就可以了。笔者反正有这样的习惯。扎着脑袋看代码，看注释，然后自己看看是否能把一个package有个系统的视图，如果需要再看相关的参考文档来确认这个系统的视图。

看一个对象有什么本事，看他的构成是什么样，远比看他由哪些行为来的要深远。其实在OOP这种以class方式承载功能的编程中，即看一个类包含的属性，比他的方法也更容易理解对象的作用。看AQS类，暂时抛开outline视图下需要两屏才能看完的重要方法（还未展开ConditionObject和Node两个重要的内部类），只看该类包含的三个重要属性的定义就能看出端倪。

    private transient volatile Node head;
    private transient volatile Node tail;
    private volatile int state;

注释其实已经告诉我们了，Node类型的head和tail是一个FIFO的wait queue；一个int类型的状态位state。到这里也能猜到AQS对外呈现（或者说声明）的主要行为就是由一个状态位和一个有序队列来配合完成。 最简单的读一下主要的四个方法：

     //释放排他锁
   public final void acquire(int arg) {
        if (!tryAcquire(arg) &&
            acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
            selfInterrupt();
    }

   //释放排他锁
public final boolean release(int arg) {
 if (tryRelease(arg)) {
  Node h = head;
 if (h != null && h.waitStatus != 0)
 unparkSuccessor(h);
 return true;
 }
return false;
 }

   //获取共享锁
 public final void acquireShared(int arg) {
        if (tryAcquireShared(arg) < 0)
            doAcquireShared(arg);
    }

   //释放共享锁
public final boolean releaseShared(int arg) {
        if (tryReleaseShared(arg)) {
            doReleaseShared();
            return true;
        }
        return false;
    }

分别对应锁的获取和释放，只是**shared后缀的表示一组表示共享锁，而另外一组没有后缀的表示排他锁。只用关注每个方法的第一行，都是这种try字体的风格：

  if (try*****(arg)) {
}

即做一个判断，然后做获取或者释放锁。 其实AQS主要的工作思路正是如此：在获取锁时候，先判断当前状态是否允许获取锁，若是可以则获取锁，否则获取不成功。获取不成功则会阻塞，进入阻塞队列。而释放锁时，一般会修改状态位，唤醒队列中的阻塞线程。 跟踪这几个try字体的方法定义，发现一个惊人的巧合，这几个方法在AQS中居然都是一样的定义：

   protected boolean tr***(int arg) {
        throw new UnsupportedOperationException();
    }

即都是父类中只有定义，在子类中实现。子类根据功能需要的不同，有选择的对需要的方法进行实现。父类中提供一个执行模板，但是具体步骤留给子类来定义，不同的子类有不同的实现。

3. AQS的重要方法定义

简单看下下面几个方法的源码发现定义中都涉及到了getState(), setState(int) compareAndSetState(int, int)，即对状态位state的维护。

• tryAcquire(int)
• tryRelease(int)
• tryAcquireShared(int)
• tryReleaseShared(int)

下图表示compareAndSetState(int, int)的调用，可以看的更清楚看到，说明几个同步工具类内定义的Sync类，即自定义子类中其实都涉及到对state的操作。

而同时不小心观察到AQS中有一大组final的方法，就是子类不能覆盖的，大致看下方法内的定义，大部分都是直接或间接涉及对head和tail的操作，即对等待队列的维护。

那在AQS的子类中有没有对有序队列的操作呢？检索下对head和tail的引用即可找到结论。

对head的操作仅限于在AQS类内部，观察方法的修饰，除了final就是private，即表示这些方法不可能被子类override，或者不可能在子类中直接被调用。看下图对于tail的调用也是同样的风格，即对等待队列的操作全部不超过AQS类内部。

于是几乎可以有这样的结论：在AQS的设计中，在父类AQS中实现了对等待队列的默认实现，无论是对共享锁还是对排他锁。子类中几乎不用修改该部分功能，而state在子类中根据需要被赋予了不同的意义，子类通过对state的不同操作来提供不同的同步器功能，进而对封装的工具类提供不同的功能。 在下面尝试对以上观点在AQS各个子类在各个工具类中的使用进行验证。

4. AQS在子类中的使用

对每个考察会从如下几个方面来进行

• 工具类的主要作用
• 主要获取锁方法（其他的类似方法如对应的可以更好的处理中断和超时或者异步等特性）
• 主要释放锁方法（其他的类似方法如对应的可以更好的处理中断和超时或者异步等特性）
• 工具类的构造方法（构造方法能告诉我们一个类最在意，最根本的属性）
• Sync构造方法
• Sync接口方法
• Sync对AQS方法的override
• state的作用
• state维护重要逻辑

我们的问题就是这些AQS的子类如何配合父类AQS的框架方法来完成各个工具类不同的锁需求。分析思路是这样：

• 这个工具类是干什么用的？可以理解为是功能需求。
• 这个工具类是通过哪些方法来实现这些功能的？可以理解为分解的需求
• AQS的子类Sync是如何支持这些方法的？可以理解为需求的实现。

按照如下的思路对每个工具类尝试进行解析，只是注意以上观点，可能并没有覆盖这个工具类的所有内容(其实就是方法)和对应Sync的所有内容。为了表达清楚些，把重点方法的代码引用在文章中，并对重点语句做了标记。因为五钟同步工具类在一起说明，看上去引用的代码有点多。

1） Semaphore

先看doc中对Semaphore的功能要求：

A counting semaphore. Conceptually, a semaphore maintains a set of permits. Each acquire blocks if necessary until a permit is available, and then takes it. Each release adds a permit, potentially releasing a blocking acquirer. However, no actual permit objects are used; the Semaphore just keeps a count of the number available and acts accordingly.

信号量Semaphore的主要作用是来控制同时访问某个特定资源的操作数量，或者同时执行某个指定操作的数量。 Semaphore只是计数，不包括许可对象，并且Semaphore也不会把许可与线程对象关联起来，因此一个线程中获得的许可可以在另外一个线程中释放。关于这点的理解可以参照What is mutex and semaphore in Java ? What is the main difference ?的说明。 Semphore对外的两个方法是 acquire()和release()方法。在许可可用前会阻塞每一个 acquire()，然后再获取该许可。每调用 release() 添加一个许可，释放一个正在阻塞的获取者。

   public void acquire() throws InterruptedException {
        sync.acquireSharedInterruptibly(1);
    }

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

达到这样的操作是通过同步器Sync来操作，可以是FairSync，也可以是NonfairSync。 从Sync的构造方法中，就可以看出Semphore中所谓的permit其实就是AQS中的state。

     public Semaphore(int permits, boolean fair) {
        sync = (fair)? new FairSync(permits) : new NonfairSync(permits);
    }

    Sync(int permits) {
            setState(permits);
        }

工具类是通过Sync的acquireSharedInterruptibly和ReleaseShared的方法提供功能。AQS中定义的这两个final方法调用的是子类对应的try*方法。在这里覆盖了tryAcquireShared和tryReleaseShared方法。每一次请求acquire()一个许可都会导致计数器减少1，同样每次释放一个许可release()都会导致计数器增加1，一旦达到了0，新的许可请求线程将被挂起。

         protected final boolean tryReleaseShared(int releases) {
            for (;;) {
                int p = getState();
                //释放锁时，许可递加
                if (compareAndSetState(p, p + releases))
                    return true;
            }
        }

每次释放锁时先调用该方法时，作用就修改state值为state+release，即表示增加新释放的许可数。 而tryAcquireShared对应于FairSync，NonfairSync有两种不同的实现。 FairSync中，总是判断当前线程是等待队列的第一个线程时，获得锁，且修改state值为state-acquires。

         protected int tryAcquireShared(int acquires) {
            Thread current = Thread.currentThread();
            for (;;) {
                // FairSync中，总是判断当前线程是等待队列的第一个线程时，获得锁
                Thread first = getFirstQueuedThread();
                if (first != null && first != current)
                    return -1;
                int available = getState();
                //获得锁，则计数递减
                int remaining = available - acquires;
                if (remaining < 0 ||
                    compareAndSetState(available, remaining))
                    return remaining;
            }
        }

对NonfairSync，不用考虑等待队列，直接修改state许可数。

          protected int tryAcquireShared(int acquires) {
            return nonfairTryAcquireShared(acquires);
        }
        final int nonfairTryAcquireShared(int acquires) {
            for (;;) {
                //对NonfairSync，不用考虑等待队列，直接修改state许可数
                int available = getState();
                int remaining = available - acquires;
                if (remaining < 0 ||
                    compareAndSetState(available, remaining))
                    return remaining;
            }
        }

即不管是公平还是非公平，acquire方法总是会判断是否还有许可可用，如果有，并且当前线程可以获得，则获得锁，许可数相应减少。state在此的作用就是许可数。

总结：在Semaphore中使用AQS的子类Sync，初始化state表示许可数，在每一次请求acquire()一个许可都会导致计数器减少1，同样每次释放一个许可release()都会导致计数器增加1。一旦达到了0，新的许可请求线程将被挂起。

2） CountDownLatch

要求完成的功能是： A synchronization aid that allows one or more threads to wait until a set of operations being performed in other threads completes. A CountDownLatch is initialized with a given count. The await methods block until the current count reaches zero due to invocations of the countDown method, after which all waiting threads are released and any subsequent invocations of await return immediately.

就像名字Latch所表达的一样，把一组线程全部关在外面，在某个状态时候放开。即一种同步机制来保证一个或多个线程等待其他线程完成。初始化了一个count计数，当count未递减到0时候，每次调用await方法都会阻塞。每次调用countDown来是的的count递减。 这是CountDownLatch 中“规定”的该工具类应该满足的功能，详细的使用的例子不再此介绍。只是分析如何借助Sync同步器来达到以上功能的。 从构造函数中可以看到该类也维护了一个计数count。这个计数其实也是通过AQS的state来完成的，

   public CountDownLatch(int count) {
        if (count < 0) throw new IllegalArgumentException("count < 0");
        this.sync = new Sync(count);}

CountDownLatch的两个重要方法是await和countDown方法。定义分别如下。定义await方法的作用是在计数器不为0时候阻塞调用线程，为0时候立即返回；countDown方法的作用是计数递减。

      public void await() throws InterruptedException {
        sync.acquireSharedInterruptibly(1);
    }
    public void countDown() {
        sync.releaseShared(1);
    }

看到这两个方法最终的执行还是同步器中的对应方法。在CountDownLatch中也定义了一个继承于AQS的Sync。在前面的分析中知道父类的acquireSharedInterruptibly方法和releaseShared其实是分别调用到了子类中定义的tryAcquireShared和tryReleaseShared方法。 在CountDownLatch的Sync类中也就仅仅实现了这两个方法。

其中tryAcquireShared方法内容非常简单，只是一个三元表达式，但是这个state值为0赋值1，不为0却赋值-1。看着不太符合我们一般的用法，这主要是为了配合父类AQS中的逻辑。当state为0表示计数递减完成，则返回值为-1，在父类中满足条件则执行后续的阻塞操作；当state不为0表示计算器递减未完成，则返回值为1，在父类调用中直接方法结束，不阻塞。

    public int tryAcquireShared(int acquires) {
 //当state为0表示计数递减完成，则返回值为-1，在父类中满足条件则执行后续的阻塞操作
            return getState() == 0? 1 : -1;
        }

tryReleaseShared方法主要是对state值的维护，当已经为0，则返回false，父类releaseShared方法直接返回；当state不为0（其实就是大于0，因为count初始化是一个正数），则递减，并通过cas的方式更新state的值。

    public boolean tryReleaseShared(int releases) {
            // Decrement count; signal when transition to zero
            for (;;) {
                int c = getState();
                if (c == 0)
                //当已经为0，则返回false，父类releaseShared方法直接返回
                    return false;
                //当state不为0（其实就是大于0，因为count初始化是一个正数），则递减，并通过cas的方式更新state的值。
                int nextc = c-1;
                if (compareAndSetState(c, nextc))
                    return nextc == 0;
            }
        }

总结：CountDownLatch 委托自定义的Sync中的，await()和countDown()方法来完成阻塞线程到计数器为0的功能和计数器递减功能。而该这两个方法委托给自定义的Sync的acquireSharedInterruptibly()和releaseShared(int arg)方法。真正实现对state(count)维护的是父类AQS中调用子类定义的tryAcquireShared(int)和tryReleaseShared(int)来维护计数count。计数count使用的是AQS的状态位state。每次调用countDown方法计数递减，在计数递减到0之前，调用await的线程都会阻塞。

3）ReentrantLock

名字翻译很好，可重入锁。功能需求如下 A reentrant mutual exclusion Lock with the same basic behavior and semantics as the implicit monitor lock accessed using synchronized methods and statements, but with extended capabilities. A ReentrantLock is owned by the thread last successfully locking, but not yet unlocking it. A thread invoking lock will return, successfully acquiring the lock, when the lock is not owned by another thread. The method will return immediately if the current thread already owns the lock. This can be checked using methods isHeldByCurrentThread, and getHoldCount.

可重入锁应该是几种同步工具里面被用的对多的一个。标准的互斥操作，也就是一次只能有一个线程持有锁，可能是AQS中最重要的一个类。基本功能就关键字Synchronize所支持的功能。关于ReentrantLock和Synchronize的差别比较等文章很多，可以参照Java 理论与实践: JDK 5.0 中更灵活、更具可伸缩性的锁定机制和《Java Concurrency in Practice》的对应章节。 ReentrantLock对外的主要方法是lock()，tryLock()和unlock()方法，当然还有其他变种的lockInterruptibly()、tryLock(long timeout, TimeUnit unit)等。

lock的功能是获取锁。如果没有线程使用则立即返回，并设置state为1；如果当前线程已经占有锁，则state加1；如果其他线程占有锁，则当前线程不可用，等待。

      public void lock() {
        sync.lock();
    }

tryLock的功能是 如果锁可用，则获取锁，并立即返回值 true。如果锁不可用，立即返回值 false。

  public boolean tryLock() {
        return sync.nonfairTryAcquire(1);
    }

unlock的功能是尝试释放锁，如果当前线程占有锁则count减一，如果count为0则释放锁。若占有线程不是当前线程，则抛异常。

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

可以看到也是借助Sync来完成，我们下面详细看下Sync是如何实现这些”规定”的需求的。ReentrantLock的构造函数告诉我们，其支持公平和非公平两种锁机制。

      public ReentrantLock(boolean fair) {
        sync = (fair)? new FairSync() : new NonfairSync();
    }

在该类中对应定了两种FairSync和NonfairSync两种同步器，都继承者AQS。可以看到对应执行的是lock、release、和Sync的nonfairTryAcquire。从前面AQS源码知道release是在父类AQS中定义的方法，lock和nonfairTryAcquire是这个Sync中特定的方法，不是对父类对应方法的覆盖。 lock方法有对于FairSync和NoFairSync有两种不同的实现，对于非公平锁只要当前没有线程持有锁，就将锁给当前线程；而公平锁不能这么做，总是调用acquire方法来和其他线程一样公平的尝试获取锁。

        /**NoFairSync**/
     final void lock() {
            if (compareAndSetState(0, 1))
                //对于非公平锁只要当前没有线程持有锁，就将锁给当前线程
                setExclusiveOwnerThread(Thread.currentThread());
            else
                acquire(1);
        }
        /**FairSync**/
          final void lock() {
            acquire(1);
        }

acquire(int arg)方法是在父类AQS中定义，在其实现中先会调用子类的tryAcquire(int arg)方法。 对于非公平锁，通过state是否为0判断，当前是否有线程持有锁，如果没有则把锁分配给当前线程；否则如果state不为0，说明当前有线程持有锁，则判断持有锁的线程是否就是当前线程，如果是增加state计数，表示持有锁的线程的重入次数增加。当然增加重入数也会检查是否超过最大值。

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

    final boolean nonfairTryAcquire(int acquires) {
            final Thread current = Thread.currentThread();
            int c = getState();
            if (c == 0) {
            //通过state是否为0判断，当前是否有线程持有锁，如果没有则把锁分配给当前线程
                if (compareAndSetState(0, acquires)) {
                    setExclusiveOwnerThread(current);
                    return true;
                }
            }
            else if (current == getExclusiveOwnerThread()) {
            //否则如果state不为0，说明当前有线程持有锁，则判断持有锁的线程是否就是当前线程，如果是增加state计数，表示持有锁的线程的重入次数增加
                int nextc = c + acquires;
                if (nextc < 0) // overflow
                    throw new Error("Maximum lock count exceeded");
                setState(nextc);
                return true;
            }
            return false;
        }

对于公平锁，其tryAcquire(int arg)方法中，如果state为0表示没有线程持有锁，会检查当前线程是否是等待队列的第一个线程，如果是则分配锁给当前线程；否则如果state不为0，说明当前有线程持有锁，则判断持有锁的线程释放就是当前线程，如果是增加state计数，表示持有锁的线程的重入次数增加。

          protected final boolean tryAcquire(int acquires) {
            final Thread current = Thread.currentThread();
            int c = getState();
            if (c == 0) {
                if (isFirst(current) &&
                    compareAndSetState(0, acquires)) {
               //如果state为0表示没有线程持有锁，会检查当前线程是否是等待队列的第一个线程，如果是则分配锁给当前线程
                    setExclusiveOwnerThread(current);
                    return true;
                }
            }
            else if (current == getExclusiveOwnerThread()) {
           //如果state不为0，说明当前有线程持有锁，则判断持有锁的线程释放就是当前线程，如果是增加state计数，表示持有锁的线程的重入次数增加
                int nextc = c + acquires;
                if (nextc < 0)
                    throw new Error("Maximum lock count exceeded");
                setState(nextc);
                return true;
            }
            return false;
        }

比较公平锁机制和非公平锁机制的差别仅仅在于如果当前没有线程持有锁，是优先把锁分配给当前线程，还是优先分配给等待队列中队首的线程。 释放锁时候调用AQS的release(int arg)方法，前面定义知道父类的该方法会先调用子类的tryRelease(int arg)方法。在该方法中主要作用是state状态位减少release个，表示释放锁，如果更新后的state为0；表示当前线程释放锁，如果不为0，表示持有锁的当前线程重入数减少。

        protected final boolean tryRelease(int releases) {
            int c = getState() - releases; //state状态位减少release个
            if (Thread.currentThread() != getExclusiveOwnerThread())
                throw new IllegalMonitorStateException();
            boolean free = false;
            if (c == 0) {
           //如果更新后的state为0，表示当前线程释放锁
                free = true;
                setExclusiveOwnerThread(null);
            }//如果不为0，表示持有锁的当前线程重入数减少。
            setState(c);
            return free;
        }

总结： ReentrantLock中定义的同步器分为公平的同步器和非公平的同步器。在该同步器中state状态位表示当前持有锁的线程的重入次数。在获取锁时，通过覆盖AQS的tryAcquire(int arg)方法，如果没有线程持有则立即返回，并设置state为1；如果当前线程已经占有锁，则state加1；如果其他线程占有锁，则当前线程不可用。释放锁时，覆盖了AQS的tryRelease(int arg)，在该方法中主要作用是state状态位减少release个，表示释放锁，如果更新后的state为0，表示当前线程释放锁，如果不为0，表示持有锁的当前线程重入数减少。

4）ReentrantReadWriteLock可重入读写锁

读写锁的要求是： A ReadWriteLock maintains a pair of associated locks, one for read-only operations and one for writing. The read lock may be held simultaneously by multiple reader threads, so long as there are no writers. The write lock is exclusive. All ReadWriteLock implementations must guarantee that the memory synchronization effects of writeLock operations (as specified in the Lock interface) also hold with respect to the associated readLock. That is, a thread successfully acquiring the read lock will see all updates made upon previous release of the write lock.

即读和读之间是兼容的，写和任何操作都是排他的。这种锁机制在数据库系统理论中应用的其实更为普遍。 允许多个读线程同时持有锁，但是只有一个写线程可以持有锁。读写锁允许读线程和写线程按照请求锁的顺序重新获取读取锁或者写入锁。当然了只有写线程释放了锁，读线程才能获取重入锁。写线程获取写入锁后可以再次获取读取锁，但是读线程获取读取锁后却不能获取写入锁。 ReentrantReadWriteLock锁从其要求的功能上来看，是对前面的ReentrantLock的扩展，因此功能复杂度上来说也提高了，看看该类下面定义的内部类，除了支持公平非公平的Sync外，还有两种不同的锁，ReadLock和WriteLock。

在向下进行之前，有必要回答这样一个问题，WriteLock和ReadLock好像完成的功能不一样，看上去似乎是两把锁。ReentrantReadWriteLock中分别通过两个public的方法readLock()和writeLock()获得读锁和写锁。

      private final ReentrantReadWriteLock.ReadLock readerLock;
    private final ReentrantReadWriteLock.WriteLock writerLock;
    private final Sync sync;

   public ReentrantReadWriteLock.WriteLock writeLock() { return writerLock; }
   public ReentrantReadWriteLock.ReadLock  readLock()  { return readerLock; }

但是如果是两把锁，可以实现前面功能要求的读锁和读锁直接的兼容，写锁和写锁直接的互斥，这本身共享锁和排他锁就能满足要求，但是如何实现对同一个对象上读和写的控制？明显，只有一把锁才能做到。 看上面代码片段时候，不小心看到了一个熟悉的字段Sync，前面的几个同步工具我们知道了，这些工具类的所有操作最终都是委托给AQS的对应子类Sync来完成，这里只有一个同步器Sync，那是不是就是只有一把锁呢。看看后面的构造函数会验证我们的猜想。

   public ReentrantReadWriteLock(boolean fair) {
        sync = (fair)? new FairSync() : new NonfairSync();
        //使用了同一个this，即统一this里面的同一个sync来构造读锁和写锁
        readerLock = new ReadLock(this);
        writerLock = new WriteLock(this);
    }

没错，ReadLock和WriteLock使用的其实是一个private的同步器Sync。 下面看下可重入读写锁提供哪些锁的方法来满足上面的需求的。

看到ReadLock提供了lock()、lockInterruptibly()、tryLock()、tryLock(long timeout, TimeUnit unit)和unlock()方法。我们看下主要的几个方法的实现如下：lock()方法的作用是获取读锁；tryLock()的作用是尝试当前没有其他线程当前持有写锁时获取读锁；unlock方法的作用是释放读锁。

   public void lock() {
            sync.acquireShared(1);
        }
       public  boolean tryLock() {
            return sync.tryReadLock();
        }
       public  void unlock() {
            sync.releaseShared(1);
        }

分别调用到Sync的三个方法acquireShared(int arg) 、releaseShared(int arg)和 tryReadLock()方法，其中前两个是AQS父类中定义的，后一个是该Sync中根据自己需要实现的方法。 前面AQS父类的介绍中知道，acquireShared(int arg) 和releaseShared(int arg)方法是在父类中定义的，调用子类的对应try字体的方法，我们看下在子类Sync中定义对应的try*字体的方法怎么满足功能的。先看acquireShared中定义的tryAcquireShared

   protected final int tryAcquireShared(int unused) {
            Thread current = Thread.currentThread();
            int c = getState();
            if (exclusiveCount(c) != 0 &&
                getExclusiveOwnerThread() != current)
               //如果有排他锁，且持有排他锁的线程不是当前线程，则获取失败。
                return -1;
            if (sharedCount(c) == MAX_COUNT)
              //否则如果已经加读锁的个数超过允许的最大值，抛出异常
                throw new Error("Maximum lock count exceeded");
            if (!readerShouldBlock(current) &&
                compareAndSetState(c, c + SHARED_UNIT)) {
             //否则检查是否需要阻塞当前线程，如果不阻塞，则使用CAS的方式给更新状态位state。其中readerShouldBlock在Sync的两个子类中实现，根据公平非公平的策略有不同的判断条件
                HoldCounter rh = cachedHoldCounter;
                if (rh == null || rh.tid != current.getId())
                    cachedHoldCounter = rh = readHolds.get();
                rh.count++;
                return 1;
            }
            return fullTryAcquireShared(current);
        }

尝试获取读锁的方法是这样的：如果有排他锁，但是持有排他锁的线程不是当前线程，则获取失败；否则如果已经加读锁的个数超过允许的最大值，抛出异常；否则检查是否需要阻塞当前线程，如果不阻塞，则使用CAS的方式给更新状态位state。其中readerShouldBlock在Sync的两个子类中实现，根据公平非公平的策略有不同的判断条件。

对应的releaseShared中调用的tryReleaseShared定义如下

   protected final boolean tryReleaseShared(int unused) {
            HoldCounter rh = cachedHoldCounter;
            Thread current = Thread.currentThread();
            if (rh == null || rh.tid != current.getId())
                rh = readHolds.get();
            if (rh.tryDecrement() <= 0)
                throw new IllegalMonitorStateException();
            for (;;) {
                int c = getState();
              // 释放读锁时更新状态位的值
                int nextc = c - SHARED_UNIT;
                if (compareAndSetState(c, nextc))
                    return nextc == 0;
            }
        }

可以看到主要的作用在准备释放读锁时更新状态位的值。 Sync中提供给ReadLock用的tryReadLock方法和tryAcquireShared内容和逻辑差不多，而且本文想着重分析的Sync对父类AQS的方法如何改变来达到需要的功能，所以这个方法这里不分析了。 可以看到加锁时候state增加了一个SHARED_UNIT，在释放锁时state减少了一个SHARED_UNIT。为什么是SHARED_UNIT，而不是1呢？这个看了下面两个方法的定义就比较清楚了。

         /** Returns the number of shared holds represented in count  */
        static int sharedCount(int c)    { return c >>> SHARED_SHIFT; }
        /** Returns the number of exclusive holds represented in count  */
       static int exclusiveCount(int c) { return c & EXCLUSIVE_MASK; }

原来为了只用一个state状态位来表示两种锁的信息，高位16位表示共享锁的状态位，低位16位表示独占锁的状态位。至于读锁和写锁的状态位的意思，随着后面分析会逐步更清楚。 在看到这里的时候，读锁的状态位的意思应该是比较清楚，表示当前持有共享锁的线程数。有一个新的线程过了想使用共享锁，如果其他线程也只是加了共享锁，则当前线程就可以加共享锁，每加一次，状态位递加一些，因为存储在高16位，所以递加时是加一个SHARED_UNIT。

接着关注下WriteLock的方法。和 ReadLock 类似，提供出来的还是lock()、tryLock()、unlock()三个和其相似方法。

      public void lock() {
            sync.acquire(1);
        }
   public boolean tryLock( ) {
            return sync.tryWriteLock();
        }
   public void unlock() {
            sync.release(1);
        }

看到分别调用了Sync的acquire() release() 和tryWriteLock方法，其中前两个都是定义在父类AQS的方法。调用了子类定义的对应try字体的方法。tryAcquire和tryRelease方法。这里我们就看下子类的这两个try*字体的方法做了哪些事情。

   protected final boolean tryAcquire(int acquires) {
            Thread current = Thread.currentThread();
            int c = getState();
            int w = exclusiveCount(c);
            if (c != 0) {
                 //通过state的判断，当有读锁时获取不成功
                 //当有写锁，如果持有写锁的线程不是当前线程，则获取不成功
                // (Note: if c != 0 and w == 0 then shared count != 0)
                if (w == 0 || current != getExclusiveOwnerThread())
                    return false;
                if (w + exclusiveCount(acquires) > MAX_COUNT)
                    throw new Error("Maximum lock count exceeded");
            }//如果可以获取，则CAS的方式更新state，并设置当前线程排他的获取锁
            if ((w == 0 && writerShouldBlock(current)) ||
                !compareAndSetState(c, c + acquires))
                return false;
            setExclusiveOwnerThread(current);
            return true;
        }

tryAcquire中尝试获取排他锁。结合排他锁的语义和代码逻辑不难看到：通过state的判断，当有读锁时获取不成功，当有写锁，如果持有写锁的线程不是当前线程，则获取不成功。如果可以获取，则CAS的方式更新state，并设置当前线程排他的获取锁。writerShouldBlock定义在Sync的子类中，对于FaireSync和UnFairSync有不同的判断。 接下来看tryRelease方法，主要作用是在释放排他锁时候更新state，减去releases的数目。看到这里发现写锁中用到的Sync和可重入锁ReentrantLock整个逻辑都对应的差不多。

           protected final boolean tryRelease(int releases) {
            //释放排他锁时候更新state，减去releases的数目
            int nextc = getState() - releases;
            if (Thread.currentThread() != getExclusiveOwnerThread())
                throw new IllegalMonitorStateException();
            if (exclusiveCount(nextc) == 0) {
                setExclusiveOwnerThread(null);
                setState(nextc);
                return true;
            } else {
                setState(nextc);
                return false;
            }
        }

只是观察到写锁state更新加和减和前面的几种比较类似，直接操作的就是传入的整形参数，这在读锁的时候讲过了，因为排他锁的状态位是存储在state的低16位。

总结： ReentrantReadWriteLock中提供了两个Lock：ReentrantReadWriteLock.ReadLock和ReentrantReadWriteLock.WriteLock。对外提供功能的是两个lock，但是内部封装的是一个同步器Sync，有公平和不公平两个版本。借用了AQS的state状态位来保存锁的计数信息。高16位表示共享锁的数量，低16位表示独占锁的重入次数。在AQS子类的对应try字体方法中实现对state的维护。

5）FutureTask

先看需求 A cancellable asynchronous computation. This class provides a base implementation of Future, with methods to start and cancel a computation, query to see if the computation is complete, and retrieve the result of the computation. The result can only be retrieved when the computation has completed; the get method will block if the computation has not yet completed. Once the computation has completed, the computation cannot be restarted or cancelled.

理解其核心需求是，一个执行任务，开始执行后可以被取消，可以查看执行结果，如果执行结果未完成则阻塞。 一般表示一个输入待执行任务。在线程池中FutureTask中一般的用法就是构造一个FutureTask，然后提交execute，返回的类型还是FutureTask，调用其get方法即可得到执行结果。 run方法定义的就是任务执行的内容，在工作线程中被调用。通过构造函数可以看到FutureTask封装的了一个Runnable的对象，另外一个泛型参数result。猜也可以猜到前者就是执行的任务内容，后者是来接收执行结果的。可以看到功能还是委托给Sync对象，构造的参数是一个有执行结果的调用Callable，也可以直接使用一个Callable参数。

      public FutureTask(Runnable runnable, V result) {
        sync = new Sync(Executors.callable(runnable, result));
    }

    public FutureTask(Callable<V> callable) {
        if (callable == null)
            throw new NullPointerException();
        sync = new Sync(callable);
    }

FutureTask实现了RunnableFuture接口，也即实现了Runnable和Future接口。作业线程执行的内容是FutureTask的的run方法内定义的任务内容。如线程池 ThreadPoolExecutor.Worker.runTask(Runnable task)方法可以看到在线程池的Worker线程中调用到执行任务的run方法。这里使用Sync的作用，就是在任务执行线程和提交任务（同时也是获取任务执行结果）的线程之间维持一个锁的关系，保证只有执行结束后才能获取到结果。

FutureTask的任务执行方法是

  public void run() {
        sync.innerRun();
}

获取执行结果的方法是

      public V get() throws InterruptedException, ExecutionException {
        return sync.innerGet();
    }

设置执行结果的方法是

      protected void set(V v) {
        sync.innerSet(v);
    }

能看到，都是调到对应的Sync的对应方法。最主要的是innerRun方法，通过CAS的方式设置任务执行状态位RUNNING，执行传入的回调，并把执行结果调用innerSet进行赋值。

   void innerRun() {
              //设置任务执行状态位RUNNING
            if (!compareAndSetState(0, RUNNING))
                return;
            try {
                runner = Thread.currentThread();
                if (getState() == RUNNING) // recheck after setting thread
                    //获取和设置回调的结果
                    innerSet(callable.call());
                else
                    releaseShared(0); // cancel
            } catch (Throwable ex) {
                innerSetException(ex);
            }
        }

在innerSet方法中设置执行状态位为执行结束，并把执行结果赋值给result。

       void innerSet(V v) {
	    for (;;) {
		int s = getState();
		if (s == RAN)
		    return;
                if (s == CANCELLED) {
		   releaseShared(0);
                    return;
                }
                   //设置执行状态位为执行结束，并把执行结果赋值给result
		if (compareAndSetState(s, RAN)) {
                    result = v;
                    releaseShared(0);
                    done();
		    return;
                }
            }
        }

前面方法把执行结果放在result中，我们知道future接口定义的get方法来获取执行结果，那如何来判断另外一个线程已经执行完毕呢？看到FutureTask的get方法还是调用到Sync的innerGet方法。 innerGet方法根据判断执行状态来获取执行结果。acquireSharedInterruptibly方法其实调用的是子类中定义的tryAcquireShared来判断任务释放执行完毕或者取消。如果未完毕或取消，则挂起当前线程。

           V innerGet() throws InterruptedException, ExecutionException {
            //acquireSharedInterruptibly方法其实调用的是子类中定义的tryAcquireShared来判断任务释放执行完毕或者取消。如果未完毕或取消，则挂起当前线程
            acquireSharedInterruptibly(0);
            if (getState() == CANCELLED)
                throw new CancellationException();
            if (exception != null)
                throw new ExecutionException(exception);
            return result;
        }

tryAcquireShared方法的定义如下，调用innerIsDone方法，根据state的状态值做出判断，如果结束则返回1，未结束返回-1。当tryAcquireShared返回-1，则在父类AQS中获取共享锁的线程会阻塞。即实现“任务未完成调用get方法的线程会阻塞”这样的功能。

     protected int tryAcquireShared(int ignore) {
    //调用innerIsDone方法，根据state的状态值做出判断，如果结束则返回1，未结束返回-1。当tryAcquireShared返回-1，则在父类AQS中获取共享锁的线程会阻塞。
            return innerIsDone()? 1 : -1;
        }
    boolean innerIsDone() {
            return ranOrCancelled(getState()) && runner == null;
        }
   private boolean ranOrCancelled(int state) {
            return (state & (RAN | CANCELLED)) != 0;
        }

tryReleaseShared没有做什么事情，因为不像前面四种其实都有锁的意味，需要释放锁。在FutureTask中state表示任务的执行状态，在几乎每个方法的开始都会判读和设置状态。

      protected boolean tryReleaseShared(int ignore) {
            runner = null;
            return true;
        }

总结：在FutureTask实现了异步的执行和提交，作为可以被Executor提交的对象。通过Sync来维护任务的执行状态，从而保证只有工作线程任务执行完后，其他线程才能获取到执行结果。AQS的子类Sync在这里主要是借用state状态位来存储执行状态，来完成对对各种状态以及加锁、阻塞的实现。

最后终于理解了这早前就算了解的类，名字为什么叫FutureTask，实现了Future接口（满足在future的某个时间获取执行结果，这是Future接口的取名的意义吧），另外在执行中作为对执行任务的封装，封装了执行的任务内容，同时也封装了执行结果，可以安全的把这个任务交给另外的线程去执行，只要执行get方法能得到结果，则一定是你想要的结果，真的是很精妙。

5. 总结对照

本文主要侧重AQS的子类在各个同步工具类中的使用情况，其实也基本涵盖了这几个同步工具类的主要逻辑，但目标并不是对这几个同步工具类的代码进行详细解析。另外AQS本身的几个final方法，才是同步器的公共基础，也不是本文的主题，也未详细展开。其实写这篇文章的一个初始目的真的只是想列出如下表格，对比下AQS中的各个子类是怎么使用state的，居然啰嗦了这么多。

完。

原文发表在：http://www.idouba.net/sync-implementation-by-aqs/

张超盟 an ExTrender，CS数据管理方向工学硕士。与妻儿蜗居于钱江畔，就职一初创安全公司任数据服务团队负责人，做数据(存储、挖掘、服务)方面研发。爱数据，爱代码，爱技术，爱豆吧。

自动装箱和拆箱从Java 1.5开始引入，目的是将原始类型值转自动地转换成对应的对象。自动装箱与拆箱的机制可以让我们在Java的变量赋值或者是方法调用等情况下使用原始类型或者对象类型更加简单直接。

如果你在Java1.5下进行过编程的话，你一定不会陌生这一点，你不能直接地向集合(Collections)中放入原始类型值，因为集合只接收对象。通常这种情况下你的做法是，将这些原始类型的值转换成对象，然后将这些转换的对象放入集合中。使用Integer,Double,Boolean等这些类我们可以将原始类型值转换成对应的对象，但是从某些程度可能使得代码不是那么简洁精炼。为了让代码简练，Java 1.5引入了具有在原始类型和对象类型自动转换的装箱和拆箱机制。但是自动装箱和拆箱并非完美，在使用时需要有一些注意事项，如果没有搞明白自动装箱和拆箱，可能会引起难以察觉的bug。

本文将介绍，什么是自动装箱和拆箱，自动装箱和拆箱发生在什么时候，以及要注意的事项。

什么是自动装箱和拆箱

自动装箱就是Java自动将原始类型值转换成对应的对象，比如将int的变量转换成Integer对象，这个过程叫做装箱，反之将Integer对象转换成int类型值，这个过程叫做拆箱。因为这里的装箱和拆箱是自动进行的非人为转换，所以就称作为自动装箱和拆箱。原始类型byte,short,char,int,long,float,double和boolean对应的封装类为Byte,Short,Character,Integer,Long,Float,Double,Boolean。

自动装箱拆箱要点

• 自动装箱时编译器调用valueOf将原始类型值转换成对象，同时自动拆箱时，编译器通过调用类似intValue(),doubleValue()这类的方法将对象转换成原始类型值。
• 自动装箱是将boolean值转换成Boolean对象，byte值转换成Byte对象，char转换成Character对象，float值转换成Float对象，int转换成Integer，long转换成Long，short转换成Short，自动拆箱则是相反的操作。

何时发生自动装箱和拆箱

自动装箱和拆箱在Java中很常见，比如我们有一个方法，接受一个对象类型的参数，如果我们传递一个原始类型值，那么Java会自动讲这个原始类型值转换成与之对应的对象。最经典的一个场景就是当我们向ArrayList这样的容器中增加原始类型数据时或者是创建一个参数化的类，比如下面的ThreadLocal。

1
2
3
4
5
6
7
8
9

ArrayList<Integer> intList = new ArrayList<Integer>();
intList.add(1); //autoboxing - primitive to object
intList.add(2); //autoboxing

ThreadLocal<Integer> intLocal = new ThreadLocal<Integer>();
intLocal.set(4); //autoboxing

int number = intList.get(0); // unboxing
int local = intLocal.get(); // unboxing in Java

举例说明

上面的部分我们介绍了自动装箱和拆箱以及它们何时发生，我们知道了自动装箱主要发生在两种情况，一种是赋值时，另一种是在方法调用的时候。为了更好地理解这两种情况，我们举例进行说明。

赋值时

这是最常见的一种情况，在Java 1.5以前我们需要手动地进行转换才行，而现在所有的转换都是由编译器来完成。

1
2
3
4
5
6
7

//before autoboxing
Integer iObject = Integer.valueOf(3);
Int iPrimitive = iObject.intValue()

//after java5
Integer iObject = 3; //autobxing - primitive to wrapper conversion
int iPrimitive = iObject; //unboxing - object to primitive conversion

方法调用时

这是另一个常用的情况，当我们在方法调用时，我们可以传入原始数据值或者对象，同样编译器会帮我们进行转换。

1
2
3
4
5
6
7
8

public static Integer show(Integer iParam){
   System.out.println("autoboxing example - method invocation i: " + iParam);
   return iParam;
}

//autoboxing and unboxing in method invocation
show(3); //autoboxing
int result = show(3); //unboxing because return type of method is Integer

show方法接受Integer对象作为参数，当调用show(3)时，会将int值转换成对应的Integer对象，这就是所谓的自动装箱，show方法返回Integer对象，而int result = show(3);中result为int类型，所以这时候发生自动拆箱操作，将show方法的返回的Integer对象转换成int值。

自动装箱的弊端

自动装箱有一个问题，那就是在一个循环中进行自动装箱操作的情况，如下面的例子就会创建多余的对象，影响程序的性能。

1
2
3
4

Integer sum = 0;
 for(int i=1000; i<5000; i++){
   sum+=i;
}

上面的代码sum+=i可以看成sum = sum + i，但是+这个操作符不适用于Integer对象，首先sum进行自动拆箱操作，进行数值相加操作，最后发生自动装箱操作转换成Integer对象。其内部变化如下

1
2

sum = sum.intValue() + i;
Integer sum = new Integer(result);

由于我们这里声明的sum为Integer类型，在上面的循环中会创建将近4000个无用的Integer对象，在这样庞大的循环中，会降低程序的性能并且加重了垃圾回收的工作量。因此在我们编程时，需要注意到这一点，正确地声明变量类型，避免因为自动装箱引起的性能问题。

重载与自动装箱

当重载遇上自动装箱时，情况会比较有些复杂，可能会让人产生有些困惑。在1.5之前，value(int)和value(Integer)是完全不相同的方法，开发者不会因为传入是int还是Integer调用哪个方法困惑，但是由于自动装箱和拆箱的引入，处理重载方法时稍微有点复杂。一个典型的例子就是ArrayList的remove方法，它有remove(index)和remove(Object)两种重载，我们可能会有一点小小的困惑，其实这种困惑是可以验证并解开的，通过下面的例子我们可以看到，当出现这种情况时，不会发生自动装箱操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public void test(int num){
    System.out.println("method with primitive argument");

}

public void test(Integer num){
    System.out.println("method with wrapper argument");

}

//calling overloaded method
AutoboxingTest autoTest = new AutoboxingTest();
int value = 3;
autoTest.test(value); //no autoboxing 
Integer iValue = value;
autoTest.test(iValue); //no autoboxing

Output:
method with primitive argument
method with wrapper argument

要注意的事项

自动装箱和拆箱可以使代码变得简洁,但是其也存在一些问题和极端情况下的问题，以下几点需要我们加强注意。

对象相等比较

这是一个比较容易出错的地方，”==“可以用于原始值进行比较，也可以用于对象进行比较，当用于对象与对象之间比较时，比较的不是对象代表的值，而是检查两个对象是否是同一对象，这个比较过程中没有自动装箱发生。进行对象值比较不应该使用”==“，而应该使用对象对应的equals方法。看一个能说明问题的例子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

public class AutoboxingTest {

    public static void main(String args[]) {

        // Example 1: == comparison pure primitive – no autoboxing
        int i1 = 1;
        int i2 = 1;
        System.out.println("i1==i2 : " + (i1 == i2)); // true

        // Example 2: equality operator mixing object and primitive
        Integer num1 = 1; // autoboxing
        int num2 = 1;
        System.out.println("num1 == num2 : " + (num1 == num2)); // true

        // Example 3: special case - arises due to autoboxing in Java
        Integer obj1 = 1; // autoboxing will call Integer.valueOf()
        Integer obj2 = 1; // same call to Integer.valueOf() will return same
                            // cached Object

        System.out.println("obj1 == obj2 : " + (obj1 == obj2)); // true

        // Example 4: equality operator - pure object comparison
        Integer one = new Integer(1); // no autoboxing
        Integer anotherOne = new Integer(1);
        System.out.println("one == anotherOne : " + (one == anotherOne)); // false

    }

}

Output:
i1==i2 : true
num1 == num2 : true
obj1 == obj2 : true
one == anotherOne : false

值得注意的是第三个小例子，这是一种极端情况。obj1和obj2的初始化都发生了自动装箱操作。但是处于节省内存的考虑，JVM会缓存-128到127的Integer对象。因为obj1和obj2实际上是同一个对象。所以使用”==“比较返回true。

容易混乱的对象和原始数据值

另一个需要避免的问题就是混乱使用对象和原始数据值，一个具体的例子就是当我们在一个原始数据值与一个对象进行比较时，如果这个对象没有进行初始化或者为Null，在自动拆箱过程中obj.xxxValue，会抛出NullPointerException,如下面的代码

1
2
3
4
5
6

private static Integer count;

//NullPointerException on unboxing
if( count <= 0){
  System.out.println("Count is not started yet");
}

缓存的对象

这个问题就是我们上面提到的极端情况，在Java中，会对-128到127的Integer对象进行缓存，当创建新的Integer对象时，如果符合这个这个范围，并且已有存在的相同值的对象，则返回这个对象，否则创建新的Integer对象。

在Java中另一个节省内存的例子就是字符串常量池,感兴趣的同学可以了解一下。

生成无用对象增加GC压力

因为自动装箱会隐式地创建对象，像前面提到的那样，如果在一个循环体中，会创建无用的中间对象，这样会增加GC压力，拉低程序的性能。所以在写循环时一定要注意代码，避免引入不必要的自动装箱操作。

如想了解垃圾回收和内存优化，可以查看本文Google IO：Android内存管理主题演讲记录

总的来说，自动装箱和拆箱着实为开发者带来了很大的方便，但是在使用时也是需要格外留意，避免引起出现文章提到的问题。

原文信息

• What is Autoboxing and Unboxing in Java – Example Tutorial and Corner cases

好书推荐

• Java编程思想(第4版)
• Java核心技术(卷1):基础知识
• 深入理解Java虚拟机:JVM高级特性与最佳实践

0     0

由 udpwork.com 聚合 | 评论: 0 | 要! 要! 即刻! Now!

在Java编程中，有些知识 并不能仅通过语言规范或者标准API文档就能学到的。在本文中，我会尽量收集一些最常用的习惯用法，特别是很难猜到的用法。（Joshua Bloch的《Effective Java》对这个话题给出了更详尽的论述，可以从这本书里学习更多的用法。）

我把本文的所有代码都放在公共场所里。你可以根据自己的喜好去复制和修改任意的代码片段，不需要任何的凭证。

目录

• 实现：
  • equals()
  • hashCode()
  • compareTo()
  • clone()
• 应用：
  • StringBuilder/StringBuffer
  • Random.nextInt(int)
  • Iterator.remove()
  • StringBuilder.reverse()
  • Thread/Runnable
  • try-finally
• 输入/输出：
  • 从输入流里读取字节数据
  • 从输入流里读取块数据
  • 从文件里读取文本
  • 向文件里写文本
• 预防性检测：
  • 数值
  • 对象
  • 数组索引
  • 数组区间
• 数组：
  • 填充元素
  • 复制一个范围内的数组元素
  • 调整数组大小
• 包装
  • 个字节包装成一个int
  • 分解成4个字节

实现equals()

class Person {
  String name;
  int birthYear;
  byte[] raw;

  public boolean equals(Object obj) {
    if (!obj instanceof Person)
      return false;

    Person other = (Person)obj;
    return name.equals(other.name)
        && birthYear == other.birthYear
        && Arrays.equals(raw, other.raw);
  }

  public int hashCode() { ... }
}

• 参数必须是Object类型，不能是外围类。
• foo.equals(null) 必须返回false，不能抛NullPointerException。（注意，null instanceof 任意类 总是返回false，因此上面的代码可以运行。）
• 基本类型域（比如，int）的比较使用 == ，基本类型数组域的比较使用Arrays.equals()。
• 覆盖equals()时，记得要相应地覆盖 hashCode()，与 equals() 保持一致。
• 参考： java.lang.Object.equals(Object)。

实现hashCode()

class Person {
  String a;
  Object b;
  byte c;
  int[] d;

  public int hashCode() {
    return a.hashCode() + b.hashCode() + c + Arrays.hashCode(d);
  }

  public boolean equals(Object o) { ... }
}

• 当x和y两个对象具有x.equals(y) == true ，你必须要确保x.hashCode() == y.hashCode()。
• 根据逆反命题，如果x.hashCode() != y.hashCode()，那么x.equals(y) == false 必定成立。
• 你不需要保证，当x.equals(y) == false时，x.hashCode() != y.hashCode()。但是，如果你可以尽可能地使它成立的话，这会提高哈希表的性能。
• hashCode()最简单的合法实现就是简单地return 0；虽然这个实现是正确的，但是这会导致HashMap这些数据结构运行得很慢。
• 参考：java.lang.Object.hashCode()。

实现compareTo()

class Person implements Comparable<Person> {
  String firstName;
  String lastName;
  int birthdate;

  // Compare by firstName, break ties by lastName, finally break ties by birthdate
  public int compareTo(Person other) {
    if (firstName.compareTo(other.firstName) != 0)
      return firstName.compareTo(other.firstName);
    else if (lastName.compareTo(other.lastName) != 0)
      return lastName.compareTo(other.lastName);
    else if (birthdate < other.birthdate)
      return -1;
    else if (birthdate > other.birthdate)
      return 1;
    else
      return 0;
  }
}

• 总是实现泛型版本 Comparable 而不是实现原始类型 Comparable 。因为这样可以节省代码量和减少不必要的麻烦。
• 只关心返回结果的正负号（负/零/正），它们的大小不重要。
• Comparator.compare()的实现与这个类似。
• 参考：java.lang.Comparable。

实现clone()

class Values implements Cloneable {
  String abc;
  double foo;
  int[] bars;
  Date hired;

  public Values clone() {
    try {
      Values result = (Values)super.clone();
      result.bars = result.bars.clone();
      result.hired = result.hired.clone();
      return result;
    } catch (CloneNotSupportedException e) {  // Impossible
      throw new AssertionError(e);
    }
  }
}

• 使用 super.clone() 让Object类负责创建新的对象。
• 基本类型域都已经被正确地复制了。同样，我们不需要去克隆String和BigInteger等不可变类型。
• 手动对所有的非基本类型域（对象和数组）进行深度复制（deep copy）。
• 实现了Cloneable的类，clone()方法永远不要抛CloneNotSupportedException。因此，需要捕获这个异常并忽略它，或者使用不受检异常（unchecked exception）包装它。
• 不使用Object.clone()方法而是手动地实现clone()方法是可以的也是合法的。
• 参考：java.lang.Object.clone()、java.lang.Cloneable()。

使用StringBuilder或StringBuffer

// join(["a", "b", "c"]) -> "a and b and c"
String join(List<String> strs) {
  StringBuilder sb = new StringBuilder();
  boolean first = true;
  for (String s : strs) {
    if (first) first = false;
    else sb.append(" and ");
    sb.append(s);
  }
  return sb.toString();
}

• 不要像这样使用重复的字符串连接：s += item ，因为它的时间效率是O(n^2)。
• 使用StringBuilder或者StringBuffer时，可以使用append()方法添加文本和使用toString()方法去获取连接起来的整个文本。
• 优先使用StringBuilder，因为它更快。StringBuffer的所有方法都是同步的，而你通常不需要同步的方法。
• 参考java.lang.StringBuilder、java.lang.StringBuffer。

生成一个范围内的随机整数

Random rand = new Random();

// Between 1 and 6, inclusive
int diceRoll() {
  return rand.nextInt(6) + 1;
}

• 总是使用Java API方法去生成一个整数范围内的随机数。
• 不要试图去使用 Math.abs(rand.nextInt()) % n 这些不确定的用法，因为它的结果是有偏差的。此外，它的结果值有可能是负数，比如当rand.nextInt() == Integer.MIN_VALUE时就会如此。
• 参考：java.util.Random.nextInt(int)。

使用Iterator.remove()

void filter(List<String> list) {
  for (Iterator<String> iter = list.iterator(); iter.hasNext(); ) {
    String item = iter.next();
    if (...)
      iter.remove();
  }
}

• remove()方法作用在next()方法最近返回的条目上。每个条目只能使用一次remove()方法。
• 参考：java.util.Iterator.remove()。

返转字符串

String reverse(String s) {
  return new StringBuilder(s).reverse().toString();
}

• 这个方法可能应该加入Java标准库。
• 参考：java.lang.StringBuilder.reverse()。

启动一条线程

下面的三个例子使用了不同的方式完成了同样的事情。

实现Runnnable的方式：

void startAThread0() {
  new Thread(new MyRunnable()).start();
}

class MyRunnable implements Runnable {
  public void run() {
    ...
  }
}

继承Thread的方式：

void startAThread1() {
  new MyThread().start();
}

class MyThread extends Thread {
  public void run() {
    ...
  }
}

匿名继承Thread的方式：

void startAThread2() {
  new Thread() {
    public void run() {
      ...
    }
  }.start();
}

• 不要直接调用run()方法。总是调用Thread.start()方法，这个方法会创建一条新的线程并使新建的线程调用run()。
• 参考：java.lang.Thread, java.lang.Runnable。

使用try-finally

I/O流例子：

void writeStuff() throws IOException {
  OutputStream out = new FileOutputStream(...);
  try {
    out.write(...);
  } finally {
    out.close();
  }
}

锁例子：

void doWithLock(Lock lock) {
  lock.acquire();
  try {
    ...
  } finally {
    lock.release();
  }
}

• 如果try之前的语句运行失败并且抛出异常，那么finally语句块就不会执行。但无论怎样，在这个例子里不用担心资源的释放。
• 如果try语句块里面的语句抛出异常，那么程序的运行就会跳到finally语句块里执行尽可能多的语句，然后跳出这个方法（除非这个方法还有另一个外围的finally语句块）。

从输入流里读取字节数据

InputStream in = (...);
try {
  while (true) {
    int b = in.read();
    if (b == -1)
      break;
    (... process b ...)
  }
} finally {
  in.close();
}

• read()方法要么返回下一次从流里读取的字节数（0到255，包括0和255），要么在达到流的末端时返回-1。
• 参考：java.io.InputStream.read()。

从输入流里读取块数据

InputStream in = (...);
try {
  byte[] buf = new byte[100];
  while (true) {
    int n = in.read(buf);
    if (n == -1)
      break;
    (... process buf with offset=0 and length=n ...)
  }
} finally {
  in.close();
}

• 要记住的是，read()方法不一定会填满整个buf，所以你必须在处理逻辑中考虑返回的长度。
• 参考： java.io.InputStream.read(byte[])、java.io.InputStream.read(byte[], int, int)。

从文件里读取文本

BufferedReader in = new BufferedReader(
    new InputStreamReader(new FileInputStream(...), "UTF-8"));
try {
  while (true) {
    String line = in.readLine();
    if (line == null)
      break;
    (... process line ...)
  }
} finally {
  in.close();
}

• BufferedReader对象的创建显得很冗长。这是因为Java把字节和字符当成两个不同的概念来看待（这与C语言不同）。
• 你可以使用任何类型的InputStream来代替FileInputStream，比如socket。
• 当达到流的末端时，BufferedReader.readLine()会返回null。
• 要一次读取一个字符，使用Reader.read()方法。
• 你可以使用其他的字符编码而不使用UTF-8，但最好不要这样做。
• 参考：java.io.BufferedReader、java.io.InputStreamReader。

向文件里写文本

PrintWriter out = new PrintWriter(
    new OutputStreamWriter(new FileOutputStream(...), "UTF-8"));
try {
  out.print("Hello ");
  out.print(42);
  out.println(" world!");
} finally {
  out.close();
}

• Printwriter对象的创建显得很冗长。这是因为Java把字节和字符当成两个不同的概念来看待（这与C语言不同）。
• 就像System.out，你可以使用print()和println()打印多种类型的值。
• 你可以使用其他的字符编码而不使用UTF-8，但最好不要这样做。
• 参考：java.io.PrintWriter、java.io.OutputStreamWriter。

预防性检测（Defensive checking）数值

int factorial(int n) {
  if (n < 0)
    throw new IllegalArgumentException("Undefined");
  else if (n >= 13)
    throw new ArithmeticException("Result overflow");
  else if (n == 0)
    return 1;
  else
    return n * factorial(n - 1);
}

• 不要认为输入的数值都是正数、足够小的数等等。要显式地检测这些条件。
• 一个设计良好的函数应该对所有可能性的输入值都能够正确地执行。要确保所有的情况都考虑到了并且不会产生错误的输出（比如溢出）。

预防性检测对象

int findIndex(List<String> list, String target) {
  if (list == null || target == null)
    throw new NullPointerException();
  ...
}

• 不要认为对象参数不会为空（null）。要显式地检测这个条件。

预防性检测数组索引

void frob(byte[] b, int index) {
  if (b == null)
    throw new NullPointerException();
  if (index < 0 || index >= b.length)
    throw new IndexOutOfBoundsException();
  ...
}

• 不要认为所以给的数组索引不会越界。要显式地检测它。

预防性检测数组区间

void frob(byte[] b, int off, int len) {
  if (b == null)
    throw new NullPointerException();
  if (off < 0 || off > b.length
    || len < 0 || b.length - off < len)
    throw new IndexOutOfBoundsException();
  ...
}

• 不要认为所给的数组区间（比如，从off开始，读取len个元素）是不会越界。要显式地检测它。

填充数组元素

使用循环：

// Fill each element of array 'a' with 123
byte[] a = (...);
for (int i = 0; i < a.length; i++)
  a[i] = 123;

（优先）使用标准库的方法：

Arrays.fill(a, (byte)123);

• 参考：java.util.Arrays.fill(T[], T)。
• 参考：java.util.Arrays.fill(T[], int, int, T)。

复制一个范围内的数组元素

使用循环：

// Copy 8 elements from array 'a' starting at offset 3
// to array 'b' starting at offset 6,
// assuming 'a' and 'b' are distinct arrays
byte[] a = (...);
byte[] b = (...);
for (int i = 0; i < 8; i++)
  b[6 + i] = a[3 + i];

（优先）使用标准库的方法：

System.arraycopy(a, 3, b, 6, 8);

• 参考：java.lang.System.arraycopy(Object, int, Object, int, int)。

调整数组大小

使用循环（扩大规模）：

// Make array 'a' larger to newLen
byte[] a = (...);
byte[] b = new byte[newLen];
for (int i = 0; i < a.length; i++)  // Goes up to length of A
  b[i] = a[i];
a = b;

使用循环（减小规模）：

// Make array 'a' smaller to newLen
byte[] a = (...);
byte[] b = new byte[newLen];
for (int i = 0; i < b.length; i++)  // Goes up to length of B
  b[i] = a[i];
a = b;

（优先）使用标准库的方法：

a = Arrays.copyOf(a, newLen);

• 参考：java.util.Arrays.copyOf(T[], int)。
• 参考：java.util.Arrays.copyOfRange(T[], int, int)。

把4个字节包装（packing）成一个int

int packBigEndian(byte[] b) {
  return (b[0] & 0xFF) << 24
       | (b[1] & 0xFF) << 16
       | (b[2] & 0xFF) <<  8
       | (b[3] & 0xFF) <<  0;
}

int packLittleEndian(byte[] b) {
  return (b[0] & 0xFF) <<  0
       | (b[1] & 0xFF) <<  8
       | (b[2] & 0xFF) << 16
       | (b[3] & 0xFF) << 24;
}

把int分解（Unpacking）成4个字节

byte[] unpackBigEndian(int x) {
  return new byte[] {
    (byte)(x >>> 24),
    (byte)(x >>> 16),
    (byte)(x >>>  8),
    (byte)(x >>>  0)
  };
}

byte[] unpackLittleEndian(int x) {
  return new byte[] {
    (byte)(x >>>  0),
    (byte)(x >>>  8),
    (byte)(x >>> 16),
    (byte)(x >>> 24)
  };
}

• 总是使用无符号右移操作符（>>>）对位进行包装（packing），不要使用算术右移操作符（>>）。

相关文章

• Java，传奇的一生！
• 十篇必读的Java文章
• 正确使用Java事件通知
• 不要“自作聪明”：{{是一种反模式
• 用Java生成字符画
• Java开发熟手该当心的11个错误
• 在Java中正确使用注释
• 追求代码质量（2）: 监视圈复杂度
• 追求代码质量（1）: 不要被覆盖报告所迷惑
• 怎样编写高质量的Java代码

一、引题

在java语言的所有数据类型中，String类型是比较特殊的一种类型，同时也是面试的时候经常被问到的一个知识点，本文结合java内存分配深度分析关于String的许多令人迷惑的问题。下面是本文将要涉及到的一些问题，如果读者对这些问题都了如指掌，则可忽略此文。

1、java内存具体指哪块内存？这块内存区域为什么要进行划分？是如何划分的？划分之后每块区域的作用是什么？如何设置各个区域的大小？

2、String类型在执行连接操作时，效率为什么会比StringBuffer或者StringBuilder低？StringBuffer和StringBuilder有什么联系和区别？

3、java中常量是指什么？String s = “s” 和 String s = new String(“s”) 有什么不一样？

本文经多方资料的收集整理和归纳，最终撰写成文，如果有错误之处，请多多指教！

二、java内存分配

1、JVM简介

Java虚拟机（Java Virtual Machine 简称JVM）是运行所有Java程序的抽象计算机，是Java语言的运行环境，它是Java 最具吸引力的特性之一。Java虚拟机有自己完善的硬体架构，如处理器、堆栈、寄存器等，还具有相应的指令系统。JVM屏蔽了与具体操作系统平台相关的信息，使得Java程序只需生成在Java虚拟机上运行的目标代码（字节码），就可以在多种平台上不加修改地运行。

一个运行时的Java虚拟机实例的天职是：负责运行一个java程序。当启动一个Java程序时，一个虚拟机实例也就诞生了。当该程序关闭退出，这个虚拟机实例也就随之消亡。如果同一台计算机上同时运行三个Java程序，将得到三个Java虚拟机实例。每个Java程序都运行于它自己的Java虚拟机实例中。

如下图所示，JVM的体系结构包含几个主要的子系统和内存区：

垃圾回收器（Garbage Collection）：负责回收堆内存（Heap）中没有被使用的对象，即这些对象已经没有被引用了。
类装载子系统（Classloader Sub-System）：除了要定位和导入二进制class文件外，还必须负责验证被导入类的正确性，为类变量分配并初始化内存，以及帮助解析符号引用。
执行引擎（Execution Engine）：负责执行那些包含在被装载类的方法中的指令。
运行时数据区（Java Memory Allocation Area）：又叫虚拟机内存或者Java内存，虚拟机运行时需要从整个计算机内存划分一块内存区域存储许多东西。例如：字节码、从已装载的class文件中得到的其他信息、程序创建的对象、传递给方法的参数，返回值、局部变量等等。

2、java内存分区

从上节知道，运行时数据区即是java内存，而且数据区要存储的东西比较多，如果不对这块内存区域进行划分管理，会显得比较杂乱无章。程序喜欢有规律的东西，最讨厌杂乱无章的东西。 根据存储数据的不同，java内存通常被划分为5个区域：程序计数器（Program Count Register）、本地方法栈（Native Stack）、方法区（Methon Area）、栈（Stack）、堆（Heap）。

程序计数器（Program Count Register）：又叫程序寄存器。JVM支持多个线程同时运行，当每一个新线程被创建时，它都将得到它自己的PC寄存器（程序计数器）。如果线程正在执行的是一个Java方法（非native），那么PC寄存器的值将总是指向下一条将被执行的指令，如果方法是 native的，程序计数器寄存器的值不会被定义。 JVM的程序计数器寄存器的宽度足够保证可以持有一个返回地址或者native的指针。

栈（Stack）：又叫堆栈。JVM为每个新创建的线程都分配一个栈。也就是说,对于一个Java程序来说，它的运行就是通过对栈的操作来完成的。栈以帧为单位保存线程的状态。JVM对栈只进行两种操作：以帧为单位的压栈和出栈操作。我们知道,某个线程正在执行的方法称为此线程的当前方法。我们可能不知道，当前方法使用的帧称为当前帧。当线程激活一个Java方法，JVM就会在线程的 Java堆栈里新压入一个帧，这个帧自然成为了当前帧。在此方法执行期间，这个帧将用来保存参数、局部变量、中间计算过程和其他数据。从Java的这种分配机制来看,堆栈又可以这样理解：栈(Stack)是操作系统在建立某个进程时或者线程(在支持多线程的操作系统中是线程)为这个线程建立的存储区域，该区域具有先进后出的特性。其相关设置参数：

• -Xss –设置方法栈的最大值

本地方法栈（Native Stack）：存储本地方方法的调用状态。

方法区（Method Area）：当虚拟机装载一个class文件时，它会从这个class文件包含的二进制数据中解析类型信息，然后把这些类型信息（包括类信息、常量、静态变量等）放到方法区中，该内存区域被所有线程共享，如下图所示。本地方法区存在一块特殊的内存区域，叫常量池（Constant Pool），这块内存将与String类型的分析密切相关。

堆（Heap）：Java堆（Java Heap）是Java虚拟机所管理的内存中最大的一块。Java堆是被所有线程共享的一块内存区域。在此区域的唯一目的就是存放对象实例，几乎所有的对象实例都是在这里分配内存，但是这个对象的引用却是在栈（Stack）中分配。因此，执行String s = new String(“s”)时，需要从两个地方分配内存：在堆中为String对象分配内存，在栈中为引用（这个堆对象的内存地址，即指针）分配内存，如下图所示。

JAVA虚拟机有一条在堆中分配新对象的指令，却没有释放内存的指令，正如你无法用Java代码区明确释放一个对象一样。虚拟机自己负责决定如何以及何时释放不再被运行的程序引用的对象所占据的内存，通常，虚拟机把这个任务交给垃圾收集器（Garbage Collection）。其相关设置参数：

• -Xms — 设置堆内存初始大小
• -Xmx — 设置堆内存最大值
• -XX:MaxTenuringThreshold — 设置对象在新生代中存活的次数
• -XX:PretenureSizeThreshold — 设置超过指定大小的大对象直接分配在旧生代中

Java堆是垃圾收集器管理的主要区域，因此又称为“GC 堆”（Garbage Collectioned Heap）。现在的垃圾收集器基本都是采用的分代收集算法，所以Java堆还可以细分为：新生代（Young Generation）和老年代（Old Generation），如下图所示。分代收集算法的思想：第一种说法，用较高的频率对年轻的对象(young generation)进行扫描和回收，这种叫做minor collection，而对老对象(old generation)的检查回收频率要低很多，称为major collection。这样就不需要每次GC都将内存中所有对象都检查一遍，以便让出更多的系统资源供应用系统使用；另一种说法，在分配对象遇到内存不足时，先对新生代进行GC（Young GC）；当新生代GC之后仍无法满足内存空间分配需求时， 才会对整个堆空间以及方法区进行GC（Full GC）。

在这里可能会有读者表示疑问：记得还有一个什么永久代（Permanent Generation）的啊，难道它不属于Java堆？亲，你答对了！其实传说中的永久代就是上面所说的方法区，存放的都是jvm初始化时加载器加载的一些类型信息（包括类信息、常量、静态变量等），这些信息的生存周期比较长，GC不会在主程序运行期对PermGen Space进行清理，所以如果你的应用中有很多CLASS的话,就很可能出现PermGen Space错误。其相关设置参数：

• -XX:PermSize –设置Perm区的初始大小
• -XX:MaxPermSize –设置Perm区的最大值

新生代（Young Generation）又分为：Eden区和Survivor区，Survivor区有分为From Space和To Space。Eden区是对象最初分配到的地方；默认情况下，From Space和To Space的区域大小相等。JVM进行Minor GC时，将Eden中还存活的对象拷贝到Survivor区中，还会将Survivor区中还存活的对象拷贝到Tenured区中。在这种GC模式下，JVM为了提升GC效率， 将Survivor区分为From Space和To Space，这样就可以将对象回收和对象晋升分离开来。新生代的大小设置有2个相关参数：

• -Xmn — 设置新生代内存大小。

• -XX:SurvivorRatio — 设置Eden与Survivor空间的大小比例

老年代（Old Generation）： 当 OLD 区空间不够时， JVM 会在 OLD 区进行 major collection；完全垃圾收集后，若Survivor及OLD区仍然无法存放从Eden复制过来的部分对象，导致JVM无法在Eden区为新对象创建内存区域，则出现”Out of memory错误”  。

三、String类型的深度解析

让我们从Java数据类型开始说起吧！Java数据类型通常（分类方法多种多样）从整体上可以分为两大类：基础类型和引用类型，基础类型的变量持有原始值，引用类型的变量通常表示的是对实际对象的引用，其值通常为对象的内存地址。对于基础类型和引用类型的细分，直接上图吧，大家看了一目了然。当然，下图也仅仅只是其中的一种分类方式。

 （原文图丢失）

针对上面的图，有3点需要说明：

•     char类型可以单独出来形成一类，很多基本类型的分类为：数值类型、字符型（char）和bool型。
•     returnAddress类型是一个Java虚拟机在内部使用的类型，被用来实现Java程序中的finally语句。
•     String类型在上图的什么位置？yes，属于引用类型下面的类类型。下面开始对String类型的挖掘！

1、String的本质

打开String的源码，类注释中有这么一段话“Strings are constant; their values cannot be changed after they are created. String buffers support mutable strings.Because String objects are immutable they can be shared.”。这句话总结归纳了String的一个最重要的特点：String是值不可变(immutable)的常量，是线程安全的(can be shared)。

接下来，String类使用了final修饰符，表明了String类的第二个特点：String类是不可继承的。

下面是String类的成员变量定义，从类的实现上阐明了String值是不可变的(immutable)。

private final char value[];
private final int count; 

因此，我们看String类的concat方法。实现该方法第一步要做的肯定是扩大成员变量value的容量，扩容的方法重新定义一个大容量的字符数组buf。第二步就是把原来value中的字符copy到buf中来，再把需要concat的字符串值也copy到buf中来，这样子，buf中就包含了concat之后的字符串值。下面就是问题的关键了，如果value不是final的，直接让value指向buf，然后返回this，则大功告成，没有必要返回一个新的String对象。但是。。。可惜。。。由于value是final型的，所以无法指向新定义的大容量数组buf，那怎么办呢？“return new String(0, count + otherLen, buf);”，这是String类concat实现方法的最后一条语句，重新new一个String对象返回。这下真相大白了吧！

总结：String实质是字符数组，两个特点：1、该类不可被继承；2、不可变性(immutable)。

2、String的定义方法

在讨论String的定义方法之前，先了解一下常量池的概念，前面在介绍方法区的时候已经提到过了。下面稍微正式的给一个定义吧。

常量池(constant pool)指的是在编译期被确定，并被保存在已编译的.class文件中的一些数据。它包括了关于类、方法、接口等中的常量，也包括字符串常量。常量池还具备动态性，运行期间可以将新的常量放入池中，String类的intern()方法是这一特性的典型应用。不懂吗？后面会介绍intern方法的。虚拟机为每个被装载的类型维护一个常量池，池中为该类型所用常量的一个有序集合，包括直接常量(string、integer和float常量)和对其他类型、字段和方法的符号引用（与对象引用的区别？读者可以自己去了解）。

String的定义方法归纳起来总共为三种方式：

• 使用关键字new，如：String s1 = new String(“myString”);
• 直接定义，如：String s1 = “myString”;
• 串联生成，如：String s1 = “my” + “String”;这种方式比较复杂，这里就不赘述了，请参见java–String常量池问题的几个例子。

第一种方式通过关键字new定义过程：在程序编译期，编译程序先去字符串常量池检查，是否存在“myString”,如果不存在，则在常量池中开辟一个内存空间存放“myString”；如果存在的话，则不用重新开辟空间，保证常量池中只有一个“myString”常量，节省内存空间。然后在内存堆中开辟一块空间存放new出来的String实例，在栈中开辟一块空间，命名为“s1”，存放的值为堆中String实例的内存地址，这个过程就是将引用s1指向new出来的String实例。各位，最模糊的地方到了！堆中new出来的实例和常量池中的“myString”是什么关系呢？等我们分析完了第二种定义方式之后再回头分析这个问题。

第二种方式直接定义过程：在程序编译期，编译程序先去字符串常量池检查，是否存在“myString”，如果不存在，则在常量池中开辟一个内存空间存放“myString”；如果存在的话，则不用重新开辟空间。然后在栈中开辟一块空间，命名为“s1”，存放的值为常量池中“myString”的内存地址。常量池中的字符串常量与堆中的String对象有什么区别呢？为什么直接定义的字符串同样可以调用String对象的各种方法呢？

带着诸多疑问，我和大家一起探讨一下堆中String对象和常量池中String常量的关系，请大家记住，仅仅是探讨，因为本人对这块也比较模糊。

第一种猜想：因为直接定义的字符串也可以调用String对象的各种方法，那么可以认为其实在常量池中创建的也是一个String实例（对象）。String s1 = new String(“myString”);先在编译期的时候在常量池创建了一个String实例，然后clone了一个String实例存储在堆中，引用s1指向堆中的这个实例。此时，池中的实例没有被引用。当接着执行String s1 = “myString”;时，因为池中已经存在“myString”的实例对象，则s1直接指向池中的实例对象；否则，在池中先创建一个实例对象，s1再指向它。如下图所示：

这种猜想认为：常量池中的字符串常量实质上是一个String实例，与堆中的String实例是克隆关系。

第二种猜想也是目前网上阐述的最多的，但是思路都不清晰，有些问题解释不通。下面引用《JAVA String对象和字符串常量的关系解析》一段内容。

在解析阶段，虚拟机发现字符串常量”myString”，它会在一个内部字符串常量列表中查找，如果没有找到，那么会在堆里面创建一个包含字符序列[myString]的String对象s1，然后把这个字符序列和对应的String对象作为名值对( [myString], s1 )保存到内部字符串常量列表中。如下图所示：

如果虚拟机后面又发现了一个相同的字符串常量myString，它会在这个内部字符串常量列表内找到相同的字符序列，然后返回对应的String对象的引用。维护这个内部列表的关键是任何特定的字符序列在这个列表上只出现一次。

例如，String s2 = “myString”，运行时s2会从内部字符串常量列表内得到s1的返回值，所以s2和s1都指向同一个String对象。

这个猜想有一个比较明显的问题，红色字体标示的地方就是问题的所在。证明方式很简单，下面这段代码的执行结果，javaer都应该知道。

String s1 = new String(“myString”);
String s2 = “myString”;

System.out.println(s1 == s2);  //按照上面的推测逻辑，那么打印的结果为true；而实际上真实的结果是false，因为s1指向的是堆中String对象，而s2指向的是常量池中的String常量。

虽然这段内容不那么有说服力，但是文章提到了一个东西——字符串常量列表，它可能是解释这个问题的关键。

文中提到的三个问题，本文仅仅给出了猜想，请知道真正内幕的高手帮忙分析分析，谢谢！

•  堆中new出来的实例和常量池中的“myString”是什么关系呢？
• 常量池中的字符串常量与堆中的String对象有什么区别呢？
• 为什么直接定义的字符串同样可以调用String对象的各种方法呢？

3、String、StringBuffer、StringBuilder的联系与区别

上面已经分析了String的本质了，下面简单说说StringBuffer和StringBuilder。

StringBuffer和StringBuilder都继承了抽象类AbstractStringBuilder，这个抽象类和String一样也定义了char[] value和int count，但是与String类不同的是，它们没有final修饰符。因此得出结论：String、StringBuffer和StringBuilder在本质上都是字符数组，不同的是，在进行连接操作时，String每次返回一个新的String实例，而StringBuffer和StringBuilder的append方法直接返回this，所以这就是为什么在进行大量字符串连接运算时，不推荐使用String，而推荐StringBuffer和StringBuilder。那么，哪种情况使用StringBuffe？哪种情况使用StringBuilder呢？

关于StringBuffer和StringBuilder的区别，翻开它们的源码，下面贴出append()方法的实现。

面第一张图是StringBuffer中append()方法的实现，第二张图为StringBuilder对append()的实现。区别应该一目了然，StringBuffer在方法前加了一个synchronized修饰，起到同步的作用，可以在多线程环境使用。为此付出的代价就是降低了执行效率。因此，如果在多线程环境可以使用StringBuffer进行字符串连接操作，单线程环境使用StringBuilder，它的效率更高。

四、参考文献

Java虚拟机体系结构
Java内存管理基础篇-Java内存分配
Java堆内存设置优化
Java内存管理和垃圾回收
Java堆内存的转换和回收
Java虚拟机的JVM垃圾回收机制

浅谈设置JVM内存分配的几个妙招
深入Java字符串
Java性能优化之String篇
java字符串常量池知识
Java内存分配及String类型详解
Java String的内存机制
Java之内存分析和String对象

String类学习总结

相关文章

• 深入理解Java String#intern() 内存模型
• Java字符串之性能优化
• 深入解析String#intern
• Java中关于String类型的10个问题
• Java 7、8中的String.intern（3）
• Java 6,7,8中的String.intern —— 多线程访问
• 10个有关String的面试问题
• Java中的String对象是不可变的吗
• 基本类型转String
• Java 1.7.0_06中String类内部实现的一些变化

文本来自StackOverflow问答网站的一个热门讨论：如何用Java编写一段会发生内存泄露的代码。

Q：刚才我参加了面试，面试官问我如何写出会发生内存泄露的Java代码。这个问题我一点思路都没有，好囧。

A1：通过以下步骤可以很容易产生内存泄露（程序代码不能访问到某些对象，但是它们仍然保存在内存中）:

应用程序创建一个长时间运行的线程（或者使用线程池，会更快地发生内存泄露）。

线程通过某个类加载器（可以自定义）加载一个类。

该类分配了大块内存（比如new byte[1000000]），在某个静态变量存储一个强引用，然后在ThreadLocal中存储它自身的引用。分配额外的内存new byte[1000000]是可选的(类实例泄露已经足够了)，但是这样会使内存泄露更快。

线程清理自定义的类或者加载该类的类加载器。

重复以上步骤。

由于没有了对类和类加载器的引用，ThreadLocal中的存储就不能被访问到。ThreadLocal持有该对象的引用，它也就持有了这个类及其类加载器的引用，类加载器持有它所加载的类的所有引用，这样GC无法回收ThreadLocal中存储的内存。在很多JVM的实现中Java类和类加载器直接分配到permgen区域不执行GC，这样导致了更严重的内存泄露。

这种泄露模式的变种之一就是如果你经常重新部署以任何形式使用了ThreadLocal的应用程序、应用容器（比如Tomcat）会很容易发生内存泄露（由于应用容器使用了如前所述的线程，每次重新部署应用时将使用新的类加载器）。

A2：

静态变量引用对象

class MemorableClass {
    static final ArrayList list = new ArrayList(100);
}

调用长字符串的String.intern()

String str=readString(); // read lengthy string any source db,textbox/jsp etc..
// This will place the string in memory pool from which you cant remove
str.intern();
try {
    BufferedReader br = new BufferedReader(new FileReader(inputFile));
    ...
    ...
} catch (Exception e) {
    e.printStacktrace();
}

未关闭连接

try {
    Connection conn = ConnectionFactory.getConnection();
    ...
    ...
} catch (Exception e) {
    e.printStacktrace();
}

JVM的GC不可达区域

比如通过native方法分配的内存。

web应用在application范围的对象，应用未重启或者没有显式移除

getServletContext().setAttribute(“SOME_MAP”, map);

web应用在session范围的对象，未失效或者没有显式移除

session.setAttribute(“SOME_MAP”, map);

不正确或者不合适的JVM选项

比如IBM JDK的noclassgc阻止了无用类的垃圾回收

A3：如果HashSet未正确实现(或者未实现)hashCode()或者equals(),会导致集合中持续增加“副本”。如果集合不能地忽略掉它应该忽略的元素，它的大小就只能持续增长，而且不能删除这些元素。

如果你想要生成错误的键值对，可以像下面这样做：

class BadKey {
   // no hashCode or equals();
   public final String key;
   public BadKey(String key) { this.key = key; }
}
Map map = System.getProperties();
map.put(new BadKey("key"), "value"); // Memory leak even if your threads die.

A4：除了被遗忘的监听器，静态引用，hashmap中key错误/被修改或者线程阻塞不能结束生命周期等典型内存泄露场景，下面介绍一些不太明显的Java发生内存泄露的情况，主要是线程相关的。

Runtime.addShutdownHook后没有移除，即使使用了removeShutdownHook，由于ThreadGroup类对于未启动线程的bug，它可能不被回收，导致ThreadGroup发生内存泄露。

创建但未启动线程，与上面的情形相同

创建继承了ContextClassLoader和AccessControlContext的线程，ThreadGroup和InheritedThreadLocal的使用，所有这些引用都是潜在的泄露，以及所有被类加载器加载的类和所有静态引用等等。这对ThreadFactory接口作为重要组成元素整个j.u.c.Executor框架(java.util.concurrent)的影响非常明显，很多开发人员没有注意到它潜在的危险。而且很多库都会按照请求启动线程。

ThreadLocal缓存，很多情况下不是好的做法。有很多基于ThreadLocal的简单缓存的实现，但是如果线程在它的期望生命周期外继续运行ContextClassLoader将发生泄露。除非真正必要不要使用ThreadLocal缓存。

当ThreadGroup自身没有线程但是仍然有子线程组时调用ThreadGroup.destroy()。发生内存泄露将导致该线程组不能从它的父线程组移除，不能枚举子线程组。

使用WeakHashMap，value直接(间接)引用key，这是个很难发现的情形。这也适用于继承Weak/SoftReference的类可能持有对被保护对象的强引用。

使用http(s)协议的java.net.URL下载资源。KeepAliveCache在系统ThreadGroup创建新线程，导致当前线程的上下文类加载器内存泄露。没有存活线程时线程在第一次请求时创建，所以很有可能发生泄露。(在Java7中已经修正了，创建线程的代码合理地移除了上下文类加载器。)

使用InflaterInputStream在构造函数(比如PNGImageDecoder)中传递new java.util.zip.Inflater()，不调用inflater的end()。仅仅是new的话非常安全，但如果自己创建该类作为构造函数参数时调用流的close()不能关闭inflater，可能发生内存泄露。这并不是真正的内存泄露因为它会被finalizer释放。但这消耗了很多native内存，导致linux的oom_killer杀掉进程。所以这给我们的教训是：尽可能早地释放native资源。

java.util.zip.Deflater也一样，它的情况更加严重。好的地方可能是很少用到Deflater。如果自己创建了Deflater或者Inflater记住必须调用end()。

可能感兴趣的文章

• 阻塞队列实现生产者消费者模式
• 我是如何从0开始，在23天里完成一款Android游戏开发的 – Part8– 第21至第23天
• Java语言基础特性—第一部分（上）
• Java FileInputStream与FileReader的区别
• Spring @Transactional工作原理
• Java Code Review清单
• 使用Java 8的Stream API列出ZIP文件中的条目
• 使用AOP与注解记录Java日志
• Java序列化示例教程
• 用Java生成字符画

大家知道，Java中string.intern()方法调用会先去字符串常量池中查找相应的字符串，如果字符串不存在，就会在字符串常量池中创建该字符串然后再返回。

字符串常量池是一个固定大小的HashMap，桶的数量默认是1009, 从Java7u40开始，该默认值增大到60013。在Java6当中，字符串常量池是放在Perm空间的，从Java7开始，字符串常量池被移到Heap空间。下面，我们通过测试程序来窥探字符串常量池在Java6，Java7两个不同版本底下的内存分配情况。

测试程序

public class StringPoolTest {

    public void testStringPoolWithLongString(){
        long i=0;
        while(true){
            String longString = "This is a very long string, very very long string to test the gc behavior of the string constant pool"+i;
            longString.intern();
            i++;
        }
    }

    public static void main(String[] args){
        StringPoolTest stringPoolTest = new StringPoolTest();
        stringPoolTest.testStringPoolWithLongString();
    }
}

测试程序很简单，一个死循环，循环里面通过递增变量i制造唯一的字符串，然后用main函数启动程序。

Java 6

我们使用版本Jdk1.6.0_29来跑该程序，打开Java VisualVM监控，可以看到，Perm区不断发生GC，由此的出结论，虽然字符串常量池放在Perm空间，但当Perm空间接近满的时候，JVM会将字符串常量池中的无用字符串回收掉。

Java 7

下面，我们切换到Jdk1.7.0_67重跑该程序，可以看到Perm区内存分配曲线很平滑，没有出现内存分配的现象。

但在Heap空间，新的对象不断产生，然后不断触发GC

结论

由于Perm区大小是有限的，通常只有几十MB，所以不推荐在Java6下广泛使用String.intern()，这篇文章string-intern-in-java-6-7-8的性能测试表明，在Java6底下大量使用intern()会导致应用性能的显著下降，还有可能产生OOM错误。但从Java7开始，字符串常量池被移到了Heap空间，Heap空间的大小只受制于机器的真实内存大小，因此，在Java7下使用String.intern()能更有效地减少重复String对象对内存的占用。

相关文章

• Java字符串之性能优化
• 深入解析String#intern
• Java中关于String类型的10个问题
• Java 7、8中的String.intern（3）
• Java 6,7,8中的String.intern —— 多线程访问
• 10个有关String的面试问题
• Java中的String对象是不可变的吗
• 基本类型转String
• Java 1.7.0_06中String类内部实现的一些变化
• 为什么String类是不可变的？

Spark 1.2在MLlib中引入了随机森林和梯度提升树(GBTs).这两种机器学习方法适用于分类和回归，且是在机器学习算法中应用得最多和最成功的算法。随机森林和GBTs都是集成学习算法，它们通过集成多棵决策树来实现强分类器。这篇博文中，我们会阐述这些模型及其他们在MLlib中的分布式实现。我们也给出一些简单例子和要点以便你知道如何上手。

集成学习方法

简单来说，集成学习方法就是基于其他的机器学习算法，并把它们有效的组合起来的一种机器学习算法。组合产生的算法相比其中任何一种算法模型更强大、准确。

在MLlib 1.2中，我们使用决策树作为基础模型。我们提供两种集成算法：随机森林和梯度提升树(GBTs)。两者之间主要差别在于每棵树训练的顺序。

随机森林通过对数据随机采样来单独训练每一棵树。这种随机性也使得模型相对于单决策树更健壮，且不易在训练集上产生过拟合。

GBTs则一次只训练一棵树，后面每一棵新的决策树逐步矫正前面决策树产生的误差。随着树的添加，模型的表达力也愈强。

最后，两种方法都生成了一个决策树的权重集合。该集成模型通过组合每棵独立树的结果来进行预测。下图显示一个由3棵决策树集成的简单实例。

在上述例子的回归集合中，每棵树都预测出一个实值。这些预测值被组合起来产生最终集成的预测结果。这里，我们通过取均值的方法来取得最终的预测结果（当然不同的预测任务需要用到不同的组合算法）。

集成学习的分布式学习算法

在MLlib中，随机森林和GBTs的数据都是按实例（行）存储的。算法的实现以原始的决策树代码为基础，每棵决策树采用分布式学习（早前的博客中有提到）。我们的许多算法优化都是参考Google’s PLANET project，特别是其中一篇关于分布式环境下的集成学习的文章。

随机森林：随机森林中的每棵树都是单独训练，多棵树可以并行训练（除此之外，单独的每棵树的训练也可以并行化）。MLlib也确实是这么做的：根据当前迭代内存的限制条件，动态调整可并行训练的子树的数量。

GBTs：因为GBTs只能一次训练一棵树，因此并行训练的粒度也只能到单棵树。

我们在这里强调一下MLlib中用到的两项重要的优化技术

• 内存：随机森林使用一个不同的样本数据训练每一棵树。我们利用TreePoint这种数据结构来存储每个子采样的数据，替代直接复制每份子采样数据的方法，进而节省了内存。
• 通信：尽管决策树经常通过选择树中每个决策点的所有功能进行训练，但随机森林则往往在每一个节点限制选择一个随机子集。MLlib的实现中就充分利用了这个子采样特点来减少通信：例如，若每个节点值用到1/3的特征，那么我们就会减少1/3的通信。

详细部分请见MLlib编程指南的集成章节。

使用MLlib集成学习

我们将演示如何使用MLlib进行学习集成模型。下面的Scala例子说明了怎么读取数据集，将数据集分割为训练集和测试集，学习一个模型以及打印出模型及其测试精度。Java和Pyton的例子请参阅MLlib编程指南。需要注意的是GBTs暂时还没有Python接口，但是我们期望Spark1.3发布版中会包含。（via Github PR 3951）

随机森林例子

import org.apache.spark.mllib.tree.RandomForest
import org.apache.spark.mllib.tree.configuration.Strategy
import org.apache.spark.mllib.util.MLUtils

// Load and parse the data file.
val data =
MLUtils.loadLibSVMFile(sc, "data/mllib/sample_libsvm_data.txt")
// Split data into training/test sets
val splits = data.randomSplit(Array(0.7, 0.3))
val (trainingData, testData) = (splits(0), splits(1))

// Train a RandomForest model.
val treeStrategy = Strategy.defaultStrategy("Classification")
val numTrees = 3 // Use more in practice.
val featureSubsetStrategy = "auto" // Let the algorithm choose.
val model = RandomForest.trainClassifier(trainingData,
treeStrategy, numTrees, featureSubsetStrategy, seed = 12345)

// Evaluate model on test instances and compute test error
val testErr = testData.map { point =>
val prediction = model.predict(point.features)
if (point.label == prediction) 1.0 else 0.0
}.mean()
println("Test Error = " + testErr)
println("Learned Random Forest:n" + model.toDebugString)

GBTs例子

import org.apache.spark.mllib.tree.GradientBoostedTrees
import org.apache.spark.mllib.tree.configuration.BoostingStrategy
import org.apache.spark.mllib.util.MLUtils

// Load and parse the data file.
val data =
MLUtils.loadLibSVMFile(sc, "data/mllib/sample_libsvm_data.txt")
// Split data into training/test sets
val splits = data.randomSplit(Array(0.7, 0.3))
val (trainingData, testData) = (splits(0), splits(1))

// Train a GradientBoostedTrees model.
val boostingStrategy =
BoostingStrategy.defaultParams("Classification")
boostingStrategy.numIterations = 3 // Note: Use more in practice
val model =
GradientBoostedTrees.train(trainingData, boostingStrategy)

// Evaluate model on test instances and compute test error
val testErr = testData.map { point =>
val prediction = model.predict(point.features)
if (point.label == prediction) 1.0 else 0.0
}.mean()
println("Test Error = " + testErr)
println("Learned GBT model:n" + model.toDebugString)

Scalability 扩展性

通过二分类问题的实证结果，我们证明了MLlib的扩展性。以下的各张图表分别对GBTs和随机森林的特性进行比较，其中每棵树都有不同的最大深度。

这些测试是一个回归的任务，即从音频特征从预测出歌曲的发布日期（YearPredictionMSD数据集来自UCI ML repository）。我们使用EC2 r3.2xlarge机器，算法的参数除非特别说明都使用默认值。

模型大小的伸缩：训练时间和测试误差

下面的两张图表显示了增加树的数量对集成效果的影响。对于GBTs和随机森林这两者而言，增加树的数量都会增加训练的时间（第一张图所示),同时树的数量增加也提高了预测精度（以测试的平均均方误差为衡量标准，图二所示)。

两者相比，随机森林训练的时间更短，但是要达到和GBTs同样的预测精度则需要更深的树。GBTs则能在每次迭代时显著地减少误差，但是经过过多的迭代，它又太容易过拟合(增加了测试误差）。随机森林则不太容易过拟合，测试误差也趋于稳定。

下面为均方误差随单棵决策树深度（深度分别为2，5，10）变化曲线图。

说明：463,715 个训练实例. 16个节点。

训练集的伸缩：训练时间和测试误差

下面两张图表显示了使用不同的训练集对算法结果产生的影响。图表表明，虽然数据集越大，两种方法的训练时间更长，但是却能产生更好的测试结果。

进一步伸缩：更多的节点，更快的训练速度

最后一张图表展示了使用更大的计算机集群来解决上述问题的效果，结论是GBTs和随机森林在大集群上速度得到显著提升。例如说，单树深度为2的GBTs在16个节点上的训练速度大约是在2个节点上的4.7倍。数据集越大则效果提升的越明显。

展望

GBTs不久就会提供Python的API。未来的另一个开发议题就是可插入性：集成方法不仅仅可以集成决策树，它可以集成几乎所有的分类和回归算法。在Spark 1.2中，处于实验中的spark.ml包中引入的Pipelines API将使得集成方法通用化，并做到真正的可插入。

进一步了解

API和相关例子详见MLlib集成学习文档。

要想了解更多用于构建集合的决策树相关背景知识，详见之前的博客。

致谢 MLlib集成算法由本博客的作者们合作开发完成，他们是Qiping Li (Alibaba), Sung Chung (Alpine Data Labs), and Davies Liu (Databricks).我们也感谢Lee Yang, Andrew Feng, and Hirakendu Das (Yahoo) ，他们帮助设计与测试。我们也欢迎你来贡献一份力量！

如何在MLlib中实现随机森林和梯度提升树（GBTs）？，首发于博客 - 伯乐在线。

什么是Spark

Apache Spark是一个围绕速度、易用性和复杂分析构建的大数据处理框架。最初在2009年由加州大学伯克利分校的AMPLab开发，并于2010年成为Apache的开源项目之一。

与Hadoop和Storm等其他大数据和MapReduce技术相比，Spark有如下优势。

首先，Spark为我们提供了一个全面、统一的框架用于管理各种有着不同性质（文本数据、图表数据等）的数据集和数据源（批量数据或实时的流数据）的大数据处理的需求。

相关厂商内容

移动解决方案专场-第三方组件背后的技术难点

云计算与大数据选型专场——专注解析主流技术方案

极致的Hybrid—从阿里「去啊」的架构演变看Web与Native的融合

涅盘新生—Android QQ音乐架构演进

驱动DT时代的数据可视化

相关赞助商

全球软件开发大会，4月23-25日，北京，敬请期待！

Spark可以将Hadoop集群中的应用在内存中的运行速度提升100倍，甚至能够将应用在磁盘上的运行速度提升10倍。

Spark让开发者可以快速的用Java、Scala或Python编写程序。它本身自带了一个超过80个高阶操作符集合。而且还可以用它在shell中以交互式地查询数据。

除了Map和Reduce操作之外，它还支持SQL查询，流数据，机器学习和图表数据处理。开发者可以在一个数据管道用例中单独使用某一能力或者将这些能力结合在一起使用。

在这个Apache Spark文章系列的第一部分中，我们将了解到什么是Spark，它与典型的MapReduce解决方案的比较以及它如何为大数据处理提供了一套完整的工具。

Hadoop和Spark

Hadoop这项大数据处理技术大概已有十年历史，而且被看做是首选的大数据集合处理的解决方案。MapReduce是一路计算的优秀解决方案，不过对于需要多路计算和算法的用例来说，并非十分高效。数据处理流程中的每一步都需要一个Map阶段和一个Reduce阶段，而且如果要利用这一解决方案，需要将所有用例都转换成MapReduce模式。

在下一步开始之前，上一步的作业输出数据必须要存储到分布式文件系统中。因此，复制和磁盘存储会导致这种方式速度变慢。另外Hadoop解决方案中通常会包含难以安装和管理的集群。而且为了处理不同的大数据用例，还需要集成多种不同的工具（如用于机器学习的Mahout和流数据处理的Storm）。

如果想要完成比较复杂的工作，就必须将一系列的MapReduce作业串联起来然后顺序执行这些作业。每一个作业都是高时延的，而且只有在前一个作业完成之后下一个作业才能开始启动。

而Spark则允许程序开发者使用有向无环图（DAG）开发复杂的多步数据管道。而且还支持跨有向无环图的内存数据共享，以便不同的作业可以共同处理同一个数据。

Spark运行在现有的Hadoop分布式文件系统基础之上（HDFS）提供额外的增强功能。它支持将Spark应用部署到现存的Hadoop v1集群（with SIMR – Spark-Inside-MapReduce）或Hadoop v2 YARN集群甚至是Apache Mesos之中。

我们应该将Spark看作是Hadoop MapReduce的一个替代品而不是Hadoop的替代品。其意图并非是替代Hadoop，而是为了提供一个管理不同的大数据用例和需求的全面且统一的解决方案。

Spark特性

Spark通过在数据处理过程中成本更低的洗牌（Shuffle）方式，将MapReduce提升到一个更高的层次。利用内存数据存储和接近实时的处理能力，Spark比其他的大数据处理技术的性能要快很多倍。

Spark还支持大数据查询的延迟计算，这可以帮助优化大数据处理流程中的处理步骤。Spark还提供高级的API以提升开发者的生产力，除此之外还为大数据解决方案提供一致的体系架构模型。

Spark将中间结果保存在内存中而不是将其写入磁盘，当需要多次处理同一数据集时，这一点特别实用。Spark的设计初衷就是既可以在内存中又可以在磁盘上工作的执行引擎。当内存中的数据不适用时，Spark操作符就会执行外部操作。Spark可以用于处理大于集群内存容量总和的数据集。

Spark会尝试在内存中存储尽可能多的数据然后将其写入磁盘。它可以将某个数据集的一部分存入内存而剩余部分存入磁盘。开发者需要根据数据和用例评估对内存的需求。Spark的性能优势得益于这种内存中的数据存储。

Spark的其他特性包括：

• 支持比Map和Reduce更多的函数。
• 优化任意操作算子图（operator graphs）。
• 可以帮助优化整体数据处理流程的大数据查询的延迟计算。
• 提供简明、一致的Scala，Java和Python API。
• 提供交互式Scala和Python Shell。目前暂不支持Java。

Spark是用Scala程序设计语言编写而成，运行于Java虚拟机（JVM）环境之上。目前支持如下程序设计语言编写Spark应用：

• Scala
• Java
• Python
• Clojure
• R

Spark生态系统

除了Spark核心API之外，Spark生态系统中还包括其他附加库，可以在大数据分析和机器学习领域提供更多的能力。

这些库包括：

• Spark Streaming:
  • Spark Streaming基于微批量方式的计算和处理，可以用于处理实时的流数据。它使用DStream，简单来说就是一个弹性分布式数据集（RDD）系列，处理实时数据。
• Spark SQL:
  • Spark SQL可以通过JDBC API将Spark数据集暴露出去，而且还可以用传统的BI和可视化工具在Spark数据上执行类似SQL的查询。用户还可以用Spark SQL对不同格式的数据（如JSON，Parquet以及数据库等）执行ETL，将其转化，然后暴露给特定的查询。
• Spark MLlib:
  • MLlib是一个可扩展的Spark机器学习库，由通用的学习算法和工具组成，包括二元分类、线性回归、聚类、协同过滤、梯度下降以及底层优化原语。
• Spark GraphX:
  • GraphX是用于图计算和并行图计算的新的（alpha）Spark API。通过引入弹性分布式属性图（Resilient Distributed Property Graph），一种顶点和边都带有属性的有向多重图，扩展了Spark RDD。为了支持图计算，GraphX暴露了一个基础操作符集合（如subgraph，joinVertices和aggregateMessages）和一个经过优化的Pregel API变体。此外，GraphX还包括一个持续增长的用于简化图分析任务的图算法和构建器集合。

除了这些库以外，还有一些其他的库，如BlinkDB和Tachyon。

BlinkDB是一个近似查询引擎，用于在海量数据上执行交互式SQL查询。BlinkDB可以通过牺牲数据精度来提升查询响应时间。通过在数据样本上执行查询并展示包含有意义的错误线注解的结果，操作大数据集合。

Tachyon是一个以内存为中心的分布式文件系统，能够提供内存级别速度的跨集群框架（如Spark和MapReduce）的可信文件共享。它将工作集文件缓存在内存中，从而避免到磁盘中加载需要经常读取的数据集。通过这一机制，不同的作业/查询和框架可以以内存级的速度访问缓存的文件。
此外，还有一些用于与其他产品集成的适配器，如Cassandra（Spark Cassandra 连接器）和R（SparkR）。Cassandra Connector可用于访问存储在Cassandra数据库中的数据并在这些数据上执行数据分析。

下图展示了在Spark生态系统中，这些不同的库之间的相互关联。

图1. Spark框架中的库

我们将在这一系列文章中逐步探索这些Spark库

Spark体系架构

Spark体系架构包括如下三个主要组件：

• 数据存储
• API
• 管理框架

接下来让我们详细了解一下这些组件。

数据存储：

Spark用HDFS文件系统存储数据。它可用于存储任何兼容于Hadoop的数据源，包括HDFS，HBase，Cassandra等。

API：

利用API，应用开发者可以用标准的API接口创建基于Spark的应用。Spark提供Scala，Java和Python三种程序设计语言的API。

下面是三种语言Spark API的网站链接。

• Scala API
• Java
• Python

资源管理：

Spark既可以部署在一个单独的服务器也可以部署在像Mesos或YARN这样的分布式计算框架之上。

下图2展示了Spark体系架构模型中的各个组件。

图2 Spark体系架构

弹性分布式数据集

弹性分布式数据集（基于Matei的研究论文）或RDD是Spark框架中的核心概念。可以将RDD视作数据库中的一张表。其中可以保存任何类型的数据。Spark将数据存储在不同分区上的RDD之中。

RDD可以帮助重新安排计算并优化数据处理过程。

此外，它还具有容错性，因为RDD知道如何重新创建和重新计算数据集。

RDD是不可变的。你可以用变换（Transformation）修改RDD，但是这个变换所返回的是一个全新的RDD，而原有的RDD仍然保持不变。

RDD支持两种类型的操作：

• 变换（Transformation）
• 行动（Action）

变换：变换的返回值是一个新的RDD集合，而不是单个值。调用一个变换方法，不会有任何求值计算，它只获取一个RDD作为参数，然后返回一个新的RDD。

变换函数包括：map，filter，flatMap，groupByKey，reduceByKey，aggregateByKey，pipe和coalesce。

行动：行动操作计算并返回一个新的值。当在一个RDD对象上调用行动函数时，会在这一时刻计算全部的数据处理查询并返回结果值。

行动操作包括：reduce，collect，count，first，take，countByKey以及foreach。

如何安装Spark

安装和使用Spark有几种不同方式。你可以在自己的电脑上将Spark作为一个独立的框架安装或者从诸如Cloudera，HortonWorks或MapR之类的供应商处获取一个Spark虚拟机镜像直接使用。或者你也可以使用在云端环境（如Databricks Cloud）安装并配置好的Spark。

在本文中，我们将把Spark作为一个独立的框架安装并在本地启动它。最近Spark刚刚发布了1.2.0版本。我们将用这一版本完成示例应用的代码展示。

如何运行Spark

当你在本地机器安装了Spark或使用了基于云端的Spark后，有几种不同的方式可以连接到Spark引擎。

下表展示了不同的Spark运行模式所需的Master URL参数。

如何与Spark交互

Spark启动并运行后，可以用Spark shell连接到Spark引擎进行交互式数据分析。Spark shell支持Scala和Python两种语言。Java不支持交互式的Shell，因此这一功能暂未在Java语言中实现。

可以用spark-shell.cmd和pyspark.cmd命令分别运行Scala版本和Python版本的Spark Shell。

Spark网页控制台

不论Spark运行在哪一种模式下，都可以通过访问Spark网页控制台查看Spark的作业结果和其他的统计数据，控制台的URL地址如下：

http://localhost:4040

Spark控制台如下图3所示，包括Stages，Storage，Environment和Executors四个标签页

（点击查看大图）

图3. Spark网页控制台

共享变量

Spark提供两种类型的共享变量可以提升集群环境中的Spark程序运行效率。分别是广播变量和累加器。

广播变量：广播变量可以在每台机器上缓存只读变量而不需要为各个任务发送该变量的拷贝。他们可以让大的输入数据集的集群拷贝中的节点更加高效。

下面的代码片段展示了如何使用广播变量。

//
// Broadcast Variables
//
val broadcastVar = sc.broadcast(Array(1, 2, 3))
broadcastVar.value

累加器：只有在使用相关操作时才会添加累加器，因此它可以很好地支持并行。累加器可用于实现计数（就像在MapReduce中那样）或求和。可以用add方法将运行在集群上的任务添加到一个累加器变量中。不过这些任务无法读取变量的值。只有驱动程序才能够读取累加器的值。

下面的代码片段展示了如何使用累加器共享变量：

//
// Accumulators
//

val accum = sc.accumulator(0, "My Accumulator")

sc.parallelize(Array(1, 2, 3, 4)).foreach(x => accum += x)

accum.value

Spark应用示例

本篇文章中所涉及的示例应用是一个简单的字数统计应用。这与学习用Hadoop进行大数据处理时的示例应用相同。我们将在一个文本文件上执行一些数据分析查询。本示例中的文本文件和数据集都很小，不过无须修改任何代码，示例中所用到的Spark查询同样可以用到大容量数据集之上。

为了让讨论尽量简单，我们将使用Spark Scala Shell。

首先让我们看一下如何在你自己的电脑上安装Spark。

前提条件：

• 为了让Spark能够在本机正常工作，你需要安装Java开发工具包（JDK）。这将包含在下面的第一步中。
• 同样还需要在电脑上安装Spark软件。下面的第二步将介绍如何完成这项工作。

注：下面这些指令都是以Windows环境为例。如果你使用不同的操作系统环境，需要相应的修改系统变量和目录路径已匹配你的环境。

I. 安装JDK

1）从Oracle网站上下载JDK。推荐使用JDK 1.7版本。

将JDK安装到一个没有空格的目录下。对于Windows用户，需要将JDK安装到像c:\dev这样的文件夹下，而不能安装到“c:\Program Files”文件夹下。“c:\Program Files”文件夹的名字中包含空格，如果软件安装到这个文件夹下会导致一些问题。

注：不要在“c:\Program Files”文件夹中安装JDK或（第二步中所描述的）Spark软件。

2）完成JDK安装后，切换至JDK 1.7目录下的”bin“文件夹，然后键入如下命令，验证JDK是否正确安装：

java -version

如果JDK安装正确，上述命令将显示Java版本。

II. 安装Spark软件：

从Spark网站上下载最新版本的Spark。在本文发表时，最新的Spark版本是1.2。你可以根据Hadoop的版本选择一个特定的Spark版本安装。我下载了与Hadoop 2.4或更高版本匹配的Spark，文件名是spark-1.2.0-bin-hadoop2.4.tgz。

将安装文件解压到本地文件夹中（如：c:\dev）。

为了验证Spark安装的正确性，切换至Spark文件夹然后用如下命令启动Spark Shell。这是Windows环境下的命令。如果使用Linux或Mac OS，请相应地编辑命令以便能够在相应的平台上正确运行。

c:
cd c:\dev\spark-1.2.0-bin-hadoop2.4
bin\spark-shell

如果Spark安装正确，就能够在控制台的输出中看到如下信息。

….
15/01/17 23:17:46 INFO HttpServer: Starting HTTP Server
15/01/17 23:17:46 INFO Utils: Successfully started service 'HTTP class server' on port 58132.
Welcome to
      ____              __
     / __/__  ___ _____/ /__
    _\ \/ _ \/ _ `/ __/  '_/
   /___/ .__/\_,_/_/ /_/\_\   version 1.2.0
      /_/

Using Scala version 2.10.4 (Java HotSpot(TM) 64-Bit Server VM, Java 1.7.0_71)
Type in expressions to have them evaluated.
Type :help for more information.
….
15/01/17 23:17:53 INFO BlockManagerMaster: Registered BlockManager
15/01/17 23:17:53 INFO SparkILoop: Created spark context..
Spark context available as sc.

可以键入如下命令检查Spark Shell是否工作正常。

sc.version

（或）

sc.appName

完成上述步骤之后，可以键入如下命令退出Spark Shell窗口：

:quit

如果想启动Spark Python Shell，需要先在电脑上安装Python。你可以下载并安装Anaconda，这是一个免费的Python发行版本，其中包括了一些比较流行的科学、数学、工程和数据分析方面的Python包。

然后可以运行如下命令启动Spark Python Shell：

c:
cd c:\dev\spark-1.2.0-bin-hadoop2.4
bin\pyspark

Spark示例应用

完成Spark安装并启动后，就可以用Spark API执行数据分析查询了。

这些从文本文件中读取并处理数据的命令都很简单。我们将在这一系列文章的后续文章中向大家介绍更高级的Spark框架使用的用例。

首先让我们用Spark API运行流行的Word Count示例。如果还没有运行Spark Scala Shell，首先打开一个Scala Shell窗口。这个示例的相关命令如下所示：

import org.apache.spark.SparkContext
import org.apache.spark.SparkContext._
 
val txtFile = "README.md"
val txtData = sc.textFile(txtFile)
txtData.cache()

我们可以调用cache函数将上一步生成的RDD对象保存到缓存中，在此之后Spark就不需要在每次数据查询时都重新计算。需要注意的是，cache()是一个延迟操作。在我们调用cache时，Spark并不会马上将数据存储到内存中。只有当在某个RDD上调用一个行动时，才会真正执行这个操作。

现在，我们可以调用count函数，看一下在文本文件中有多少行数据。

txtData.count()

然后，我们可以执行如下命令进行字数统计。在文本文件中统计数据会显示在每个单词的后面。

val wcData = txtData.flatMap(l => l.split(" ")).map(word => (word, 1)).reduceByKey(_ + _)

wcData.collect().foreach(println)

如果想查看更多关于如何使用Spark核心API的代码示例，请参考网站上的Spark文档。

后续计划

在后续的系列文章中，我们将从Spark SQL开始，学习更多关于Spark生态系统的其他部分。之后，我们将继续了解Spark Streaming，Spark MLlib和Spark GraphX。我们也会有机会学习像Tachyon和BlinkDB等框架。

小结

在本文中，我们了解了Apache Spark框架如何通过其标准API帮助完成大数据处理和分析工作。我们还对Spark和传统的MapReduce实现（如Apache Hadoop）进行了比较。Spark与Hadoop基于相同的HDFS文件存储系统，因此如果你已经在Hadoop上进行了大量投资和基础设施建设，可以一起使用Spark和MapReduce。

此外，也可以将Spark处理与Spark SQL、机器学习以及Spark Streaming结合在一起。关于这方面的内容我们将在后续的文章中介绍。

利用Spark的一些集成功能和适配器，我们可以将其他技术与Spark结合在一起。其中一个案例就是将Spark、Kafka和Apache Cassandra结合在一起，其中Kafka负责输入的流式数据，Spark完成计算，最后Cassandra NoSQL数据库用于保存计算结果数据。

不过需要牢记的是，Spark生态系统仍不成熟，在安全和与BI工具集成等领域仍然需要进一步的改进。

参考文献

• Spark主站
• Spark示例
• 2014年Spark峰会演示文稿和视频
• Spark on Databricks website
• Databricks网站上的Spark栏目

关于作者

Srini Penchikala目前是一家金融服务机构的软件架构师，这个机构位于德克萨斯州的奥斯汀。他在软件系统架构、设计和开发方面有超过20年的经验。Srini目前正在撰写一本关于NoSQL数据库模式的书。他还是曼宁出版社出版的《Spring Roo in Action》一书的合著者（http://www.manning.com/SpringRooinAction）。他还曾经出席各种会议，如JavaOne，SEI Architecture Technology Conference（SATURN），IT Architect Conference（ITARC），No Fluff Just Stuff，NoSQL Now和Project World Conference等。Srini还在InfoQ，The ServerSide，OReilly Network（ONJava），DevX Java，java.net以及JavaWorld等网站上发表过很多关于软件系统架构、安全和风险管理以及NoSQL数据库等方面的文章。他还是InfoQ NoSQL数据库社区的责任编辑。

查看英文原文：Big Data Processing with Apache Spark – Part 1: Introduction

当初在学校实验室的时候，常常写一个算法，让程序跑着四处去晃荡一下回来，结果也就出来了。可工作后，算法效率似乎重要多了，毕竟得真枪实弹放到产品中，卖给客户的；很多时候，还要搞到嵌入式设备里实时地跑，这么一来真是压力山大了~~~。这期间，对于程序优化也算略知皮毛，下面就针对这个问题讲讲。

首先说明一下，这里说的程序优化是指程序效率的优化。一般来说，程序优化主要是以下三个步骤：

1.算法优化

2.代码优化

3.指令优化

算法优化

算法上的优化是必须首要考虑的，也是最重要的一步。一般我们需要分析算法的时间复杂度，即处理时间与输入数据规模的一个量级关系，一个优秀的算法可以将算法复杂度降低若干量级，那么同样的实现，其平均耗时一般会比其他复杂度高的算法少（这里不代表任意输入都更快）。

比如说排序算法，快速排序的时间复杂度为O(nlogn)，而插入排序的时间复杂度为O(n*n)，那么在统计意义下，快速排序会比插入排序快，而且随着输入序列长度n的增加，两者耗时相差会越来越大。但是，假如输入数据本身就已经是升序(或降序)，那么实际运行下来，快速排序会更慢。

因此，实现同样的功能，优先选择时间复杂度低的算法。比如对图像进行二维可分的高斯卷积，图像尺寸为MxN，卷积核尺寸为PxQ，那么

直接按卷积的定义计算，时间复杂度为O(MNPQ)

如果使用2个一维卷积计算，则时间复杂度为O(MN(P+Q))

使用2个一位卷积+FFT来实现，时间复杂度为O(MNlogMN)

如果采用高斯滤波的递归实现，时间复杂度为O(MN)（参见paper：Recursive implementation of the Gaussian filter，源码在GIMP中有）

很显然，上面4种算法的效率是逐步提高的。一般情况下，自然会选择最后一种来实现。

还有一种情况，算法本身比较复杂，其时间复杂度难以降低，而其效率又不满足要求。这个时候就需要自己好好地理解算法，做些修改了。一种是保持算法效果来提升效率，另一种是舍弃部分效果来换取一定的效率，具体做法得根据实际情况操作。

代码优化

代码优化一般需要与算法优化同步进行，代码优化主要是涉及到具体的编码技巧。同样的算法与功能，不同的写法也可能让程序效率差异巨大。一般而言，代码优化主要是针对循环结构进行分析处理，目前想到的几条原则是：

a.避免循环内部的乘(除)法以及冗余计算

这一原则是能把运算放在循环外的尽量提出去放在外部，循环内部不必要的乘除法可使用加法来替代等。如下面的例子，灰度图像数据存在BYTE Img[MxN]的一个数组中，对其子块　　(R1至R2行，C1到C2列)像素灰度求和，简单粗暴的写法是：

int sum = 0; 
for(int i = R1; i < R2; i++)
{
    for(int j = C1; j < C2; j++)
    {
        sum += Image[i * N + j];
    }
}

但另一种写法：

int sum = 0;
BYTE *pTemp = Image + R1 * N;
for(int i = R1; i < R2; i++, pTemp += N)
{
    for(int j = C1; j < C2; j++)
    {
        sum += pTemp[j];
    }
}

可以分析一下两种写法的运算次数，假设R=R2-R1，C=C2-C1，前面一种写法i++执行了R次，j++和sum+=…这句执行了RC次，则总执行次数为3RC+R次加法，RC次乘法；同　　样地可以分析后面一种写法执行了2RC+2R+1次加法，1次乘法。性能孰好孰坏显然可知。

b.避免循环内部有过多依赖和跳转，使cpu能流水起来

关于CPU流水线技术可google/baidu，循环结构内部计算或逻辑过于复杂，将导致cpu不能流水，那这个循环就相当于拆成了n段重复代码的效率。

另外ii值是衡量循环结构的一个重要指标，ii值是指执行完1次循环所需的指令数，ii值越小，程序执行耗时越短。下图是关于cpu流水的简单示意图：

简单而不严谨地说，cpu流水技术可以使得循环在一定程度上并行，即上次循环未完成时即可处理本次循环，这样总耗时自然也会降低。

先看下面一段代码：

for(int i = 0; i < N; i++)
{
    if(i < 100) a[i] += 5;
    else if(i < 200) a[i] += 10;
    else a[i] += 20;
}

这段代码实现的功能很简单，对数组a的不同元素累加一个不同的值，但是在循环内部有3个分支需要每次判断，效率太低，有可能不能流水；可以改写为3个循环，这样循环内部就不　　用进行判断，这样虽然代码量增多了，但当数组规模很大(N很大)时，其效率能有相当的优势。改写的代码为：

for(int i = 0; i < 100; i++)
{
    a[i] += 5;        
}
for(int i = 100; i < 200; i++)
{
    a[i] += 10;        
}
for(int i = 200; i < N; i++)
{
    a[i] += 20;
}

关于循环内部的依赖，见如下一段程序：

for(int i = 0; i < N; i++)
{
    int x = f(a[i]);
    int y = g(x);
    int z = h(x,y);
}

其中f，g，h都是一个函数，可以看到这段代码中x依赖于a[i]，y依赖于x，z依赖于xy，每一步计算都需要等前面的都计算完成才能进行，这样对cpu的流水结构也是相当不利的，尽　　量避免此类写法。另外C语言中的restrict关键字可以修饰指针变量，即告诉编译器该指针指向的内存只有其自己会修改，这样编译器优化时就可以无所顾忌，但目前VC的编译器似乎不支　　持该关键字，而在DSP上，当初使用restrict后，某些循环的效率可提升90%。

c.定点化

定点化的思想是将浮点运算转换为整型运算，目前在PC上我个人感觉差别还不算大，但在很多性能一般的DSP上，其作用也不可小觑。定点化的做法是将数据乘上一个很大的数后，将　　所有运算转换为整数计算。例如某个乘法我只关心小数点后3位，那把数据都乘上10000后，进行整型运算的结果也就满足所需的精度了。

d.以空间换时间

空间换时间最经典的就是查表法了，某些计算相当耗时，但其自变量的值域是比较有限的，这样的情况可以预先计算好每个自变量对应的函数值，存在一个表格中，每次根据自变量的　　值去索引对应的函数值即可。如下例：

//直接计算
for(int i = 0 ; i < N; i++)
{
    double z = sin(a[i]);
}

//查表计算
double aSinTable[360] = {0, ..., 1,...,0,...,-1,...,0};
for(int i = 0 ; i < N; i++)
{
    double z = aSinTable[a[i]];
}

后面的查表法需要额外耗一个数组double aSinTable[360]的空间，但其运行效率却快了很多很多。

e.预分配内存

预分配内存主要是针对需要循环处理数据的情况的。比如视频处理，每帧图像的处理都需要一定的缓存，如果每帧申请释放，则势必会降低算法效率，如下所示：

//处理一帧
void Process(BYTE *pimg)
{
    malloc
    ...
    free
}

//循环处理一个视频
for(int i = 0; i < N; i++)
{
    BYTE *pimg = readimage();
    Process(pimg)；
}

//处理一帧
void Process(BYTE *pimg， BYTE *pBuffer)
{
    ...
}

//循环处理一个视频
malloc pBuffer
for(int i = 0; i < N; i++)
{
    BYTE *pimg = readimage();
    Process(pimg, pBuffer)；
}
free

前一段代码在每帧处理都malloc和free，而后一段代码则是有上层传入缓存，这样内部就不需每次申请和释放了。当然上面只是一个简单说明，实际情况会比这复杂得多，但整体思想　　是一致的。

指令优化

对于经过前面算法和代码优化的程序，一般其效率已经比较不错了。对于某些特殊要求，还需要进一步降低程序耗时，那么指令优化就该上场了。指令优化一般是使用特定的指令集，可快速实现某些运算，同时指令优化的另一个核心思想是打包运算。目前PC上intel指令集有MMX，SSE和SSE2/3/4等，DSP则需要跟具体的型号相关，不同型号支持不同的指令集。intel指令集需要intel编译器才能编译，安装icc后，其中有帮助文档，有所有指令的详细说明。

例如MMX里的指令 __m64 _mm_add_pi8(__m64 m1, __m64 m2)，是将m1和m2中8个8bit的数对应相加，结果就存在返回值对应的比特段中。假设2个N数组相加，一般需要执行N个加法指令，但使用上述指令只需执行N/8个指令，因为其1个指令能处理8个数据。

实现求2个BYTE数组的均值，即z[i]=(x[i]+y[i])/2，直接求均值和使用MMX指令实现2种方法如下程序所示：

#define N 800
BYTE x[N],Y[N], Z[N];
inital x,y;...
//直接求均值
for(int i = 0; i < N; i++)
{
    z[i] = (x[i] + y[i]) >> 1;
}

//使用MMX指令求均值，这里N为8的整数倍，不考虑剩余数据处理
__m64 m64X, m64Y, m64Z;
for(int i = 0; i < N; i+=8)
{
    m64X = *(__m64 *)(x + i);
    m64Y = *(__m64 *)(y + i);
    m64Z = _mm_avg_pu8(m64X, m64Y);
    *(__m64 *)(x + i) = m64Z;
}

使用指令优化需要注意的问题有：

a.关于值域，比如2个8bit数相加，其值可能会溢出；若能保证其不溢出，则可使用一次处理8个数据，否则，必须降低性能，使用其他指令一次处理4个数据了；

b.剩余数据，使用打包处理的数据一般都是4、8或16的整数倍，若待处理数据长度不是其单次处理数据个数的整数倍，剩余数据需单独处理；

补充——如何定位程序热点

程序热点是指程序中最耗时的部分，一般程序优化工作都是优先去优化热点部分，那么如何来定位程序热点呢？

一般而言，主要有2种方法，一种是通过观察与分析，通过分析算法，自然能知道程序热点；另一方面，观察代码结构，一般具有最大循环的地方就是热点，这也是前面那些优化手段都针对循环结构的原因。

另一种方法就是利用工具来找程序热点。x86下可以使用vtune来定位热点，DSP下可使用ccs的profile功能定位出耗时的函数，更近一步地，通过查看编译保留的asm文件，可具体分析每个循环结构情况，了解到该循环是否能流水，循环ii值，以及制约循环ii值是由于变量的依赖还是运算量等详细信息，从而进行有针对性的优化。由于Vtune刚给卸掉，没法截图；下图是CCS编译生成的一个asm文件中一个循环的截图：

最后提一点，某些代码使用Intel编译器编译可以比vc编译器编译出的程序快很多，我遇到过最快的可相差10倍。对于gcc编译后的效率，目前还没测试过。

浅谈程序优化，首发于博客 - 伯乐在线。

David Bolton是一名独立开发者，他使用PostgreSQL和MySQL都已有超过十年的时间。近日，他撰文阐述了选择PostgreSQL而不是MySQL的理由。他认为，MySQL之所以仍然如此流行是因为每个Linux Web托管软件包中都包含它。但随着Oracle将其收购，MySQL的开源程度大不如前。而PostgreSQL不仅发展更快，还加入了JSON支持，成为少数几个支持NoSQL的关系型数据库之一。

MySQL/MariaDB的当前版本是5.7.6（MariaDB为MySQL创建者Monty Widenius创建的一个MySQL分支），PostgreSQL的版本是9.4.1。Bolton从以下几个方面对比了两者的最新版本：

• ANSI标准兼容性：与先前的版本相比，MySQL已经有了长足的进步，但MySQL背后的哲学是，如果客户喜欢，他们就会支持非标准扩展，而PostgreSQL从开始就将标准构建到平台里。不过，二者殊途同归，差别不大；
• ACID遵从性：PostgreSQL有一个存储引擎，而MySQL有9个，但只有MyIsam和InnoDB与大部分用户有关，其中，后者为默认存储引擎。InnoDB和PostgreSQL都完全遵循ACID，差别不大；
• 无锁表修改：MyIsam使用表级锁来提升速度，这会导致写互斥。但PostgreSQL和InnoDB均使用行级锁，差别不大；
• 子查询：长期以来，这一直是MySQL的一个弱点，虽然5.6.5作了重大改进，但PostgreSQL对表连接支持得更好，尤其是MySQL不支持全外连接，因此，这方面PostgreSQL胜过MySQL；
• JSON支持和NoSQL：PostgreSQL最近增加了JSON支持，与传统的关系型数据库相比，它提供了更大的数据存储灵活性，因此，这方面PostgreSQL胜过MySQL。

此外，Bolton指出，选择PostgreSQL还有如下理由：

• 更好的许可：PostgreSQL采用类似MIT的许可协议，允许开发人员做任何事情，包括在开源或闭源产品中商用，而MySQL的客户端遵循GPL许可协议，所以开发人员必须向Oracle付费或者将自己的应用程序开源；
• 更好的数据一致性： PostgreSQL会在数据插入和更新之前进行严格的验证，确保数据合法才会进行相应的操作，但在MySQL中，开发人员需要将服务器设定为严格SQL模式才能达到同样的目的，否则可能会产生不规范数据；
• 服务器扩展：MySQL提供了插件程序API，支持C/C++或任何兼容C的语言，而且从5.7.3版本开始支持全文搜索，PostgreSQL有一个类似的系统但支持的语言更多，包括C/C++、Java、.Net、Perl、 Python、Ruby、Tcl、ODBC等，它甚至可以在单独的进程中运行用户提供的代码；除了所有关系型数据库都包含的有关数据库、表和列的一般信息外，PostgreSQL系统目录中还可以包含关于数据类型、函数和存取方法的信息，开发人员可以通过修改这些信息实现扩展。

感谢徐川对本文的审校。

给InfoQ中文站投稿或者参与内容翻译工作，请邮件至editors@cn.infoq.com。也欢迎大家通过新浪微博（@InfoQ，@丁晓昀），微信（InfoQ）关注我们，并与我们的编辑和其他读者朋友交流。

先来看一张本文所有概念的一个思维导图（在新窗口查看原图）

为什么要有CPU Cache

随着工艺的提升最近几十年CPU的频率不断提升，而受制于制造工艺和成本限制，目前计算机的内存主要是DRAM并且在访问速度上没有质的突破。因此，CPU的处理速度和内存的访问速度差距越来越大，甚至可以达到上万倍。这种情况下传统的CPU通过FSB直连内存的方式显然就会因为内存访问的等待，导致计算资源大量闲置，降低CPU整体吞吐量。同时又由于内存数据访问的热点集中性，在CPU和内存之间用较为快速而成本较高的SDRAM做一层缓存，就显得性价比极高了。

为什么要有多级CPU Cache

随着科技发展，热点数据的体积越来越大，单纯的增加一级缓存大小的性价比已经很低了。因此，就慢慢出现了在一级缓存(L1 Cache)和内存之间又增加一层访问速度和成本都介于两者之间的二级缓存(L2 Cache)。下面是一段从What Every Programmer Should Know About Memory中摘录的解释：

Soon after the introduction of the cache the system got more complicated. The speed difference between the cache and the main memory increased again, to a point that another level of cache was added, bigger and slower than the first-level cache. Only increasing the size of the first-level cache was not an option for economical rea- sons.

此外，又由于程序指令和程序数据的行为和热点分布差异很大，因此L1 Cache也被划分成L1i (i for instruction)和L1d (d for data)两种专门用途的缓存。
下面一张图可以看出各级缓存之间的响应时间差距，以及内存到底有多慢！

什么是Cache Line

Cache Line可以简单的理解为CPU Cache中的最小缓存单位。目前主流的CPU Cache的Cache Line大小都是64Bytes。假设我们有一个512字节的一级缓存，那么按照64B的缓存单位大小来算，这个一级缓存所能存放的缓存个数就是512/64 = 8个。具体参见下图：

为了更好的了解Cache Line，我们还可以在自己的电脑上做下面这个有趣的实验。

下面这段C代码，会从命令行接收一个参数作为数组的大小创建一个数量为N的int数组。并依次循环的从这个数组中进行数组内容访问，循环10亿次。最终输出数组总大小和对应总执行时间。

#include "stdio.h"
#include <stdlib.h>
#include <sys/time.h>

long timediff(clock_t t1, clock_t t2) {
    long elapsed;
    elapsed = ((double)t2 - t1) / CLOCKS_PER_SEC * 1000;
    return elapsed;
}

int main(int argc, char *argv[])
#*******
{

    int array_size=atoi(argv[1]);
    int repeat_times = 1000000000;
    long array[array_size];
    for(int i=0; i<array_size; i++){
        array[i] = 0;
    }
    int j=0;
    int k=0;
    int c=0;
    clock_t start=clock();
    while(j++<repeat_times){
        if(k==array_size){
            k=0;
        }
        c = array[k++];
    }
    clock_t end =clock();
    printf("%lu\n", timediff(start,end));
    return 0;
}

如果我们把这些数据做成折线图后就会发现：总执行时间在数组大小超过64Bytes时有较为明显的拐点（当然，由于博主是在自己的Mac笔记本上测试的，会受到很多其他程序的干扰，因此会有波动）。原因是当数组小于64Bytes时数组极有可能落在一条Cache Line内，而一个元素的访问就会使得整条Cache Line被填充，因而值得后面的若干个元素受益于缓存带来的加速。而当数组大于64Bytes时，必然至少需要两条Cache Line，继而在循环访问时会出现两次Cache Line的填充，由于缓存填充的时间远高于数据访问的响应时间，因此多一次缓存填充对于总执行的影响会被放大，最终得到下图的结果：

如果读者有兴趣的话也可以在自己的linux或者MAC上通过gcc cache_line_size.c -o cache_line_size编译，并通过./cache_line_size执行。

了解Cache Line的概念对我们程序猿有什么帮助？

我们来看下面这个C语言中常用的循环优化例子
下面两段代码中，第一段代码在C语言中总是比第二段代码的执行速度要快。具体的原因相信你仔细阅读了Cache Line的介绍后就很容易理解了。

for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
        int num;    
        //code
        arr[i][j] = num;
    }
}

for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
        int num;    
        //code
        arr[j][i] = num;
    }
}

CPU Cache 是如何存放数据的

你会怎么设计Cache的存放规则

我们先来尝试回答一下那么这个问题：

假设我们有一块4MB的区域用于缓存，每个缓存对象的唯一标识是它所在的物理内存地址。每个缓存对象大小是64Bytes，所有可以被缓存对象的大小总和（即物理内存总大小）为4GB。那么我们该如何设计这个缓存？

如果你和博主一样是一个大学没有好好学习基础/数字电路的人的话，会觉得最靠谱的的一种方式就是：Hash表。把Cache设计成一个Hash数组。内存地址的Hash值作为数组的Index，缓存对象的值作为数组的Value。每次存取时，都把地址做一次Hash然后找到Cache中对应的位置操作即可。
这样的设计方式在高等语言中很常见，也显然很高效。因为Hash值得计算虽然耗时(10000个CPU Cycle左右)，但是相比程序中其他操作（上百万的CPU Cycle）来说可以忽略不计。而对于CPU Cache来说，本来其设计目标就是在几十CPU Cycle内获取到数据。如果访问效率是百万Cycle这个等级的话，还不如到Memory直接获取数据。当然，更重要的原因是在硬件上要实现Memory Address Hash的功能在成本上是非常高的。

为什么Cache不能做成Fully Associative

Fully Associative 字面意思是全关联。在CPU Cache中的含义是：如果在一个Cache集内，任何一个内存地址的数据可以被缓存在任何一个Cache Line里，那么我们成这个cache是Fully Associative。从定义中我们可以得出这样的结论：给到一个内存地址，要知道他是否存在于Cache中，需要遍历所有Cache Line并比较缓存内容的内存地址。而Cache的本意就是为了在尽可能少得CPU Cycle内取到数据。那么想要设计一个快速的Fully Associative的Cache几乎是不可能的。

为什么Cache不能做成Direct Mapped

和Fully Associative完全相反，使用Direct Mapped模式的Cache给定一个内存地址，就唯一确定了一条Cache Line。设计复杂度低且速度快。那么为什么Cache不使用这种模式呢？让我们来想象这么一种情况：一个拥有1M L2 Cache的32位CPU，每条Cache Line的大小为64Bytes。那么整个L2Cache被划为了1M/64=16384条Cache Line。我们为每条Cache Line从0开始编上号。同时32位CPU所能管理的内存地址范围是2^32=4G，那么Direct Mapped模式下，内存也被划为4G/16384=256K的小份。也就是说每256K的内存地址共享一条Cache Line。

但是，这种模式下每条Cache Line的使用率如果要做到接近100%，就需要操作系统对于内存的分配和访问在地址上也是近乎平均的。而与我们的意愿相反，为了减少内存碎片和实现便捷，操作系统更多的是连续集中的使用内存。这样会出现的情况就是0-1000号这样的低编号Cache Line由于内存经常被分配并使用，而16000号以上的Cache Line由于内存鲜有进程访问，几乎一直处于空闲状态。这种情况下，本来就宝贵的1M二级CPU缓存，使用率也许50%都无法达到。

什么是N-Way Set Associative

为了避免以上两种设计模式的缺陷，N-Way Set Associative缓存就出现了。他的原理是把一个缓存按照N个Cache Line作为一组（set），缓存按组划为等分。这样一个64位系统的内存地址在4MB二级缓存中就划成了三个部分（见下图），低位6个bit表示在Cache Line中的偏移量，中间12bit表示Cache组号（set index），剩余的高位46bit就是内存地址的唯一id。这样的设计相较前两种设计有以下两点好处：

• 给定一个内存地址可以唯一对应一个set，对于set中只需遍历16个元素就可以确定对象是否在缓存中（Full Associative中比较次数随内存大小线性增加）
• 每2^18(256K)*64=16M的连续热点数据才会导致一个set内的conflict（Direct Mapped中512K的连续热点数据就会出现conflict）

为什么N-Way Set Associative的Set段是从低位而不是高位开始的

下面是一段从How Misaligning Data Can Increase Performance 12x by Reducing Cache Misses摘录的解释：

The vast majority of accesses are close together, so moving the set index bits upwards would cause more conflict misses. You might be able to get away with a hash function that isn’t simply the least significant bits, but most proposed schemes hurt about as much as they help while adding extra complexity.

由于内存的访问通常是大片连续的，或者是因为在同一程序中而导致地址接近的（即这些内存地址的高位都是一样的）。所以如果把内存地址的高位作为set index的话，那么短时间的大量内存访问都会因为set index相同而落在同一个set index中，从而导致cache conflicts使得L2, L3 Cache的命中率低下，影响程序的整体执行效率。

了解N-Way Set Associative的存储模式对我们有什么帮助

了解N-Way Set的概念后，我们不难得出以下结论：2^(6Bits <Cache Line Offset> + 12Bits <Set Index>) = 2^18 = 512K。即在连续的内存地址中每512K都会出现一个处于同一个Cache Set中的缓存对象。也就是说这些对象都会争抢一个仅有16个空位的缓存池（16-Way Set）。而如果我们在程序中又使用了所谓优化神器的“内存对齐”的时候，这种争抢就会越发增多。效率上的损失也会变得非常明显。具体的实际测试我们可以参考： How Misaligning Data Can Increase Performance 12x by Reducing Cache Misses 一文。

这里我们引用一张Gallery of Processor Cache Effects 中的测试结果图，来解释下内存对齐在极端情况下带来的性能损失。

该图实际上是我们上文中第一个测试的一个变种。纵轴表示了测试对象数组的大小。横轴表示了每次数组元素访问之间的index间隔。而图中的颜色表示了响应时间的长短，蓝色越明显的部分表示响应时间越长。从这个图我们可以得到很多结论。当然这里我们只对内存带来的性能损失感兴趣。有兴趣的读者也可以阅读原文分析理解其他从图中可以得到的结论。

从图中我们不难看出图中每1024个步进，即每1024*4即4096Bytes，都有一条特别明显的蓝色竖线。也就是说，只要我们按照4K的步进去访问内存(内存根据4K对齐），无论热点数据多大它的实际效率都是非常低的！按照我们上文的分析，如果4KB的内存对齐，那么一个80MB的数组就含有20480个可以被访问到的数组元素；而对于一个每512K就会有set冲突的16Way二级缓存，总共有512K/20480=25个元素要去争抢16个空位。那么缓存命中率只有64%，自然效率也就低了。

想要知道更多关于内存地址对齐在目前的这种CPU-Cache的架构下会出现的问题可以详细阅读以下两篇文章：

• How Misaligning Data Can Increase Performance 12x by Reducing Cache Misses
• Gallery of Processor Cache Effects

Cache淘汰策略

在文章的最后我们顺带提一下CPU Cache的淘汰策略。常见的淘汰策略主要有LRU和Random两种。通常意义下LRU对于Cache的命中率会比Random更好，所以CPU Cache的淘汰策略选择的是LRU。当然也有些实验显示在Cache Size较大的时候Random策略会有更高的命中率

总结

CPU Cache对于程序猿是透明的，所有的操作和策略都在CPU内部完成。但是，了解和理解CPU Cache的设计、工作原理有利于我们更好的利用CPU Cache，写出更多对CPU Cache友好的程序

Reference

1. Gallery of Processor Cache Effects
2. How Misaligning Data Can Increase Performance 12x by Reducing Cache Misses
3. Introduction to Caches

关于CPU Cache：程序猿需要知道的那些，首发于博客 - 伯乐在线。

简介

我常常主张说，研究分布式系统最难的是改变你思考的方式。对于激发这种改变，我找到的一些很实用的阅读材料。如下。

Thought Provokers

一些让你考虑你设计方式的随笔。不是所有事都可以靠大服务器，数据库和事物来解决的。

• Harvest, Yield and Scalable Tolerant Systems CAP原理在现实世界里的应用来自Brewer等人
• On Designing and Deploying Internet Scale Services James Hamilton
• Latency Exists, Cope! 处理延迟及其架构方面影响的说明
• Latency – the new web performance bottleneck 内容不太新了，但是值得关注下
• The Perils of Good Abstractions 构建完美的API/接口很困难
• Chaotic Perspectives 大规模系统有开发人员不喜欢的所有东西——不可预测，无序，并行
• Website Architecture 一些来自各类大型网站的可扩展架构文章
• Data on the Outside versus Data on the Inside Pat helland
• Memories, Guesses and Apologies Pat Helland
• SOA and Newton’s Universe – Pat Helland
• Building on Quicksand – Pat Helland
• Why Distributed Computing – Jim Waldo
• A Note on Distributed Computing – Waldo, Wollrath 等人
• Stevey’s Google Platforms Rant – Yegge的SOA平台经验

Amazon

有些有关的技术，但更有趣的是他们创造的与之配合的文化和结构。

• A Conversation with Werner Vogels 关于亚马逊转型为一个基于服务的架构的采访报道
• Discipline and Focus 关于亚马逊转型为一个基于服务的架构的另一篇采访
• Vogels on Scalability
• SOA creates order out of chaos @ Amazon

Google

当前分布式系统领域的“火箭科学”（形容艰深的学问）

• MapReduce
• Chubby Lock Manager
• Google File System
• BigTable
• Data Management for Internet-Scale Single-Sign-On
• Dremel: Interactive Analysis of Web-Scale Datasets
• Large-scale Incremental Processing Using Distributed Transactions and Notifications
• Megastore: Providing Scalable, Highly Available Storage for Interactive Services – 实现跨数据中心、低延迟的paxos算法的巧妙设计。
• Spanner – Google的可扩展、多版本、全球分布且同步复制的数据库。
• Photon – 连续数据流的容错和扩容。扩容是非常困难的，尤其是在时钟偏移、高可用性和分布式的情况下.
• Mesa: Geo-Replicated, Near Real-Time, Scalable Data Warehousing 用于存储谷歌互联网广告业务相关的关键测量数据的数据仓库系统。

eBay

有趣的是他们抛弃了大多数的J2EE，并使用了大量的数据库分区。同时，看看他们的网站升级工具。

• SD Forum 2006

一致性模型

构建能够适应环境的系统的关键是寻求正确权衡一致性和可用性。

• CAP Conjecture – 一致性，可用性，分区容忍性不可能同时满足
• Consistency, Availability, and Convergence – 证明了在一个典型系统中一致性可能的上界。
• CAP Twelve Years Later: How the “Rules” Have Changed – Eric Brewer 在原来权衡描述工作上的扩展
• Consistency and Availability – Vogels
• Eventual Consistency – Vogels
• Avoiding Two-Phase Commit – 两阶段提交的避免方法
• 2PC or not 2PC, Wherefore Art Thou XA – 两阶段提交不是银弹
• Life Beyond Distributed Transactions – Helland
• If you have too much data, then ‘good enough’ is good enough – NoSQL, 数据理论的未来- Pat Helland
• Starbucks doesn’t do two phase commit – 在起作用的异步机制
• You Can’t Sacrifice Partition Tolerance – 另外的 CAP 说明
• Optimistic Replication – 数据主从复制的弱一致性方法

理论

一些描述了分布式系统设计中各种各样的重要因素的论文。

• Distributed Computing Economics – Jim Gray
• Rules of Thumb in Data Engineering – Jim Gray and Prashant Shenoy
• Fallacies of Distributed Computing – Peter Deutsch
• Impossibility of distributed consensus with one faulty process 也称为FLP [访问需要帐号或付费，免费版本在这里： here]
• Unreliable Failure Detectors for Reliable Distributed Systems.一种处理FLP难题的方法
• Lamport Clocks -当每台电脑的时钟都是独立的时候，你如何建立对时间的全局视图。
• The Byzantine Generals Problem
• Lazy Replication: Exploiting the Semantics of Distributed Services
• Scalable Agreement – Towards Ordering as a Service
• Scalable Eventually Consistent Counters over Unreliable Networks 在不可靠的世界，可扩展计数很困难。

语言和工具

使用特定技术构建分布式系统的问题。

• Programming Distributed Erlang Applications: Pitfalls and Recipes 构建可靠的分布式应用并不仅仅是的选择Erlang还是OTP的问题那么简单。

基础设施

• Principles of Robust Timing over the Internet 即便是调试这么基础的事，管理时钟也很重要。

存储

• Consistent Hashing and Random Trees
• Amazon’s Dynamo Storage Service

Paxos 一致性算法

理解这种算法是一个挑战。我建议在阅读其他论文之前先读读“Paxos Made Simple”，然后在读完其他论文之后，再读一遍。

• The Part-Time Parliament – Leslie Lamport
• Paxos Made Simple – Leslie Lamport
• Paxos Made Live – An Engineering Perspective – Chandra等人
• Revisiting the Paxos Algorithm – Lynch 等人
• How to build a highly available system with consensus – Butler Lampson
• Reconfiguring a State Machine – Lamport 等人 -改变集群的成员
• Implementing Fault-Tolerant Services Using the State Machine Approach: a Tutorial – Fred Schneider

其他一致性文章

• Mencius: Building Efficient Replicated State Machines for WANs – 针对广域网的一致性算法

Gossip 协议（传染行为）

• Epidemic Routing Bibliography
• How robust are gossip-based communication protocols 
• Astrolabe: A Robust and Scalable Technology For Distributed Systems Monitoring, Management, and Data Mining
• Epidemic Computing at Cornell
• Fighting Fire With Fire: Using Randomized Gossip To Combat Stochastic Scalability Limits
• Bi-Modal Multicast
• ACM SIGOPS Operating Systems Review – Gossip-based computer networking
• SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol

P2P

• Chord:一种针对互联网应用的可扩展的点对点查找协议。
• Kademlia: 一种基于XOR的点对点信息系统
• Pastry: 可扩展的，去中心化的对象位置和对大规模点对点系统的路由。
• PAST: 一种大规模，持久化的点对点存储功能——Pastry上的存储系统
• SCRIBE: 一个大规模且去中心化的应用层多播基础设施——Pastry上的广域消息系统。

分布式系统阅读清单，首发于博客 - 伯乐在线。

我们先回顾一下主流Java的垃圾回收器(HotSpot JVM)。本文是针对堆的垃圾回收展开讨论的。

堆被分解为较小的三个部分。具体分为：新生代、老年代、持久代。

1. 绝大部分新生成的对象都放在Eden区，当Eden区将满，JVM会因申请不到内存，而触发Young GC ,进行Eden区+有对象的Survivor区(设为S0区)垃圾回收，把存活的对象用复制算法拷贝到一个空的Survivor(S1)中，此时Eden区被清空，另外一个Survivor S0也为空。下次触发Young GC回收Eden+S0，将存活对象拷贝到S1中。新生代垃圾回收简单、粗暴、高效。
2. 若发现Survivor区满了，则将这些对象拷贝到old区或者Survivor没满但某些对象足够Old,也拷贝到Old区(每次Young GC都会使Survivor区存活对象值+1，直到阈值)。 3.Old区也会进行垃圾收集(Young GC),发生一次 Major GC 至少伴随一次Young GC，一般比Young GC慢十倍以上。
3. JVM在Old区申请不到内存，会进行Full GC。Old区使用一般采用Concurrent-Mark–Sweep策略回收内存。

总结：Java垃圾回收器是一种“自适应的、分代的、停止—复制、标记-清扫”式的垃圾回收器。

缺点：

1. GC过程中会出现STW(Stop-The-World)，若Old区对象太多，STW耗费大量时间。
2. CMS收集器对CPU资源很敏感。
3. CMS收集器无法处理浮动垃圾，可能出现“Concurrent Mode Failure”失败而导致另一次Full GC的产生。
4. CMS导致内存碎片问题。

G1收集器

在G1中，堆被划分成 许多个连续的区域(region)。每个区域大小相等，在1M~32M之间。JVM最多支持2000个区域，可推算G1能支持的最大内存为2000*32M=62.5G。区域(region)的大小在JVM初始化的时候决定，也可以用-XX:G1HeapReginSize设置。

在G1中没有物理上的Yong(Eden/Survivor)/Old Generation，它们是逻辑的，使用一些非连续的区域(Region)组成的。

新生代收集

G1的新生代收集跟ParNew类似，当新生代占用达到一定比例的时候，开始出发收集。

被圈起的绿色部分为新生代的区域(region)，经过Young GC后存活的对象被复制到一个或者多个区域空闲中，这些被填充的区域将是新的新生代；当新生代对象的年龄(逃逸过一次Young GC年龄增加１)已经达到某个阈值(ParNew默认15)，被复制到老年代的区域中。

回收过程是停顿的(STW,Stop-The-Word);回收完成之后根据Young GC的统计信息调整Eden和Survivor的大小，有助于合理利用内存，提高回收效率。

回收的过程多个回收线程并发收集。

老年代收集

和CMS类似，G1收集器收集老年代对象会有短暂停顿。

1. 标记阶段，首先初始标记(Initial-Mark),这个阶段是停顿的(Stop the World Event)，并且会触发一次普通Mintor GC。对应GC log:GC pause (young) (inital-mark)
2. Root Region Scanning，程序运行过程中会回收survivor区(存活到老年代)，这一过程必须在young GC之前完成。
3. Concurrent Marking，在整个堆中进行并发标记(和应用程序并发执行)，此过程可能被young GC中断。在并发标记阶段，若发现区域对象中的所有对象都是垃圾，那个这个区域会被立即回收(图中打X)。同时，并发标记过程中，会计算每个区域的对象活性(区域中存活对象的比例)。
4. Remark, 再标记，会有短暂停顿(STW)。再标记阶段是用来收集 并发标记阶段 产生新的垃圾(并发阶段和应用程序一同运行)；G1中采用了比CMS更快的初始快照算法:snapshot-at-the-beginning (SATB)。
5. Copy/Clean up，多线程清除失活对象，会有STW。G1将回收区域的存活对象拷贝到新区域，清除Remember Sets，并发清空回收区域并把它返回到空闲区域链表中。
6. 复制/清除过程后。回收区域的活性对象已经被集中回收到深蓝色和深绿色区域。

关于Remembered Set概念：G1收集器中，Region之间的对象引用以及其他收集器中的新生代和老年代之间的对象引用是使用Remembered Set来避免扫描全堆。G1中每个Region都有一个与之对应的Remembered Set，虚拟机发现程序对Reference类型数据进行写操作时，会产生一个Write Barrier暂时中断写操作，检查Reference引用的对象是否处于不同的Region之间(在分代中例子中就是检查是否老年代中的对象引用了新生代的对象)，如果是便通过CardTable把相关引用信息记录到被引用对象所属的Region的Remembered Set中。当内存回收时，在GC根节点的枚举范围加入Remembered Set即可保证不对全局堆扫描也不会有遗漏。

G1虽然保留了CMS关于代的概念，但是代已经不是物理上连续区域，而是一个逻辑的概念。在标记过程中，每个区域的对象活性都被计算，在回收时候，就可以根据用户设置的停顿时间，选择活性较低的区域收集，这样既能保证垃圾回收，又能保证停顿时间，而且也不会降低太多的吞吐量。Remark阶段新算法的运用，以及收集过程中的压缩，都弥补了CMS不足。引用Oracle官网的一句话：“G1 is planned as the long term replacement for the Concurrent Mark-Sweep Collector (CMS)”。

参考：

1. Memory Management in the Java HotSpot™ Virtual Machine
2. Getting Started with the G1 Garbage Collector
3. 垃圾优先型垃圾回收器调优
4. 深入理解Java虚拟机:JVM高级特性与最佳实践

相关文章

• Java/JVM是如何构建的？看看OpenJDK吧！
• Linux与JVM的内存关系分析
• 自恢复JVM
• 5步避免Java堆空间错误
• JVM必备指南
• 从Java代码到字节码（1）
• 高吞吐低延迟Java应用的垃圾回收优化
• JVM的重排序
• Linux HotSopt虚拟机GC线程的CPU占用率
• 如何估算内存消耗

今年是2015年，在过去几年中，电面（电话面试）是筛选程序员职位候选人的最流行的方式。它让雇佣双方很容易互相了解对方，候选人不需要去未来雇主的所在地，面试官也不用做额外的安排。这是我介绍程序员面试问题的文章的第二部分。我得到反馈说第一部分过于偏重编码的题了，许多程序员希望我针对电面问题列一个类似的列表。为了顺利通过电面进入下一轮，你必须足够好地回答与你工作要求相关的全部问题。在大多针对Java和C++开发者的电面中，你不仅会遇到相应程序语言的问题，还会遇到其他技术的问题，比如SQL、XML、UNIX、泛型编程、面向对象编程、数据结构与算法、网络、编码以及工作的其他方面。由于程序员求职电面的多变性，你需要有特殊的技巧，以面试官期待的方式展示自己。

要记住一件重要的事，在回答电面问题的时候，尽早提出关键点，总是给出关键性回答。由于面试官的问题往往会覆盖很大范围的主题，他们更喜欢关键性回答，而不是“OK，我知道”之类的空话。在面对面的面试中，你会有机会更深入地解释问题的。顺便说一下，这并不是固定的规则，根据面试官对你的回答的反应，你可以了解到他期望得到什么样的回答。如果他进行追问，期望你多说一些，那么你就应该多说。但如果他立刻跳到下一个问题，那么你就应该回答得清晰简洁。在这篇文章中，我要和你分享一些常见的有趣编程问题，它们是针对电面改编过的。其中大部分都来自科技公司的电面环节，包括Barclays、Citi、Nomura之类的银行，和Infosys、TCS、CTS、Tech Mahindra和HCL之类的提供服务的公司。像我之前提过的，面试题是随机选的，但大部分是基于基础知识，因为那是面试官在电面时想考察的。尽管这些问题大多数是针对初级开发者（2至5年经验），高级和资深程序员仍然可以把它们用作自己面试的题目。如果你是一名面试官，你可以用这些问题快速筛选开发职位的候选人。我在此提供简短答案，并给出详细答案的链接。

编程岗位电话面试问答Top 50

下面是几乎50道程序员电面题目的列表。这些问题可以用来考察任何程序员、开发者、软件工程师、测试和运营工程师，因为它们是基于程序设计的基础知识的。但它们最适合程序员和开发者。顺便说一下，如果你是Java开发者，并且在寻找Java电面题目，去看看那个列表。本列表更加普遍，适用于所有的程序员，包括Python、Ruby、Perl和C#开发者。

1. 从哈希表，二叉树和链表中取元素需要多少时间？如果你有数百万记录呢？

哈希表需要O(1)时间，二叉树需要O(logN) (N是树中节点数)，链表需要O(N) (N是链表中节点数）。如果数据结构工作正常（比如哈希表没有或只有相对少量冲突，二叉树是平衡的），数百万记录并不影响效率。如果工作不正常，那么效率会随着记录数上升而下降。

2. 覆盖(Overriding)和重载(Overloading)的区别是什么？  (detailed answer)

覆盖在运行时决定，重载是在编译时决定。并且覆盖和重载的机制不同，例如在Java中，重载方法的签名必须不同于原先方法的，但对于覆盖签名必须相同。

3. fork一个进程和生成一个线程有什么区别？

当你fork一个进程时，新的进程将执行和父进程相同的代码，只是在不同的内存空间中。但当你在已有进程中生成一个线程时，它会生成一个新的代码执行路线，但共享同一个内存空间。

4. 什么是临界区？ (answer)

临界区是一段代码，十分重要，在多线程中同一时间只能被一个线程执行。可以用信号量或互斥量来保护临界区。在Java中你可以用synchronized关键字或ReentrantLock来保护临界区。

5. 值类型和引用类型有什么区别？ (answer)

值类型是更加优化的类型，总是不可变的(immutable)，例如Java原始的int、long、double和float。引用类型指向一个对象，可能是可变的，也可能是不变的。你也可以说值类型指向一个值，引用类型指向一个对象。

6. 什么是在进程中的堆和栈？(detailed answer)

在同一个进程中，有两块不同的内存区域。以Java来说，栈用来存储原始值和指向对象的引用类型，但对象本身总是在堆中被创建。堆和栈的一个重要区别是，堆内存被所有线程共享，但每个线程有自己的栈。

7. 什么是版本控制？(answer)

版本控制是用来存储代码和管理代码库版本的软件，例如SVN、CVS、Git、Perforce和ClearCase。它们在对比代码、审查代码和从之前的稳定版本构造时十分高效。所有的专业开发都使用某种版本控制工具，否则你无法有效的管理代码，尤其是如果有20个开发者在同一个代码库上工作的时候。版本控制工具在保持代码库一致性和处理代码冲突上扮演着十分重要的角色。

8. 什么是强类型程序设计语言？(answer)

在强类型语言中，编译器确保类型的正确性，例如你无法在String类型中存放数字，反之亦然。Java是强类型语言，因此存在各种数据类型（如int、float、String、char、boolean等）。你只能将兼容的值存入相应的类型中。与此相反，弱类型语言不要求在编译时进行类型检查，它们根据上下文处理值。Python和Perl是两个常见的弱类型程序设计语言的例子，你可以将数字组成的字符串保存在数字类型中。

9. 可否描述一下有效(valid)的XML和格式正确(well-formed)的XML的区别？

格式正确的XML有根元素，所有标签都是正确关闭的，属性是正确定义的，它们的值正确地加上了引号。另一方面，有效的XML可以根据一个XSD文件或模式(schema)进行验证。所以一个XML可能是格式正确但不有效的（因为包含不被模式允许的标签）。

10. DOM和SAX语法分析器有什么区别？(detailed answer)

DOM语法分析器是驻留内存的，将整个XML文件装载到内存中，并创建一个DOM树进行语法分析。SAX语法分析器是一个基于事件的语法分析器，所以它根据收到的事件（如开始标签、结束标签、属性开始和属性结束）来对XML文档进行语法分析。根据他们的分析方法，DOM语法分析器并不适用于大的XML文件，因为它会占用大量的内存空间，你的进程可能会耗尽内存。应该用SAX分析大的文件。对于小的文件，DOM往往比SAX快很多。

11. 线程和进程的关系是什么？(detailed answer)

一个进程可以有多个线程，但一个线程总是属于唯一的进程。两个进程不能共享内存空间，除非它们有意通过共享内存进行进程间通信。但是同一进程的两个线程总是共享相同的内存。

12. 不可变(immutable)类是什么意思？(detailed answer)

一个类，如果在创建之后它的状态就不能被改变，那么他就是不可变的。例如Java中的String。一旦你创建了一个String，例如“Java”，你就不能再改变它的内容。任何对这个字符串的改变（例如转换到大写、与另一个String连接）将创建一个新的对象。不可变的对象在并行程序设计中很有用，因为它们可以在进程间被共享，不需要担心同步。事实上，整个函数是程序设计的模型都是在不可变对象上构建的。

13. 你为何要创建模拟(mock)对象？ (answer)

模拟对象在测试软件中一个独立的单元时很有用，事实上，存根(stub)和模拟都是创建自动化单元测试的有力工具。假设你在写一个显示货币兑换率的程序，但没有一个可以连通的URL，现在如果想测试你的代码，可以用模拟对象。在Java的世界中，有很多框架可以为你生成强大的模拟对象，例如Mockito和PowerMock。

14. 什么是SQL注入？

SQL注入是一种安全漏洞，它使得入侵者可以从系统中窃取数据。任何从用户那里得到输入并不加验证地创建SQL查询的系统都可能被SQL注入攻击。在这样的系统中，入侵者可以输入SQL代码，而不是数据，来获取额外的数据。有很多用敏感信息（如用户id、密码和个人信息）被人利用这种漏洞获取的实例。 在Java中，你可以用Prepared语句来避免SQL注入。

15. 在SQL中，内连接(inner join)和左连接(left join)有什么区别？(answer)

在SQL中，主要有两种连接类型，内连接和外连接。外连接包括右外连接和左外连接。内连接和左连接的主要区别是，内连接中两个表都匹配的记录才被选中，左连接中两个表都匹配的记录被选中，外加左表的所有记录都被选中。要留意包含“所有”的查询，它们往往要求左连接，例如写一个SQL查询来找所有的部门和它们的雇员人数。如果你用内连接处理这个查询，你会漏掉没有人工作的空部门。

16. MVC中的V代表什么，意味着什么？(answe）

在MVC模式中，V是视图(View)。视图是用户看到的东西，比如网页。这是一个非常重要的web应用开发设计模式，它基于关注点分离原则，目的是不同模块可以独立修改，不影响其他模块。在Java的世界中，有很多提供MVC模式的开源框架，例如Struts 2和Spring MVC。顺便说一下，M代表模型(Model)，C代表控制器(Controller)。模型是实际的业务对象，例如用户、雇员、订单，控制器用来将请求分发给正确的处理单元。

17. 类和对象的区别是什么？ (detailed answer)

类是用来创建对象的设计图。一个类包括代码和行为，一个对象包括状态和行为。要创建一个对象，你必须创建一个表达对象结构的类。类还被用来在内存中映射对象，在Java中，JVM替你完成这项工作。

18. 什么是疏耦合(loose-coupling)？

疏耦合是一种值得追求的软件特性，它使得对软件一个部分的修改不会影响到其他的部分。例如，在一个疏耦合的软件中，对UI布局的改变不应该影响后端的类结构。

19. 组合(composition)，聚合(aggregation)和关联(association)的区别是什么？ (detailed answer)

关联的意思是两个对象是相互联系的。组合是关联的一种形式，即一个对象由多个对象组成，但是它们必须共存，例如人体由各种器官组合而成，独立的器官不能生存，它们必须在身体内发挥作用。聚合也是关联的一种形式，表示对象的集合，例如城市是居民的聚合。

20. 接口和抽象类有什么区别？ (detailed answer)

这是所有程序员面试最经典的问题。接口是最纯粹的抽象形式，没有任何具体的东西。抽象类是一些抽象和具体事物的组合体。这个区别在不同语言中可能会不同，例如在Java中你可以扩展(extend)多个接口，但只能继承一个抽象类。更详细的讨论见于详细答案。

21. 什么是单元测试？(answer)

单元测试是测试独立单元（而不是整个应用程序）功能性的一种方法。在不同语言中，有很多工具可以做单元测试。例如在Java中，你可以用JUnit或TestNG来写单元测试。单元测试经常在构建时自动运行，或者在一个持续的环境（例如Jenkins）中运行。

22. 你能否描述三种不同的在应用程序发布前对其进行测试的方式？

单元测试，集成测试，冒烟测试。单元测试用来测试独立的单元是否依照预期工作，集成测试用来测试已被测试过的独立单元能否共同工作，冒烟测试用来测试软件最常用的功能是否正常工作，例如在一个飞机订票网站中，你应该能订票，取消或更改航班。

23. 迭代和递归有什么区别？(detailed answer)

迭代通过循环来重复执行同一步骤，递归通过调用函数自身来做重复性工作。递归经常是复杂问题（例如汉诺塔、反转链表或反转字符串）的清晰简洁的解决方案。递归的一个缺陷是深度，由于递归在栈中存储中间结果，你只能进行一定深度的递归，在那之后你的程序会因为StackOverFlowError而崩溃。这就是在产品代码中优先使用迭代而不是递归的原因。

24. &和&&运算符的区别是什么？(detailed answer)

&是位运算符，&&是逻辑运算符。&和&&的一个区别是位运算符（&）可以被用于整型和布尔类型，逻辑运算符（&&）只能被用于布尔类型变量。当你写a & b时，两个整型数的每一位都会进行与运算。当你写a && b时，第二个参数可能会也可能不会被执行，这也是它被称为短路运算符的原因，至少在Java中是这样的。我很喜欢这个问题，经常对初级开发者和毕业生问这个问题。

25. 1 XOR 1的结果是什么？

答案是0，因为XOR在两个操作数（按位）不同时返回1，相同时返回0。例如0 XOR 0仍然是零，但0 XOR 1和1 XOR 0的结果是1。

26. 如何得到一个整型数的最后一位？ (answer)

用取模运算符，数字 % 10返回数字的最后一位。例如2345 % 10会返回5，567 % 10会返回7。类似的，除运算符可以用来去掉数字的最后一位，例如2345 / 10的结果是234，567 / 10的结果是56。这是值得了解的一个重要技巧，可以用来解决类似回文数、反转数的问题。

27. 什么是测试驱动开发？

测试驱动是一种常见的开发方法，在这种方法中，测试代码在功能代码之前编写。测试决定了程序的结构。测试驱动的纯粹主义者在写为应用写测试之前，不会写一行的应用代码。这能很大幅度地提高代码质量，经常被认为是巨星级开发者的品质。

28. 里氏替换原则(Liskov substitution principle, LSP)是什么？(answer)

里氏替换原则是鲍勃大叔称作SOLID的五条设计原则中的一条。里氏替换原则规定，所有的子类都能作为父类的代理(proxy)工作。例如，如果一个方法需要父类对象作为输入，那么如果你提供一个子类对象，它也应该正常工作。任何不能替代父类的类都违反了里氏替换原则。这实际上是一个难以答出的问题，如果你答出了，那么就会给面试官留下好的印象。

29. 什么是开闭(Open closed)设计原则？(answer)

开闭原则是SOLID中另一个重要的原则，它规定一个系统对扩展是开放的，但对修改是封闭的。意思是说，如果一个新的功能要被加入一个稳定的系统，那么你不需要碰已被测试过的现有代码，新的功能可以通过只添加新类来实现。

30. 二叉树和二叉查找树的区别是什么？

二叉查找树是有序的二叉树，所有节点（例如根节点）的左子树节点的值都小于或等于该节点的值，右子树节点的值都大于或等于该节点的值。它是一个重要的数据结构，可以用来表示有序的数据。

31. 你能否给出一个递归算法的实际例子？(example)

递归算法能适用在很多地方，例如与二叉树和链表相关的算法。几个与递归算法的例子包括反转字符串，计算斐波那契数列。其他的例子包括反转链表、树遍历以及快速排序。

31. 算法的时间复杂度是什么？

时间复杂度表示的是运行时间对输入量的比率。他表示一个算法处理一定量的输入需要多长时间。它是一个估计值，但足够表示输入量从十增长到一千万时，你的算法会有什么样的表现。

33. 链表和数组有哪些重要区别？(detailed answer)

链表和数组都是程序设计世界中重要的数据结构。它们间最明显的区别是，数组将元素存放在连续的地址中，链表将数据存放在内存中任意的位置。这使得链表有巨大的扩展自己的灵活性，因为内存总是分散的。这种情况总是可能的：你无法创建一个数组来存放一百万个整数，但可以用链表来存放，因为空间是存在的，只是不连续。其他的不同都是源于这项事实。例如，在数组中，如果你知道下标，可以用O(1)的时间得到一个元素，但在链表中要花O(n)的时间。更多不同参见详细答案。

33. 在哈希表中处理冲突的方法都有哪些？

线性探测(linear probing)，二次哈希(double hashing)和链接(chaining)。在线性探测中，如果桶已经被占据了，那么函数会线性地检查下一个桶，直到找到一个空位。在链接中，多个元素可以存储在同一个桶中。

34. 正则表达式是什么意思？ (answer)

正则表达式是在文本型数据上进行模式匹配的方法。它是一种搜索的强有力方法，例如搜索长字符串中的某些字符，例如搜索一本书中是否含有某个单词。所有主流程序设计语言都支持正则表达式，但是Perl正则表达式的能力是著名的。Java的java.util.regex包也支持类似Perl的正则表达式。你可以用正则表达式检查email地址是否有效，电话号码是否有效，邮政编码是否有效，甚至社会保险号(SSN)是否有效。正则表达式最简答的例子之一是检查字符串是不是一个数。

35. 什么是无状态(stateless)系统？

无状态系统是不维护内部状态的系统。这种系统在任何时刻，对相同的输入都会给出相同的输出。编写优化一个无状态系统总是比较简单的，所以如果可能，你总是应该优先编写无状态系统。

36. 写一个SQL查询，在雇员表中查找第二高的工资。 (solution)

这是SQL面试的经典题目之一，尽管已经很老了，还是很有趣，并且可以追问很多问题来测试候选人的知识深度。你可以用相关或不相关的子查询来查找第二高工资。如果你在用SQL Server或MySQL，你也可以用类似TOP和LIMIT之类的关键字，前提是面试官允许。查找第二高工资的最简答方法是：

这个查询首先查找最高工资，然后将它从列表中排除，再查找最高工资。很明显，第二次返回的是第二高工资。

37. 可否描述一下什么是关联的和不关联的子查询？(answer)

在关联的子查询中，内层查询依赖于外层查询，对外层查询的每一行执行。非关联的子查询不依赖于外层查询，可以独立执行。因此，前者慢，后者快。顺便说一下，关联的子查询有一些很棒的应用，其中包括在雇员表中查找第N高的工资，这在上一道SQL问题中也有提到。

39. 不用算术运算符，如何判定一个数是否是二的幂？(solution)

当你听到不能用算术运算符的限制时，应该立刻假定这是一道关于位运算的题。如果没有这条限制，那么你可以轻松地用取模和除运算符检查一个数是不是二的幂。用位运算符，有一个很巧妙的方法来完成任务。你可以用下面这段代码来检查一个数是不是二的幂

public static boolean powerOfTwo(int x) {
return (x & (x - 1)) == 0;
}

x & (x-1)是一个很棒的技巧，可以将最右边的为1的位设为0。我是从《高效程序的奥秘》这本书中学到的。

40. 如何在UNIX上找到一个正在运行的Java进程？(command)

你可以组合使用ps和grep命令来查找UNIX机器上的任何进程。假设你的Java进程有名字，或者有任何可以用来匹配的文字，那么使用这个命令。

ps -ef | grep “myJavaApp”

ps -e将列出所有的进程（所有用户的进程，不只是你的），ps -f将显示所有细节，包括PID。如果你想要深入调查或用kill命令杀死这个进程，你会需要PID。

41. 如何在UNIX中寻找大的文件，例如1GB以上的文件？ (command)

你可以轻松地用find命令寻找大的文件，因为它提供依据大小寻找文件的选项。如果你的文件系统满了，你的Java进程因为没有空间而崩溃，那么就使用这个命令。这个命令可以列出所有大于1GB的文件。你可以很容易地改变大小，例如寻找所有100MB以上的文件，就用+100M。

find . – type f -size +1G -print

42. shell脚本是什么？

shell脚本是包含程序元素（例如if和for循环）的一组shell命令，它可以自动做一些重复的任务。例如，你可以写一个shell脚本来每天清理日志文件，为记录历史备份数据，以及其他家务活、版本发布、监视等等。

这个程序员电面问题列表到此为止了。你可能已经注意到了，只有42道题，但是标题说有50道，剩下的8道在哪？好吧，为了补偿这8道题，我在此分享8篇文章，你可以找到剩余的问题：

• 给程序员的20道字符串编程题( read here)

• 给软件开发者的15道数据结构与算法题(see here)

• 10道所有开发者都应该指导的面试题(read more)

• 给2至3年经验程序员的20道核心Java问题(check here)

• 21道SQL查询面试题与答案(read more)

• 给Java程序员的23道难题 (read here)

• 给程序员的10道XML面试题(see here)

• 来自Java面试的50道多线程和并发问题 (check here)

• 来自程序员面试的20道软件设计问题(read more)

• 18道Java设计模式面试题(see here)

感谢你一直读到这里，如果你喜欢这篇文章，并觉得它对你的电话面试有帮助，请与朋友和同事分享。十分感谢所有提高面试题质量的建议。

扩展阅读：

http://javarevisited.blogspot.com/2015/02/50-programmer-phone-interview-questions-answers.html

【译者注：译文对原文的描述有修改。】

程序员面试：电话面试问答Top 50，首发于博客 - 伯乐在线。

Linux 4.0 里，你可能再也不需要重启你的操作系统。

在大多数的服务器或者数据中心里，喜欢用linux的一个原因是你不需要频繁的进行重启操作。诚然，某些关键性的补丁必须要进行重启，但你也可以等到数月后再做此操作。现在，得益于 linux 内核的最新更新 你也许可以数年间都不用重启。

感谢 Ksplice 项目，使得这一特性在2009年就可以实现。此项目在对原始和打过补丁的内核进行比较后，使用一个定制的内核模块将新的代码加入到运行内核中。在支持Ksplice的内核中，每个将被修补的功能都携带有一套特殊标志用以进行区分。Ksplice进程会监视正在修补该函数的代码是不是当前不在使用，当当，打上补丁，你的服务器上继续运行。

Oracle 在 2011 年收购了 Ksplice 项目，并将其作为 RHEL 的一项可选服务，使其应用于它自己的Oracle Linux 中(一个RHEL(Red Hat Enterprise Linux ) 的克隆版本)。这将此项技术隔离于其他企业版和服务器版 Linux 之外。

后来 KemelCare 为大部分企业发行版 Linux 发布了一项提供非启动式补丁服务。此程序作为专利软件，只能通过按月支付来享有此服务。这从而很难满足大多数Linux系统管理员。

所以，Red Hat 和 SUSE 开始着手完全开源的为 Linux 安装严重补丁的非重启方案。Red Had 的项目命名为 kpatch, SUSE的项目命名为 kGraft.

两个公司采用了不同的途径。Kpatch 发布了一个 stop_machine() 命令。之后，它着眼于现有的栈处理去使用ftrace，如果打补丁可以被做得很安全，它会重定向运行着的代码到补丁函数，而后就删除现在过时的代码。

比过去好的是，数据中心被运行在世界各处，但是它们中的许多都需要一个21世纪式的重启。今天的数据中心必须更有效率，更有鲁棒性和灵活性，这超过以往任何时候。我们检查怎样才能运行好你的数据中心，与之相对的是外包到一个云或者一个服务提供商，或是采取混合的方式。

Kgraft 一直使用ftrace，尽管它是工作在线程级的。当一个老的函数被调用，它会定位到线程的一个点，然后将其切换到新的函数。

虽然最终结果相同，即操作系统在打补丁的时候保持运行，但还是有显著的性能差异的。当kGraft可能花费数分钟的时候，Kpatch可以只需要1到40毫秒，但他们从不会停机。

在2014年10月召开的linux 开发者大会上，两个小组合二为一并且开始致力于联合最好的程序使linux打补丁时不再重启。实际上，他们最终是把kpatch和kGraft都丢进了Linux内核。
Jiri Kosina，一位SUSE软件工程师和Linux内核开发者解释说，Linux内核的热补丁将会“为函数提供一个基本基础设施”  热补丁（例如：代码重定向），包括为了包含实际补丁的内核模块的API（应用程序接口），和为了在用户空间可以操作补丁的API/ABI(应用二进制接口)，这是“相对简单和简约的，因为它尽可能多的利用了已有的内核基础（名为ftrace）。它也是自包含的，在某种意义上说，它不在任何其他的内核子系统中调用自身（它甚至不接触其他任何代码）”

Linux 4.0 RC 版现在已经放出，Kosina 声称：”现在实施的x86架构只是作为一个参考架构，对于powerpc, s390 和 arm 的支持工作已经在进行中了“。确实，对于这些架构的支持源代码已经在 Live Patching Git code 上了。

简单的代码仅仅只是开始，你的发行版将通过补丁来支持和使用它。随着 Red Hat 和 SUSE 的支持，live 补丁将很快默认在所有商业Linux发行版中。

Linux 4.0 不再需要重启，首发于博客 - 伯乐在线。