Java集合框架
- 集合接口与实现分离，用接口来持有具体实现，可以随时切换实现。
迭代器Iterator
- 通过hasNex()方法判断是否有下个元素，next()方法获取下个元素
- for each循环集合原理就是编译成调用集合iterator()方法，使用不同集合最合适的循环方法
- for each可以处理任何实现了Iterable接口的对象
- Collection接口实现了Iterable接口，因此，标准类库中任何集合都可以使用for each循环
- remove()方法与next()方法紧密相连，必选先next再remove
集合框架中的接口
- 两个基本接口：Collection Map
List
- List接口描述的是一个有序集合
- 集合中每个元素的位置都很重要
- 两种方式访问元素：
- 通过迭代器
- 通过get（n） 随机访问，只适合数组列表
- 实现了RandomAccess接口的可以用来快速访问
链表结构
- 链表结构是将每个元素存放在单独的链接中，每个链接存储着前一个和后一个元素地址，插入和删除很轻松，无法随机访问，链表都是双向的
LinkedList
- 一个链表可以关联多个迭代器。一个迭代器在遍历链表时，另外的迭代器如果添加或者删除元素改变了链表结构，当前迭代器会出现异常，如果只是set替换元素，不会异常
- 提供有一个加的随机访问get(n)方法，方法效率极低，千万不要在循环中调用，每次都要从第一个元素往后找（有一个优化就是n大于元素总数的一半，就从后往前找）
ListIterator
- 继承于Iterator
- LinkedList的listIterator()方法返回一个ListIterator
- 增加了add方法，链表用来添加元素，
- 增加了previous()、hasPrevious()方法来反向遍历链表
- 增加了set()方法来替换next或previous方法返回的上一个元素
数组列表
- 数组结构在内存中是一块连续的地址，插入和删除元素开销很大，位于变动元素之后的都要移动，可以通过下标随机访问
ArrayList
- 底层是数组，通过动态再分配数组对象实现了不限长度的数组结构
散列集
- 不在乎元素顺序
- 通过对象的hashCode来计算散列码，可以快速访问对象
- 自定义类要重写equals和hashCode方法，二者要保持一致
- 散列表用链表数组实现，每个列表称为桶，对象索引值为散列码与桶总数取余
- 由于桶的数量是有限的，要存储的对象是无限的，会产生散列冲突，也就是哈希冲突。一个桶中有多个对象时，用链表来存储，java8中桶满时会从链表变成平衡二叉树
- 装填因子（默认0.75），表中填满75%以上，会发生再散列，新表桶数为原来的两倍
HashSet
- 基于散列表的集，没有重复元素
树集
- TreeSet与散列集十分类似，不过树集是一个有序集合
- 插入对象必须实现了Comparable接口或者指定一个Comparator
- 树排序是用红黑树实现的