Category Archives: Interview

正确使用 Volatile 变量

Java 语言中的 volatile 变量可以被看作是一种 “程度较轻的 synchronized”;与 synchronized 块相比,volatile 变量所需的编码较少,并且运行时开销也较少,但是它所能实现的功能也仅是 synchronized 的一部分。本文介绍了几种有效使用 volatile 变量的模式,并强调了几种不适合使用 volatile 变量的情形。

锁提供了两种主要特性:互斥(mutual exclusion)可见性(visibility)。互斥即一次只允许一个线程持有某个特定的锁,因此可使用该特性实现对共享数据的协调访问协议,这样,一次就只有一个线程能够使用该共享数据。可见性要更加复杂一些,它必须确保释放锁之前对共享数据做出的更改对于随后获得该锁的另一个线程是可见的 —— 如果没有同步机制提供的这种可见性保证,线程看到的共享变量可能是修改前的值或不一致的值,这将引发许多严重问题。

Volatile 变量

Volatile 变量具有 synchronized 的可见性特性,但是不具备原子特性。这就是说线程能够自动发现 volatile 变量的最新值。Volatile 变量可用于提供线程安全,但是只能应用于非常有限的一组用例:多个变量之间或者某个变量的当前值与修改后值之间没有约束。因此,单独使用 volatile 还不足以实现计数器、互斥锁或任何具有与多个变量相关的不变式(Invariants)的类(例如 “start <=end”)。

出于简易性或可伸缩性的考虑,您可能倾向于使用 volatile 变量而不是锁。当使用 volatile 变量而非锁时,某些习惯用法(idiom)更加易于编码和阅读。此外,volatile 变量不会像锁那样造成线程阻塞,因此也很少造成可伸缩性问题。在某些情况下,如果读操作远远大于写操作,volatile 变量还可以提供优于锁的性能优势。

正确使用 volatile 变量的条件

您只能在有限的一些情形下使用 volatile 变量替代锁。要使 volatile 变量提供理想的线程安全,必须同时满足下面两个条件:

  • 对变量的写操作不依赖于当前值。
  • 该变量没有包含在具有其他变量的不变式中。

实际上,这些条件表明,可以被写入 volatile 变量的这些有效值独立于任何程序的状态,包括变量的当前状态。

第一个条件的限制使 volatile 变量不能用作线程安全计数器。虽然增量操作(x++)看上去类似一个单独操作,实际上它是一个由读取-修改-写入操作序列组成的组合操作,必须以原子方式执行,而 volatile 不能提供必须的原子特性。实现正确的操作需要使 x 的值在操作期间保持不变,而 volatile 变量无法实现这点。(然而,如果将值调整为只从单个线程写入,那么可以忽略第一个条件。)

大多数编程情形都会与这两个条件的其中之一冲突,使得 volatile 变量不能像 synchronized 那样普遍适用于实现线程安全。清单 1 显示了一个非线程安全的数值范围类。它包含了一个不变式 —— 下界总是小于或等于上界。

清单 1. 非线程安全的数值范围类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
@NotThreadSafe
public class NumberRange {
    private int lower, upper;
    public int getLower() { return lower; }
    public int getUpper() { return upper; }
    public void setLower(int value) {
        if (value > upper)
            throw new IllegalArgumentException(...);
        lower = value;
    }
    public void setUpper(int value) {
        if (value < lower)
            throw new IllegalArgumentException(...);
        upper = value;
    }
}

这种方式限制了范围的状态变量,因此将 lower 和 upper 字段定义为 volatile 类型不能够充分实现类的线程安全;从而仍然需要使用同步。否则,如果凑巧两个线程在同一时间使用不一致的值执行 setLowersetUpper 的话,则会使范围处于不一致的状态。例如,如果初始状态是 (0, 5),同一时间内,线程 A 调用 setLower(4) 并且线程 B 调用 setUpper(3),显然这两个操作交叉存入的值是不符合条件的,那么两个线程都会通过用于保护不变式的检查,使得最后的范围值是 (4, 3) —— 一个无效值。至于针对范围的其他操作,我们需要使 setLower()setUpper() 操作原子化 —— 而将字段定义为 volatile 类型是无法实现这一目的的。

性能考虑

使用 volatile 变量的主要原因是其简易性:在某些情形下,使用 volatile 变量要比使用相应的锁简单得多。使用 volatile 变量次要原因是其性能:某些情况下,volatile 变量同步机制的性能要优于锁。

很难做出准确、全面的评价,例如 “X 总是比 Y 快”,尤其是对 JVM 内在的操作而言。(例如,某些情况下 VM 也许能够完全删除锁机制,这使得我们难以抽象地比较 volatilesynchronized 的开销。)就是说,在目前大多数的处理器架构上,volatile 读操作开销非常低 —— 几乎和非 volatile 读操作一样。而 volatile 写操作的开销要比非 volatile 写操作多很多,因为要保证可见性需要实现内存界定(Memory Fence),即便如此,volatile 的总开销仍然要比锁获取低。

volatile 操作不会像锁一样造成阻塞,因此,在能够安全使用 volatile 的情况下,volatile 可以提供一些优于锁的可伸缩特性。如果读操作的次数要远远超过写操作,与锁相比,volatile 变量通常能够减少同步的性能开销。

正确使用 volatile 的模式

很多并发性专家事实上往往引导用户远离 volatile 变量,因为使用它们要比使用锁更加容易出错。然而,如果谨慎地遵循一些良好定义的模式,就能够在很多场合内安全地使用 volatile 变量。要始终牢记使用 volatile 的限制 —— 只有在状态真正独立于程序内其他内容时才能使用 volatile —— 这条规则能够避免将这些模式扩展到不安全的用例。

模式 #1:状态标志

也许实现 volatile 变量的规范使用仅仅是使用一个布尔状态标志,用于指示发生了一个重要的一次性事件,例如完成初始化或请求停机。

很多应用程序包含了一种控制结构,形式为 “在还没有准备好停止程序时再执行一些工作”,如清单 2 所示:

清单 2. 将 volatile 变量作为状态标志使用
1
2
3
4
5
6
7
8
9
10
11
volatile boolean shutdownRequested;
...
public void shutdown() { shutdownRequested = true; }
public void doWork() {
    while (!shutdownRequested) {
        // do stuff
    }
}

很可能会从循环外部调用 shutdown() 方法 —— 即在另一个线程中 —— 因此,需要执行某种同步来确保正确实现 shutdownRequested 变量的可见性。(可能会从 JMX 侦听程序、GUI 事件线程中的操作侦听程序、通过 RMI 、通过一个 Web 服务等调用)。然而,使用 synchronized 块编写循环要比使用清单 2 所示的 volatile 状态标志编写麻烦很多。由于 volatile 简化了编码,并且状态标志并不依赖于程序内任何其他状态,因此此处非常适合使用 volatile。

这种类型的状态标记的一个公共特性是:通常只有一种状态转换;shutdownRequested 标志从 false 转换为 true,然后程序停止。这种模式可以扩展到来回转换的状态标志,但是只有在转换周期不被察觉的情况下才能扩展(从 falsetrue,再转换到 false)。此外,还需要某些原子状态转换机制,例如原子变量。

模式 #2:一次性安全发布(one-time safe publication)

缺乏同步会导致无法实现可见性,这使得确定何时写入对象引用而不是原语值变得更加困难。在缺乏同步的情况下,可能会遇到某个对象引用的更新值(由另一个线程写入)和该对象状态的旧值同时存在。(这就是造成著名的双重检查锁定(double-checked-locking)问题的根源,其中对象引用在没有同步的情况下进行读操作,产生的问题是您可能会看到一个更新的引用,但是仍然会通过该引用看到不完全构造的对象)。

实现安全发布对象的一种技术就是将对象引用定义为 volatile 类型。清单 3 展示了一个示例,其中后台线程在启动阶段从数据库加载一些数据。其他代码在能够利用这些数据时,在使用之前将检查这些数据是否曾经发布过。

清单 3. 将 volatile 变量用于一次性安全发布
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class BackgroundFloobleLoader {
    public volatile Flooble theFlooble;
    public void initInBackground() {
        // do lots of stuff
        theFlooble = new Flooble();  // this is the only write to theFlooble
    }
}
public class SomeOtherClass {
    public void doWork() {
        while (true) {
            // do some stuff...
            // use the Flooble, but only if it is ready
            if (floobleLoader.theFlooble != null)
                doSomething(floobleLoader.theFlooble);
        }
    }
}

如果 theFlooble 引用不是 volatile 类型,doWork() 中的代码在解除对 theFlooble 的引用时,将会得到一个不完全构造的 Flooble

该模式的一个必要条件是:被发布的对象必须是线程安全的,或者是有效的不可变对象(有效不可变意味着对象的状态在发布之后永远不会被修改)。volatile 类型的引用可以确保对象的发布形式的可见性,但是如果对象的状态在发布后将发生更改,那么就需要额外的同步。

模式 #3:独立观察(independent observation)

安全使用 volatile 的另一种简单模式是:定期 “发布” 观察结果供程序内部使用。例如,假设有一种环境传感器能够感觉环境温度。一个后台线程可能会每隔几秒读取一次该传感器,并更新包含当前文档的 volatile 变量。然后,其他线程可以读取这个变量,从而随时能够看到最新的温度值。

使用该模式的另一种应用程序就是收集程序的统计信息。清单 4 展示了身份验证机制如何记忆最近一次登录的用户的名字。将反复使用 lastUser 引用来发布值,以供程序的其他部分使用。

清单 4. 将 volatile 变量用于多个独立观察结果的发布
1
2
3
4
5
6
7
8
9
10
11
12
13
public class UserManager {
    public volatile String lastUser;
    public boolean authenticate(String user, String password) {
        boolean valid = passwordIsValid(user, password);
        if (valid) {
            User u = new User();
            activeUsers.add(u);
            lastUser = user;
        }
        return valid;
    }
}

该模式是前面模式的扩展;将某个值发布以在程序内的其他地方使用,但是与一次性事件的发布不同,这是一系列独立事件。这个模式要求被发布的值是有效不可变的 —— 即值的状态在发布后不会更改。使用该值的代码需要清楚该值可能随时发生变化。

模式 #4:“volatile bean” 模式

volatile bean 模式适用于将 JavaBeans 作为“荣誉结构”使用的框架。在 volatile bean 模式中,JavaBean 被用作一组具有 getter 和/或 setter 方法 的独立属性的容器。volatile bean 模式的基本原理是:很多框架为易变数据的持有者(例如 HttpSession)提供了容器,但是放入这些容器中的对象必须是线程安全的。

在 volatile bean 模式中,JavaBean 的所有数据成员都是 volatile 类型的,并且 getter 和 setter 方法必须非常普通 —— 除了获取或设置相应的属性外,不能包含任何逻辑。此外,对于对象引用的数据成员,引用的对象必须是有效不可变的。(这将禁止具有数组值的属性,因为当数组引用被声明为 volatile 时,只有引用而不是数组本身具有 volatile 语义)。对于任何 volatile 变量,不变式或约束都不能包含 JavaBean 属性。清单 5 中的示例展示了遵守 volatile bean 模式的 JavaBean:

清单 5. 遵守 volatile bean 模式的 Person 对象
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
@ThreadSafe
public class Person {
    private volatile String firstName;
    private volatile String lastName;
    private volatile int age;
    public String getFirstName() { return firstName; }
    public String getLastName() { return lastName; }
    public int getAge() { return age; }
    public void setFirstName(String firstName) {
        this.firstName = firstName;
    }
    public void setLastName(String lastName) {
        this.lastName = lastName;
    }
    public void setAge(int age) {
        this.age = age;
    }
}

volatile 的高级模式

前面几节介绍的模式涵盖了大部分的基本用例,在这些模式中使用 volatile 非常有用并且简单。这一节将介绍一种更加高级的模式,在该模式中,volatile 将提供性能或可伸缩性优势。

volatile 应用的的高级模式非常脆弱。因此,必须对假设的条件仔细证明,并且这些模式被严格地封装了起来,因为即使非常小的更改也会损坏您的代码!同样,使用更高级的 volatile 用例的原因是它能够提升性能,确保在开始应用高级模式之前,真正确定需要实现这种性能获益。需要对这些模式进行权衡,放弃可读性或可维护性来换取可能的性能收益 —— 如果您不需要提升性能(或者不能够通过一个严格的测试程序证明您需要它),那么这很可能是一次糟糕的交易,因为您很可能会得不偿失,换来的东西要比放弃的东西价值更低。

模式 #5:开销较低的读-写锁策略

目前为止,您应该了解了 volatile 的功能还不足以实现计数器。因为 ++x 实际上是三种操作(读、添加、存储)的简单组合,如果多个线程凑巧试图同时对 volatile 计数器执行增量操作,那么它的更新值有可能会丢失。

然而,如果读操作远远超过写操作,您可以结合使用内部锁和 volatile 变量来减少公共代码路径的开销。清单 6 中显示的线程安全的计数器使用 synchronized 确保增量操作是原子的,并使用 volatile 保证当前结果的可见性。如果更新不频繁的话,该方法可实现更好的性能,因为读路径的开销仅仅涉及 volatile 读操作,这通常要优于一个无竞争的锁获取的开销。

清单 6. 结合使用 volatile 和 synchronized 实现 “开销较低的读-写锁”
1
2
3
4
5
6
7
8
9
10
11
12
@ThreadSafe
public class CheesyCounter {
    // Employs the cheap read-write lock trick
    // All mutative operations MUST be done with the 'this' lock held
    @GuardedBy("this") private volatile int value;
    public int getValue() { return value; }
    public synchronized int increment() {
        return value++;
    }
}

之所以将这种技术称之为 “开销较低的读-写锁” 是因为您使用了不同的同步机制进行读写操作。因为本例中的写操作违反了使用 volatile 的第一个条件,因此不能使用 volatile 安全地实现计数器 —— 您必须使用锁。然而,您可以在读操作中使用 volatile 确保当前值的可见性,因此可以使用锁进行所有变化的操作,使用 volatile 进行只读操作。其中,锁一次只允许一个线程访问值,volatile 允许多个线程执行读操作,因此当使用 volatile 保证读代码路径时,要比使用锁执行全部代码路径获得更高的共享度 —— 就像读-写操作一样。然而,要随时牢记这种模式的弱点:如果超越了该模式的最基本应用,结合这两个竞争的同步机制将变得非常困难。

结束语

与锁相比,Volatile 变量是一种非常简单但同时又非常脆弱的同步机制,它在某些情况下将提供优于锁的性能和伸缩性。如果严格遵循 volatile 的使用条件 —— 即变量真正独立于其他变量和自己以前的值 —— 在某些情况下可以使用 volatile 代替 synchronized 来简化代码。然而,使用 volatile 的代码往往比使用锁的代码更加容易出错。本文介绍的模式涵盖了可以使用 volatile 代替 synchronized 的最常见的一些用例。遵循这些模式(注意使用时不要超过各自的限制)可以帮助您安全地实现大多数用例,使用 volatile 变量获得更佳性能。


相关主题

  • 您可以参阅本文在 developerWorks 全球站点上的 英文原文
  • Java Concurrency in Practice:使用 Java 代码开发并发程序的 how-to 手册,内容包括构建并编写线程安全的类和程序、避免性能影响、管理性能和测试并发应用程序。
  • 流行的原子:介绍了 Java 5.0 中新增的原子变量类,该特性对 volatile 变量进行了扩展,从而支持原子状态转换。
  • 非阻塞算法简介:介绍如何使用原子变量而不是锁实现并发算法。
  • Volatiles:从 Wikipedia 获得关于 volatile 变量的更多信息。
  • Java 技术专区:提供了数百篇有关 Java 编程各个方面的文章。

from:https://www.ibm.com/developerworks/cn/java/j-jtp06197.html

技术面试要了解的算法和数据结构知识

目录

  • 在线练习
  • 在线编程面试
  • 数据结构
  • 算法
  • 贪心算法
  • 位运算
  • 复杂度分析
  • 视频教程
  • 面试宝典
  • 计算机科学资讯
  • 文件结构

在线练习

在线编程面试

数据结构

链表

  • 链表是一种由节点(Node)组成的线性数据集合,每个节点通过指针指向下一个节点。它是一种由节点组成,并能用于表示序列的数据结构。
  • 单链表 :每个节点仅指向下一个节点,最后一个节点指向空(null)。
  • 双链表 :每个节点有两个指针p,n。p指向前一个节点,n指向下一个节点;最后一个节点指向空。
  • 循环链表 :每个节点指向下一个节点,最后一个节点指向第一个节点。
  • 时间复杂度:
    • 索引:O(n)
    • 查找:O(n)
    • 插入:O(1)
    • 删除:O(1)

  • 栈是一个元素集合,支持两个基本操作:push用于将元素压入栈,pop用于删除栈顶元素。
  • 后进先出的数据结构(Last In First Out, LIFO)
  • 时间复杂度
    • 索引:O(n)
    • 查找:O(n)
    • 插入:O(1)
    • 删除:O(1)

队列

  • 队列是一个元素集合,支持两种基本操作:enqueue 用于添加一个元素到队列,dequeue 用于删除队列中的一个元素。
  • 先进先出的数据结构(First In First Out, FIFO)。
  • 时间复杂度
    • 索引:O(n)
    • 查找:O(n)
    • 插入:O(1)
    • 删除:O(1)

  • 树是无向、联通的无环图。

二叉树

  • 二叉树是一个树形数据结构,每个节点最多可以有两个子节点,称为左子节点和右子节点。
  • 满二叉树(Full Tree) :二叉树中的每个节点有 0 或者 2 个子节点。

大数据

  • 完美二叉树(Perfect Binary) :二叉树中的每个节点有两个子节点,并且所有的叶子节点的深度是一样的。
  • 完全二叉树 :二叉树中除最后一层外其他各层的节点数均达到最大值,最后一层的节点都连续集中在最左边。

二叉查找树

  • 二叉查找树(BST)是一种二叉树。其任何节点的值都大于等于左子树中的值,小于等于右子树中的值。
  • 时间复杂度
    • 索引:O(log(n))
    • 查找:O(log(n))
    • 插入:O(log(n))
    • 删除:O(log(n))

大数据

字典树

  • 字典树,又称为基数树或前缀树,是一种用于存储键值为字符串的动态集合或关联数组的查找树。树中的节点并不直接存储关联键值,而是该节点在树中的位置决定了其关联键值。一个节点的所有子节点都有相同的前缀,根节点则是空字符串。

大数据

树状数组

  • 树状数组,又称为二进制索引树(Binary Indexed Tree,BIT),其概念上是树,但以数组实现。数组中的下标代表树中的节点,每个节点的父节点或子节点的下标可以通过位运算获得。数组中的每个元素都包含了预计算的区间值之和,在整个树更新的过程中,这些计算的值也同样会被更新。
  • 时间复杂度
    • 区间求和:O(log(n))
    • 更新:O(log(n))

大数据

线段树

  • 线段树是用于存储区间和线段的树形数据结构。它允许查找一个节点在若干条线段中出现的次数。
  • 时间复杂度
    • 区间查找:O(log(n))
    • 更新:O(log(n))

大数据

  • 堆是一种基于树的满足某些特性的数据结构:整个堆中的所有父子节点的键值都满足相同的排序条件。堆分为最大堆和最小堆。在最大堆中,父节点的键值永远大于等于所有子节点的键值,根节点的键值是最大的。最小堆中,父节点的键值永远小于等于所有子节点的键值,根节点的键值是最小的。
  • 时间复杂度
    • 索引:O(log(n))
    • 查找:O(log(n))
    • 插入:O(log(n))
    • 删除:O(log(n))
    • 删除最大值/最小值:O(1)

大数据

哈希

  • 哈希用于将任意长度的数据映射到固定长度的数据。哈希函数的返回值被称为哈希值、哈希码或者哈希。如果不同的主键得到相同的哈希值,则发生了冲突。
  • Hash Maphash map  是一个存储键值间关系的数据结构。HashMap 通过哈希函数将键转化为桶或者槽中的下标,从而便于指定值的查找。
  • 冲突解决
    • 链地址法( Separate Chaining :在链地址法中,每个桶(bucket)是相互独立的,每一个索引对应一个元素列表。处理HashMap 的时间就是查找桶的时间(常量)与遍历列表元素的时间之和。
    • 开放地址法( Open Addressing :在开放地址方法中,当插入新值时,会判断该值对应的哈希桶是否存在,如果存在则根据某种算法依次选择下一个可能的位置,直到找到一个未被占用的地址。开放地址即某个元素的位置并不永远由其哈希值决定。

大数据

  • 图是G =(V,E)的有序对,其包括顶点或节点的集合 V 以及边或弧的集合E,其中E包括了两个来自V的元素(即边与两个顶点相关联 ,并且该关联为这两个顶点的无序对)。
  • 无向图 :图的邻接矩阵是对称的,因此如果存在节点 u 到节点 v 的边,那节点 v 到节点 u 的边也一定存在。
  • 有向图 :图的邻接矩阵不是对称的。因此如果存在节点 u 到节点 v 的边并不意味着一定存在节点 v 到节点 u 的边。

大数据

算法

排序

快速排序

  • 稳定:否
  • 时间复杂度
    • 最优:O(nlog(n))
    • 最差:O(n^2)
    • 平均:O(nlog(n))

大数据

合并排序

  • 合并排序是一种分治算法。这个算法不断地将一个数组分为两部分,分别对左子数组和右子数组排序,然后将两个数组合并为新的有序数组。
  • 稳定:是
  • 时间复杂度:
    • 最优:O(nlog(n))
    • 最差:O(nlog(n))
    • 平均:O(nlog(n))

桶排序

  • 桶排序是一种将元素分到一定数量的桶中的排序算法。每个桶内部采用其他算法排序,或递归调用桶排序。
  • 时间复杂度
    • 最优:Ω(n + k)
    • 最差: O(n^2)
    • 平均:Θ(n + k)

大数据

基数排序

  • 基数排序类似于桶排序,将元素分发到一定数目的桶中。不同的是,基数排序在分割元素之后没有让每个桶单独进行排序,而是直接做了合并操作。
  • 时间复杂度
    • 最优:Ω(nk)
    • 最差: O(nk)
    • 平均:Θ(nk)

图算法

深度优先 搜索

  • 深度优先搜索是一种先遍历子节点而不回溯的图遍历算法。
  • 时间复杂度:O(|V| + |E|)

大数据

广度优先 搜索

  • 广度优先搜索是一种先遍历邻居节点而不是子节点的图遍历算法。
  • 时间复杂度:O(|V| + |E|)

大数据

拓扑排序

  • 拓扑排序是有向图节点的线性排序。对于任何一条节点 u 到节点 v 的边,u 的下标先于 v。
  • 时间复杂度:O(|V| + |E|)

Dijkstra算法

  • Dijkstra 算法是一种在有向图中查找单源最短路径的算法。
  • 时间复杂度:O(|V|^2)

大数据

Bellman-Ford算法

  • Bellman-Ford  是一种在带权图中查找单一源点到其他节点最短路径的算法。
  • 虽然时间复杂度大于 Dijkstra 算法,但它可以处理包含了负值边的图。
  • 时间复杂度:
    • 最优:O(|E|)
    • 最差:O(|V||E|)

大数据

Floyd-Warshall 算法

  • Floyd-Warshall  算法是一种在无环带权图中寻找任意节点间最短路径的算法。
  • 该算法执行一次即可找到所有节点间的最短路径(路径权重和)。
  • 时间复杂度:
    • 最优:O(|V|^3)
    • 最差:O(|V|^3)
    • 平均:O(|V|^3)

最小生成树算法

  • 最小生成树算法是一种在无向带权图中查找最小生成树的贪心算法。换言之,最小生成树算法能在一个图中找到连接所有节点的边的最小子集。
  • 时间复杂度:O(|V|^2)

Kruskal 算法

  • Kruskal  算法也是一个计算最小生成树的贪心算法,但在 Kruskal 算法中,图不一定是连通的。
  • 时间复杂度:O(|E|log|V|)

贪心算法

  • 贪心算法总是做出在当前看来最优的选择,并希望最后整体也是最优的。
  • 使用贪心算法可以解决的问题必须具有如下两种特性:
    • 最优子结构
      • 问题的最优解包含其子问题的最优解。
    • 贪心选择
      • 每一步的贪心选择可以得到问题的整体最优解。
  • 实例-硬币选择问题
  • 给定期望的硬币总和为 V 分,以及 n 种硬币,即类型是 i 的硬币共有 coinValue[i] 分,i的范围是 [0…n – 1]。假设每种类型的硬币都有无限个,求解为使和为 V 分最少需要多少硬币?
  • 硬币:便士(1美分),镍(5美分),一角(10美分),四分之一(25美分)。
  • 假设总和 V 为41,。我们可以使用贪心算法查找小于或者等于 V 的面值最大的硬币,然后从 V 中减掉该硬币的值,如此重复进行。
    • V = 41 | 使用了0个硬币
    • V = 16 | 使用了1个硬币(41 – 25 = 16)
    • V = 6 | 使用了2个硬币(16 – 10 = 6)
    • V = 1 | 使用了3个硬币(6 – 5 = 1)
    • V = 0 | 使用了4个硬币(1 – 1 = 0)

运算

  • 位运算即在比特级别进行操作的技术。使用位运算技术可以带来更快的运行速度与更小的内存使用。
  • 测试第 k 位:s & (1 << k);
  • 设置第k位:s |= (1 << k);
  • 关闭第k位:s &= ~(1 << k);
  • 切换第k位:s ^= (1 << k);
  • 乘以2n:s << n;
  • 除以2n:s >> n;
  • 交集:s & t;
  • 并集:s | t;
  • 减法:s & ~t;
  • 提取最小非0位:s & (-s);
  • 提取最小0位:~s & (s + 1);
  • 交换值:x ^= y; y ^= x; x ^= y;

运行时分析

大 O 表示

  • 大 O 表示用于表示某个算法的上界,用于描述最坏的情况。

大数据

小 O 表示

  • 小 O 表示用于描述某个算法的渐进上界,二者逐渐趋近。

大 Ω 表示

  • 大 Ω 表示用于描述某个算法的渐进下界。

大数据

小 ω 表示

  • 小 ω 表示用于描述某个算法的渐进下界,二者逐渐趋近。

Theta Θ 表示

  • Theta Θ 表示用于描述某个算法的确界,包括最小上界和最大下界。

大数据

视频教程

面试宝典

 

技术面试要了解的算法和数据结构知识

java面试题

关于Spring的69个面试问答

这篇文章总结了一些关于Spring框架的重要问题,这些问题都是你在面试或笔试过程中可能会被问到的。下次你再也不用担心你的面试了,Java Code Geeks这就帮你解答。
大多数你可能被问到的问题都列举在下面的列表中了。所有的核心模块,从基础的Spring功能(如Spring Beans)到上层的Spring MVC框架,文章中都会进行简短的讲解。看完这些面试问题,你应该看看我们的Spring教程

我们开始吧!

目录

Spring概述

依赖注入

Spring Beans

Spring注解

Spring的对象访问

Spring面向切面编程

Spring MVC框架

Spring概述

1.什么是Spring?

Spring是一个开源的Java EE开发框架。Spring框架的核心功能可以应用在任何Java应用程序中,但对Java EE平台上的Web应用程序有更好的扩展性。Spring框架的目标是使得Java EE应用程序的开发更加简捷,通过使用POJO为基础的编程模型促进良好的编程风格。

2.Spring有哪些优点?

  • 轻量级:Spring在大小和透明性方面绝对属于轻量级的,基础版本的Spring框架大约只有2MB。
  • 控制反转(IOC):Spring使用控制反转技术实现了松耦合。依赖被注入到对象,而不是创建或寻找依赖对象。
  • 面向切面编程(AOP): Spring支持面向切面编程,同时把应用的业务逻辑与系统的服务分离开来。
  • 容器:Spring包含并管理应用程序对象的配置及生命周期。
  • MVC框架:Spring的web框架是一个设计优良的web MVC框架,很好的取代了一些web框架。
  • 事务管理:Spring对下至本地业务上至全局业务(JAT)提供了统一的事务管理接口。
  • 异常处理:Spring提供一个方便的API将特定技术的异常(由JDBC, Hibernate, 或JDO抛出)转化为一致的、Unchecked异常。

3.Spring框架有哪些模块?

Spring框架的基本模块如下所示:

  • Core module
  • Bean module
  • Context module
  • Expression Language module
  • JDBC module
  • ORM module
  • OXM module
  • Java Messaging Service(JMS) module
  • Transaction module
  • Web module
  • Web-Servlet module
  • Web-Struts module
  • Web-Portlet module

4.解释核心容器(应用上下文)模块

这是Spring的基本模块,它提供了Spring框架的基本功能。BeanFactory 是所有Spring应用的核心。Spring框架是建立在这个模块之上的,这也使得Spring成为一个容器。

5.BeanFactory – BeanFactory 实例

BeanFactory是工厂模式的一种实现,它使用控制反转将应用的配置和依赖与实际的应用代码分离开来。

最常用的BeanFactory实现是XmlBeanFactory类。

6.XmlBeanFactory

最常用的就是org.springframework.beans.factory.xml.XmlBeanFactory,它根据XML文件中定义的内容加载beans。该容器从XML文件中读取配置元数据,并用它来创建一个完备的系统或应用。

7.解释AOP模块

AOP模块用来开发Spring应用程序中具有切面性质的部分。该模块的大部分服务由AOP Aliance提供,这就保证了Spring框架和其他AOP框架之间的互操作性。另外,该模块将元数据编程引入到了Spring。

8.解释抽象JDBC和DAO模块

通过使用抽象JDBC和DAO模块保证了与数据库连接代码的整洁与简单,同时避免了由于未能关闭数据库资源引起的问题。它在多种数据库服务器的错误信息之上提供了一个很重要的异常层。它还利用Spring的AOP模块为Spring应用程序中的对象提供事务管理服务。

9.解释对象/关系映射集成模块

Spring通过提供ORM模块在JDBC的基础上支持对象关系映射工具。这样的支持使得Spring可以集成主流的ORM框架,包括Hibernate, JDO, 及iBATIS SQL Maps。Spring的事务管理可以同时支持以上某种框架和JDBC。

10.解释web模块

Spring的web模块建立在应用上下文(application context)模块之上,提供了一个适合基于web应用程序的上下文环境。该模块还支持了几个面向web的任务,如透明的处理多文件上传请求及将请求参数同业务对象绑定起来。

11.解释Spring MVC模块

Spring提供MVC框架构建web应用程序。Spring可以很轻松的同其他MVC框架结合,但Spring的MVC是个更好的选择,因为它通过控制反转将控制逻辑和业务对象完全分离开来。

12.Spring的配置文件

Spring的配置文件是一个XML文件,文件包含了类信息并描述了这些类是如何配置和互相调用的。

13.Spring IoC容器是什么?

Spring IOC负责创建对象、管理对象(通过依赖注入)、整合对象、配置对象以及管理这些对象的生命周期。

14.IOC有什么优点?

IOC或依赖注入减少了应用程序的代码量。它使得应用程序的测试很简单,因为在单元测试中不再需要单例或JNDI查找机制。简单的实现以及较少的干扰机制使得松耦合得以实现。IOC容器支持勤性单例及延迟加载服务。

15.应用上下文是如何实现的?

FileSystemXmlApplicationContext 容器加载XML文件中beans的定义。XML Bean配置文件的完整路径必须传递给构造器。

FileSystemXmlApplicationContext 容器也加载XML文件中beans的定义。注意,你需要正确的设置CLASSPATH,因为该容器会在CLASSPATH中查看bean的XML配置文件。

WebXmlApplicationContext:该容器加载xml文件,这些文件定义了web应用中所有的beans。

16.Bean Factory和ApplicationContext有什么区别?

ApplicationContext提供了一种解决文档信息的方法,一种加载文件资源的方式(如图片),他们可以向监听他们的beans发送消息。另外,容器或者容器中beans的操作,这些必须以bean工厂的编程方式处理的操作可以在应用上下文中以声明的方式处理。应用上下文实现了MessageSource,该接口用于获取本地消息,实际的实现是可选的。

17.Spring应用程序看起来像什么?

  • 一个定义功能的接口
  • 实现包括属性,setter和getter方法,功能等
  • Spring AOP
  • Spring的XML配置文件
  • 使用该功能的客户端编程

依赖注入

18.Spring中的依赖注入是什么?

依赖注入作为控制反转(IOC)的一个层面,可以有多种解释方式。在这个概念中,你不用创建对象而只需要描述如何创建它们。你不必通过代码直接的将组件和服务连接在一起,而是通过配置文件说明哪些组件需要什么服务。之后IOC容器负责衔接。

19.有哪些不同类型的IOC(依赖注入)?

  • 构造器依赖注入:构造器依赖注入在容器触发构造器的时候完成,该构造器有一系列的参数,每个参数代表注入的对象。
  • Setter方法依赖注入:首先容器会触发一个无参构造函数或无参静态工厂方法实例化对象,之后容器调用bean中的setter方法完成Setter方法依赖注入。

20.你推荐哪种依赖注入?构造器依赖注入还是Setter方法依赖注入?

你可以同时使用两种方式的依赖注入,最好的选择是使用构造器参数实现强制依赖注入,使用setter方法实现可选的依赖关系。

Spring Beans

21.什么是Spring Beans?

Spring Beans是构成Spring应用核心的Java对象。这些对象由Spring IOC容器实例化、组装、管理。这些对象通过容器中配置的元数据创建,例如,使用XML文件中定义的创建。

在Spring中创建的beans都是单例的beans。在bean标签中有一个属性为”singleton”,如果设为true,该bean是单例的,如果设为false,该bean是原型bean。Singleton属性默认设置为true。因此,spring框架中所有的bean都默认为单例bean。

22.Spring Bean中定义了什么内容?

Spring Bean中定义了所有的配置元数据,这些配置信息告知容器如何创建它,它的生命周期是什么以及它的依赖关系。

23.如何向Spring 容器提供配置元数据?

有三种方式向Spring 容器提供元数据:

24.你如何定义bean的作用域?

在Spring中创建一个bean的时候,我们可以声明它的作用域。只需要在bean定义的时候通过’scope’属性定义即可。例如,当Spring需要产生每次一个新的bean实例时,应该声明bean的scope属性为prototype。如果每次你希望Spring返回一个实例,应该声明bean的scope属性为singleton。

25.说一下Spring中支持的bean作用域

Spring框架支持如下五种不同的作用域:

  • singleton:在Spring IOC容器中仅存在一个Bean实例,Bean以单实例的方式存在。
  • prototype:一个bean可以定义多个实例。
  • request:每次HTTP请求都会创建一个新的Bean。该作用域仅适用于WebApplicationContext环境。
  • session:一个HTTP Session定义一个Bean。该作用域仅适用于WebApplicationContext环境.
  • globalSession:同一个全局HTTP Session定义一个Bean。该作用域同样仅适用于WebApplicationContext环境.

bean默认的scope属性是’singleton‘。

26.Spring框架中单例beans是线程安全的吗?

不是,Spring框架中的单例beans不是线程安全的。

27.解释Spring框架中bean的生命周期

  • Spring容器读取XML文件中bean的定义并实例化bean。
  • Spring根据bean的定义设置属性值。
  • 如果该Bean实现了BeanNameAware接口,Spring将bean的id传递给setBeanName()方法。
  • 如果该Bean实现了BeanFactoryAware接口,Spring将beanfactory传递给setBeanFactory()方法。
  • 如果任何bean BeanPostProcessors 和该bean相关,Spring调用postProcessBeforeInitialization()方法。
  • 如果该Bean实现了InitializingBean接口,调用Bean中的afterPropertiesSet方法。如果bean有初始化函数声明,调用相应的初始化方法。
  • 如果任何bean BeanPostProcessors 和该bean相关,调用postProcessAfterInitialization()方法。
  • 如果该bean实现了DisposableBean,调用destroy()方法。

28.哪些是最重要的bean生命周期方法?能重写它们吗?

有两个重要的bean生命周期方法。第一个是setup方法,该方法在容器加载bean的时候被调用。第二个是teardown方法,该方法在bean从容器中移除的时候调用。

bean标签有两个重要的属性(init-method 和 destroy-method),你可以通过这两个属性定义自己的初始化方法和析构方法。Spring也有相应的注解:@PostConstruct 和 @PreDestroy。

29.什么是Spring的内部bean?

当一个bean被用作另一个bean的属性时,这个bean可以被声明为内部bean。在基于XML的配置元数据中,可以通过把元素定义在 或元素内部实现定义内部bean。内部bean总是匿名的并且它们的scope总是prototype。

30.如何在Spring中注入Java集合类?

Spring提供如下几种类型的集合配置元素

  • list元素用来注入一系列的值,允许有相同的值。
  • set元素用来注入一些列的值,不允许有相同的值。
  • map用来注入一组”键-值”对,键、值可以是任何类型的。
  • props也可以用来注入一组”键-值”对,这里的键、值都字符串类型。

31.什么是bean wiring?

Wiring,或者说bean Wiring是指beans在Spring容器中结合在一起的情况。当装配bean的时候,Spring容器需要知道需要哪些beans以及如何使用依赖注入将它们结合起来。

32.什么是bean自动装配?

Spring容器可以自动配置相互协作beans之间的关联关系。这意味着Spring可以自动配置一个bean和其他协作bean之间的关系,通过检查BeanFactory 的内容里没有使用和< property>元素。

33.解释自动装配的各种模式?

自动装配提供五种不同的模式供Spring容器用来自动装配beans之间的依赖注入:

  • no:默认的方式是不进行自动装配,通过手工设置ref 属性来进行装配bean。
  • byName:通过参数名自动装配,Spring容器查找beans的属性,这些beans在XML配置文件中被设置为byName。之后容器试图匹配、装配和该bean的属性具有相同名字的bean。
  • byType:通过参数的数据类型自动自动装配,Spring容器查找beans的属性,这些beans在XML配置文件中被设置为byType。之后容器试图匹配和装配和该bean的属性类型一样的bean。如果有多个bean符合条件,则抛出错误。
  • constructor:这个同byType类似,不过是应用于构造函数的参数。如果在BeanFactory中不是恰好有一个bean与构造函数参数相同类型,则抛出一个严重的错误。
  • autodetect:如果有默认的构造方法,通过 construct的方式自动装配,否则使用 byType的方式自动装配。

34.自动装配有哪些局限性?

自动装配有如下局限性:

  • 重写:你仍然需要使用 和< property>设置指明依赖,这意味着总要重写自动装配。
  • 原生数据类型:你不能自动装配简单的属性,如原生类型、字符串和类。
  • 模糊特性:自动装配总是没有自定义装配精确,因此,如果可能尽量使用自定义装配。

35.你可以在Spring中注入null或空字符串吗?

完全可以。

Spring注解

36.什么是Spring基于Java的配置?给出一些注解的例子

基于Java的配置允许你使用Java的注解进行Spring的大部分配置而非通过传统的XML文件配置。

以注解@Configuration为例,它用来标记类,说明作为beans的定义,可以被Spring IOC容器使用。另一个例子是@Bean注解,它表示该方法定义的Bean要被注册进Spring应用上下文中。

37.什么是基于注解的容器配置?

另外一种替代XML配置的方式为基于注解的配置,这种方式通过字节元数据装配组件而非使用尖括号声明。开发人员将直接在类中进行配置,通过注解标记相关的类、方法或字段声明,而不再使用XML描述bean之间的连线关系。

38.如何开启注解装配?

注解装配默认情况下在Spring容器中是不开启的。如果想要开启基于注解的装配只需在Spring配置文件中配置元素即可。

39.@Required 注解

@Required表明bean的属性必须在配置时设置,可以在bean的定义中明确指定也可通过自动装配设置。如果bean的属性未设置,则抛出BeanInitializationException异常。

40.@Autowired 注解

@Autowired 注解提供更加精细的控制,包括自动装配在何处完成以及如何完成。它可以像@Required一样自动装配setter方法、构造器、属性或者具有任意名称和/或多个参数的PN方法。

41. @Qualifier 注解

当有多个相同类型的bean而只有其中的一个需要自动装配时,将@Qualifier 注解和@Autowire 注解结合使用消除这种混淆,指明需要装配的bean。

Spring数据访问

42.在Spring框架中如何更有效的使用JDBC?

使用Spring JDBC框架,资源管理以及错误处理的代价都会减轻。开发人员只需通过statements和queries语句从数据库中存取数据。Spring框架中通过使用模板类能更有效的使用JDBC,也就是所谓的JdbcTemplate(例子)。

43.JdbcTemplate

JdbcTemplate类提供了许多方法,为我们与数据库的交互提供了便利。例如,它可以将数据库的数据转化为原生类型或对象,执行写好的或可调用的数据库操作语句,提供自定义的数据库错误处理功能。

44.Spring对DAO的支持

Spring对数据访问对象(DAO)的支持旨在使它可以与数据访问技术(如 JDBC, Hibernate 及JDO)方便的结合起来工作。这使得我们可以很容易在的不同的持久层技术间切换,编码时也无需担心会抛出特定技术的异常。

45.使用Spring可以通过什么方式访问Hibernate?

使用Spring有两种方式访问Hibernate:

  • 使用Hibernate Template的反转控制以及回调方法
  • 继承HibernateDAOSupport,并申请一个AOP拦截器节点

46.Spring支持的ORM

Spring支持一下ORM:

  • Hibernate
  • iBatis
  • JPA (Java -Persistence API)
  • TopLink
  • JDO (Java Data Objects)
  • OJB

47.如何通过HibernateDaoSupport将Spring和Hibernate结合起来?

使用Spring的SessionFactory 调用LocalSessionFactory。结合过程分为以下三步:

  • 配置Hibernate SessionFactory
  • 继承HibernateDaoSupport实现一个DAO
  • 使用AOP装载事务支持

48.Spring支持的事务管理类型

Spring支持如下两种方式的事务管理:

  • 编程式事务管理:这意味着你可以通过编程的方式管理事务,这种方式带来了很大的灵活性,但很难维护。
  • 声明式事务管理:这种方式意味着你可以将事务管理和业务代码分离。你只需要通过注解或者XML配置管理事务。

49.Spring框架的事务管理有哪些优点?

  • 它为不同的事务API(如JTA, JDBC, Hibernate, JPA, 和JDO)提供了统一的编程模型。
  • 它为编程式事务管理提供了一个简单的API而非一系列复杂的事务API(如JTA).
  • 它支持声明式事务管理。
  • 它可以和Spring 的多种数据访问技术很好的融合。

50.你更推荐那种类型的事务管理?

许多Spring框架的用户选择声明式事务管理,因为这种方式和应用程序的关联较少,因此更加符合轻量级容器的概念。声明式事务管理要优于编程式事务管理,尽管在灵活性方面它弱于编程式事务管理(这种方式允许你通过代码控制业务)。

Spring面向切面编程(AOP)

51.解释AOP

面向切面编程,或AOP允许程序员模块化横向业务逻辑,或定义核心部分的功能,例如日志管理和事务管理。

52.切面(Aspect)

AOP的核心就是切面,它将多个类的通用行为封装为可重用的模块。该模块含有一组API提供 cross-cutting功能。例如,日志模块称为日志的AOP切面。根据需求的不同,一个应用程序可以有若干切面。在Spring AOP中,切面通过带有@Aspect注解的类实现。

53.在Spring AOP中concern和 cross-cutting concern的区别是什么?

Concern(核心逻辑):表示在应用程序中一个模块的行为。Concern可以定义为我们想要实现的功能。

Cross-cutting concern(横向的通用逻辑):指的是整个应用程序都会用到的功能,它影响整个应用程序。例如,日志管理(Logging)、安全管理(Security)以及数据交互是应用程序的每个模块都要涉及到的,因此这些都属于Cross-cutting concern。

54.连接点(Join point)

连接点代表应用程序中插入AOP切面的地点。它实际上是Spring AOP框架在应用程序中执行动作的地点。

55.通知(Advice)

通知表示在方法执行前后需要执行的动作。实际上它是Spring AOP框架在程序执行过程中触发的一些代码。

Spring切面可以执行一下五种类型的通知:

  • before(前置通知):在一个方法之前执行的通知。
  • after(最终通知):当某连接点退出的时候执行的通知(不论是正常返回还是异常退出)。
  • after-returning(后置通知):在某连接点正常完成后执行的通知。
  • after-throwing(异常通知):在方法抛出异常退出时执行的通知。
  • around(环绕通知):在方法调用前后触发的通知。

56.切入点(Pointcut)

切入点是一个或一组连接点,通知将在这些位置执行。可以通过表达式或匹配的方式指明切入点。

57.什么是引入?

引入允许我们在已有的类上添加新的方法或属性。

58.什么是目标对象?

被一个或者多个切面所通知的对象。它通常是一个代理对象。也被称做被通知(advised)对象。

59.什么是代理?

代理是将通知应用到目标对象后创建的对象。从客户端的角度看,代理对象和目标对象是一样的。

60.有几种不同类型的自动代理?

  • BeanNameAutoProxyCreator:bean名称自动代理创建器
  • DefaultAdvisorAutoProxyCreator:默认通知者自动代理创建器
  • Metadata autoproxying:元数据自动代理

61.什么是织入?什么是织入应用的不同点?

织入是将切面和其他应用类型或对象连接起来创建一个通知对象的过程。织入可以在编译、加载或运行时完成。

62.解释基于XML Schema方式的切面实现

在这种情况下,切面由使用XML文件配置的类实现。

63.解释基于注解方式(基于@AspectJ)的切面实现

在这种情况下(基于@AspectJ的实现),指的是切面的对应的类使用Java 5注解的声明方式。

Spring的MVC框架

64.什么是Spring的MVC框架?

Spring提供了一个功能齐全的MVC框架用于构建Web应用程序。Spring框架可以很容易的和其他的MVC框架融合(如Struts),该框架使用控制反转(IOC)将控制器逻辑和业务对象分离开来。它也允许以声明的方式绑定请求参数到业务对象上。

65.DispatcherServlet

Spring的MVC框架围绕DispatcherServlet来设计的,它用来处理所有的HTTP请求和响应。

66.WebApplicationContext

WebApplicationContext继承了ApplicationContext,并添加了一些web应用程序需要的功能。和普通的ApplicationContext 不同,WebApplicationContext可以用来处理主题样式,它也知道如何找到相应的servlet。

67.什么是Spring MVC框架的控制器?

控制器提供对应用程序行为的访问,通常通过服务接口实现。控制器解析用户的输入,并将其转换为一个由视图呈现给用户的模型。Spring 通过一种极其抽象的方式实现控制器,它允许用户创建多种类型的控制器。

68.@Controller annotation

@Controller注解表示该类扮演控制器的角色。Spring不需要继承任何控制器基类或应用Servlet API。

69.@RequestMapping annotation

@RequestMapping注解用于将URL映射到任何一个类或者一个特定的处理方法上。

好了,现在你可以去面试了!不要忘了访问我们的Spring教程

原文链接: javacodegeeks 翻译: ImportNew.com 人晓
译文链接: http://www.importnew.com/11657.html