计算机学习大全

JAVA基础题库

1、作用域public,private,protected,以及不写时的区别

注：不写时关键字默认为friendly

作用域当前类同一package子孙类其他package

public7qq

protectedqqqX

friendlyqqXX

privateqXXX

2、AnonymousInnerClass（匿名内部类）是否可以extends（继承）其它类，是否可以

implements（实现）interface（接口）

答：匿名的内部类是没有名字的内部类。不能extends（继承）其它类，但一个内部类可以作为

一个接口，由另一个内部类实现

3•>&和&&的区别。

答：&和&&都可以用作逻辑与的运算符，表示逻辑与（and）,当运算符两边的表达式的结果都为

true时，整个运算结果才为true,否则，只要有一方为false,则结果为false。

&&还具有短路的功能，即如果第个表达式为false,则不再计算第二个表达式，例如，对

于if（str!=nul1&&!str.equals（""））表达式，当str为null时，后面的表达式不会执行，

所以不会出现NullPointerException如果将&&改为&,则会抛出NullPointerException异常。

If（x==33&++y>0）y会增长，If（x==33&&++y>0）不会增长

&还可以用作位运算符，当&操作符两边的表达式不是boolean类型时，&表示按位与操作，

我们通常使用OxOf来与一个整数进行&运算，来获取该整数的最低4个bit位，例如,0x31&OxOf

的结果为0x01»

4、StaticNestedClass和InnerClass的不同

NestedClass一般是C++的说法，InnerClass一般是JAVA的说法。

Nestedclass分为静态Staticnestedclass的和非静态的innerclass,

静态的Staticnestedclass是不可以直接调用它的外部类enclosingclass的，但是可以通过

外部类的引用来调用，就像你在-•个类中写了main方法一样。

非静态类innerclass可以自由的引用外部类的属性和方法，但是它与一个实例绑定在了以其,

不可以定义静态的属性、方法。

InnerClass（内部类）定义在类中的类。

NestedClass（嵌套类）是静态（static）内部类。1.要创建嵌套类的对象，并不需要其外围

类的对象。2.不能从嵌套类的对象中访问非静态的外围类对象。

AnonymousInnerClass（匿名内部类）匿名的内部类是没有名字的内部类。

匿名的内部类不能extends（继承）其它类，但•个内部类可以作为一个接口，由另一个内部类

实现。

嵌套类可以作为接口的内部类。正常情况下，你不能在接口内部放置任何代码，但嵌套类可以作

为接口的一部分，因为它是static的。只是将嵌套类置于接口的命名空间内，这并不违反接口

的规则。

静态方法是不能继承的，因为它是静态的，所谓静态当然是时间和空间的静止喽……所以任何人

都别想改变他。

但是它不介意有人和它叫一样的名字，所以子类是可以cover的，但是其实这样会出来两个函数,

一个父类的一个子类的，各管各的。

然后final是java里面定义的，不能被重载的函数。

java里面的函数如果没有特别标识，只要在子类中定义了一个同名的函数，那么父类的函数就

被重载掉了。如果new一个子类的对象给父类再调用这个函数，就是调用子类的了。只有new

的是父类的调的才是父类的。

java里面没有virtual的说法，因为不是final或static就是virtual的。

abstract是虚函数，自然不可能是final的，同时如上所说，static是不能被重载只能被覆盖

的，所以也不可以是abstract的

内部类被继承，由于内部类有一个指向外围类对象的秘密引用，所以在继承内部类的时候，该秘

密引用必须被初始化。解决方法是enclosingClassReference.super。；语法，看一下代码：

classOuter

...(

classInner

...(

}

)

classAnoClassextendsOuter.Inner

...{

AnoClass(Outerwi)

...(

wi.super();

)

匿名类(AnonymousClass)

当一个内部类的类声名只是在创建此类对象时用了一次，而且要产生的新类需继承于一个已

有的父类或实现一个接口，才能考虑用匿名类，由于匿名类木身无名，因此它也就不存在构造方

法，它需要显示地调用一个无参的父类的构造方法，并且重写父类的方法。

f.addMouseMotionListener(newMouseMotionAdapter(){〃匿名类开始

publicvoidmouseDragged(MouseEvente){

Strings="Mousedragging:x="+e.getX()+"Y="+e.getY();

tf.setText(s);}

});〃匿名类结束

存在它的原因是：

1.一个内部类的对象能够访问创建它的对象的实现，包括私有数据。即内部类实例对包含它

的哪个类的实例来说，是特权的。

2.对于同一个包中的其他类来说，内部类能够隐藏起来,换句话说，内部类不管方法的可见性

如何，那怕是public,除了包容类，其他类都无法使用它。

3.匿名内部类可以很方便的定义回调。

4.使用内部类可以非常方便的编写事件驱动程序。

其实它真正的目的仅仅为了定义回调一一进步就是事件驱动。

在使用匿名内部类时，要记住以下几个原则：

•匿名内部类不能有构造方法。

•匿名内部类不能定义任何静态成员、方法和类。

,匿名内部类不能是public,protected,private,static。

•只能创建匿名内部类的一个实例。

•一个匿名内部类一定是在new的后面，用其隐含实现一个接口或实现一个类。

•因匿名内部类为局部内部类，所以局部内部类的所有限制都对其生效。

匿名类和内部类中的中的this:

有时候，我们会用到一些内部类和匿名类。当在匿名类中用this时，这个this则指的是匿名类

或内部类本身。这时如果我们要使用外部类的方法和变量的话，则应该加上外部类的类名。

5、ASCII,unicode和UTF-8,UTF—16,gbk,gb2312的区另!I与不同。

1.ASCII（AmericanStandardCodeforInformationInterchange）码，是一种字符集。美国标

准信息交换代码是由美国国家标准学会（AmericanNationalStandardInstitute,ANSI）制定

的，标准的单字节字符编码方案，用于基于文木的数据。起始于50年代后期，在1967年定案。它

最初是美国国家标准，供不同计算机在相互通信时用作共同遵守的西文字符编码标准，它已被

国际标准化组织（InternationalOrganizationforStandardization,ISO）定为国际标准，

称为ISO646标准。适用于所有拉丁文字字母。ASCII码使用指定的7位或8位二进制数组合

来表示128或256种可能的字符。标准ASCII码也叫基础ASCII码，使用7位二进制数来表

示所有的大写和小写字母，数字0到9、标点符号，以及在美式英语中使用的特殊控制字符。

其中：

0〜31及127（共33个）是控制字符或通讯专用字符（其余为可显示字符），如控制符：LF（换

行）、CR（回车）、FF（换页）、DEL（删除）、BS（退格）、BEL（振铃）等；通讯专用字符：SOH

（文头）、EOT（文尾）、ACK（确认）等；ASCII值为8、9、10和13分别转换为退格、制表、

换行和回车字符。它们并没有特定的图形显示，但会依不同的应用程序，而对文木显示有不同的

影响。

32〜126（共95个）是字符（32sp是空格），其中48〜57为0到9十个阿拉伯数字；

65〜90为26个大写英文字母，97〜122号为26个小写英文字母，其余为一些标点符号、运算

符号等。

同时还要注意，在标准ASCII中，其最高位（b7）用作奇偶校验位。所谓奇偶校验，是指在代码

传送过程中用来检验是否出现错误的种方法，一般分奇校验和偶校验两种。奇校验规定：正

确的代码一个字节中1的个数必须是奇数，若非奇数，则在最高位b7添1；偶校验规定：正确的

代码一个字节中1的个数必须是偶数，若非偶数，则在最高位b7添1。

2.UNICODE（UniversalMultiple-OctetCodedCharacterSet）字符集

Unicode（统一码、万国码、单一码）是一种在计算机上使用的字符编码。它为每种语言中的每

个字符设定了统一并且唯一的二进制编码，以满足跨语言、跨平台进行文本转换、处理的要求。

unicode有两种方式：UCS-2,UC5-4,顾名思义，是两个字节和4个字节。

具体的可以google和百度。总的来讲，计算机前期，一般是ASCII,现在基于全球一体化,

基木都用unicode.

字符编码

l.Gbk,GB2312,GB18030

字符必须编码后才能被计算机处理。计算机使用的缺省编码方式就是计算机的内码。早期的计算

机使用7位的ASCII编码，为了处理汉字，程序员设计了用于简体中文的GB2312和用于繁体中

文的big5«

GB2312（1980年）一共收录了7445个字符，包括6763个汉字和682个其它符号。汉字区的内码范围

高字节从B0-F7,低字节从A1-FE,占用的码位是72*94=6768。其中有5个空位是D7FA-D7FE。

GB2312支持的汉字太少。1995年的汉字扩展规范GBK1.0收录了21886个符号，它分为汉字区和

图形符号区。汉字区包括21003个字符。2000年的GB18030是取代GBK1.0的正式国家标准。该标

准收录了27484个汉字，同时还收录了藏文、蒙文、维吾尔文等主要的少数民族文字。现在的PC

平台必须支持GB18030,对嵌入式产品暂不作要求。所以手机、MP3般只支持GB2312。

从ASCH、GB2312、GBK到GB18030,这些编码方法是向下兼容的，即同一个字符在这些方案中

总是有相同的编码，后面的标准支持更多的字符。在这些编码中，英文和中文可以统一地处理。

区分中文编码的方法是高字节的最高位不为0。按照程序员的称呼，GB2312,GBK到GB18030都属

于双字节字符集（DBCS）。

GB18030是中国所有非手持/嵌入式计算机系统的强制实施标准.

2.UTF-8,UTF-16,UTF-32

UTF-8,8bit编码，ASCH不作变换，其他字符做变长编码，每个字符「3byte.通常作为外码.

有以下优点：

*与CPU字节顺序无关，可以在不同平台之间交流

*容错能力高，任何一个字节损坏后，最多只会导致一个编码码位损失，不会链锁错误（如GB

码错一个字节就会整行乱码）

UTF-16,16bit编码，是变长码，大致相当于20位编码，值在0到OxlOFFFF之间，基本上就是

Unicode编码的实现.它是变长码，与CPU字序有关，但因为最省空间，常作为网络传输的外码.

UTF-16是unicode的preferredencoding.

UTF-32,仅使用了unicode范围（0到OxlOFFFF）的32位编码，相当于UCS-4的子集.

14、给我一个你最常见到的runtimeexception

答：常见的运行时异常有如下这些ArithmeticException,ArrayStoreException,

BufferOverflowException,BufferUnderflowException,CannotRedoException,

CannotUndoException,ClassCastException,CMMException,

ConcurrentModificationException,DOMException,EmptyStackException,

IllegalArgumentException,11legalMonitorStateException,IllegalPathStateException,

IllegalStateException,ImagingOpException,IndexOutOfBoundsException,

MissingResourceException,NegativeArraySizeException,NoSuchElementException,

NullPointerException,Profi1eDataException,ProviderException,RasterFormatException,

SecurityException,SystemException,UndeclaredThrowab1eException,

UnmodifiableSetException,UnsupportedOperationException

5、Collection和Collections的区别

答：Collection是集合类的上级接口，继承与他的接口主要有Set和List.

Collections是针对集合类的一个帮助类,他提供•系列静态方法实现对各种集合的搜索、排序、

线程安全化等操作

15、error和exception有什么区另！J

答：error表示恢复不是不可能但很困难的情况下的一种严重问题。比如说内存溢出。不可能指

望程序能处理这样的情况

exception表示一种设计或实现问题。也就是说，它表示如果程序运行正常，从不会发生

的情况

16、List,Set,Map是否继承自Collection接口

答：List,Set是，Map不是

17、abstractclass和interface有什么区别

答：声明方法的存在而不去实现它的类被叫做抽象类(abstractclass),它用于要创建一个体

现某些基本行为的类，并为该类声明方法，但不能在该类中实现该类的情况。不能创建abstract

类的实例。然而可以创建一个变量，其类型是一个抽象类，并让它指向具体子类的一个实例。不

能有抽象构造函数或抽象静态方法。Abstract类的子类为它们父类中的所有抽象方法提供实

现，否则它们也是抽象类为。取而代之，在子类中实现该方法。知道其行为的其它类可以在类中

实现这些方法

接口(interface)是抽象类的变体。在接口中，所有方法都是抽象的。多继承性可通过实现这

样的接口而获得。接口中的所有方法都是抽象的，没有一个有程序体。接口只可以定义static

final成员变量。接口的实现与子类相似，除了该实现类不能从接口定义中继承行为。当类实现

特殊接口时.，它定义(即将程序体给予)所有这种接口的方法。然后，它可以在实现了该接口的

类的任何对象上调用接口的方法。由于有抽象类，它允许使用接口名作为引用变量的类型。通

常的动态联编将生效。引用可以转换到接口类型或从接口类型转换，instanceof运算符可以用

来决定某对象的类是否实现了接口

6、Java基本概念：集合类List/Set/Map…的区别和联系

Collection：List、Set

Map：HashMap>HashTable

如何在它们之间选择

一、Array,Arrays

Java所有“存储及随机访问一连串对象”的做法，array是最有效率的一种。

1、

效率高，但容量固定且无法动态改变。

array还有一■个缺点是，无法判断其中实际存有多少元素，length只是告诉我们array的容量。

2、Java中有一个Arrays类，专门用来操作array。

arrays中拥有一组static函数，

equals()：比较两个array是否相等。array拥有相同元素个数，且所有对应元素两两相等。

将值填入array中。

sort()：用来对array进行排序。

binarySearch()：在排好序的array中寻找元素。

System.arraycopyO：array的复制。

二、Collection,Map

若撰写程序时不知道究竟需要多少对象，需要在空间不足时自动扩增容量，则需要使用容器类

库，array不适用。

1、Collection和Map的区别

容器内每个为之所存储的元素个数不同。

Collection类型者，每个位置只有一个元素。

Map类型者，持有key-valuepair,像个小型数据库。

2、各自旗下的子类关系

Collection

-List：将以特定次序存储元素。所以取出来的顺序可能和放入顺序不同。

—ArrayList/LinkedList/Vector

-Set：不能含有重复的元素

—HashSet/TreeSet

Map

—HashMap

-HashTable

-TreeMap

Collection

-List

[-LinkedList

-AiTayList

^-Vector

^-Stack

LSet

Map

-Hashtable

-HashMap

1-WcakHashMap

Collection接口

Collection是最基本的集合接口，一个Collection代表一组Object,即Collection的元素

(Elements)。一些Collection允许相同的元素而另一些不行。一些能排序而另一些不行。Java

SDK不提供直接继承自Collection的类，JavaSDK提供的类都是继承自Collection的“子接

口''如List和Seto

所有实现Collection接口的类都必须提供两个标准的构造函数：无参数的构造函数用

于创建一个空的Collection,有一个Collection参数的构造函数用于创建•个新的Collection,

这个新的Collection与传入的Collection有相同的元素。后一个构造函数允许用户复制一个

Collectiono

如何遍历Collection中的每一个元素？不论Collection的实际类型如何，它都支持一个

iterator。的方法，该方法返回一个迭代子，使用该迭代子即可逐一访问Collection中每一个

元素。典型的用法如下：

Iteratorit=collection.iterator();//获得一个迭代子

while(it.hasNext()){

Objectobj=it.next();//得到下一个元素

)

由Collection接口派生的两个接口是List和Set。

List接口

List是有序的Collection,使用此接口能够精确的控制每个元素插入的位置。用户能够

使用索引(元素在List中的位置，类似于数组下标)来访问List中的元素，这类似于Java

的数组。

和下面要提到的Set不同，List允许有相同的元素。

除了具有Collection接口必备的iterator。方法外，List还提供一个listlterator。方法，返

回一个Listiterator接口，和标准的Iterator接口相比，Listiterator多了一些add()之类的方法，

允许添加，删除，设定元素，还能向前或向后遍历。

实现List接口的常用类有LinkedList,ArrayList,Vector和Stacko

LinkedList类

LinkedList实现了List接口,允许null元素。此外LinkedList提供额外的get,remove,

insert方法在LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈(stack),队

列(queue)或双向队列(deque)。

注意LinkedList没有同步方法。如果多个线程同时访问一个List,则必须自己实现访

问同步。一种解决方法是在创建List时构造一个同步的List：

Listlist=Collcctions.synchronizedList(newLinkedList(...));

ArrayList类

ArrayList实现了可变大小的数组。它允许所有元素，包括null。ArrayList没有同步。

size,isEmpty,get,set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个

元素需要O(n)的时间。其他的方法运行时间为线性。

每个ArrayList实例都有一个容量(Capacity),即用于存储元素的数组的大小。这个容

量可随着不断添加新元素而自动增加，但是增长算法并没有定义。当需要插入大量元素时;

在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。

和LinkedList一样，ArrayList也是非同步的(unsynchronized)o

Vector类

Vector非常类似ArrayList,但是Vector是同步的。由Vector创建的Iterator,虽然和

ArrayList创建的Iterator是同一接口，但是，因为Vector是同步的，当一个Iterator被创建

而且正在被使用，另一个线程改变了Vector的状态(例如，添加或删除了一些元素)，这

时调用Iterator的方法时将抛出ConcurrentModificationExceptiorb因此必须捕获该异常。

Stack类

Stack继承自Vector,实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector

得以被当作堆栈使用。基本的push和pop方法，还有peek方法得到栈顶的元素，empty方

法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。

Set接口

Set是一种不包含重复的元素的Collection,即任意的两个元素el和e2都有

e1.equals(e2)=false,Set最多有一个null元素。

很明显，Set的构造函数有一个约束条件，传入的Collection参数不能包含重复的元素。

请注意：必须小心操作可变对象(MutableObject)。如果一个Set中的可变元素改变了

自身状态导致Object.equals(Object尸true将导致一些问题。

Map接口

请注意，Map没有继承Collection接口，Map提供key到value的映射。一个Map中不

能包含相同的key,每个key只能映射一个valueoMap接口提供3种集合的视图，Map的

内容可以被当作一组key集合，一组value集合，或者一组key・value映射。

Hashtable类

Hashtable继承Map接口，实现一个key-value映射的哈希表。任何非空(non-null)的

对象都可作为key或者valueo

添加数据使用put(key,value),取出数据使用get(key),这两个基本操作的时间开销为常

数。

Hashtable通过initialcapacity和loadfactor两个参数调整性能。通常缺省的loadfactor0.75

较好地实现了时间和空间的均衡。增大loadfhctor可以节省空间但相应的查找时间将增大，

这会影响像get和put这样的操作。

使用Hashtable的简单示例如下，将1,2,3放到Hashtable中，他们的key分别

是"one","two","three”：

Hashtablcnumbers=newHashtable();

numbers.put(“one"，newInteger(l));

numbers.put("two'',newInteger(2));

numbers.put(44three,\newInteger(3));

要取出一个数，比如2,用相应的key：

Integern=(Integer)numbers.get("two’')；

System.out.println(€4two=''+n);

由于作为key的对象将通过计算其散列函数来确定与之对应的value的位置，因此任何

作为key的对象都必须实现hashCode和equals方法。hashCode和equals方法继承自根类

Object,如果你用自定义的类当作key的话，要相当小心，按照散列函数的定义，如果两

个对象相同，即obj1.equals(obj2)=true,则它们的hashCode必须相同，但如果两个对象不同，

则它们的hashCode不一定不同，如果两个不同对象的hashCode相同，这种现象称为冲突，

冲突会导致操作哈希表的时间开销增大，所以尽量定义好的hashCode。方法，能加快哈希

表的操作。

如果相同的对象有不同的hashCode,对哈希表的操作会现意想不到的结果(期待的

get方法返回null),要避免这种问题，只需要牢记一•条：要同时复写equals方法和hashCode

方法，而不要只写其中一个。

Hashtable是同步的。

HashMap类

HashMap和Hashtable类似，不同之处在于HashMap是非同步的，并且允许null,即

nullvalue和nullkey。,但是将HashMap视为Collection时(values。方法可返回Collection),

其迭代子操作时间开销和HashMap的容量成比例。因此，如果迭代操作的性能相当重要的

话，不要将HashMap的初始化容量设得过高，或者loadfactor过低。

WeakHashMap类

WeakHashM叩是一种改进的HashMap,它对key实行"弱引用”，如果•个key不再被

外部所引用，那么该key可以被GC回收。

总结

如果涉及到堆栈，队列等操作，应该考虑用List,对于需要快速插入，删除元素，应该

使用LinkedList,如果需要快速随机访问元素，应该使用ArrayList。

如果程序在单线程环境中，或者访问仅仅在个线程中进行，考虑非同步的类，其效率

较高，如果多个线程可能同时操作一个类，应该使用同步的类-

要特别注意对哈希表的操作，作为key的对象要正确复写equals和hashCode方法。

尽量返回接U而非实际的类型，如返回List而非ArrayList,这样如果以后需要将

ArrayList换成LinkedList时，客户端代码不用改变。这就是针对抽象编程。

3、其他特征

*List,Set,Map将持有对象一律视为Object型别。

*Collection,List^Set、Map都是接口，不能实例化。

继承自它们的ArrayList,Vector,HashTable,HashMap是具象class,这些才可被实例化。

*vector容器确切知道它所持有的对象隶属什么型别。vector不进行边界检查。

三、Collections

Collections是针对集合类的一个帮助类。提供了一系列砂态方法实现对各种集合的搜索、排序、

线程完全化等操作。

相当于对Array进行类似操作的类—Arrays,

如，Collections.max(Collectioncoll);取coll中最大的元素。

Collections.sort(Listlist);对list中元素排序

四、如何选择？

1、容器类和Array的区别、择取

*容器类仅能持有对象引用(指向对象的指针)，而不是将对象信息copy一份至数列某位置。

*一旦将对象置入容器内，便损失了该对象的型别信息。

2、

*在各种Lists中，最好的做法是以ArrayList作为缺省选择。当插入、删除频繁时，使用

LinkedList()；

Vector总是比ArrayList慢，所以要尽量避免使用。

*在各种Sets中，HashSet通常优于HashTree(插入、查找)。只有当需要产生•个经过排序

的序列，才用TreeSet。

HashTree存在的唯一理由：能够维护其内元素的排序状态。

*在各种Maps中

HashMap用于快速查找。

*当元素个数固定，MJArray,因为Array效率是最高的。

结论：最常用的是ArrayList,HashSetHashMap>Arrayo

注意：

1、Collection没仃get()方法来取得某个元素。只能通过iterator。遍历元素。

2、Set和Collection拥有一模一样的接口。

3、List,可以通过get()方法来•次取出•个元素。使用数字来选择一堆对象中的•个，

get(0)...o(add/get)

4、一•般使用ArrayListo用LinkedList构造堆栈stack、队列queueo

5、Map用put(k,v)/get(k),还可以使用containsKey()/containsVakie()来检查其中是否含有

某个key/valueo

HashMap会利用对象的hashCode来快速找到key。

*hashing

哈希码就是将对象的信息经过一些转变形成一个独一无二的int值，这个值存储在

一个array中。

我们都知道所有存储结构中，array查找速度是最快的。所以，可以加速查找。

发生碰撞时，让array指向多个values。即，数组每个位置上又生成一个植表。

6、Map中元素，可以将key序列、value序列单独抽取出来。

使用keySet()抽取key序列，将map中的所有keys生成一个Set。

使用values。抽取value序列，将map中的所有values生成一个Collectiono

为什么一个生成Set,•个生成Collection?那是因为，key总是独一无二的，value允许重

复。

CollectionListSetMap区别记忆

这些都代表了Java中的集合，这里主要从其元素是否有序，是否可重复来进行

区别记忆，以便恰当地使用，当然还存在同步方面的差异，见上一篇相关文章。

有序否允许元素重复否

Collection否是

List是是

AbstractSet

否

SetHashSet否

TreeSet是（用二叉树排序）

MaAbstractMap使用key-value来

否

PHashMap映射和存储数据，

TreeMap是（用二叉树排序）Key必须惟一，

value可以重复

http://tb.bloM./TrackBack.aspx?PostId=584112

List接口对Collection进行了简单的扩充,它的具体实现类常用的有ArrayList和LinkedList。

你可以将任何东西放到一个List容器中，并在需要时从中取出。ArrayList从其命名中可以

看出它是一种类似数组的形式进行存储，因此它的随机访问速度极快，而LinkedList的内部

实现是链表，它适合于在链表中间需要频繁进行插入和删除操作。在具体应用时可以根据

需要自由选择。前面说的Iterator只能对容器进行向前遍历，而Listiterator则继承了Iterator

的思想，并提供了对List进行双向遍历的方法。

Set接口也是Collection的一种扩展,而与List不同的时,在Set中的对象元素不能重复,

也就是说你不能把同样的东西两次放入同一个Set容器中。它的常用具体实现有HashSet和

TreeSet类。HashSet能快速定位一个元素，但是你放到HashSet中的对象需要实现hashCode（）

方法，它使用了前面说过的哈希码的算法。而TreeSet则将放入其中的元素按序存放，这

就要求你放入其中的对象是可排序的，这就用到了集合框架提供的另外两个实用类

Comparable和Comparator。•个类是可排序的，它就应该实现Comparable接口。有时多个

类具有相同的排序算法，那就不需要在每分别重复定义相同的排序算法，只要实现

Comparator接口即可。集合框架中还有两个很实用的公用类：Collections和Arrays..

Collections提供了对一个Collection容器进行诸如排序、复制、查找和填充等一些非常有用

的方法，Arrays则是对•个数组进行类似的操作。

Map是一种把键对象和值对象进行关联的容器，而一个值对象又可以是一个Map,依次类

推，这样就可形成一个多级映射。对于键对象来说，像Set一样，一个Map容器中的键对

象不允许重复，这是为了保持查找结果的致性;如果有两个键对象一样，那你想得到那个

键对象所对应的值对象时就有问题了，可能你得到的并不是你想的那个值对象，结果会造

成混乱，所以键的唯一性很重要，也是符合集合的性质的。当然在使用过程中，某个键所对

应的值对象可能会发生变化，这时会按照最后一次修改的值对象与键对应。对于值对象则

没有唯一性的要求。你可以将任意多个键都映射到一个值对象上，这不会发生任何问题(不

过对你的使用却可能会造成不便，你不知道你得到的到底是那一个键所对应的值对象)。

Map有两种比较常用的实现：HashM叩和TreeMap。HashM叩也用到了哈希码的算法，以

便快速查找一个键，TreeMap则是对键按序存放，因此它便有一些扩展的方法，比如

firstKey(),lastKey()等，你还可以从TreeMap中指定一个范围以取得其子M叩。键和值的关

联很简单，用pub(Objectkey,Objectvalue)方法即可将一个键与一个值对象相关联。用

get(Objectkey)可得到与此key对象所对应的值对象。

7、Java语言中链表和双向链表

链表是•种重要的数据结构，在程序设计中占有很重要的地位。C语言和C++语言

中是用指针来实现链表结构的，由于Java语言不提供指针，所以有人认为在Java语言

中不能实现链表，其实不然，Java语言比C和C++更容易实现链表结构。Java语言中

的对象引用实际上是一个指针(本文中的指针均为概念上的意义，而非语言提供的数据

类型)，所以我们可以编写这样的类来实现链表中的结点。

classNode

(

Objectdata;

Nodenext;〃指向下一•个结点

)

将数据域定义成Object类是因为Object类是广义超类，任何类对象都可以给其赋

值，增加了代码的通用性。为了使链表可以被访问还需要定义一个表头，表头必须包含

指向第一个结点的指针和指向当前结点的指针。为了便于在链表尾部增加结点，还可以

增加一•指向链表尾部的指针，另外还可以用一个域来表示链表的大小，当调用者想得到

链表的大小时，不必遍历整个链表。下图是这种链表的示意图：

链表的数据结构

我们可以用类List来实现链表结构,用变量Head、Tail、Length、Pointer来实

现表头。存储当前结点的指针时有一定的技巧，Pointer并非存储指向当前结点的指针,

而是存储指向它的前趋结点的指针,当其值为null时表示当前结点是第一个结点。那么

为什么要这样做呢？这是因为当删除当前结点后仍需保证剩下的结点构成链表，如果

Pointer指向当前结点，则会给操作带来很大困难。那么如何得到当前结点呢，我们定

义了一个方法cursor。，返回值是指向当前结点的指针。类List还定义了一些方法来实

现对链表的基本操作，通过运用这些基本操作我们可以对链表进行各种操作。例如

reset()方法使第一个结点成为当前结点。insert(Objectd)方法在当前结点前插入一

个结点，并使其成为当前结点。remove。方法删除当前结点同时返回其内容，并使其后

继结点成为当前结点，如果删除的是最后一个结点，则第一个结点变为当前结点。

链表类List的源代码如下：

importjava.io.*;

publicclassList

{

/*用变量来实现表头*/

privateNodeHead=null;

privateNodeTail=null;

privateNodePointer=nul1;

privateintLength=0;

publicvoiddeleteAll()

/*清空整个链表*/

(

Head=null;

Tail=null;

Pointer=null;

Length=0;

)

publicvoidresetO

/*链表复位，使第一个结点成为当前结点*/

Pointer=null;

}

publicbooleanisEmpty()

/*判断链表是否为空*/

(

return(Length==0);

)

publicbooleanisEnd()

/*判断当前结点是否为最后一个结点*/

(

if(Length==0)

thrownewjava.lang.NullPointerExceptionO;

elseif(Length==l)

returntrue;

else

return(cursor()—Tail);

)

publicObjectnextNode()

/*返回当前结点的卜一个结点的值，并使其成为当前结点*/

(

if(Length==l)

thrownewjava.util.NoSuchElementException();

elseif(Length==0)

thrownewjava.lang.NullPointerExceptionO;

else

(

Nodetemp=cursor();

Pointer=temp;

if(temp!=Tai1)

return(temp.next,data);

else

thrownewjava.util.NoSuchElementException();

)

)

publicObjectcurrentNodeO

/*返回当前结点的值*/

(

Nodetemp=cursor();

returntemp,data;

)

publicvoidinsert(Objectd)

/*在当前结点前插入一个结点，并使其成为当前结点*/

(

Nodee=newNode(d);

if(Length-0)

(

Tail=e;

Head二e;

)

else

(

Nodetemp二cursor();

e.next=temp;

if(Pointer==null)

Head=e;

else

Pointer,next=e;

Length++;

)

publicintsize()

/*返回链表的大小*/

(

return(Length);

)

publicObjectremove()

/*将当前结点移出链表，下•个结点成为当前结点，如果移出的结点是最后一个结

点，则第一个结点成为当前结点*/

(

Objecttemp;

if(Length-0)

thrownewjava.util.NoSuchElementException();

elseif(Length==l)

(

temp=Head,data;

deleteAll();

)

else

(

Nodecur=cursor();

temp=cur.data;

if(cur二二Head)

Head=cur.next;

elseif(cur==Tail)

(

Pointer,next=null;

Tai「Pointer;

reset();

)

else

Pointer.next=cur.next;

Length---;

)

returntemp;

}

privateNodecursor()

/*返回当前结点的指针*/

(

if(Head==null)

thrownewjava.lang.NullPointerExceptionO;

elseif(Pointer二二null)

returnHead;

else

returnPointer,next;

)

publicstaticvoidmain(String[]args)

/*链表的简单应用举例*/

(

Lista=newList();

for(inti=l;i<=10;i++)

a.insert(newInteger(i));

System.out.println(a.currentNode());

while(!a.isEnd())

System,out.printin(a.nextNodeO);

a.reset();

while(!a.isEnd())

a.remove();

)

a.remove();

a.reset();

if(a.isEmpty())

System,out.println(z/ThereisnoNodeinList\n〃);

System,in.println(，zYoucanpressreturntoquit\n〃);

try

(

System,in.read();

//确保用户看清程序运行结果

)

catch(lOExceptione)

()

)

)

classNode

/*构成链表的结点定义*/

(

Objectdata;

Nodenext;

Node(Objectd)

(

data=d;

next=null;

)

)

读者还可以根据实际需要定义新的方法来对链表进行操作。双向链表可以用类似的

方法实现只是结点的类增加了—个指向前趋结点的指针。

可以用这样的代码来实现:

classNode

(

Objectdata;

Nodenext;

Nodeprevious;

Node(Objectd)

(

data=d;

next=null;

previous=null;

)

}

当然，双向链表基本操作的实现略有不同。链表和双向链表的实现方法，也可以用

在堆栈和队列的实现中，这里就不再多写了，有兴趣的读者可以将List类的代码稍加

改动即可。

(1)简单链表

Java代码j

1packageChapterFive;

2

3classLink<E>{

4

5publicEdata;

6

publicLink<E>next;

8

9publicLink(Edata){

10this.data=data;

H}

12)

13

14classLinkList<E>{

15

16publicLink<E>first;

17//链表中数据项的个数

18publicintsize;

19

20publicLinkList(){

21first=null;

22size=0;

23}

24//在表头插入新的数据

25publicvoidinsertFirst(Evalue){

26Link<E>link=newLink<E>(value);

27link.next=first;

28first=link;

29size++;

30)

31//判断链表是否为空

32publicbooleanisEmpty(){

33returnsize==0;

34)

35//删除表头

36publicLink<E>deleteFirst(){

37Link<E>temp=first;

38first=first.next;

39size——;

40returntemp;

41}

42//输出链表中的所有数据

43publicvoiddisplay(){

44Link<E>curr=first;

45while(curr!=null){

46System.out.print(curr.data+"n);

47curr=curr.next;

48}

49System.out.printIn();

50)

51//返回链表中数据项的个数

52publicintsize(){

53returnsize;

54)

55〃获取从头至尾的第i个数据项

56publicLink<E>get(inti){

57if(i>size()-1||i<0)

58try{

59thrownewIndexOutOfBoundsException();

60}catch(Exceptione){

61e.printStack.Trace();

62)

63Link<E>curr=first;

64for(intn=0;n<size();n++){

65if(n==i)

66returncurr;

67else

68curr=curr.next;

69}

70returnnull;

71}

72//输出从头至尾的第i个数据项

73publicvoidremove(inti){

74if(i==0)

乃deleteFirst();

76elseif(i==size()-1)

77get(i-1).next=null;

78else{

79get(i-1).next=get(i+1);

80)

81size—;

82)

83}

84

85publicclassLink_list{

86publicstaticvoidmain(String[]args){

87LinkList<Long>11=newLinkList<Long>();

88for(inti=0;i<10;i++){

89Longvalue=(long)(Math.random()*100);

9011.inser