《数据布局与算法分析》读书笔记：第一章 引 论

目次
1.1本书讨论的内容
1.2数学知识复习
1.2.1指数
1.2.2对数
1.2.3级数
1.2.4模运算
1.2.5证明的方法
1.3递归简论
1.4实现泛型构件pre-Java 5
1.4.1利用Object表示泛型
1.4.2根本类型的包装
1.4.3利用接口类型表示泛型
1.4.4数组类型的兼容性
1.5利用Java 5泛型特性实现泛型构件
1.5.1简单的泛型类和接口
1.5.2主动装箱/拆箱
1.5.3菱形运算符
1.5.4带有限定的通配符
1.5.5泛型static方法
1.5.6类型限界
1.5.7类型擦除
1.5.8对于泛型的限定
1.6函数对象

---

1.1本书讨论的内容

    在许多题目当中，一个重要的观念是:写出一个工作步伐并不够。如果这个步伐在巨大的数据集上运行，那么运行时间就变成了重要的题目。我们将在本书看到对于大量的输入怎样估计步伐的运行时间，尤其是怎样在尚未具体编码的情况下比较两个步伐的运行时间。我们还将看到彻底改进步伐速度以及确定步伐瓶颈的方法。这些方法将使我们能够发现必要我们会合精力积极优化的那些代码段。
1.2数学知识复习

本节列出一些必要记忆或是能够推导出的根本公式，并从推导过程复习根本的证明方法。
1.2.1指数

1.2.2对数

在盘算机科学中，除非有特别的声明，否则全部的对数都是以2为底的。

1.2.3级数

 

1.2.4模运算

      如果N整除A-B,那么就说A与B模N同余，记为A≡B( mod N)。直观地看，这意味着无论是A还是B被N去除，所得余数都是相同的。于是，81 ≡61≡1 ( mod 10)。如划一号的情形一样，若A≡B( mod N)，则A+C≡B+C( mod N)以及AD≡BD( mod N)。
      有许多定理适用模运算，此中有些特别必要用到数论来证明。我们将尽量少利用模运算，这样，前面的一些定理也就足够了。
1.2.5证明的方法

      证明数据布局分析中的结论的两种最常用的方法是归纳法证明和反证法证明(偶然也被迫用到只有教授们才利用的证明)。证明一个定理不建立的最好的方法是举出一个反例。
      归纳法证明
      由归纳法进行的证明有两个尺度的部分。第一步是证明基准情形，就是确定定理对于某个(某些)小的(通常是退化的)值的精确性;这一步几乎总是很简单的。接着，进行归纳假设。一般说来，它指的是假设定理对直到某个有限数k的全部的情况都是建立的。然后利用这个假设证明定理对下一个值(通常是k+1)也是建立的。至此定理得证(在k是有限的情形下)。

1.3递归简论

 

上面的讨论导致递归的前两个根本法则:

• 基准情形。必须总要有某些基准的情形，它们不用递归就能求解。
  
• 不停推进。对于那些要递归求解的情形，递归调用必须总能够朝着一个基准情形推进。
  

      在本书中我们将用递归办理一些题目。作为非数学应用的一个例子,考虑一本大词典。词典中的词都是用其他的词定义的。当查一个单词的时候，我们不是总能理解对该词的解释，于是我们不得不再查找解释中的一些词。同样，对这些词中的某些地方我们又不理解，因此还要继续这种查找。由于词典是有限的，以是现实上大概我们最终要查到一处，明白了此处解释中全部的单词(从而理解这里的解释，并按照查找的路径回查其余的解释)大概我们发现这些解释形成一个循环，无法理解其最终含义，大概在解释中必要我们理解的某个单词不在这本词典里。
      我们理解这些单词的递归策略如下:如果知道一个单词的含义，那么就算我们成功;否则，就在词典里查找这个单词。如果我们理解对该词解释中的全部的单词，那么又算我们成功;否则，通过递归查找一些我们不认识的单词来“算出”对该单词解释的含义。如果词典编纂得完美无瑕，那么这个过程就能够终止;如果此中一个单词没有查到或是循环定义(解释)，那么这个过程则循环不定。
     打印输出整数
       设有一个正整数n并盼望把它打印出来。我们的例程的名字为printout(n)。假设仅有的现成I/O例程将只处理单个数字并将其输出到终端。我们为这种例程命名为printDigit;例如，printDigit(4)将输出4到终端。
      递归将为该题目提供一个非常美丽的解。要打印76234，我们首先必要打印出7623，然后再打印出4。第二步用语句printDigit(n% 10)很容易完成，但是第一步却不比原题目简单多少。它现实上是同一个题目，因此可以用语句printout (n /10 )递归地办理它。
      这告诉我们怎样去办理一般的题目，不外我们仍然必要确认步伐不是循环不定的。由于我们尚未定义一个基准情况，因此很清晰，我们仍然还有些事情要做。如果0≤n<10,那么基准情形就是printDigit(n)。现在，printout(n)已对每一个从0到9的正整数定义，而更大的正整数则用较小的正整数定义。因此，不存在循环的题目。整个方法在图1-4中指出。

 
      我们没有积极去高效地做这件事。我们本可以避免利用mod例程(它是非常耗时的)，由于n%10 = n -(n/10)* 10
      递归和归纳
     让我们多少严格一些地证明上述递归的整数打印步伐是可行的。为此,我们将利用归纳法证明。        定理1.4
      递归的整数打印算法对n≥0是精确的。
      证明(通过对n所含数字的个数，用归纳法证明之):
首先，如果n只有一位数字,那么步伐显然是精确的，由于它只是调用一次printDigit。然后，设printout对全部k个或更少位数的数均能正常工作。我们知道k +1位数字的数可以通过其前k位数字后跟一位最低位数字来表示。但是前k位数字形成的数恰好是n/10，由归纳假设它能够被精确地打印出来，而末了的一位数字是n mod 10，因此该步伐能够精确打印出恣意k+1位数字的数。于是，根据归纳法，全部的数都能被精确地打印出来。
       这个证明看起来大概有些希奇，但它现实上相称于是算法的形貌。证明论述的是在设计递归步伐时，同一题目的全部较小实例均可以假设运行精确，递归步伐只必要把这些较小题目的解(它们通过递归奇迹般地得到)联合起来形成现行题目的解。其数学根据则是归纳法的证明。由此，我们给出递归的第三个法则:
      3．设计法则( design rule)。假设全部的递归调用都能运行。
      这是一条重要的法则，由于它意味着，当设计递归步伐时一般没有必要知道簿记管理的细节，你不必试图追踪大量的递归调用。追踪具体的递归调用的序列常常是非常困难的。当然，在许多情况下，这正是利用递归好处的体现，由于盘算性能够算出复杂的细节。
     递归的主要题目是隐含的簿记开销。固然这些开销几乎总是合理的(由于递归步伐不但简化了算法设计而且也有助于给出更加简洁的代码)，但是递归绝不应该作为简单for循环的代替物。我们将在3.6节更细致地讨论递归涉及的系统开销。
     当编写递归例程时，关键是要牢记递归的四条根本法则:

• 基准情形。必须总要有某些基准情形，它无需递归就能解出。
  
• 不停推进。对于那些必要递归求解的情形，每一次递归调用都必须要使状态朝向一种基准情形推进。
  
• 设计法则。假设全部的递归调用都能运行。
  
• 合成效益法则( compound interest rule)。在求解一个题目的同一实例时，切勿在差别的递归调用中做重复性的工作。
  

     第四条法则(连同它的名称一起)将在后面的章节证明是合理的。利用递归盘算诸如斐波那契数之类简单数学函数的值的想法一般来说不是一个好主意，其道理正是根据第四条法则。只要在头脑中记取这些法则，递归步伐设计就应该是简单明白的。
1.4实现泛型构件pre-Java 5

面向对象的一个重要目标是对代码重用的支持。支持这个目标的一个重要的机制就是泛型机制：如果撤除对象的根本类型外，实现方法是相同的，那么我们就可以用泛型实现来形貌这种根本的功能。例如，可以编写一个方法，将由一些项组成的数组排序;方法的逻辑关系与被排序的对象的类型无关，此时可以利用泛型方法。
     与许多新的语言(例如C++，它利用模板来实现泛型编程)差别，在1.5版从前，Java并不直接支持泛型实现，泛型编程的实现是通过利用继续的一些根本概念来完成的。本节形貌在Java中怎样利用继续的根本原则来实现一些泛型方法和类。
     Sun公司在2001年是把对泛型方法和类的直接支持作为未来的语言加强剂来宣布的。厥后,终于在2004年末发表了Java 5并提供了对泛型方法和类的支持。然而，利用泛型类必要理解pre-Java 5对泛型编程的语言特性。因此，对继续怎样用来实现泛型步伐的理解是根本的关键，以致在Java 5中仍然云云。
1.4.1利用Object表示泛型

    Java中的根本思想就是可以通过利用像Object这样得当的超类来实现泛型类。在下列代码所示的 Memorycell类就是这样一个例子。

   当我们利用这种策略时，有两个细节必须要考虑。第一个细节在图1-6中阐释，它形貌一个main方法，该方法把串“37”写到MemoryCell对象中，然后又从Memorycell对象读出。为了访问这种对象的一个特定方法，必须要逼迫转换成精确的类型。(当然，在这个例子中，可以不必进行逼迫转换，由于在步伐的第9行可以调用toString()方法，这种调用对恣意对象都是能够做到的)。

     第二个重要的细节是不能利用根本类型。只有引用类型能够与Object相容。这个题目的尺度工作立刻就要讨论。
1.4.2根本类型的包装

     当我们实现算法的时候，常常遇到语言定型题目:我们已有一种类型的对象，但是语言的语法却必要一种差别类型的对象。
       这种技巧阐释了包装类的根本主题。一种典型的用法是存储一个根本的类型，并添加一些这种根本类型不支持或不能精确支持的操作。
      在Java中我们已经看到,固然每一个引用类型都和Object相容，但是,8种根本类型却不能。于是，Java为这8种根本类型中的每一种都提供了一个包装类。例如，int类型的包装是Integer。每一个包装对象都是不可变的(就是说它的状态绝不能改变)，它存储一种当该对象被构建时所设置的原值，并提供一种方法以重新得到该值。包装类也包罗不少的静态实用方法。
     例如，图1-7说明怎样能够利用Memorycel1来存储整数。
 

1.4.3利用接口类型表示泛型

      只有在利用Object类中已有的那些方法能够表示所执行的操作的时候，才气利用Object作为泛型类型来工作。
     例如，考虑在由一些项组成的数组中找出最大项的题目。根本的代码是类型无关的，但是它的确必要一种能力来比较恣意两个对象，并确定哪个是大的，哪个是小的。因此，我们不能直接找出Object 的数组中的最大元素——-我们必要更多的信息。最简单的想法就是找出Comparable 的数组中的最大元。要确定次序，可以利用compareTo方法，我们知道，它对全部的Comparable都一定是现成可用的。图1-8中的代码做的就是这项工作，它提供一种main方法,该方法能够找出String或Shape数组中的最大元。
      现在，提出几个忠告很重要。首先，只有实现Comparable接口的那些对象才气够作为Comparable数组的元素被传递。仅有compareTo方法但并未宣称实现Comparable接口的对象不是Comparable的，它不具有必须的IS-A关系。由于我们大概会比较两个shape的面积，因此假设shape实现Comparable接口。这个测试步伐还告诉我们，circle、square和Rectangle都是Shape的子类。
      第二，如果Comparable数组有两个不相容的对象(例如，一个 string和一个Shape),那么CompareTo方法将抛出异常classCastException。这是我们期望的性质。
       第三，如前所述，根本类型不能作为Comparable传递，但是包装类则可以，由于它们实现了Comparable接口。
      第四,接口毕竟是不是尺度的库接口倒不是必须的。
      末了，这个方案不是总能够行得通，由于偶然宣称一个类实现所需的接口是不大概的。例如，一个类大概是库中的类，而接口却是用户定义的接口。如果一个类是final类，那么我们就不大概扩展它以创建一个新的类。1.6节对这个题目提出了另一个办理方案，即function object。这种函数对象也利用一些接口，它大概是我们在Java库中所遇到的核心论题之一。
 

1.4.4数组类型的兼容性

     语言设计中的困难之一是怎样处理聚集类型的继续题目。设Employee IS-A Person。那么，这是不是也意味着数组Employee[ ] IS-A Person[]呢?换句话说，如果一个例程担当Person[]作为参数，那么我们能不能把Employee[]作为参数来传递呢?
     乍一看，该题目不值得一问，似乎 Employee[]就应该是和 Person[]类型兼容的。然而，这个题目却要比想象的复杂。假设除Employee外，我们还有student IS-A Person，并设Employee[]是和Person[]类型兼容的。此时考虑下面两条赋值语句:

     两句都编译，而arr[0]现实上是引用一个Employee，但是 student IS- NOT- AEmployee。这样就产生了类型杂乱。运行时系统( runtime system ) ( Java 虚拟机―译者注)不能抛出classCastException异常，由于不存在类型转换。
     避免这种题目的最容易的方法是指定这些数组不是类型兼容的。但是，在Java 中数组却是类型兼容的。这叫作协变数组类型。每个数组都明白它所允许存储的对象的类型。如果将一个不兼容的类型插入到数组中,那么虚拟机将抛出一个ArraystoreException异常。
     在较早版本的Java中是必要数组的协变性的，否则在图1-8的第29行和第30行的调用将编译不了。
1.5利用Java 5泛型特性实现泛型构件

1.5.1简单的泛型类和接口

1. //MemoryCell类的泛型实现
2. public class GenericMemoryCell<AnyType>{
3.    public AnyType read(){
4.        return storedValue;
5.    }
6.    public void write(AnyType x){
7.       storedValue=x;
8.    }
9.    private AnyType storedValue;
10. }

复制代码

     上述代码是前面图1-5形貌的 Memorycell的泛型版代码。这里，我们把名字改成了GenericMemoryCel1，由于两个类都不在包中，以是名字也就不能相同。
      当指定一个泛型类时,类的声明则包罗一个或多个类型参数，这些参数被放在类名后面的一对尖括号内。第1行指出，Generic-Memorycell有一个类型参数。在这个例子中，对类型参数没有明显的限定，以是用户可以创建像GenericMemorycell<String >和GenericMemoryCell <Integer >这样的类型，但是不能创建GenericMemoryCell<int>这样的类型。在GenericMemorycell类声明内部，我们可以声明泛型类型的域和利用泛型类型作为参数或返回类型的方法。例如在代码中的第5行，类GenericMemorycell<string >的write方法必要一个string类型的参数。如果传递其他参数那将产生一个编译错误。
     也可以声明接口是泛型的。例如，在Java 5从前，comparable接口不是泛型的，而它的compareTo方法必要一个object作为参数。于是，传递到compareTo方法的任何引用变量即使不是一个合理的类型也都会编译，而只是在运行时报告ClassCastException错误。在Java 5 中，Comparable接口是泛型的，

1. //Java 5 版本的Comparable接口，它是泛型接口
2. package java.lang;
4. pub1ic interface Comparable<AnyType>{
5.    public int compareTo( AnyType ths,AnyType rhs );
6. }

复制代码

    例如，现在String类实现Comparable < String >并有一个compareTo方法，这个方法以一个String 作为其参数。通过使类变成泛型类，从前只有在运行时才气报告的许多错误现在变成了编译时的错误。
1.5.2主动装箱/拆箱

      图1-7中的代码写得很贫苦，由于利用包装类必要在调用write之前创建Integer对象，然后才气利用intvalue方法从Integer中提取int 值。在Java 5从前，这是必要的，由于如果一个int型的量被放到必要 Integer对象的地方，那么编译将会产生一个错误信息，而如果将一个Integer对象的结果赋值给一个int 型的量，则编译也将产生一个错误信息。图1-7中的代码准确地反映出根本类型和引用类型之间的区别，但还没有清晰地表示出步伐员把那些int存入聚集( collection)的意图。
     Java 5矫正了这种情形。如果一个int型量被传递到必要一个Integer对象的地方，那么，编译器将在幕后插人一个对Integer构造方法的调用。这就叫作主动装箱。而如果一个Integer对象被放到必要int 型量的地方，则编译器将在幕后插入一个对intvalue方法的调用，这就叫作主动拆箱。对于其他7对根本类型包装类型，同样会发生雷同的情形。下列代码用Java 5形貌了主动装箱和主动拆箱的利用。注意，在GenericMemoryCell中引用的那些实体仍然是Integer对象;在GenericMemorycell的实例化中，int不能够代替Integero

1. //自动装箱和拆箱(Java 5)
2. class BoxingDemo{
3.    public static void main( String [ ] args ){
4.       GenericMemoryCe11<Integer> m = new GenericMemoryCe11<Integer>();
5.       m.write(37);
6.       int val = m.read();
7.       System.out.println( "Contents are: " + val );
8.    }
9. }

复制代码

1.5.3菱形运算符

    在上述代码中，第5行有些烦人，由于既然m 是GenericMemorycell <Integer >类型的，显然创建的对象也必须是GenericMemorycell<Integer >类型的，任何其他类型的参数都会产生编译错误。Java 7增加了一种新的语言特性，称为菱形运算符，使得第5行可以改写为

1. GenericMemorycell<Integer> m = new GenericMemoryCe11<>( );

复制代码

      菱形运算符在不增加开发者负担的情况下简化了代码，我们通篇都会利用它。下列代码给出了带菱形运算符的Java 7版代码。

1. //自动装箱和拆箱(Java 7，使用菱形运算符)
2. class BoxingDemo{
3.    public static void main( String [ ] args ){
4.       GenericMemoryCe11<Integer> m = new GenericMemoryCe11<>();
5.       m.write(5);
6.       int val = m.read();
7.       System.out.println( "Contents are: " + val );
8.    }
9. }

复制代码

1.5.4带有限定的通配符

1. //Shape[]的totalArea方法
2. public static doub1e totalArea( Shape[] arr ){
3.    double total = 0;
4.    for( Shape s : arr )
5.        if( s != nul1 )
6.          total += s.area();
7.    return total;
8. }

复制代码

     上述代码体现一个static方法，该方法盘算一个Shape数组的总面积(假设Shape是含有area方法的类;而circle和 square则是继续shape 的类)。假设我们想要重写这个盘算总面积的方法，使得该方法能够利用Collection <Shape >这样的参数。Collection将在第3章形貌。当前，唯一重要的是它能够存储一些项，而且这些项可以用一个加强的for循环来处理。由于是加强的for循环，因此代码是相同的,末了的结果如下列代码所示。如果传递一个Collection <Shape >，那么，步伐会正常运行。但是，要是传递一个Collection<square >会发生什么情况呢?答案依靠于是否Collection <Square > IS-A Collection<Shape >。回顾1.4.4节可知，用技能术语来说即是否我们拥有协变性。

1. /totalArea方法，如果传递一个Collection<Square>,则该方法不能运行
2. public static double tota1Area( Collection<Shape> arr ){
3.    double total = 0;
4.    for( Shape s : arr )
5.      if( s != nul1 )
6.        total += s.area( );
7.    return total;
8. }

复制代码

     我们在1.4.4节提到,Java中的数组是协变的。于是，Square[ ]  lS-A Shape[ ]。一方面，这种一致性意味着，如果数组是协变的，那么聚集也将是协变的。另一方面，我们在1.4.4节看到，数组的协变性导致代码得以编译，但以后会产生一个运行时异常(一个ArraystoreException)。由于利用泛型的全部缘故原由就在于产生编译器错误而不是类型不匹配的运行时异常，以是，泛型聚集不是协变的。因此，我们不能把collection <square >作为参数传递到代码中的方法里去。
     现在的题目是，泛型(以及泛型聚集)不是协变的(但有意义)，而数组是协变的。若无附加的语法，则用户就会避免利用聚集( collection)，由于失去协变性使得代码缺少灵活性。
      Java 5用通配符( wildcard)来补充这个不足。通配符用来表示参数类型的子类(或超类)。下列代码形貌带有限定的通配符的利用，图中编写一个将collection <T >作为参数的方法totalArea，此中T IS-A Shape。因此,Collection <Shape >和Collection<square >都是可以担当的参数。通配符还可以不带限定利用(此时假设为extends object),或不用extends而用super(来表示超类而不是子类);别的还存在一些其他的语法，我们就不在这里讨论了。

1. //用通配符修正后的totalArea方法，如果传递一个
2. collection < Square >，则方法能够正常运行
4. public static double tota1Area( Collection<? extends Shape> arr ){
5.   double total = 0;
6.   for( Shape s : arr )
7.     if( s != nu11 )
8.       total += s.area( );
9.   return total;
10. }

复制代码

1.5.5泛型static方法

    从某种意义上说，上述代码中的totalArea方法是泛型方法，由于它能够担当差别类型的参数。但是，这里没有特定类型的参数表，正如在GenericMemorycell类的声明中所做的那样。偶然候特定类型很重要，这大概由于下列的缘故原由:

• 该特定类型用做返回类型;
  
• 该类型用在多于一个的参数类型中;
  
• 该类型用于声明一个局部变量。
  

     如果是这样，那么，必须要声明一种带有若干类型参数的显式泛型方法。
     例如，下面代码体现一种泛型static方法，该方法对值x在数组arr中进行一系列查找。通过利用一种泛型方法，代替利用object作为参数的非泛型方法，当在Shape对象的数组中查找Apple对象时我们能够得到编译时错误。

1. //泛型static方法搜索数组
2. public static <AnyType> boolean contains( AnyType[] arr，AnyType x ){
3.    for( AnyType val : arr )
4.       if( x.equals( val ) )
5.          return true;
6.    return false;
7. }

复制代码

    泛型方法特别像是泛型类，由于类型参数表利用相同的语法。在泛型方法中的类型参数位于返回类型之前。
1.5.6类型限界

     假设我们想要编写一个findMax例程。考虑下列的代码。由于编译器不能证明在第6行上对compareTo 的调用是合法的，因此，步伐不能正常运行;只有在AnyType是Comparable的情况下才气保证compareTo存在。我们可以利用类型限界办理这个题目。类型限界在尖括号内指定，它指定参数类型必须具有的性质。一种自然的想法是把性质改写成

1. public ststic<AnyType extends Comparable>...

复制代码

1. //泛型static方法查找一个数组中最大元素，该方法不能正常运行
2. public static <AnyType> AnyType findMax ( AnyType [ ] arr ){
3.    int maxIndex = o;
4.    for( int i = l; i < arr.length; i++ )
5.      if( arr[ i ].compareTo( arr[ maxIndex ] ) > 0 )
6.         maxIndex = i;
7.    return arr[ maxIndex ];
8. )

复制代码

     我们知道，由于Comparable接口现在是泛型的，以是这种做法很自然。固然这个步伐能够被编译，但是更好的做法却是

1. public static <AnyType extends Comparable<AnyType>> ...

复制代码

     然而，这个做法还是不能令人满意。为了看清这个题目，假设Shape实现 Comparable
<Shape > ,设Square继续 Shape。此时，我们所知道的只是Square实现Comparable<shape >。于是，Square IS-A Comparable < Shape >，但它IS-NOT-A Comparable<square > !
应该说，AnyType IS-A Comparable <T>，此中，T是AnyType的父类。由于我们不必要知道准确的类型T，因此可以利用通配符。末了的结果变成

1. public static <AnyType extends Comparable<? super AnyTypes>>

复制代码

     下列代码体现findMax的实现。编译器将担当类型T的数组，只是使得T实现Comparable<S>接口，此中T IS-A S。当然，限界声明看起来有些杂乱。荣幸的是，我们不会再看到任何比这种用语更复杂的用语了。

1. //在一个数组中找出最大元的泛型static方法。以例说明类型参数的限界
2. public static <AnyType extends Comparable<? super AnyType>>
3. AnyType findMax ( AnyType [ ] arr ){
4.    int maxIndex = 0;
5.    for( int i = 1; i < arr.length; i++ )
6.       if( arr[ i ].compareTo( arr[ maxIndex ] ) > 0 )
7.          maxIndex = i;
8.    return arr[ maxIndex ];
9. }

复制代码

1.5.7类型擦除

     泛型在很大程度上是Java语言中的身分而不是虚拟机中的布局。泛型类可以由编译器通过所谓的类型擦除过程而转变成非泛型类。这样，编译器就生成一种与泛型类同名的原始类，但是类型参数都被删去了。类型变量由它们的类型限界来代替，当一个具有擦除返回类型的泛型方法被调用的时候，一些特性被主动地插入。如果利用一个泛型类而不带类型参数,那么利用的是原始类。
    类型擦除的一个重要推论是，所生成的代码与步伐员在泛型之前所写的代码并没有太多的差异，而且事实上运行的也并不快。其显著的优点在于，步伐员不必把一些类型转换放到代码中，编译器将进行重要的类型检验。
1.5.8对于泛型的限定

     对于泛型类型有许多的限定。由于类型擦除的缘故原由，这里列出的每一个限定都是必须要遵守的。
     根本类型
     根本类型不能用做类型参数。因此，GenericMemorycell <int >是非法的。我们必须利用包装类。
     instanceof检测
      instanceof检测和类型转换工作只对原始类型进行。在下列代码中:

1. GenericMemoryCe11<Integer> ce111 = new GenericMemoryCe11<>( );
2. ce111.write( 4 );
3. 0bject cell = ce111;
4. GenericMemoryCe11<String> ce112 = (GenericMemoryCe11<String>) cel1;
5. String s = ce112.read( );

复制代码

     这里的类型转换在运行时是成功的，由于全部的类型都是GenericMemorycell。但在末了一行，由于对read的调用计划返回一个String对象从而产生一个运行时错误。结果，类型转换将产生一个告诫，而对应的instanceof检测是非法的。
      static的语境
      在一个泛型类中，static方法和static域均不可引用类的类型变量，由于在类型擦除后类型变量就不存在了。别的，由于现实上只存在一个原始的类，因此static域在该类的诸泛型实例之间是共享的。
      泛型类型的实例化
      不能创建一个泛型类型的实例。如果T是个类型变量，则语句

1. T obj = new T( );/右边是非法的

复制代码

是非法的。T由它的限界代替，这大概是object(或以致是抽象类)，因此对new的调用没有意义。
       泛型数组对象
     也不能创建一个泛型的数组。如果T是一个类型变量，则语句

1. T [ ] arr = new T[ 10 ];//右边是非法的

复制代码

     是非法的。T将由它的限界代替，这很大概是Object T，于是(由类型擦除产生的)对T[]的类型转换将无法进行,由于object[ ] IS-NOT-A T[ ]。由于我们不能创建泛型对象的数组，因此一般说来我们必须创建一个擦除类型的数组，然后利用类型转换。这种类型转换将产生一个关于未检验的类型转换的编译告诫。
      参数化类型的数组
     参数化类型的数组的实例化是非法的。考虑下列代码:

1. GenericMemoryCe11<String> [ ] arrl = new GenericMemoryce11<>[10];
2. GenericMemoryCe11<Double> cell = new GenericMemoryCe11>( ); ce11.write( 4.5 );
3. 0bject [ ] arr2 = arr1;
4. arr2[ 0 ] = cell;
5. String s = arr1[ 0 ].read( );

复制代码

      正常情况下，我们以为第4行的赋值会生成一个ArraystoreException，由于赋值的类型有错误。但是，在类型擦除之后，数组的类型为GenericMemoryCell[ ]，而加到数组中的对象也是GenericMemoryCell,因此不存在ArrayStoreException异常。于是,该段代码没有类型转换，它最终将在第5行产生一个classCastException异常，这正是泛型应该避免的情况。
1.6函数对象

     在1.5节我们指出怎样编写泛型算法。例如，图1-16中的泛型方法可以用于找出一个数组中的最大项。
       然而，这种泛型方法有一个重要的范围:它只对实现Comparable接口的对象有效，由于它利用compareTo作为全部比较决策的底子。在许多情形下，这种处理方式是不可行的。例如，尽管假设Rectangle类实现Comparable接口有些太过，但即使实现了该接口，它所具有的compareTo方法恐怕还不是我们想要的方法。例如，给定一个2×10的矩形和一个5×5的矩形，哪个是更大的矩形呢?答案恐怕依靠于我们是利用面积还是利用长度来决定。大概，如果我们试图通过一个开口构造该矩形，那么大概较大的矩形就是具有较大最小周长的矩形。作为第二个例子,在一个字符串的数组中如果想要找出最大的串(即字典序排在末了的串)，默认的compareTo不忽略字符的大小写，则“ZEBRA”按字典序排在“alligator”之前，这大概不是我们想要的。
     上述这些情形的办理方案是重写findMax，使它担当两个参数:一个是对象的数组，另一个是比较函数，该函数解释怎样决定两个对象中哪个大哪个小。现实上，这些对象不再知道怎样比较它们自己;这些信息从数组的对象中完全去除了。
      一种将函数作为参数传递的独创方法是注意到对象既包罗数据也包罗方法，于是我们可以定义一个没有数据而只有一个方法的类，并传递该类的一个实例。事实上，一个函数通过将其放在一个对象内部而被传递。这样的对象通常叫作函数对象。
     图1-18体现函数对象想法的最简单的实现。findMax的第二个参数是Comparator类型的对象。接口Comparator在java. util中指定并包罗一个compare方法。这个接口在图1-19中指出。

     实现接口Comparator <AnyType >类型的任何类都必须要有一个叫作compare 的方法，该方法有两个泛型类型( AnyType)的参数并返回一个int 型的量，遵守和compareTo相同的一般约定。因此，在图1-18中的第9行对compare的调用可以用来比较数组的项。第4行的带有限定的通配符用来表示如果查找数组中的最大的项,那么该comparator必须知道怎样比较这些项,大概这些项的超类型的那些对象。我们可以在第26行看到，为了利用这种版本的findMax，findMax通过传递一个string数组以及一个实现comparator <string >的对象而被调用。这个对象属于CaseInsensitiveCompare类型，它是我们编写的一个类。
       在第4章我们将给出关于一个类的例子，这个类必要将它存储的项排序。我们将利用comparable编写大部分的代码，并指出此中必要利用函数对象的改动部分。在本书的其他地方，我们将避免函数对象的细节以使得代码尽大概地简单，我们知道以后将函数对象添加进去并不困难。