Java程序设计基础课程JAVA集合类课件

1、Java集合类Java集合类collections framework概述所有抽象出来的数据结构和操作统称为collections framework框架。Java程序员不必考虑数据结构的算法细节，只需要定义具体应用的数据结构实体。数据结构上的方法也用不着程序员去写，用系统的方法就行了，系统的方法总比一般程序员编的要快所有这些framework都在java.util包中9/27/20222collections framework概述所有抽象出来的collections framework概述在Java 2的Collections框架中，主要包括两个接口及其扩展和实现类：Collection接

2、口和Map接口 Collection是集合接口Collections是集合类Collection接口:Set不允许重复List可以有重复元素9/27/20223collections framework概述在Java 2集合类说明 CollectionListLinkedListArrayListVectorStackSetMapHashtableHashMapWeakHashMap 9/27/20224集合类说明 CollectionListLinkeJava类库中具体的集合(部分)9/27/20225Java类库中具体的集合(部分)9/26/20225Collection接口Collect

3、ion API提供“集合”的功能Collection API包含下述接口Collection: 将一组对象以集合元素的形式组织到一起，在其子接口中分别实现不同的组织方式Set: Collection的子接口，不记录元素的保存顺序，且不允许有重复元素List: Collection的子接口，记录元素的保存顺序，且允许有重复元素9/27/20226Collection接口Collection API提供“集Collection接口定义了集合的基本行为,一个Collection的实现类的实例能够:存放一个元素增加/删除一个元素查找一个元素是否在此集合中计算此集合的元素数目Collection没有约束

4、元素的具体类型(是否为空也未规定),元素的顺序,元素是否可重复部分Collection是整齐的(ordered)(注意,整齐的并不是一定是一定要经过排序的,即不一定是sorted).这样的Collection的元素之间在逻辑上是一个接一个(one by one),即可以得到一个元素的下一个元素的引用.这些元素可以是排序的(sorted,元素的次序由自然顺序或者规定的顺序排列)也可以是未排序的(unsorted,元素顺序由插入的顺序决定) java.util.List接口继承Collection接口定义这一类Collection部分Collection要求无重复的元素,称之为Set,java.u

5、til.Set接口继承Collection来定义这一类Collection9/27/20227Collection接口定义了集合的基本行为,一个ColleCollection 层次结构Collection+add(element : Object) : boolean+remove(element : Object) : boolean+size() : int+isEmpty() : boolean+contains(element : Object) : boolean+iterator() : IteratorSetHashSetListArrayListVectorLinkedList

6、9/27/20228Collection 层次结构+aCollectionArrayList非常象Vector ,它实现了可变长的数组。而LinkedList 则有些不同，它是List的链表实现。LinkedList可以成为堆栈,队列或者双向链表.9/27/20229CollectionArrayList非常象Vector ,数组列表ArrayList在编程中常常会遇到需要动态操纵数组，比如在运行时增加和删除数组元素，而且有时在编译时又不想确定数组大小希望它可以动态伸缩，在java中解决这一问题的方法是使用java.util包中的ArrayList类 ArrayList是List接口的一个可变

7、长数组实现。 9/27/202210数组列表ArrayList在编程中常常会遇到需要动态操纵数组数组列表ArrayListpublic int size();/返回列表中的元素个数public Object get(int index);/返回指定位置的元素public void set(int index, Object obj);/设置指定位置元素public void add(Object obj);/在列表末尾增加元素public void add(int index, Object obj);/在列表指定位置插入元素public void clear();/删除列表中所有元素publ

8、ic void remove(int index);/删除列表中指定位置元素元素public void contains(Object obj);/判断列表中指定对象是否存在9/27/202211数组列表ArrayListpublic int size()ArrayList示例（ArrayListExample）public class ArrayListExample public static void main( String args ) ArrayList al = new ArrayList(); / Create a new ArrayListfor( int i=0; i10;

9、 i+ ) al.add( new Integer( i ) ); / Add Items to the array list for( int i=0; ial.size(); i+ ) System.out.println( i + = + al.get( i ) ); al.remove( 5 );al.set( 5, new Integer( 66 ) );for( Iterator i=al.iterator(); i.hasNext(); ) Integer integer = ( Integer )i.next(); System.out.println( integer );

10、9/27/202212ArrayList示例（ArrayListExample）pA List Exampleimport java.util.*public class ListExample public static void main(String args) List list = new ArrayList();list.add(one);list.add(second);list.add(3rd);list.add(new Integer(4);list.add(new Float(5.0F);list.add(second); / duplicate, is addedlist

11、.add(new Integer(4); / duplicate, is addedSystem.out.println(list);Output: one, second, 3rd, 4, 5.0, second, 49/27/202213A List Exampleimport java.utilVector和ArrayList区别要回答这个问题不能一概而论，有时候使用Vector比较好；有时是ArrayList，有时候这两个都不是最好的选择。你别指望能够获得一个简单肯定答案，因为这要看你用它们干什么。Vector类似于ArrayList.。所有从API的角度来看这两个类非常相似。但他们之

12、间也还是有一些主要的区别的。同步性(jdk 1.4)Vector是同步的。这个类中的一些方法保证了Vector中的对象是线程安全的。而ArrayList则是异步的，因此ArrayList中的对象并不是线程安全的。因为同步的要求会影响执行的效率，所以如果你不需要线程安全的集合那么使用ArrayList是一个很好的选择，这样可以避免由于同步带来的不必要的性能开销。数据增长从内部实现机制来讲ArrayList和Vector都是使用数组(Array)来控制集合中的对象。当你向这两种类型中增加元素的时候，如果元素的数目超出了内部数组目前的长度它们都需要扩展内部数组的长度，Vector缺省情况下自动增长原

13、来一倍的数组长度，ArrayList是原来的50%,所以最后你获得的这个集合所占的空间总是比你实际需要的要大。所以如果你要在集合中保存大量的数据那么使用Vector有一些优势，因为你可以通过设置集合的初始化大小来避免不必要的资源开销。9/27/202214Vector和ArrayList区别要回答这个问题不能一概而Vector和ArrayList区别使用模式在ArrayList和Vector中，从一个指定的位置（通过索引）查找数据或是在集合的末尾增加、移除一个元素所花费的时间是一样的，这个时间我们用O(1)表示。但是，如果在集合的其他位置增加或移除元素那么花费的时间会呈线形增长：O(n-i)，

14、其中n代表集合中元素的个数，i代表元素增加或移除元素的索引位置。为什么会这样呢？因为在进行上述操作的时候集合中第i和第i个元素之后的所有元素都要执行位移的操作。这一切意味着什么呢？这意味着，你只是查找特定位置的元素或只在集合的末端增加、移除元素，那么使用Vector或ArrayList都可以。如果是其他操作，你最好选择其他的集合操作类。比如，LinkedList集合类在增加或移除集合中任何位置的元素所花费的时间都是一样的?O(1)，但它在索引一个元素的使用缺比较慢O(i),其中i是索引的位置.使用ArrayList也很容易，因为你可以简单的使用索引来代替创建iterator对象的操作。Link

15、List也会为每个插入的元素创建对象，所有你要明白它也会带来额外的开销。9/27/202215Vector和ArrayList区别使用模式9/26/202Set 接口(例：SetTest)Set 接口继承 Collection 接口，而且它不允许集合中存在重复项，每个具体的 Set 实现类依赖添加的对象的 equals()方法来检查独一性。Set接口没有引入新方法，所以Set就是一个Collection，只不过其行为不同。不能包含重复值,两个元素是否重复的依据是a.equals(b).特例:因此最多只允许一个null存在不能按照索引访问,因为Set的储存顺序不是有序的Set的实现类往往有更快的

16、对象操作(增加删除)速度,如: ArrayList查找一个对象是否存在于List中,需要遍历,而HashSet只根据哈希算法进行快速的查找(HashSet元素的储存不是有序的, 9/27/202216Set 接口(例：SetTest)Set 接口继承 CollSet的实现类HashSet允许插入最多一个null值不保证元素的顺序与插入的顺序一致,也不能按索引访问.通过将插入的元素分成一束一束,达到更快的数据操作功能实现原理,是利用了一个HashMap实例,以每个元素为key如果储存元素的分布是均匀的,增删查的恒定,且比较高.加入Set中的元素应该重载Object.hashCode()和Obje

17、ct.equals()方法(所有与哈希表有关的类都应该重载)HashSet是线程不安全的. 如需要同步,用Collections. synchronizedSE(Setset)方法创建一个Set适用场合:需要储存大量的不可重复元素集合,频繁的增删操作,且不需要记录插入时顺序.9/27/202217Set的实现类HashSet允许插入最多一个null值9/2Set 接口(例：SetTest)HashSet h = new HashSet();h.add(1st);h.add(2nd);h.add(new Integer(3);h.add(new Double(4.0);h.add(2nd); /

18、 重复元素, 未被加入h.add(new Integer(3); / 重复元素, 未被加入9/27/202218Set 接口(例：SetTest)HashSet h = HashSetHashSet继承AbstractSet并且实现Set接口。它创建一个类集，该类集使用散列表进行存储。正像大多数读者很可能知道的那样，散列表通过使用称之为散列法的机制来存储信息。在散列（hashing）中，一个关键字的信息内容被用来确定唯一的一个值，称为散列码（hashcode）。而散列码被用来当做与关键字相连的数据的存储下标。关键字到其散列码的转换是自动执行的？你看不到散列码本身。你的程序代码也不能直接索引散列

19、表。散列法的优点在于即使对于大的集合，它允许一些基本操作如add（ ），contains（ ），remove（ ）和size（ ）方法的运行时间保持不变。9/27/202219HashSetHashSet继承AbstractSet并且实HashSetHashSet( )构造一个默认的散列集合HashSet(Collection c)用c中的元素初始化散列集合HashSet(int capacity)用capacity初始化散列集合的容量HashSet(int capacity, float fillRatio)第四种形式用它的参数初始化散列集合的容量和填充比（也称为加载容量）。填充比必须介于0

20、.0与1.0之间，它决定在散列集合向上调整大小之前，有多少能被充满。具体的说，就是当元素的个数大于散列集合容量乘以它的填充比时，散列集合被扩大。对于没有获得填充比的构造函数，默认使用0.75.9/27/202220HashSetHashSet( )构造一个默认的散列集合HashSet(例 )HashSet没有定义任何超过它的超类和接口提供的其他方法。重要的是，注意散列集合并没有确保其元素的顺序，因为散列法的处理通常不让自己参与创建排序集合。如果需要排序存储，另一种类集TreeSet将是一个更好的选择。9/27/202221HashSet(例 )HashSet没有定义任何超过它的超类A Set

21、Exampleimport java.util.*;public class SetExample public static void main(String args) Set set = new HashSet();set.add(one);set.add(second);set.add(3rd);set.add(new Integer(4);set.add(new Float(5.0F);set.add(second); / duplicate, not addedset.add(new Integer(4); / duplicate, not addedSystem.out.prin

22、tln(set);/Output:one, second, 5.0, 3rd, 4HashSet以哈希表形式存放,操作速度很快9/27/202222A Set Exampleimport java.util.Iterator接口Iterator接口定义了对Collection类型对象中所含元素的遍历等增强处理功能可以通过Collection接口中定义的iterator()方法获得一个对应的Iterator(实现类)对象Set (实现类)对象对应的Iterator仍然是无序的List(实现类)对象对应的ListIterator对象可以实现对所含元素的双向遍历: 使用next()方法和previo

23、us()方法9/27/202223Iterator接口Iterator接口定义了对CollecIterator接口层次Iterator+hasNext() : boolean+next() : object+remove() ListIterator+hasPrevious() : boolean+previous() : Object+add(element : Object)+set(element : Object) 9/27/202224Iterator接口层次+hasNIterator接口Iterator:提供对所有集合(Collection)进行遍历的接口对Collection提供

24、一个统一的遍历接口是原Collection的一个视图，故在进行遍历时对应Collection中元素的改变会影响Iterator。与旧版本遍历Enumeration的区别：Iterator可以在遍历时删除对应Collection中的元素Iterator有更好的方法名Enumeration已过时不同的Collection产生Iterator产生的效率是不同的，ArrayList的遍历应该使用索引List list = new ArrayList();Iterator elements = list.iterator();while(elements.hasNext() System.out.pri

25、ntln(elements.next();9/27/202225Iterator接口Iterator:提供对所有集合(ColIterator接口boolean hasNext( ) 如果存在更多的元素，则返回true，否则返回falseObject next( ) 返回下一个元素。如果没有下一个元素，则引发NoSuchElementException异常void remove( ) 删除当前元素，如果试图在调用next( )方法之后，调用remove( )方法，则引发IllegalStateException异常9/27/202226Iterator接口boolean hasNext( ) 9

26、Iterator接口hasPrevious（ ） 如果存在前一个元素，则返回true；否则返回falseint nextIndex（ ） 返回下一个元素的下标，如果不存在下一个元素，则返回列表的大小Object previous（ ） 返回前一个元素，如果前一个元素不存在，则引发一个NoSuchElementException异常int previousIndex（ ） 返回前一个元素的下标，如果前一个元素不存在，则返回-1void set(Object obj) 将obj赋给当前元素。这是上一次调用next( )方法或previous( )方法最后返回的元素void add(Object o

27、bj) 将obj插入列表中的一个元素之后，该元素在下一次调用next( )方法时，被返回9/27/202227Iterator接口hasPrevious（ ） 如果存在前Iterator next()对于a,b,c,d,e这样一个5个元素的序列，有6个插入位置，每次next()是由一个插入位置移动到下一个插入位置，而不是元素的位置本身9/27/202228Iterator next()对于a,b,c,d,e这样一个Iterator接口在通过迭代函数访问类集之前，必须得到一个迭代函数。每一个Collection类都提供一个iterator（ ）函数，该函数返回一个对类集头的迭代函数。通过使用这个

28、迭代函数对象，可以访问类集中的每一个元素，一次一个元素。通常，使用迭代函数循环通过类集的内容，步骤如下：9/27/202229Iterator接口在通过迭代函数访问类集之前，必须得到一个Iterator接口1. 通过调用类集的iterator( )方法获得对类集头的迭代函数。2. 建立一个调用hasNext( )方法的循环，只要hasNext( )返回true，就进行循环迭代。3. 在循环内部，通过调用next( )方法来得到每一个元素。对于执行List的类集，也可以通过调用ListIterator来获得迭代函数。正如上面解释的那样，列表迭代函数提供了前向或后向访问类集的能力，并可让你修改元素

29、。否则，ListIterator如同Iterator功能一样。9/27/202230Iterator接口1. 通过调用类集的iterator( Iterator接口import java.util.*;class HashSetTest public static void main(String args) HashSet hs = new HashSet();/ hs.add(one);/ hs.add(two);/ hs.add(three); / hs.add(one);hs.add(new Student1(1, zhangsan);hs.add(new Student1(2, li

30、si);hs.add(new Student1(3, wangwu);hs.add(new Student1(1, zhangsan);Iterator it = hs.iterator();while (it.hasNext() System.out.println(it.next();9/27/202231Iterator接口import java.util.*;9Iterator接口class Student1 int num;String name;Student1(int num, String name) this.num = num; = name;public

31、 int hashCode() return num * name.hashCode();public boolean equals(Object o) Student1 s = (Student1) o;return num = s.num & name.equals();public String toString() return num + : + name; 9/27/202232Iterator接口class Student1 9/26Iterator作为返回值class IterTest31 public Iterator tt() List aa = new Arr

32、ayList();aa.add(new Person(w1, 1);aa.add(new Person(w2, 1);aa.add(new Person(w3, 1);aa.add(new Person(w4, 1);aa.add(new Person(w5, 1);Iterator it = aa.iterator();System.out.println(-);System.out.println(aa);return it;public static void main(String argc) IterTest31 itt = new IterTest31();Iterator it

33、= itt.tt(); while(it.hasNext()Person p1 = (Person)it.next();System.out.println(p1); 9/27/202233Iterator作为返回值class IterTest31 多次调用对象xxx.iterator()获取的Iteratorclass IterTest41 public Iterator tt() List aa = new ArrayList();aa.add(new Person(w1, 1);aa.add(new Person(w2, 1);aa.add(new Person(w3, 1);aa.ad

34、d(new Person(w4, 1);aa.add(new Person(w5, 1);Iterator it = aa.iterator();while(it.hasNext()Person p1 = (Person)it.next();System.out.println(p1);if(p1.getName().equals(w3)System.out.println(-);Iterator it11 = aa.iterator();if (it11.hasNext()System.out.println(it11.next();System.out.println(-);System.

35、out.println(aa);return it;public static void main(String argc) IterTest41 itt = new IterTest41();Iterator it = itt.tt();9/27/202234多次调用对象xxx.iterator()获取的IteratoConcurrentModificationException异常获取叠代器后通过Connection接口的实现类增加删除数据通过叠代器自身增加删除数据9/27/202235ConcurrentModificationExceptio映射（map） 映射（map）是一个存储关键

36、字和值的关联或者说是关键字/值对的对象。给定一个关键字，可以得到它的值。关键字和值都是对象。关键字必须是唯一的。但值是可以被复制的。有些映射可以接收null关键字和null值。而有的则不行。Map是一个维护一组”键-值”映射的类(map keys to values)(这里的key,value全部都是引用类型)一个Map中key的值是唯一的,不重复 (如，不要用员工姓名作为key)一个Map中一个key只能对应一个value(可以为空),但一个value可以有多个key与之对应Map能让你通过key快速查找到相应的对象并获得它对应的value的引用(如存储员工资料并用员工ID作为key来查找某

37、一员工的信息)9/27/202236映射（map） 映射（map）是一个存储关键字和值的关联或者HashMapHashMap类使用散列表实现Map接口。这允许一些基本操作如get（ ）和put（ ）的运行时间保持恒定，即便对大型集合，也是这样的。HashMap( )构造一个默认的散列映射HashMap(Map m)用m的元素初始化散列映射HashMap(int capacity)将散列映射的容量初始化为capacityHashMap(int capacity, float fillRatio)用它的参数同时初始化散列映射的容量和填充比。容量和填充比的含义与前面介绍的HashSet中的容量和填充

38、比相同。9/27/202237HashMapHashMap类使用散列表实现Map接口。这允Map接口,HashMap 类Map接口是Dictionary类的替代品。HashMap是以哈希表的形式存储键值对，速度快。9/27/202238Map接口,HashMap 类Map接口是DictionarHashMap HashMap实现Map并扩展AbstractMap.它本身并没有增加任何新的方法。应该注意的是散列映射并不保证它的元素的顺序。因此，元素加入散列映射的顺序并不一定是它们被迭代函数读出的顺序。9/27/202239HashMap HashMap实现Map并扩展AbstracHashMap

39、 import java.util.*;class HashMapTest public static void printElements(Collection c) Iterator it = c.iterator();while (it.hasNext() System.out.println(it.next();public static void main(String args) HashMap hm = new HashMap();hm.put(one, zhangsan);hm.put(two, lisi);hm.put(three, wangwu);System.out.pr

40、intln(hm.get(one);System.out.println(hm.get(two);System.out.println(hm.get(three);Set keys = hm.keySet();System.out.println(Key:);printElements(keys);Collection values = hm.values();System.out.println(Value:);printElements(values);Set entry = hm.entrySet();/printElements(entry);Iterator it = entry.i

41、terator();while (it.hasNext() Map.Entry me = (Map.Entry) it.next();System.out.println(me.getKey() + : + me.getValue();9/27/202240HashMap import java.util.*;9/2HashMapHashMap类:实现Map接口及它的它的所有可选操作。允许空key和空value.类似Hashtable,但Hashtable是线程安全的，且不允许空key和空value.不保证元素的顺序基本元素操作（put and get）速度恒定。（前提是各“桶”内分布的元素是

42、均匀的）线程不安全9/27/202241HashMapHashMap类:9/26/202241 HashSet 和 HashMapHashMap可以看作三个视图：key的Set，value的Collection，Entry的Set。 这里HashSet就是其实就是HashMap的一个视图。HashSet内部就是使用Hashmap实现的，和Hashmap不同的是它不需要Key和Value两个值。往hashset中插入对象其实只不过是内部做了public boolean add(Object o) return map.put(o, PRESENT)=null; HashMap为散列映射,它是基于

43、hash table的一个实现,它可在常量时间内安插元素,或找出一组key-value pair.HashSet为散列集,它把查找时间看的很重要,其中所有元素必须要有hashCode()9/27/202242 HashSet 和 HashMapHashMap可以看作三Dictionary和Hashtable类Dictionary类提供了根据关键字查值的功能。Dictionary是个abstract的类，因此我们不直接使用它。直接使用的一般是Hashtable类。Hashtable继承了dictionary类，称为哈希表类。快速寻址等9/27/202243Dictionary和Hashtable

44、类DictionarHashtable类如果要取得并显示哈希表中所有记录值，应该用以下程序段Enumeration enum=table.elements() ;while(enum.hasMoreElements() )show(Found Elements(not key): +enum.nextElement() );其中的table.elements 取得的是所有哈希表中的对象如果要取得并显示哈希表中所有关键字的值，就应该这么做Enumeration enum1=table.keys() ;while(enum1.hasMoreElements() )show(Key is -+enu

45、m1.nextElement() );其中的table.keys 取得哈希表中所有关键字的值9/27/202244Hashtable类如果要取得并显示哈希表中所有记录值，应该Hashtable (注意不是HashTable)import java.util.*;class HashTableTest1 public Hashtable tt() try Hashtable mm = new Hashtable();mm.put(w1, new Person(w1, 11);mm.put(w2, new Person(w2, 11);mm.put(w3, new Person(w3, 11);m

46、m.put(w4, new Person(w4, 11);/* * mm.put(null,sdfds); mm.put(w3,null); Enumeration */return mm; catch (Exception e) e.printStackTrace();return null;public static void main(String argc) HashTableTest1 htt = new HashTableTest1();Hashtable mm = htt.tt();/ 可以采用Map的 keySet(),values(),entrySet()方法来访问Hasht

47、able/* * Set ss = mm.keySet(); Iterator ii = ss.iterator(); * while(ii.hasNext() System.out.println(ii.next(); */ 也可以用早期提供的Enumeration访问/elements()返回value的,keys()返回key的Enumeration , values()返回values的CollectionEnumeration bb = mm.elements();while (bb.hasMoreElements() System.out.println(-);Object o = bb.nextElement();System.out.println(o);if (o instanceof Person) Person p1 = (Person) o;System.out.println(name -: + p1.getName();System.out.println(age -: + p1.getAge();Enumeration kk = mm.keys();while(kk.hasMoreElements()Syste