数据结构

排序

ArrayList没有sort()方法，ArrayList有add(index, element)方法向指定位置插入元素，但这样比直接用add()插入在后面要费时间
将String放入TreeSet中，这些String会自动按照字母顺序排序，TreeSet的成本，每当插入新项目时，它都要花时间找出适当的插入位置
toString()方法是定义在Object类中的，所以每个类都有继承到，toString()方法在System.out.println(anObject)时会被调用
Collection类有一个sort()方法
public static <T extends Comparable<? super T>> void sort(List<T> list)
T必须实现Comparable接口，并实现compareTo()方法才能使用被Collection排序
实现Comparable接口，并实现compareTo()方法只能有一种将自己与同类型比较的方法，如果需要有各种不同的比较方法，就需要一个独立的Comparator接口来帮助我们
sort()有两种形式：
单一参数的sort(List o)代表由List上元素所实现的compareTo()方法来决定排序，这个元素必须要实现Comparable接口
两个参数的sort(List o,Comparator c)代表不会调用List元素的compareTo()方法，而会使用Comparator的compare()方法，这意味着元素不需要实现Comparable接口

泛型

几乎所有泛型(generic)都与处理集合有关，泛型的主要目的是让你写出类型安全性的集合(type-safe collections)
List<Song> songList = new ArrayList<Song>();
如果一个类的的声明中用到了类型参数，则这个类被称为泛型类。在泛型类的内部任何地方，你都可以用这个E代替类型，在初始化泛型类时，这当中的所有E都会被替换为你所指定的类
public class ArrayList<E> extends AbstractList<E> ... {
public boolean add(E o)
如果一个方法中使用了未定义在类声明中的类型参数，则这个方法被称为泛型方法。如果类本身没有使用一个类型参数，你可以通过在方法的返回类型之前来指定这个类型参数给方法
public <T extends Animal> void takeThing(ArrayList<T> list)
public <T extends Animal> void takeThing(ArrayList<T> list)与public void takeThing(ArrayList<Animal> list)两者所代表的意义是不同的，前者为泛型方法，后者为普通方法。前者中 <T extends Animal> 是方法声明的一部分，表示任意一种Animal的ArrayList都是合法的，如ArrayList<Animal>、ArrayList<Cat>、ArrayList<Dog>都可以；后者中参数为ArrayList<Animal> list，表示只用ArrayList<Animal>是合法的，其他的ArrayList<Cat>、ArrayList<Dog>都是非法的
如果方法声明成取用ArrayList<Animal>，它只会取用ArrayList<Animal>参数，ArrayList<Dog>与ArrayList<Cat>都不行，如果是数组声明成void foo(Animal[] a){}，则foo(anAnimalArray);和foo(anDogArray);都可以调用
如果真的想创建能接受ArrayList<Animal>，ArrayList<Dog>与ArrayList<Cat>的方法，可以使用万用字符(wildcard)，使用带有<?>的声明时，编译器不会让你使用add()功能将任何东西加入到集合中
public void takeThing(ArrayList<? extends Animal> list)
public <T extends Animal> void takeThing(ArrayList<T> list)
两句语法不通，但功能相同，区别在于有时候声明一次效率会比较高：
public <T extends Animal> void takeThing(ArrayList<T> one, ArrayList<T> two)
public void takeThing(ArrayList<? extends Animal> one, ArrayList<? extends Animal> two)
在泛型的<>中extends代表extends或者implements，泛型的<>中extends可以让你对参数的类型加上限制的方法

集合

The Collection API.JPG

三种主要的接口：
List：是一种知道索引的集合，可以有多个元素指向相同的对象
Set：是一种不允许重复的集合，它知道某物是否已经存在于集合中，不会有多个元素指向相同的对象(被认为相等的两个对象也不行)
Map：是一种使用键值对的集合，两个key可以引用相同的对象，但key不能重复

HashSet：防止重复，通过hashCode可快速寻找相符元素
TreeSet：防止重复，元素以有序状态排列。TreeSet有无参的默认构造方法，使用元素对象的compareTo()来排序，还有带Comparator参数的构造方法，通过Comparator的compare()来排序

如果为两个对象相等，那么这两个对象必须符合两个条件：a.hashCode()与b.hashCode()相等；a.equals(b)返回true。如果两个对象有相同的hashCode()，他们也不一定相等,因为hashCode所使用的杂凑算法也许刚好会让多个对象返回相同的杂凑值。hashCode()的默认行为是对堆上的对象产生独特的值，equals()的默认行为是执行==的比较，也就是去测试两个引用是否是同一个对象。所以a.equals(b)返回true意味着a.hashCode()与b.hashCode()等值，但a.hashCode()与b.hashCode()等值并不意味着a.equals(b)返回true。因此如果equals()被复写过，则equals()也一定要被复写
HashSet首先会通过hashCode()来判断是否有重复元素，并判断对象加入的位置，如果hashCode()相同，还会接着使用equals()来判断。hashCode()是用来缩小寻找成本，但最后还是得用equals()来认定是否找到相同项目
引用相等：堆上同一对象的两个引用是相等的，要想知道两个引用是否引用相等可以用if(a==b)来判断
对象相等：通过复写类的hashCode()与equals()方法