集合（上）
传统的容器(数组)在进行增、删等破坏性操作时，需要移动元素，可能导致性能问题；同时添加、删除等算法和具体业务耦合在一起，增加了程序开发的复杂度。java集合框架提供了一套性能优良、使用方便的接口和类，它们位于java.util包中。
1 collection 接口
collection是java集合框架(collection-frame)中的顶层接口。collection接口是一个容器，容器中只能存储引用数据类型，建议存同一类型的引用类型，方便后续遍历等操作。容器中的元素可以是有序的、可重复的，称为list接口；也可能是无序的、唯一的，称为set接口。
1.1 集合常用方法
1 public static void main(string[] args) {
2
3 /**
4 * 增:add/addall
5 * 删:clear/remove/removeall/retainall
6 * 改:
7 * 查:contains/containsall/isempty/size
8 */
9
10 collection c1 = new arraylist();
11
12 // 追加
13 c1.add("apple"); // object object = new string("apple");
14 // c1.add(1); // object object = new integer(1);
15 c1.add("banana");
16 system.out.println(c1);
17
18 // 追加一个集合
19 collection c2 = new arraylist();
20 c2.add("java");
21 c2.add("c++");
22 c1.addall(c2);
23 system.out.println(c1);
24
25 system.out.println(c1.contains("apple"));
26 c2.add("js");
27 system.out.println(c1.containsall(c2));
28 // c1.clear();
29 system.out.println(c1.isempty());
30 // 返回集合元素的个数
31 system.out.println(c1.size());
32
33 system.out.println(c1.equals(c2));
34 }
1.3 集合的遍历
iterable 是一个可遍历的接口，集合接口继承于它，集合支持快速遍历。
for (object item : c1) {
system.out.println(item.tostring());
}
快速遍历的本质：
collection 继承 iterable 接口，表示集合支持快速遍历。iterable 接口定义了一个方法iterator()用于获取集合的迭代器，是一个 iterator 接口类型，iterator()内部返回一个实现类实现类 iterator 接口。这个实现类一定具有 hasnext 和 next 方法用于判断是否有下一个元素和获取下一个元素。快速遍历就是基于迭代器工作的。
1 public static void main(string[] args) {
2
3 collection c1 = new arraylist();
4 c1.add("apple");
5 c1.add("banana");
6 c1.add("coco");
7
8 // 快速遍历
9 // for-each
10 // object 表示元素类型
11 // item表示迭代变量
12 // c1表示集合
13 for (object item : c1) {
14 system.out.println(item.tostring());
15 }
16
17 // 方法1
18 iterator it = c1.iterator();
19 while(it.hasnext()) {
20 object item = it.next();
21 system.out.println(item.tostring());
22 }
23
24 // 方法2（推荐）
25 for(iterator it2=c1.iterator();it2.hasnext();) {
26 object item = it2.next();
27 system.out.println(item.tostring());
28 }
29 }
查看源码可以看到 next 方法的实现
1 @suppresswarnings("unchecked")
2 public e next() {
3 checkforcomodification();
4 int i = cursor;
5 if (i >= size)
6 throw new nosuchelementexception();
7 object[] elementdata = arraylist.this.elementdata;
8 if (i >= elementdata.length)
9 throw new concurrentmodificationexception();
10 cursor = i + 1;
11 return (e) elementdata[lastret = i];
12 }
iterator 方法会返回一个私有类 itr 的实例，该类中定义了一个 cursor 变量，初始值为 0，表示当前”光标“指向的元素索引；定义了一个 lastret 变量初始值为 -1，表示上一个遍历过的元素的索引。每次使用 next 后，将 cursor 赋给 i ，光标 cursor 后移一位，同时返回当前 i 指向的元素，并将 i 赋给 lastret。
iterator 是线程不安全的，不支持在遍历的同时修改集合元素。每次使用 next 的时候，会首先使用 checkforcomodification 方法，查看源码可知，该方法会判断两个变量 modcount、expectedmodcount 是否相等，如果不相等就抛出“同时修改异常”。modcount 是 arraylist 的父类 abstractlist 中定义的一个变量，arraylist 的 add 方法每次执行时，会先调用 ensurecapacityinternal 方法判断容量并自动扩容，该方法又调用了 ensureexplicitcapacity 方法，该方法每次调用时 modcount 会自加一次。而expectedmocount 是在创建 itr 实例时生成的，将arraylist 的 modcount 赋给它，所以当在遍历过程中修改集合元素，next 方法调用时就会抛出“同时修改异常”。
1 private void ensurecapacityinternal(int mincapacity) {
2 ensureexplicitcapacity(calculatecapacity(elementdata, mincapacity));
3 }
4
5 private void ensureexplicitcapacity(int mincapacity) {
6 modcount++;
7
8 // overflow-conscious code
9 if (mincapacity - elementdata.length > 0)
10 grow(mincapacity);
11 }
2 list 接口
list 继承 collection。list 接口中的元素时有序的、可重复的。list接口中的元素通过索引(index)来确定元素的顺序。可以对列表中每个元素的插入位置进行精确地控制。用户可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。
2.1 list 常用方法
1 public static void main(string[] args) {
2
3 /**
4 * 增:add/addall/add(index,el)/addall(index,collection)
5 * 删:clear/remove/removeall/remove(index)
6 * 改:set(index,el)
7 * 查:get(index)/indexof/lastindexof()
8 * 其他:contains/containsall/isempty/size
9 */
10 list list1 = new arraylist();
11 // 添加元素
12 list1.add("apple");
13 list1.add("banana");
14 // 在指定位置添加元素
15 list1.add(0, "coco");
16
17 system.out.println(list1);
18
19 list list2 = new arraylist();
20 list2.add("java");
21 list2.add("c++");
22
23 list1.addall(1, list2);
24 system.out.println(list1);
25
26 // 删除
27 list1.remove(0);
28 system.out.println(list1);
29
30 // 修改
31 list1.set(0, "javax");
32 system.out.println(list1);
33
34 // 查
35 system.out.println(list1.get(0));
36 list1.add("apple");
37 list1.add("apple");
38 system.out.println(list1);
39 system.out.println(list1.indexof("apple"));
40 system.out.println(list1.lastindexof("apple"));
41 }
2.2 list 接口的遍历
listiterator 继承于iterator，在iterator的基础上提供了以正向遍历集合，也可以以逆序遍历集合。hasnext/next 以正向遍历；hasprevious/previous 以逆序遍历。
1 public static void main(string[] args) {
2
3 list list1 = new arraylist();
4 list1.add("apple");
5 list1.add("banana");
6 list1.add("coco");
7
8 // 【1】快速遍历
9 system.out.println("--for each--");
10 for (object item : list1) {
11 system.out.println(item.tostring());
12 }
13
14 // 【2】普通for
15 system.out.println("--for--");
16 for(int i=0;i<list1.size();i++) {
17 system.out.println(list1.get(i));
18 }
19
20 // 【3】集合迭代器
21 system.out.println("--iterator--");
22 iterator it = list1.iterator();
23 while(it.hasnext()) {
24 system.out.println(it.next());
25 }
26
27 system.out.println("--list iterator--");
28 // 正向遍历
29 listiterator it2 = list1.listiterator();
30 while(it2.hasnext()) {
31 system.out.println(it2.next());
32 }
33
34 // 逆序遍历
35 while(it2.hasprevious()) {
36 system.out.println(it2.previous());
37 }
38
39 system.out.println("--list iterator with index--");
40 listiterator it3 = list1.listiterator(1);
41 while(it3.hasnext()) {
42 system.out.println(it3.next());
43 }
44 }
3 arraylist/vector
arraylist 是list接口的实现类，底层数据结构是数组，实现大小可变的数组。arraylist 线程不安全，从 jdk1.2 开始使用。arraylist 底层数据结构是数组，默认数组大小是10,如果添加的元素个数超过默认容量，arraylist会自动拓容，拓容原则:newcapacity = oldcapacity + oldcapacity / 2；如果未来确定序列的元素不在增加，通过调用trimtosize()调制容量至合适的空间。arraylist作为list接口的实现类，常用方法和遍历方法参考list接口。
vector 是list接口的实现类，底层数据结构也是数组，也是大小可变的数组。vector是线程安全的，从 jdk1.0 开始使用。vector底层数据结构是数组，默认数组大小是10,如果添加的元素个数超过默认容量，vector会自动拓容，拓容原则:newcapacity = oldcapacity +capacityincrement(增长因子);如果未来确定序列的元素不在增加，通过调用trimtosize()调制容量至合适的空间。
注意:vector 在实现list接口的同时，同添加了自身特有的方法xxxelement,未来使用时为了程序的可拓展性，一定要按照接口来操作vector。
4 linkedlist
linkedlist是list接口的实现类，底层数据结构是链表。lineklist常用方法和遍历方法参照list接口。linkedlist 线程不安全。
除了实现list接口， 还实现了栈接口（后进先出 lifo），通过 push 和 pop 方法实现栈的操作。
1 public static void main(string[] args) {
2 linkedlist list = new linkedlist();
3 list.push("apple");
4 list.push("banana");
5 list.push("coco");
6
7
8 system.out.println(list.pop()); //coco
9 system.out.println(list.pop()); //banana
10 system.out.println(list.pop());
11
12 // java.util.nosuchelementexception
13 system.out.println(list.pop());
14 }
也实现了队列接口（先进先出 fifo），提供两套方法实现。
add/remove/element() 可能会出现nosuchelementexception异常
1 public static void main(string[] args) {
2
3 linkedlist queue = new linkedlist();
4 // 入队
5 /**
6 * 队列头 队列尾
7 *<----- <-----
8 * [apple, banana, coco]
9 */
10 queue.add("apple");
11 queue.add("banana");
12 queue.add("coco");
13 system.out.println(queue);
14
15 // 出队
16 system.out.println(queue.remove()); //返回队列头元素，并从队列中移除
17 system.out.println(queue.remove());
18 system.out.println(queue.remove());
19 system.out.println(queue);
20
21 // java.util.nosuchelementexception
22 system.out.println(queue.remove());
23
24
25 // 获取表头元素
26 system.out.println(queue.element());
27 }
offer/poll/peek 可能会返回特殊值(null)
1 public static void main(string[] args) {
2
3 linkedlist queue = new linkedlist();
4 // 入队
5 /**
6 * 队列头 队列尾
7 *<----- <-----
8 * [apple, banana, coco]
9 */
10 queue.offer("apple");
11 queue.offer("banana");
12 queue.offer("coco");
13
14 // 出队列
15 //system.out.println(queue.poll());
16 //system.out.println(queue.poll());
17 //system.out.println(queue.poll());
18 system.out.println(queue);
19
20 //system.out.println(queue.poll());//输出 null
21
22 // 获取表头元素
23 system.out.println(queue.peek());
24
25 }
同时也继承了双向队列接口，两头可进可出，一样提供两套方法，一个会抛异常，一个会返回 null。
用法如上面代码类似。
5 listiterator
正如上文讲遍历时所说的，iterator 不支持遍历的过程中修改集合元素，而 listiterator 正好弥补了这个缺陷，arraylist 对象可以使用 listiterator 方法获得一个 listiterator 的实例。listiterator允许程序员按任一方向遍历列表、迭代期间修改列表，并获得迭代器在列表中的当前位置。
1 public static void main(string[] args) {
2 arraylist list = new arraylist();
3 list.add("apple");
4 list.add("banana");
5 list.add("coco");
6
7 listiterator it = list.listiterator();
8 while(it.hasnext()) {
9 string item = (string) it.next();
10 if(item.equals("banana")) {
11 it.add("test");
12 //在当前光标（cursor）位置插入一个元素，这个 add 方法是属于listiterator 的
13 // next 方法调用后，光标 cursor 会后移
14 }
15 }
16
17 system.out.println(list); //[apple, banana, test, coco]
18 }
6 泛型（generic）
6.1 概念
泛型允许开发者在强类型程序设计语言（java）编写代码时定义一些可变部分，这些部分在使用前必须作出指明。泛型就是将类型参数化。
- arraylist<e> list表示声明了一个列表list，列表的元素是e类型
- arraylist<string> list = new arraylist<string>()；声明了一个列表list，列表的元素只能是string类型。
6.2 泛型的擦除
泛型在编译器起作用，运行时jvm察觉不到泛型的存在。泛型在运行时已经被擦除了。
1 public static void main(string[] args) {
2 arraylist<string> list = new arraylist<string>();
3 list.add("apple");
4 system.out.println(list instanceof arraylist); //true
5 system.out.println(list instanceof arraylist<string>);
6 //cannot perform instanceof check against parameterized type arraylist<string>.
7 // use the form arraylist<?> instead since further generic type information will
8 //be erased at runtime
9 }
6.3 泛型的应用
泛型类
当一个类中属性的数据类型不确定时，具体是什么类型由使用者来确定时，使用泛型。泛型类的形式：
1 public class 类名<t> {
2
3 }
定义一个泛型类：
1 class fanclass<t> {
2 private t t;
3
4 public t gett() {
5 return t;
6 }
7
8 public void sett(t t) {
9 this.t = t;
10 }
11
12 public fanclass(t t) {
13 super();
14 this.t = t;
15 }
16
17 public fanclass() {
18 super();
19 }
20 }
21 public class test01 {
22 public static void main(string[] args) {
23 fanclass<string> fan = new fanclass<string>();
24 fan.sett("apple");
25
26 fanclass<integer> fan2 = new fanclass<integer>();
27 fan2.sett(1);
28 }
29 }
泛型方法
当一个方法的参数类型不确定时，具体是什么类型由使用者来确定，可以考虑使用泛型方法，泛型方法在调用时确定(指明)类型。形式：
1 public <t> void xxx(t a) {
2 system.out.println(a);
3 }
举例：
1 class student {
2 public <t> void showinfo(t a) {
3 system.out.println(a);
4 }
5 }
6 public class test {
7 public static void main(string[] args) {
8 student stu = new student();
9 stu.showinfo(1);
10 stu.showinfo("apple");
11 stu.showinfo(1.0f); //传入的参数是什么类型，t 就是什么类型
12 }
13 }
推荐阅读