【容器框架】Java容器框架综述
问：什么是容器？它与数组的区别是？
数组是保存一组对象的最有效的方式，但是数组具有固定大小，如果不知道对象的数量有多少个，那么应该使用容器。
问：Java容器类类库的基本概念？
- Collection。一个独立元素的序列，包括：List、Set和Queue。List必须按照插入的顺序保存元素，而Set不允许有重复的元素。Queue按照排队的规则来确定对象产生的顺序。
- Map，一组成对的“键值对”对象，允许你用键来查找值。
一、容器框架图
学习容器必须先大致了解其整体框架，对整体有一个把握，然后根据自己的需求去学习对应部分，下图展示了Java整个容器框架（没有包括并发，Java SE5新添加了Queue接口）：
说明：
- 容器接口：短虚线表示，有6个：Collection、List、Set、SortedSet、Map和SortedMap。
- 抽象类：长虚线表示，对容器接口的部分实现，可扩展为自定义集合类，这样就不需要直接实现所有接口方法。
- 实现类：实现表示，对接口的具体实现。
- Collection接口允许一组重复的对象。
- Set接口继承（extends）Collection，集合元素不允许重复。
- List接口继承Collection，允许重复，并维护元素的插入顺序。
- Map接口存储键-值对象，与Collection接口没什么关系。
- Produces代表使用了某个接口
【泛化关系】：带空心三角形的实线，表示继承关系，箭头指向父类。
【实现关系】：带空心三角形的虚线，表示类与接口的实现关系，箭头指向接口。
二、接口说明
2.1 Collection接口
上图中，除了Map接口，其他容器都是Collection的子类，对于Collection而言，都会包含添加、删除、判断、清空、大小等基本操作。
2.2 Map接口
Map是一个键值对的容器，特别适用于以下情形，一个主属性作为key，一个副属性（如：姓名，性别作为一个key-value对）。添加元素时，若存在相同的键，会用新值代替旧值。
说明：
- Map接口有一个内部接口Entry，对容器中的元素定义了一组通用的操作，维护这键值对，可以对键值进行相应的操作，通过Map接口的EntrySet()可以返回容器对象的视图集，用来进行遍历等操作。
- Map接口也包含都会包含添加、删除、判断、清空、大小等基本操作。
2.3 Iterator接口 & LinkedIterator接口
迭代器具体可以看设计模式的迭代器模式的笔记，这里只做个简单介绍。
作用：
- 提供一种方法顺序访问一个聚合对象中的各个元素，而又不暴露该对象的内部表示。
- 它使得对于聚合对象的遍历行为和聚合对象分离，即迭代器模式为遍历不同的聚合结构提供统一的接口，如：hasNext()等。
Collection和Map的具体实现类中，内部都有一个Iterator接口的具体实现类，作为iterator()函数的返回，以用来遍历集合。
- Iterator接口在遍历容器元素时，只能往后遍历，通常无序容器实现的都是这个接口，如：HashSet、HashMap；
- 对于有序容器，实现的一般是LinkedIterator接口，实现这个接口的容器可以双向遍历，即可以通过next()和previous()来访问下一个和前一个元素，如：ArrayList。
2.4 Comparable && Comparator
具体可以看 “Comparable && Comparator浅析” 的笔记。
三、工具类Collections 和 Arrays
Collections 和 Arrays都是工具类提供了很多操作容器的方法，具体使用可以查看API。
四、equals 和 HashCode()
4.1 == 和 equals() 的区别？
- 对于基本数据类型（如int，long等），“==”就是判断两个变量是否相等，而equals()是用于对象的，不能用于基本数据类型。
- 对于对象引用变量，由于该变量存储的是对象在内存中的路径，即内存地址，所以“==”进行比较时，即使对象的值相等，但是它们的内存地址不同，“==”的结果为false。
- equals()方法时Object类的方法，它内部默认就是使用“==”比较，这个方法设计的目的就是比较两个对象是否相等（怎么才算相等，可以重写该方法）。
- 需要注意的是：一些基本数据类型的包装类，如Integer、String类等，JDK已经重写了其equals()方法，是比较其值判断两个对象是否相等。
4.2 理解散列和hashCode()？
- Object类的hashCode()方法生成散列码，它默认是使用对象的地址来计算散列码的；
- Object类的equals()方法默认只是比较对象的地址。
注意：如果键没有覆盖hashCode()和equals()，那么使用散列的数据结构（如HashSet、HashMap、LinkedHashSet或LinkedHashMap）就无法正确处理该键。
像基本数据类型的包装类被用于HashMap的键，能用得很好，这是因为它具有键的全部性质，即已经覆盖了hashCode()和equals()。
为什么Map要用散列？
- 如果不使用散列，假设只用ArrayList保存Key和Value，那么查找键就只能通过简单的线性查询，而线性查询是最慢的查询方式。
- 存储一组元素最快的数据结构就是数组，散列就用数组来表示键的信息，这样通过键的信息就可以快速查找到key-value对了。
- 注意：数组本身并不保存键本身，而是通过键对象生成一个数字，将其作为数组的下标，这个数字就是散列码。
Object规范规定：
- 在应用程序执行期间，只要equals()方法比较操作所用到的信息没有被修改，那么对这个对象调用多次hashCode()方法必须返回相同的整数。
- 如果两个对象根据equals()方法比较是相等的，那么这两个对象调用hashCode()方法产生的整数结果一定要相等。
- 如果两个对象根据equals()方法比较是不相等的，两个对象产生的散列码不一定不同，相同的情况被称为“冲突”。
总结：
- 相同的对象有着相同的散列码；
- equals()相等，则hashCode()一定相等；
- hashCode()相等，equals()不一定相等。
一个好的hashCode()函数倾向于为不同对象产生不相等的散列码，从而提升性能（介绍冲突，加快查询速度），不好的hashCode()会使散列表退化成链表，性能急剧下降。