chapter13集合类PartI

1、Chater13 集合框架集合框架1 1、集合框架概述、集合框架概述2 2、CollectionCollection接口接口3 List3 List接口接口方法名方法名说说 明明boolean add(Object o)在列表的末尾顺序添加元素，起始索引位置从0开始void add(int index,Object o)在指定的索引位置添加元素。索引位置必须介于0和列表中元素个数之间int size()返回列表中的元素个数Object get(int index)返回指定索引位置处的元素。取出的元素是Object类型，使用前需要进行强制类型转换boolean contains(Object o

2、)判断列表中是否存在指定元素boolean remove(Object o)从列表中删除元素Objectremove(int index)从列表中删除指定位置元素，起始索引位置从0开始具体参看具体参看jdk文档文档3.1 ArrayList3.1 ArrayListArrayList list = new ArrayList(); / 创建创建ArrayList集合集合list.add(stu1); / 向集合中添加元素list.add(stu2);list.add(stu3);list.add(stu4);System.out.println(集合的长度： + list.size(); Sy

3、stem.out.println(第2个元素是： + list.get(1); 注意：（1）ArrayList特点：底层使用数组保存元素，增加删除指定位置的元素时，会导致创建新的数组，效率较低，因此不适合做大量的增删操作，但是查询速度较快。（2）用ArrayList时，尽量指定类型（或者泛型），避免安全隐患，如下：ArrayList list = new ArrayList; 3.2 LinkedList3.2 LinkedList针对ArrayList的优缺点，LinkedList如下：（1）LinkedList为双向循环链表机制，每个元素都通过引用的方式来记住它的前一个和后一个元素。插入（

4、删除）元素时，修改元素间的引用关系。因此LinkedList对增删操作有很高效率。（2）特有方法如下：方法名方法名说说 明明voidaddFirst(Object o)在列表的首部添加元素voidaddLast(Object o)在列表的末尾添加元素ObjectgetFirst()返回列表中的第一个元素ObjectgetLast()返回列表中的最后一个元素ObjectremoveFirst()删除并返回列表中的第一个元素ObjectremoveLast()删除并返回列表中的最后一个元素LinkedList link = new LinkedList; link.add(stu1);link.a

5、dd(stu2);link.add(stu3);link.add(stu4);/取出并打印该集合中的元素System.out.println(link.toString(); /向该集合中指定位置插入元素link.add(3, Student);/向该集合第一个位置插入元素link.addFirst(First); System.out.println(link);/取出该集合中第一个元素System.out.println(link.getFirst(); /移除该集合中指定位置的元素link.remove(3); /移除该集合中第一个元素link.removeFirst(); System

6、.out.println(link);3.3 Iterator3.3 Iterator接口接口Collection和Map接口主要用于存储元素，Iterator接口主要用于迭代访问（遍历）元素，因此称为迭代器。ArrayList list = new ArrayList(); list.add(data_1); list.add(data_2);list.add(data_3);list.add(data_4);Iterator it = list.iterator();/判断判断ArrayList集合中是否存在下一个元素集合中是否存在下一个元素while (it.hasNext() /取出取

7、出ArrayList集合中的元素集合中的元素 Object obj = it.next(); System.out.println(obj);注意：使用Iterator迭代访问元素时，如果调用集合容器对象的remove方法删除某个元素，会出现异常。如下：ArrayList list = new ArrayList(); list.add(Jack);list.add(Annie);list.add(Rose);list.add(Tom);Iterator it = list.iterator(); while (it.hasNext() Object obj = it.next(); if (

8、Annie.equals(obj) list.remove(obj); System.out.println(list);解决方法1：如果只是想删除某学生，则删除完之后直接break，不要再遍历ArrayList list = new ArrayList(); list.add(Jack);list.add(Annie);list.add(Rose);list.add(Tom);Iterator it = list.iterator(); while (it.hasNext() Object obj = it.next(); if (Annie.equals(obj) list.remove(

9、obj); break； System.out.println(list);解决方法2：删除后，仍然想要遍历，则需要使用迭代器的删除方法。即调用迭代器对象remove方法删除元素后导致的迭代次数变换，对于迭代器对象本身可以预知。ArrayList list = new ArrayList(); list.add(Jack);list.add(Annie);list.add(Rose);list.add(Tom);Iterator it = list.iterator(); while (it.hasNext() Object obj = it.next(); if (Annie.equals(

10、obj) it.remove(obj); System.out.println(list);3.4 ListIterator3.4 ListIterator接口接口Iterator接口：迭代方向是正向迭代，即从第一个到最后一个。ListIterator接口：实现反向迭代，从最后一个到第一个。方法：add、hasPrevious、previous、removeArrayList list = new ArrayList();list.add(data_1);list.add(data_2);list.add(data_3);System.out.println(list);/list.size作

11、为参数，说明当前的迭代指针位置，从哪往前遍历，不包括本索引/也可以用其他整数，比如本例中使用1，注意观察ListIterator it = list.listIterator(list.size();while (it.hasPrevious() Object obj = it.previous(); System.out.print(obj + ); 3.5 Vector3.5 Vector和和EnumerationEnumerationVector:用法与ArrayList完全相同，Vector是线程安全的，ArrayList是线程不安全的。Enumeration接口：JDK1.2前实现迭

12、代的接口，目前还在用，和Iterator相同方法：hasMoreElements、nextElementVector v = new Vector(); v.add(Jack); v.add(Rose);v.add(Tom);Iterator it = v.iterator();while (it.hasNext() Object o = it.next(); System.out.println(o);Vector v = new Vector(); v.add(Jack); v.add(Rose);v.add(Tom);Enumeration en = v.elements(); whil

13、e (en.hasMoreElements() Object obj = en.nextElement(); System.out.println(obj);4. Set4. Set接口接口Set接口的方法与Collection接口基本一致。与List接口不同：Set接口的元素无序，通过某种规则保证存入的元素不重复不重复。主要实现类：HashSet和TreeSet（1）HashSet主要通过哈希值来确定元素在集合中的存储位置，具有较好的存取和查找性能。（哈希值是通过哈希算法对对象的内存地址值进行计算得到的一个整数值，可以理解为一个数字标识。不同对象的哈希值是有可能相同的）（2）TreeSet则

14、是以二叉树的方式来存储元素，可以实现对集合中的元素进行排序。4.1 HashSet4.1 HashSetString str1 = new String(aa);String str2 = new String(aa);if (str1=str2) System.out.println(value is not equal);if (str1.hashCode()=str2.hashCode() System.out.println(hashcode is equal); HashSet set = new HashSet();set.add(str1);set.add(str2);set.a

15、dd(bb);set.add(cc);set.add(dd);Iterator iterator = set.iterator();while (iterator.hasNext() String temp = (String)iterator.next();System.out.println(temp);System.out.println(set);注意输出情况：注意输出情况：（1 1）和存入顺序不一致，）和存入顺序不一致，无序的无序的（2 2）没有重复的）没有重复的bbbb，元素，元素不重复不重复此外注意此外注意（1 1）基础数据类型变量和）基础数据类型变量和字符串变量，如果值相等，字

16、符串变量，如果值相等，则计算出来的哈希值相等。则计算出来的哈希值相等。（2 2）对象即使内部值相等，）对象即使内部值相等，但是哈希值也可能不相等但是哈希值也可能不相等（3 3）不同对象的哈希值可）不同对象的哈希值可能相同能相同4.1 HashSet4.1 HashSet通过add方法向HashSet存入元素调用存储对象的hashCode方法获得对象的哈希值根据对象的哈希值计算对象的存储位置该位置是否有对象存在舍弃该对象是将该对象存入集合调用eauals比较对象是否相等否是否算法过程算法过程参见案例参见案例1010和和11114.2 TreeSet4.2 TreeSet注意：注意：TreeSet

17、TreeSet内部使用的算法是平衡排序二叉树，使用的是中序遍历，内部使用的算法是平衡排序二叉树，使用的是中序遍历，即首先访问左子树，然后遍历根结点，最后遍历右子树1 1、二叉排序树、二叉排序树（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；（3）左、右子树也分别为二叉排序树；（4）没有键值相等的节点。2 2、平衡二叉树、平衡二叉树平衡二叉树又被称为AVL树，具有以下性质：（1）它是一棵空树或它的左右两个子树的高度差的绝对值不超过1（2）左右两个子树都是一棵平衡二叉树。4.2 TreeSet4.2 TreeSet例如数列13、8、17、17、1、11、15、25，使用平衡二叉树存储时，如下图，同时存储过程中，去掉重复元素。具体插入顺序过于复杂，此处略去。TreeSet ts = new TreeSet(); ts.add(Jack); ts.add(Helena);ts.add(Helena);ts.add(Eve);Iterator it = ts.iterator(); while(it.hasNext() System.out.println(i