月度归档:2011年10月

可执行文件从装载到进程建立的过程

程序从被装载至运行需经过2次转换,当可执行文件被装载时,操作系统要做的事情是为进程的建立做好准备,创建虚拟空间和相关的数据结构,这是第一次转换,第二次转换发生在程序开始执行时,由于现代操作系统都是采用分页机制来解决物理内存不足的问题,因此进程运行前必须保证待执行的代码和数据所在页都已经在物理内存中存在了,这个页映射的过程是由内存管理单元(Memory Management Unit, MMU)负责实现的,这是第二次转换。至此,一个可执行文件到进程执行的过程就完成了。以下带有个人理解,仅作参考,不可全信,以免被误导。

先声明几个关键概念。

 一、可执行文件结构

可执行文件一般按段(Section)来组织自身,无论Linux下的ELF(Executable Linkable Format)文件,还是Windows下的PE(Portable Executable)文件,其原理都是大同小异,比如它们都包含以下几个常见的段:.text表示代码段,存储代码,.data表示数据段,存储已经初始化的全局变量和局部静态变量,.bss(Block Started by Symbol)段用来存储未初始化的全局变量和局部静态变量,其他还有比如只读数据段.rdata,调试信息段.debug等等。

 二、进程虚拟地址空间

现代操作系统为每个程序会单独分配一个虚拟地址空间(Virtual Address Space, VAS),VAS的大小由CPU的位数决定,如果是32位硬件平台,那么分配给一个程序的VAS大小就是232,即4GB大小。由此也决定了该平台下指针的位数要求必须与虚拟空间的位数一致(大了也没必要,小了就无法访问到整个虚拟空间了)。这个虚拟地址空间之所以说是虚拟的,因为它实际上只不过是一个数据结构,它只是从操作系统层面上规定了一个进程是长什么样的,比如,Linux环境下进程的虚拟地址空间被分成两个部分:Kernel Space和User Space。Kernel Space是留给操作系统用的,占用1G,其地址范围为虚拟空间的高字节区0xC0000000-0xFFFFFFFF,User Space为程序空间,占用3G,其地址范围为虚拟空间的低字节区0x00000000-0xBFFFFFFFF。User Space还可以再细分为(由低地址到高地址排列):保留区、代码区、数据区、堆和栈,这些区域也被称为虚拟内存区域(Virtual Memory Area, VMA)。进程的虚拟地址空间示例图如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
                              +----------------+ 0xFFFFFFFF
                              | Kernel Space   |
                              +----------------+ 0xC0000000
                              |   User Space   |
                              | +------------+ |
                              | |   Stack    | |
                              | +------------+ |
                              / .    ...     . /
                              / .    ...     . /
                              | +------------+ |
                              | |    Heap    | |
                              | +------------+ |
                              | |    Data    | |
                              | +------------+ |
                              | |    Code    | |
                              | +------------+ |
                              | |  Reversed  | |
                              | +------------+ |
                              +----------------+ 0x00000000

图1 进程虚拟空间分布
(Download ASCII Picture)

其中User Space区的Stack和Heap都是能动态增长的,但是它们的增长方向不同,栈(Stack)区是由上往下(高地址向低地址)增长,而堆(Heap)区是由下往上(低地址向高地址)增长。

 三、页映射

页映射是当前解决物理内存不足问题的主流方法,它的实现机制为:将进程的虚拟地址空间VAS按固定大小划分成页,例如我们一般的PC机采用4KB的页大小,对于一个32位的进程虚拟地址空间,那么整个进程可以被划分成232/212 = 220个页面,同理,物理内存也会按固定大小划分成页,一块1GB大小的内存就能被划分为230/212 = 218个页面。如何将220个虚拟页面映射到218个物理页面里,这就是开头提到的内存管理单元(MMU)来实现的,MMU的具体实现可参考操作系统原理相关的资料或Wiki

有了以上一些基本知识作为铺垫,就能更好了解一个可执行文件从装载到运行的全过程了。
操作系统装载可执行文件之前首先要做的是创建一个如图1所示的进程虚拟空间VAS结构,然后读取可执行文件头,将可执行文件中的各个段(Section)分别映射到VAS中的各个VMA中,例如将可执行文件中的.text段映射到Code区,把.data和.bss段映射到Data区等等,此后,再将CPU的PC寄存器设置成可执行文件的入口地址,此致,操作系统将CPU控制权交予进程。但是以上步骤只是可执行文件的装载过程,到目前为止,内存中还并没有待执行进程的任何代码和数据,因此就发生了页错误(Page Fault),进程将CPU的控制权重新交回给操作系统,由操作系统的内存管理模块根据一定的页面调度算法进行页的换出,总之要在物理内存中留出一页空白页来,然后根据可执行文件装载时建立的映射关系在可执行文件中找到当前页的偏移,并将内容复制到内存,完成以后CPU控制权交还给进程,进程开始执行该页代码。

这个过程用以下示例图简化表示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
                           +----------------+ 0xFFFFFFFF
                           | Kernel Space   |
                           +----------------+ 0xC0000000
                           |   User Space   |
                           | +------------+ |              +-------------------+
                           | |   Stack    | |              | +---------------+ |
                           | +------------+ |              | |Physical Page n| |
      +-------------+      / .    ...     . /              | +---------------+ |
      |             |      / .    ...     . /              / .    ......     . /
      | +---------+ |      | +------------+ |              / .    ......     . /
      | |   ...   | |      | |    Heap    | |              | .    ......     . |
      | +---------+ |      | +------------+ |              | +---------------+ |
      | |  .data  |-+------+>|    Data    |-+--------------+>|Physical Page 2| |
      | +---------+ |  OS  | +------------+ |     MMU      | +---------------+ |
      | |  .text  |-+------+>|    Code    |-+--------------+>|Physical Page 1| |
      | +---------+ |      | +------------+ |              | +---------------+ |
      | |   ...   | |      | |  Reversed  | |              | |Physical Page 0| |
      | +---------+ |      | +------------+ |              | +---------------+ |
      +-------------+      +----------------+ 0x00000000   +-------------------+
         ELF File        Virtual Address Space                Physical Memory

图2 可执行文件装载到运行示意图
(Download ASCII Picture)

Reference:
[1] 俞甲子, 石凡, 潘爱民著. 程序员的自我修养 ——链接、装载与库[M]. 电子工业出版社. 2010.10.

--EOF--

Java类加载器运行机制

Java类加载机制是指将静态的class文件加载至JVM,并生成一个Class类对象的机制。这个与操作系统创建进程之前加载可执行文件(Linux下的ELF文件,Windows下的PE文件)的概念有些类似。Java是通过类加载器(ClassLoader)来实现类加载机制的,类加载器的层次结构是一颗树,从上到下划分为:引导类加载器(BootStrap ClassLoader)、扩展类加载器(Extension ClassLoader)、系统类加载器(System ClassLoader)和用户自定义加载器(User-Defined ClassLoader),如下示例图所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
                                   +-------------+
                                   |  BootStrap  |
                                   | ClassLoader |
                                   +------^------+
                                          |
                                   +-------------+
                                   |  Extension  |
                                   | ClassLoader |
                                   +------^------+
                                          |
                                   +-------------+
                                   |   System    |
                                   | ClassLoader |
                                   +-^---------^-+
                                     |         |
                        +--------------+     +--------------+
                        | User-Defined | ... | User-Defined |
                        | ClassLoader1 | ... | ClassLoader2 |
                        +--------------+     +--------------+

图1 Classloader层次结构
(Download ASCII Picture)

1、BootStrap ClassLoader用于加载Java的核心库,由native代码实现。Sun JDK中的BootStrap ClassLoader由C++实现,负责对$JAVA_HOME/jre/lib/rt.jar中的类进行加载。
2、Extension ClassLoader用于加载Java扩展库,Sun JDK中的Extension ClassLoader负责对$JAVA_HOME/jre/lib/ext目录下的jar包进行加载。
3、System ClassLoader用来加载CLASSPATH路径下的jar包。
4、User-Defined ClassLoader是程序员通过扩展ClassLoader类来实现的。

上述4层ClassLoader结构中,除BootStrap ClassLoader外,其余类加载器都有一个直接父类加载器,因此,System ClassLoader是User-Defined ClassLoader的父类,Extension ClassLoader是System ClassLoader的父类,BootStrap ClassLoader是Extension ClassLoader的父类,要得到一个ClassLoader的父类加载器,只需在该ClassLoader上调用getParent()方法即可,这里有一个地方需要注意,虽然BootStrap ClassLoader是Extension ClassLoader的父类加载器,但是根据JVM虚拟机的实现不同,例如在Sun JDK中,对Extension ClassLoader调用getParent()会得到null值。

以上提到的getParent()方法只是ClassLoader中一个与类加载相关的方法,还有其他方法比如loadClass()、defineClass()、findClass()等等,详情可见JDK中关于ClassLoader的说明文档。

当一个类被加载到JVM以后,用于标识其唯一性身份的元素有两个:类的全限定名(包名+类名,例如java.lang.Object)+ClassLorder的实例ID。这意味着,当同样一个类被不同的ClassLoader加载后,对JVM来讲就是两个不同的类,这两个类之间进行赋值或强制转换会导致ClassCastException异常的抛出,由此可见,JVM可以按加载器将内部空间划成一个个互不干扰的类空间。但是这样做又会出现一个问题,因为所有Java类最终都会引用到java.lang.Object类,那么不同的ClassLoader加载的Object类之间是不兼容,这显然不合理,因此Java的类加载机制采用树形结构原则来对类进行加载,以此来保证Java核心库类的类型安全问题。所谓树形结构原则是指,采用代理模式,一个ClassLoader在准备加载某个类之前,先将其代理给它的父类加载器进行加载,父类加载器又会再代理给父类的父类加载器进行尝试加载,依次类推......对于Java核心库中的类,往往最后被代理到所有类加载器的基类BootStrap ClassLoader类,由它进行加载。

当ClassLoader采用代理模式对类进行加载时,类加载就被分离成启动加载和实际加载两个过程,并且,这两个过程往往在不同的类加载器中完成,把启动加载过程的类加载器称为初始加载器(Initiating Loader),把实际完成加载的类加载器称为定义加载器(Defining Loader),初始加载器通过调用loadClass()方法来实现,定义加载器通过调用defineClass()来完成实际的类加载工作。例如当在ClassLoader A中用Class.forName来加载某个类时,实际上通过代理模式,这个类实际上是由ClassLoader A的父类ClassLoader B来完成加载的,那么这里ClassLoader A称为初始加载器,而ClassLoader B称为定义加载器。一般初始加载器在调用loadClass()方法时会抛出ClassNotFoundException异常,表示即便通过代理模式及其自身的寻找,均没有找到待加载的类的jar包或class文件。而定义加载器往往会在调用defineClass方法时抛出NoClassDefFoundError异常,表示正在加载的这个类中引用到的另一个类不存在或者当前的ClassLoader无法加载这个被引用的类。用一个例子解释上面两个异常出现的场景:

1
2
3
public class A{
    private B b = new B();
}

现在有ClassLoader Child和它的父类加载器ClassLoader Father,在ClassLoader Child负责加载的代码中试图加载A,ClassLoader Child先代理给其父类加载器ClassLoader Father对A进行加载,如果ClassLoader Child和ClassLoader Father都无法找到A的class文件,那么ClassLoader Child就会抛出ClassNotFoundException异常。如果ClassLoader Father找到了A的class文件,但是在加载过程中找不到B的class文件或者无法对B进行加载,那么ClassLoader Father就会抛出NoClassDefFoundError异常。

Reference:
[1] 林昊, 分布式Java应用:基础与实践[M], 电子工业出版社, 2011.5.
[2] 成富, 深入探讨Java类加载器[EB/OL], IBM Developer Works, 2011-10-27 accessed.

--EOF--

单链表快速排序算法

快速排序的算法思想是:确定一个枢轴元素,通过一趟排序将待排关键字分成两个部分,其中一部分元素均比枢轴元素小,另一部分元素均比枢轴元素大,这样的一趟排序称为快速排序的一次划分。再对两个部分分别再递归进行划分操作,最后获得的序列就是排好序的关键字序列。可见,快速排序的性能与枢轴元素的选取有关,快排的时间复杂度在最好、最坏、平均的情况下分别为:O(nlog2n)、O(n2)和O(nlog2n),空间复杂度在最好、最坏、平均情况下分别为:O(log2n)、O(n)和O(log2n),快排的C++实现和效率分析见『六种基本内部排序算法的C++实现』『六种基本内部排序算法效率分析』

上述快排算法的实现中采用的存储结构是数组,采用数组有一个好处,就是待排元素可以随机存取。而以单链表方式存储的待排序列就无法随机存取元素了,其实根据快排思想,稍作改动,对单链表的快速排序算法也能实现。

因为快排最核心的思想就是划分,确定一个枢轴元素(pivot),每一趟划分的目的就是把待排序列分为两部分,前一部分比枢轴小(序列A),后一部分比枢轴大(序列B)。经过一趟划分之后序列变为:{A} pivot {B}。以下是具体步骤:
1、确定每一次划分的枢轴元素为当前待排序列的头节点。
2、设置Slow和Fast两个游标,Slow指向序列A中的最后一个元素,初始化为枢轴本身(待排序列头节点)。让Fast遍历一遍待排序列,当所指元素比枢轴小时,将Slow往前游一格,交换Slow和Fast所指元素的值,这样仍能保证Slow指向的元素是序列A中的最后一个元素。
3、交换Slow所指元素和枢轴元素的值。
4、对序列A和B重复步骤1~4。

下面是单链表快速排序算法的Java实现:
1、单链表节点的定义。

1
2
3
4
5
/* 单链表节点 */
class Element {
    public int     data;
    public Element next;
}

2、单链表的快排算法

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
36
37
38
39
40
41
/**
 * @param ListHead 待排序列的头节点
 * @param ListEnd 待排序列的尾节点
 */
public static void qsort(Element ListHead, Element ListEnd) {
    if (ListHead == null || ListEnd == null)
        return;
    if (ListHead == ListEnd) {
        return;
    }
    //Slow游标,指向序列A的最末尾元素。
    Element Slow = ListHead;
    //Fast游标,用于遍历整个待排序列。
    Element Fast = ListHead.next;
    //TempEnd游标,总是指向Slow游标的前驱节点,递归调用时需要。
    Element TempEnd = ListHead;
    int temp;
    while (Fast != null) {
        //当前节点的值比枢轴小,进行交换。
        if (Fast.data < ListHead.data) {
            //TempEnd游标总是指向Slow的前驱。
            TempEnd = Slow;
            Slow = Slow.next;
 
            //交换Slow和Fast游标所指的元素的值
            temp = Slow.data;
            Slow.data = Fast.data;
            Fast.data = temp;
        }
        Fast = Fast.next;
    }
 
    //交换Slow游标所指的元素和枢轴元素的值,使序列成为{A} povit {B}形式
    temp = ListHead.data;
    ListHead.data = Slow.data;
    Slow.data = temp;
 
    //递归调用
    qsort(ListHead, TempEnd);
    qsort(Slow.next, ListEnd);
}

--EOF--

设计模式 —— Observer(观察者模式)

Observer模式(观察者模式)在GoF归纳的23种设计模式里还算是比较容易理解的一种,它适用于一种一对多的环境下,"一"和"多"之间存在依赖关系,当"一"的状态发生改变时,依赖于它的"多"都会得到通知并自动更新自己。Observer模式的对象有两类,一类为目标,就是上述关系中的"一",另一类为观察者,是上述关系中的"多"。

观察者模式的结构图如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 +-----------+ obervers                 +------------+
 |  Subject  |------------------------->|  Observer  |
 +===========+                          +============+
 |  attach() |   +------------------+   |  Update()  |
 |  detach() |   |foreach observers{|   +------^-----+
 |  notify() |-->|   o->Updata()    |          |
 +-----^-----+   |}                 |          |
       |         +------------------+ +----------------+
       |                              |ConcreteObserver|   +--------------------+
+---------------+             subject +================+   |observerState =     |
|ConcreteSubject|<--------------------|   Update()     |-->| subject->GetState()|
+===============+                     | observerState  |   +--------------------+
|  GetStatus()  |                     +----------------+
|  SetStatus()  |
+---------------+

图1 观察者模式结构图
(Download ASCII Picture)

如图所示,观察者模式的参与者分为4类:
1、Subject(目标)
Suject至少需提供3个接口,Attach()和Detach()用于注册和解除观察者对象。Notify()用于在状态改变时通知所有观察者对象。
2、Observer(观察者)
Observer至少需要提供一个Update()接口,用于更新具体观察者对象的状态。
3、ConcreteSubject(具体目标)
ConcreteSubject除了必须实现Subject接口中的方法之外,还必须提供一个"注册中心",所有观察者对象都必须在这个注册中心进行注册,方便在目标状态发生改变时受到通知。
4、ConcreteObserver(具体观察者)
ConcreteObserver维护着一个自身的状态,该状态与ConcreteSubject中的状态要一致,要达到这个目的,还要维护一个指向ConcreteSubject的引用。

观察者模式几个常见的应用场景比如Web开发中的MVC架构,Model作为一个目标(Subject),View组件就是观察者(Observer),一个Model可能会对应多个View组件,因此当Model中数据更新时就通过观察者模式来通知View,从而使得各个View能保持数据的一致性。另一个应用场景如GoF中举例的图形用户界面工具箱。它将数据和界面分离,当数据有更新时,多个界面(表格,柱状图,饼图)均能得到更新。此外,C#中的委托机制也采用了观察者设计模式,委托给一个delegate类的函数就是观察者模式中的Observer角色,delegate类通过"+="和"-="运算符来注册和解除观察者对象,参见『C#的委托和事件』

以下的程序是一个Observer模式的简单实现,其功能与GoF中举例的GUI工具箱类似,目标类为一个数据源(DataSourceMng),观察者类有三个:TableGraph、PieGraph、BarGraph分别表示不同的数据展示方式:表格,饼图,柱状图。数据源中的数据可由数据源本身修改,也可由观察者类进行修改,但无论是谁对其进行修改,目标类都有责任调用Notify()通知向它注册过的所有观察者发送通知。特别当观察者类修改数据源数据时,要注意这个观察者类自身的状态需要由目标类的Notify()统一进行修改,而不是直接擅自进行修改,这也是出于保证数据一致性的重要考虑。

1、Suject类

1
2
3
4
5
6
7
package cn.edu.zju.dp.observer;
 
public interface Subject {
    public void Attach(Observer o);
    public void Detach(Observer o);
    public void Notify();
}

2、Observer类

1
2
3
4
5
6
package cn.edu.zju.dp.observer;
 
public interface Observer {
    public void Updata();
    public void QueryData();
}

3、ConcreteSuject类

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
package cn.edu.zju.dp.observer;
 
import java.util.LinkedList;
import java.util.List;
 
public class DataSourceMng implements Subject {
    private double               rate = 0.0;
    private final List<Observer> list = new LinkedList<Observer>();
 
    public void setRate(double rate) {
        this.rate = rate;
        Notify();
    }
 
    public double getRate() {
        return this.rate;
    }
 
    @Override
    public void Attach(Observer o) {
        list.add(o);
    }
 
    @Override
    public void Detach(Observer o) {
        list.remove(o);
    }
 
    @Override
    public void Notify() {
        for (Observer o : list) {
            o.Updata();
        }
    }
}

4、ConcreteObserver类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class TableGraph implements Observer {
    private final Subject datasource;
    private double        rate;
 
    public TableGraph(Subject datasource) {
        this.datasource = datasource;
    }
 
    @Override
    public void Updata() {
        this.rate = ((DataSourceMng) datasource).getRate();
    }
 
    @Override
    public void QueryData() {
        System.out.println("TableGraph's Rate = " + rate);
    }
 
    public void ModifyRate(double rate) {
        ((DataSourceMng) datasource).setRate(rate);
    }
}

因PieGraph和BarGraph的实现与TableGraph完全一致,故不重复贴出。

5、测试程序

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
/**
 * 衔山的博客 - http://fengchj.com
 * Copyright (c) 2011 All Rights Reserved.
 */
package cn.edu.zju.dp.observer;
 
/**
 * 
 * @author 衔山
 * @version $Id: ObserverPatternTest.java, v 0.1 2011-10-23 下午03:01:49
 */
public class ObserverPatternTest {
    public static void main(String[] args) {
        Subject datasource = new DataSourceMng();
 
        Observer table = new TableGraph(datasource);
        Observer pie = new PieGraph(datasource);
        Observer bar = new BarGraph(datasource);
 
        //在目录类中注册观察者类
        datasource.Attach(table);
        datasource.Attach(pie);
        datasource.Attach(bar);
 
        //观察者类修改数据源
        ((TableGraph) table).ModifyRate(0.75);
 
        //所有观察者类的状态得到修改
        table.QueryData(); //TableGraph's Rate = 0.75
        pie.QueryData(); //PieGraph's Rate = 0.75
        bar.QueryData(); //BarGraph's Rate = 0.75
    }
}

Reference:
[1] GoF. 设计模式:可复用面向对象软件的基础[M], 机械工业出版社, 2006-07.

--EOF--

为什么要覆盖hashCode()?

hashCode()是Object类自带的11个方法之一,当需要将一个对象存进HashMap的时候,特别是当这个对象已经重写了equals()方法时,就需要在对象中重写hashCode()方法,否则,很容易造成严重问题。

现在考虑最简单的情况,假如要将没有重写equals()和hashCode()方法的对象加入一个HashMap中。由于Object类中equals()方法默认采用"=="操作符来比对两个对象是否相同,而"=="操作符是用于比较两个对象的内存地址是否相同的,因此,默认情况下,任何对象都是不同的,因为new出它们的时候,JVM在堆中会为它们分配不同的内存地址。因此,对于下面这样一个Car类:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//Program 1
public class Car {
    private String name;
 
    public Car(String name) {
        this.name = name;
    }
 
    public static void main(String[] args) {
        Car c1 = new Car("Benz");
        Car c2 = new Car("Benz");
 
        Map<Car, Integer> m = new HashMap<Car, Integer>();
        m.put(c1, 1);
        m.put(c2, 1);
        System.out.println(m.size()); //print 2
    }
}

上述程序中,虽然c1和c2拥有相同的name值(Benz),但对JVM来讲,它们都是不同的对象,如果要加入到HashMap里,它们会被当成不同的对象哈希到不同的位置,所以line16输出map的size是2。

现在假如Car重写了equals()方法,所有相同name值的对象都表示同一个对象,这个时候如果不同时重写Car类的hashCode()方法,就会出现如下现象:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//Program 2
public class Car {
    private final String name;
 
    public Car(String name) {
        this.name = name;
    }
 
    @Override
    public boolean equals(Object o) {
        Car c = (Car) o;
        return this.name.equals(c.name);
    }
 
    public static void main(String[] args) {
        Car c1 = new Car("Benz");
        Car c2 = new Car("Benz");
 
        Map<Car, Integer> m = new HashMap<Car, Integer>();
        m.put(c1, 1);
        System.out.println(m.get(c2)); //print null
    }
}

按理说,覆盖equals()方法后,c1和c2表示的时同一个对象,那么往HashMap中put了c1后,理应通过get(c2)能返回c1的value值1。但实际上line21输出的是null,表示HashMap中不存在key为c2的对象。这样就在程序中埋下了一个bug:两个相同的对象A和B,把A放进HashMap,用B去取取不出来。要修正这样的错误只需在覆盖Car类equals()对象的同时再覆盖hashCode()方法,如下所示:

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
//Program 3
public class Car {
    private final String name;
 
    public Car(String name) {
        this.name = name;
    }
 
    @Override
    public boolean equals(Object o) {
        Car c = (Car) o;
        return this.name.equals(c.name);
    }
 
    @Override
    public int hashCode() {
        return name.hashCode();
    }
 
    public static void main(String[] args) {
        Car c1 = new Car("Benz");
        Car c2 = new Car("Benz");
 
        Map<Car, Integer> m = new HashMap<Car, Integer>();
        m.put(c1, 1);
        System.out.println(m.get(c2)); //print 1
    }
}

这个时候line26就能输出正确值1了。

要理解出现上述现象的原因需了解HashMap的实现原理,HashMap put()和get()的实现中,要调用对象hashCode()得到的int值作为间接索引,定位到该对象在数组中所在的下标位置。因为HashMap采用的是拉链法解决哈希冲突,所以当两个对象拥有相同的hashCode()值时就表示它们冲突了,然后HashMap调用当前对象的equals()方法与链表中的所有对象进行判定,如果equals()返回true,表示该对象已存在,如果当前是put操作就更新其value值,如果是get操作就返回其value值。如果遍历完冲突链表上挂着的所有对象,发现equals()均返回false,表示该对象不存在,如果当前是put操作就将该key-value键值对挂在链表上,如果是get操作就返回null。

再分析Program 2出现的bug,因为Car只是重写了equals()而没有重写hashCode(),于是HashMap在get(c2)时根本没有将c2定位到c1所在的冲突链表的位置中去,所以,根据c2默认hashCode()值找到的冲突链表中自然找不到相应的key和value,所以返回null。

Thinking In Java: Third Edition』关于hashCode()的覆盖原则有个总结[1]:
1、无论何时,对同一个对象调用hashCode()都应该生成同样的值。(这里"同一个对象"是指用equals()判定返回为true的对象)
2、不应该使hashCode()依赖于具有唯一性的对象信息。(默认hashCode()方法就是依赖于具有唯一性特点的内存地址)

此外,设计一个好的hashCode()函数是程序员的责任。hashCode()函数设计的好坏会对HashMap的性能产生重大影响。一个好的hashCode()方法应该能产生分布均匀的哈希值。举一个极端的例子:

1
2
3
public int hashCode() {
    return 1;
}

这个hashCode()方法表示,对于任何对象,其哈希值总为1,这就导致所有put进HashMap的Car对象都会被哈希到数组中的同一个位置,挂在同一个冲突链表上,虽然这样的设计不会出现如Program 2这样的bug,但是这确实是一个最糟糕的设计,它会造成HashMap退化为一个LinkedList(不是特别准确,因为LinkedList底层采用双向链表,而HashMap退化后是个单向链表),其put和get操作的时间复杂度降为O(n),完全失去了HashMap本来的作用。

Reference:
[1] Bruce Eckel. Java编程思想(第3版). 机械工业出版社. 2005.5. P353-356.

--EOF--