抽象数据类型+面向对象编程基础

1.基本数据类型、引用数据类型

基本数据类型

1、在基本数据类型中，除了boolean类型所占长度与平台有关外，其他数据类型长度都是与平台无关的。比如，int永远占4个字节（1 Byte = 8 bit）。

2、void不是基本数据类型

3、基本数据类型的默认值仅在作为类中属性时生效，在方法内部必须先对基本数据类型变量赋值后才能使用，否则编译不通过。

引用数据类型

引用类型（reference type）指向一个对象，不是原始值，指向对象的变量是引用变量。

在java里面除去基本数据类型的其它类型都是引用数据类型，自己定义的class类都是引用类型，可以像基本类型一样使用。

引用类型常见的有：String，StringBuffer，ArrayList，HashSet，HashMap等。
如果要对比两个对象是否相同，则需要使用equals()方法，但有一点需要注意：equals()方法的默认行为是比较引用。如果是你自己写的类，你应该为它重写equals()来比较对象的内容。大多数Java类库都实现了比较对象内容的equals()方法。

两者比较

2.类型检查

静态类型检查：编译时可在编译阶段发现错误，避免了将错误带入到运行阶段，可提高程序正确性/健壮性

关于“类型”的检查，不考虑值

①语法错误

②类名、函数名错误

③参数数目错误

④参数类型错误

⑤返回值类型错误

⑥其他情况，如变量可能没有初始化，在一些条件分支里声明的变量无法在分支外使用等等

动态类型检查：运行时

关于“值”的检查

①非法的参数值，如除零错误

②非法的返回值，如返回的具体值不能被转换成对应的类型

③越界

④空指针

3.可变对象、不可变对象、final关键字

不变对象：

如String,一旦被创建，始终指向同一个值/引用。如果编译器无法确定final变量不会改变，就提示错误，这也是静态类型检查的一部分。

不提供可改变其内部数据的值的操作。

可变对象：

如StringBuilder，拥有方法可以修改自己的值/引用。

提供了可改变其内部数据的值的操作。

比较：

①使用不可变类型，对其频繁修改会产生大量的临时拷贝(需要垃圾回收) ,使用可变类型会减少拷贝

②使用可变数据类型，可以提高性能，方便在多个模块之间共享数据。

③使用不可变数据类型，更容易达到安全要求。

final关键字：

①修饰类当用final去修饰一个类的时候，表示这个类不能被继承。

注意：

a. 被final修饰的类，final类中的成员变量可以根据自己的实际需要设计为fianl。

b. final类中的成员方法都会被隐式的指定为final方法。

②被final修饰的方法不能被重写。

注意：

a. 一个类的private方法会隐式的被指定为final方法。

b. 如果父类中有final修饰的方法，那么子类不能去重写。

③修饰局部变量

注意：

a. 必须要赋初始值，而且是只能初始化一次。

④修饰成员变量

注意：

a. 必须初始化值。

b. 被fianl修饰的成员变量赋值，有两种方式：1、直接赋值 2、全部在构造方法中赋初值。

c. 如果修饰的成员变量是基本类型，则表示这个变量的值不能改变。

d. 如果修饰的成员变量是一个引用类型，则是说这个引用的地址的值不能修改，但是这个引用所指向的对象里面的内容还是可以改变

4.防御式拷贝

返回可变类型对象时，为了防止该对象在别处被修改，创建一个新的对象，并复制原来的对象的各项属性，并返回这个复制后的新对象。

5.snapshot diagram

①基本类型的值

②对象类型的值

③不可变对象：双线椭圆

④可变对象

⑤不可变的引用：双线箭头

6.spec、precondition、postcondition

spec:

写在方法之前，只讨论输入输出的数据类型、功能和正确性、性能等，不讨论具体实现

应该包含前置条件、后置条件、和函数期望完成的行为。

@param 输入参数的含义

@return 返回参数的含义

@throws 抛出异常的含义

前置条件：

对客户端的约束，在使用方法时必须满足的条件

后置条件：

对开发者的约束，方法结束时必须满足的条件

前置条件满足，则后置条件必须满足。

前置条件不满足，则方法可做任何事情。

在涉及到可变类型等情况时，不要只依靠客户端和开发者的行为，要在规约里限定住。

7.行为等价性

定义：两个函数是否可相互替换?

①单纯的看实现代码，并不足以判定不同的implmentation是否是“行为等价的”

②需要根据spec判定行为等价性

③在编写代码之前先要确定spec如何形成、撰写。

8.spec强度

spec变强：更放松的前置条件，更严格的后置条件。

意味着实现更难，使用更轻松。

spec强的函数可以替换spec弱的。

9.ADT的四种基本操作

①构造器：t* -> T

创建对象，可能为静态函数或构造函数

②变值器：T+,t* -> void|t|T

通常返回void，但改变了内部的某些状态。

也可能返回非空类型。

③观察器：T+,t* -> t

返回内部某些状态

④生产器：T+,t* -> T

从旧对象中构建新对象。

10.表示独立性

内部实现如何变化，不影响客户端使用，也不影响规约。

如果没写前置、后置条件，就不能改变内部表示。

11.AF、RI

RI:

不变量，程序的某种“特性”，这种特性无论在什么时候都需要成立。

表示不变量，表示空间集合中的一个子集，包含了所有合法的表示值，或者说对于合法表示的描述。

和客户端无关，由ADT自身负责维持不变量。

如果出现了表示泄露，就不能保证不变量，也不能保证独立性。

ADT要保证不变性、不产生表示泄露。

checkRep()表示检查表示不变量的函数，要保证ADT的四个操作都要执行这个检查函数，并且在"null"的情况下不能通过检查。

R:表示空间，实际存入ADT中真实的值

A:抽象空间，使用ADT的客户端看到和使用的值。

AF:R→A的一个映射关系，是R中的值在A中的解释。

这个映射是满射，但未必是单射、双射，并且R中的一些值可能是非法的，在A中无对应。

同样的R、RI，但可能有不同的AF，即解释不同。

12.表示泄露

把R空间的东西泄露给了客户端

一旦泄露(将引用传递到客户端），内部表示可能被意外更改，无法保证RI

13.接口、抽象类、类

14.访问控制符:public,protected,default,private

①私有权限 private
private可以修饰数据成员，构造方法，方法成员，不能修饰类（此处指外部类，不考虑内部类）。被private修饰的成员，只能在定义它们的类中使用，在其他类中不能调用。
②默认权限 (default)
类，数据成员，构造方法，方法成员，都能够使用默认权限，即不写任何关键字。默认权限即同包权限，同包权限的元素只能在定义它们的类中，以及同包的类中被调用。
③受保护权限protected
protected可以修饰数据成员，构造方法，方法成员，不能修饰类（此处指外部类，不考虑内部类）。被protected修饰的成员，能在定义它们的类中，同包（最后一次重写该函数的位置）的类中被调用。如果有不同包的类想调用它们，那么这个类必须是定义它们的类的子孙类。
④公共权限 public
public可以修饰类，数据成员，构造方法，方法成员。被public修饰的成员，可以在任何一个类中被调用，不管同包或不同包，是权限最大的一个修饰符。

有关Java语言的修饰符，需要注意的问题有如下几个：
①并不是每个修饰符都可以修饰类（指外部类），只有public和default可以。
②所有修饰符都可以修饰数据成员，方法成员，构造方法。
③为了代码安全起见，修饰符不要尽量使用权限大的，而是适用即可。比如，数据成员，如果没有特殊需要，尽可能用private。
④修饰符修饰的是“被访问”的权限。

15.重写（override），重载（overload）

16.泛型

泛型的本质是为了参数化类型（在不创建新的类型的情况下，通过泛型指定的不同类型来控制形参具体限制的类型）。也就是说在泛型使用过程中，操作的数据类型被指定为一个参数，这种参数类型可以用在类、接口和方法中，分别被称为泛型类、泛型接口、泛型方法。

①泛型类

//此处T可以随便写为任意标识，常见的如T、E、K、V等形式的参数常用于表示泛型
//在实例化泛型类时，必须指定T的具体类型
public class Generic<T>{ 
    //key这个成员变量的类型为T,T的类型由外部指定  
    private T key;

    public Generic(T key) { //泛型构造方法形参key的类型也为T，T的类型由外部指定
        this.key = key;
    }

    public T getKey(){ //泛型方法getKey的返回值类型为T，T的类型由外部指定
        return key;
    }
}
//泛型的类型参数只能是类类型（包括自定义类），不能是简单类型
//传入的实参类型需与泛型的类型参数类型相同，即为Integer.
Generic<Integer> genericInteger = new Generic<Integer>(123456);

//传入的实参类型需与泛型的类型参数类型相同，即为String.
Generic<String> genericString = new Generic<String>("key_vlaue");
Log.d("泛型测试","key is " + genericInteger.getKey());
Log.d("泛型测试","key is " + genericString.getKey());

/*在使用泛型的时候如果传入泛型实参，则会根据传入的泛型实参做相应的限制，此时泛才会起到本应起到的限制作用。如果不传入泛型类型实参的话，在泛型类中使用泛型的方法或成员变量定义的类型可以为任何的类型。*/

Generic generic = new Generic("111111");
Generic generic1 = new Generic(4444);
Generic generic2 = new Generic(55.55);
Generic generic3 = new Generic(false);

Log.d("泛型测试","key is " + generic.getKey());
Log.d("泛型测试","key is " + generic1.getKey());
Log.d("泛型测试","key is " + generic2.getKey());
Log.d("泛型测试","key is " + generic3.getKey());

②泛型接口

//定义一个泛型接口
public interface Generator<T> {
    public T next();
}

/**
 * 未传入泛型实参时，与泛型类的定义相同，在声明类的时候，需将泛型的声明也一起加到类中
 * 即：class FruitGenerator<T> implements Generator<T>{
 * 如果不声明泛型，如：class FruitGenerator implements Generator<T>，编译器会报错："Unknown class"
 */
class FruitGenerator<T> implements Generator<T>{
    @Override
    public T next() {
        return null;
    }
}

/**
 * 传入泛型实参时：
 * 定义一个生产器实现这个接口,虽然我们只创建了一个泛型接口Generator<T>
 * 但是我们可以为T传入无数个实参，形成无数种类型的Generator接口。
 * 在实现类实现泛型接口时，如已将泛型类型传入实参类型，则所有使用泛型的地方都要替换成传入的实参类型
 * 即：Generator<T>，public T next();中的的T都要替换成传入的String类型。
 */
public class FruitGenerator implements Generator<String> {

    private String[] fruits = new String[]{"Apple", "Banana", "Pear"};

    @Override
    public String next() {
        Random rand = new Random();
        return fruits[rand.nextInt(3)];
    }
}

③泛型方法

/**
 * 泛型方法的基本介绍
 * @param tClass 传入的泛型实参
 * @return T 返回值为T类型
 * 说明：
 *     1）public 与 返回值中间<T>非常重要，可以理解为声明此方法为泛型方法。
 *     2）只有声明了<T>的方法才是泛型方法，泛型类中的使用了泛型的成员方法并不是泛型方法。
 *     3）<T>表明该方法将使用泛型类型T，此时才可以在方法中使用泛型类型T。
 *     4）与泛型类的定义一样，此处T可以随便写为任意标识，常见的如T、E、K、V等形式的参数常用于表示泛型。
 */
public <T> T genericMethod(Class<T> tClass)throws InstantiationException ,
  IllegalAccessException{
        T instance = tClass.newInstance();
        return instance;
}

public class StaticGenerator<T> {
    ....
    ....
    /**
     * 如果在类中定义使用泛型的静态方法，需要添加额外的泛型声明（将这个方法定义成泛型方法）
     * 即使静态方法要使用泛型类中已经声明过的泛型也不可以。
     * 如：public static void show(T t){..},此时编译器会提示错误信息：
          "StaticGenerator cannot be refrenced from static context"
     */
    public static <T> void show(T t){

    }
}

17.==,equals(),hashcode()

对于基本数据类型，直接比较值是否相等

对于非基本数据类型，如果未重写equals()，则==和equals()都是直接返回地址，hashcode()默认实现也是直接返回地址。

java内部的一些实现，如list里的contains，在判断相等的时候，使用的是equals()函数，而不是==

java内部的一些依靠哈希表实现的数据结构中，先用hashcode()缩小范围，再用equals()判断相等，所以重写equals()时必须重写hashcode()

Java 语言规范要求 equals 方法具有下面的特性：

1 ) 自反性：对于任何非空引用 x, x.equals(x)应该返回 true

2 ) 对称性: 对于任何引用 x 和 y, 当且仅当 y.equals(x) 返回 true, x.equals(y) 也应该返回 true。

3 ) 传递性：对于任何引用 x、 y 和 z, 如果 x.equals(y) 返 N true， y.equals(z) 返回 true,x.equals(z) 也应该返回 true。

4 ) 一致性：如果 x 和 y 引用的对象没有发生变化，反复调用 x.eqimIS(y) 应该返回同样的结果。

5 ) 对于任意非空引用 x, x.equals(null) 应该返回 false,

18.可变、不可变对象的等价性

可变对象：引用等价性、对象等价性

引用等价性就是只有内存地址相等才等价

对象等价性就是对象的各个属性相等才等价

比如默认的equals()就是引用等价性。

不可变对象：行为等价性，观察等价性

观察等价性：在不改变状态的前提下，调用观察函数所获得的结果一致。

行为等价性：调用任何方法都显示出一致的结果。大部分情况下是指“同一个对象”。

java中的集合类使用观察等价性，即比较大小、各个元素是否相等，而Stringbuilder比较的是地址，即行为等价性。

如果是观察等价性，那把一个可变对象改变了，他就很可能跟以前不相等了，比如hashset中把一个list改了，再调用contains可能就会有问题。

如果要弄一个观察等价性的判断，最好单独实现一个函数而不要用equals()