早早就听说过开发方向的笔试面试都是以算法和数据结构这些基础为主，我自恃着那么一丁点项目经验，一直没放在心上。
连日下来的笔试彻底印证了师兄们的话，笔试基本不过。最可惜的是淘宝，笔试中发挥不错终于能进一面，一开始聊家常聊框架聊开源技术还聊得不错，突然
间，连续问了三个问题：
1.多线程访问hashtable和hashmap有什么不一样？我只答出线程安全不一样，具体怎么不一样就有一句每一句了（回来google一
下，这种java基础还真TM简单，枉称精通java了）
2.平衡二叉树查找算法的复杂度？再次雷响，随便蒙了个归并排序的复杂度给他。
3.对于100W条数据的排序和查找有什么效率高的方式？完了，结结巴巴的说一通，最后自认不会……
原本以为技术面会比笔试好过的，回学校的路上我泪流满面啊我。这些都不是RP问题了，铁了心恶补数据结构……
Java线
程安全同步解决方案
1、 问题描述：
如果一个资源或对象可能被多个线程同时访问，它就是一个共享资源；例如
类的成员变量，包括类变量和实例变量，再比如对一个文件进行写操作等。一般情况下，对共享资源的访问需要考虑线程安全的问题。
如果一个对象的完整生命周期只在一个线程内，则不需要考虑线程安全，例
如一个局部变量。下面为一个示例代码：
- public class C1 {
- public static java.text.SimpleDateFormat
sdf = new java.text.SimpleDateFormat("yyyy-MM-dd");
- //其他代码
-
}
假如在一个JSP中这样的去调用：
- <a.jsp>:
- <%
- Java.util.Date date =
C1.sdf.parse(“2003-4-15”);
-
%>
则这样的代码不是线程安全的。因为java.text.SimpleDateFormat
不是线程安全的，a.jsp中的代码将会有若干个线程同时执行，而都访问的是同一个线程不安全的对象，这样就不是一个线程安全的代码。正确的写法应该如
下：
- <a.jsp>:
- <%
- java.text.SimpleDateFormat sdf =
new java.text.SimpleDateFormat("yyyy-MM-dd");
- Java.util.Date date =
sdf.parse(“2003-4-15”);
-
%>
2、 原因分析：
此时，sdf对象从创建到销毁都位于一个方法中，相当于一个局部变量，不是一个共享资源，因此则没有线程不安全的问题。
3、 解决方法或过程：
1） 如果对象是immutable，则是线程安全的，例如:String，可以放心使用。
2） 如果对象是线程安全的，则放心使用
3） 有
条件线程安全，对于Vector和Hashtable一般情况下是线程安全的，但是对于某些特殊情况，需要通过额外的synchronized保证线程安
全。
4） 使用synchronized关键字；
对于上例中可以改写jsp代码，在sdf上进行同步，而不需要每次创建一个新的对象来保证线程安全，代码如下：
- <%
- synchronized(C1.sdf){
- Java.util.Date date =
C1.sdf.parse(“2003-4-15”);
- }
-
%>
这种写法是在一个对象级别上进行同步，也就是说任何时候，对于这个对象，最多只能有一个线程在执行同步方法。
另外一种写法是在Class级别上进行同步，写法如下：
- public class C1 {
- public static java.text.SimpleDateFormat
sdf = new java.text.SimpleDateFormat("yyyy-MM-dd");
- public void method(){
- synchronized(C1.class){
- //synchronized code
- }
- }
-
}
这种写法表示无论C1有多少个实例，在任何一个时间点，最多只能有一个线程和一个实例进入同步块中。这种同步会比较大的影响性能。
5） 有些对象不能在多线程间共享，则只能在方法内部使用，或者只在一个线程内部使用。
synchronized详解
Java对多线程的支持与同步机制深受大家的喜爱，似乎看起来使用了synchronized关键字就可以轻松地解决多线程共享数据同步问题。到底如何？――还得对synchronized关键字的作用进行深入了解才可定论。
总的说来，synchronized关键字可以作为函数的修饰符，也可作为函数内的语句，也就是平时说的同步方法和同步语句块。如果再细的分类，synchronized可作用于instance变量、object
reference（对象引用）、static函数和class literals(类名称字面常量)身上。
在进一步阐述之前，我们需要明确几点：
A．无论synchronized关键字加在方法上还是对象上，它取得的锁都是对象，而不是把一段代码或函数当作锁――而且同步方法很可能还会被其他线程的对象访问。
B．每个对象只有一个锁（lock）与之相关联。
C．实现同步是要很大的系统开销作为代价的，甚至可能
造成死锁，所以尽量避免无谓的同步控制。
接着来讨论synchronized
用到不同地方对代码产生的影响：
假设P1、P2是同一个类的不同对象，这个类中定义了以下几种情况的同步块或同步方法，P1、P2就都可以调用它们。
1． 把synchronized当作函数修饰符时，示例代码如下：
Public synchronized void methodAAA()
{
//….
}
这也就是同步方法，那这时synchronized锁定的是哪个对象呢？它锁定的是调用这个同步方法对象。也就是说，当一个对象P1在不
同的线程中执行这个同步方法时，它们之间会形成互斥，达到同步的效果。但是这个对象所属的Class所
产生的另一对象P2却可以任意调用这个被加了synchronized关键字的方法。
上边的示例代码等同于如下代码：
public void methodAAA()
{
synchronized (this) // (1)
{
//…..
}
}
(1)处
的this指的是什么呢？它指的就是调用这个方法的对象，如P1。可见
同步方法实质是将synchronized作用于object
reference。――那个拿到了P1对象
锁的线程，才可以调用P1的同步方法，而对P2而
言，P1这个锁与它毫不相干，程序也可能在这种情形下摆脱同步机制的控制，造成数据混乱：（
2．同步块，示例代码如下：
public void method3(SomeObject so)
{
synchronized(so)
{
//…..
}
}
这时，锁就是so这个对象，谁拿到这个锁谁就可以运行它所控制的那段代码。当有一个明确的对象作为锁时，就可以这样写程序，但当没有明确的对象作为
锁，只是想让一段代码同步时，可以创建一个特殊的instance变量（它得是一个对象）来充当锁：
class Foo implements Runnable
{
private byte[] lock = new
byte[0]; // 特殊的instance变量
Public void methodA()
{
synchronized(lock) { //… }
}
//…..
}
注：零长度的byte数
组对象创建起来将比任何对象都经济――查看编译后的字节码：生成零长度的byte[]对
象只需3条操作码，而Object lock = new Object()则
需要7行操作码。
3．将synchronized作用于static 函数，示例代码如下：
Class Foo
{
public synchronized static void methodAAA() // 同步的static 函数
{
//….
}
public void methodBBB()
{
synchronized(Foo.class) // class literal(类名称字面常量)
}
}
代码中的methodBBB()方法是把class literal作为锁的情况，它和同步的static函
数产生的效果是一样的，取得的锁很特别，是当前调用这个方法的对象所属的类（Class，
而不再是由这个Class产生的某个具体对象了）。
记得在《Effective Java》一书中看到过将 Foo.class和 P1.getClass()用于作同步锁还不一样，不能用P1.getClass()来达到锁这个Class的目的。P1指的是由Foo类产生的对象。
可以推断：如果一个类中定义了一个synchronized的static函数A，也定
义了一个synchronized 的instance函数B，那么这个类的同一对象Obj在多线程中分别访问A和B两个方法时，不会构成同步，因为它们的锁都不一样。A方法的锁
是Obj这个对象，而B的锁是Obj所属的那个Class。
小结如下：
搞清楚synchronized锁定的是哪个对象，就能帮助我们设计更安全的多线程程序。
还有一些技巧可以让我们对共享资源的同步访问更加安全：
1． 定义private 的instance变量+它的 get方法，而不要定义public/protected的instance变量。如果将变量定义为public，对象在外界可以绕过同步方法的控制而
直接取得它，并改动它。这也是JavaBean的标准实现方式之一。
2． 如果instance变量是一个对象，如数组或ArrayList什么的，那上述方法仍然不安全，
因为当外界对象通过get方法拿到这个instance对象的引用后，又将其指向另一个对象，那么这个private变量也就变了，岂不是很危险。这个时候就需要将get方法
也加上synchronized同步，并且，只返回这个private对象的clone()――这样，调用端得到的就是对象副本的引用了。