Java集合类.

Presentation on theme: "Java集合类."— Presentation transcript:

1 Java集合类

2 collections framework概述
所有抽象出来的数据结构和操作统称为collections framework框架。Java程序员不必考虑数据结构的算法细节，只需要定义具体应用的数据结构实体。数据结构上的方法也用不着程序员去写，用系统的方法就行了，系统的方法总比一般程序员编的要快 所有这些framework都在java.util包中 2018/12/29

3 collections framework概述
在Java 2的Collections框架中，主要包括两个接口及其扩展和实现类：Collection接口和Map接口 Collection是集合接口 Collections是集合类 Collection接口: Set—不允许重复 List—可以有重复元素 2018/12/29

4 集合类说明 Collection ├List │├LinkedList │├ArrayList │└Vector │　└Stack └Set Map ├Hashtable ├HashMap └WeakHashMap 2018/12/29

5 Java类库中具体的集合(部分) 2018/12/29

6 Collection接口 Collection API提供“集合”的功能 Collection API包含下述接口
Set: Collection的子接口，不记录元素的保存顺序，且不允许有重复元素 List: Collection的子接口，记录元素的保存顺序，且允许有重复元素 2018/12/29

7 Collection接口 定义了集合的基本行为,一个Collection的实现类的实例能够: 存放一个元素 增加/删除一个元素
查找一个元素是否在此集合中 计算此集合的元素数目 Collection没有约束元素的具体类型(是否为空也未规定),元素的顺序,元素是否可重复 部分Collection是整齐的(ordered)(注意,整齐的并不是一定是一定要经过排序的,即不一定是sorted).这样的Collection的元素之间在逻辑上是一个接一个(one by one),即可以得到一个元素的下一个元素的引用.这些元素可以是排序的(sorted,元素的次序由自然顺序或者规定的顺序排列)也可以是未排序的(unsorted,元素顺序由插入的顺序决定) java.util.List接口继承Collection接口定义这一类Collection 部分Collection要求无重复的元素,称之为Set,java.util.Set接口继承Collection来定义这一类Collection 2018/12/29

8 Collection 层次结构 Collection +add(element : Object) : boolean
<<interface>> Collection +add(element : Object) : boolean +remove(element : Object) : boolean +size() : int +isEmpty() : boolean +contains(element : Object) : boolean +iterator() : Iterator <<interface>> Set <<interface>> List HashSet ArrayList Vector LinkedList 2018/12/29

9 Collection ArrayList非常象Vector ,它实现了可变长的数组。而LinkedList 则有些不同，它是List的链表实现。 LinkedList可以成为堆栈,队列或者双向链表. 2018/12/29

10 数组列表ArrayList 在编程中常常会遇到需要动态操纵数组，比如在运行时增加和删除数组元素，而且有时在编译时又不想确定数组大小希望它可以动态伸缩，在java中解决这一问题的方法是使用java.util包中的ArrayList类 ArrayList是List接口的一个可变长数组实现。 C++通过模板技术可以指定集合的元素类型，而Java在1.5之前一直没有相对应的功能。一个集合可以放任何类型的对象，相应地从集合里面拿对象的时候我们也不得不对他们进行强制得类型转换。猛虎引入了泛型，它允许指定集合里元素的类型，这样你可以得到强类型在编译时刻进行类型检查的好处。 Collection<String> c = new ArrayList(); c.add(new Date()); 编译器会给出一个错误， add(java.lang.String) in java.util.Collection<java.lang.String> cannot be applied to (java.util.Date) 2018/12/29

11 数组列表ArrayList public 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();//删除列表中所有元素 public void remove(int index);//删除列表中指定位置元素元素 public void contains(Object obj);//判断列表中指定对象是否存在 2018/12/29

12 ArrayList示例（ArrayListExample）
public class ArrayListExample{ public static void main( String[] args ) { ArrayList al = new ArrayList(); // Create a new ArrayList for( int i=0; i<10; i++ ) { al.add( new Integer( i ) ); // Add Items to the array list } for( int i=0; i<al.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 ); 2018/12/29

13 A List Example import 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 added list.add(new Integer(4)); // duplicate, is added System.out.println(list); } Output: [one, second, 3rd, 4, 5.0, second, 4] 2018/12/29

14 Vector和ArrayList区别 要回答这个问题不能一概而论，有时候使用Vector比较好；有时是ArrayList，有时候这两个都不是
最好的选择。你别指望能够获得一个简单肯定答案，因为这要看你用它们干什么。Vector类似于ArrayList.。所有从API的角度来看这两个类非常相似。但他们之间也还是有一些主要的区别的。 同步性(jdk 1.4) Vector是同步的。这个类中的一些方法保证了Vector中的对象是线程安全的。而ArrayList则是异步的，因此ArrayList中的对象并不是线程安全的。因为同步的要求会影响执行的效率，所以如果你不需要线程安全的集合那么使用ArrayList是一个很好的选择，这样可以避免由于同步带来的不必要的性能开销。 数据增长 从内部实现机制来讲ArrayList和Vector都是使用数组(Array)来控制集合中的对象。当你向这两种类型中增加元素的时候，如果元素的数目超出了内部数组目前的长度它们都需要扩展内部数组的长度，Vector缺省情况下自动增长原来一倍的数组长度，ArrayList是原来的50%,所以最后你获得的这个集合所占的空间总是比你实际需要的要大。所以如果你要在集合中保存大量的数据那么使用Vector有一些优势，因为你可以通过设置集合的初始化大小来避免不必要的资源开销。 2018/12/29

15 Vector和ArrayList区别 使用模式
在ArrayList和Vector中，从一个指定的位置（通过索引）查找数据或是在集合的末尾增加、移除一个元素所花费的时间是一样的，这个时间我们用O(1)表示。但是，如果在集合的其他位置增加或移除元素那么花费的时间会呈线形增长：O(n-i)，其中n代表集合中元素的个数，i代表元素增加或移除元素的索引位置。为什么会这样呢？因为在进行上述操作的时候集合中第i和第i个元素之后的所有元素都要执行位移的操作。这一切意味着什么呢？ 这意味着，你只是查找特定位置的元素或只在集合的末端增加、移除元素，那么使用Vector或ArrayList都可以。如果是其他操作，你最好选择其他的集合操作类。比如，LinkedList集合类在增加或移除集合中任何位置的元素所花费的时间都是一样的?O(1)，但它在索引一个元素的使用缺比较慢－O(i),其中i是索引的位置.使用ArrayList也很容易，因为你可以简单的使用索引来代替创建iterator对象的操作。LinkList也会为每个插入的元素创建对象，所有你要明白它也会带来额外的开销。 2018/12/29

16 Set 接口(例：SetTest) Set 接口继承 Collection 接口，而且它不允许集合中存在重复项，每个具体的 Set 实现类依赖添加的对象的 equals()方法来检查独一性。Set接口没有引入新方法，所以Set就是一个Collection，只不过其行为不同。 不能包含重复值,两个元素是否重复的依据是a.equals(b). 特例:因此最多只允许一个null存在 不能按照索引访问,因为Set的储存顺序不是有序的 Set的实现类往往有更快的对象操作(增加删除)速度,如: ArrayList查找一个对象是否存在于List中,需要遍历,而HashSet只根据哈希算法进行快速的查找(HashSet元素的储存不是有序的, 如上面解释的那样，元素并没有按顺序进行存储 2018/12/29

17 Set的实现类HashSet 允许插入最多一个null值 不保证元素的顺序与插入的顺序一致,也不能按索引访问.
通过将插入的元素分成一束一束,达到更快的数据操作功能 实现原理,是利用了一个HashMap实例,以每个元素为key 如果储存元素的分布是均匀的,增删查的恒定,且比较高. 加入Set中的元素应该重载Object.hashCode()和Object.equals()方法(所有与哈希表有关的类都应该重载) HashSet是线程不安全的. 如需要同步,用Collections. synchronizedSE(Set set)方法创建一个Set 适用场合:需要储存大量的不可重复元素集合,频繁的增删操作,且不需要记录插入时顺序. 2018/12/29

18 Set 接口(例：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"); // 重复元素, 未被加入 h.add(new Integer(3)); // 重复元素, 未被加入 如上面解释的那样，元素并没有按顺序进行存储 2018/12/29

19 HashSet HashSet继承AbstractSet并且实现Set接口。它创建一个类集，该类集使用散列表进行存储。正像大多数读者很可能知道的那样，散列表通过使用称之为散列法的机制来存储信息。在散列（hashing）中，一个关键字的信息内容被用来确定唯一的一个值，称为散列码（hashcode）。而散列码被用来当做与关键字相连的数据的存储下标。关键字到其散列码的转换是自动执行的？？你看不到散列码本身。你的程序代码也不能直接索引散列表。散列法的优点在于即使对于大的集合，它允许一些基本操作如add（ ），contains（ ），remove（ ）和size（ ）方法的运行时间保持不变。 2018/12/29

20 HashSet HashSet( ) 构造一个默认的散列集合 HashSet(Collection c) 用c中的元素初始化散列集合
HashSet(int capacity) 用capacity初始化散列集合的容量　　 HashSet(int capacity, float fillRatio) 第四种形式用它的参数初始化散列集合的容量和填充比（也称为加载容量）。填充比必须介于0.0与1.0之间，它决定在散列集合向上调整大小之前，有多少能被充满。具体的说，就是当元素的个数大于散列集合容量乘以它的填充比时，散列集合被扩大。对于没有获得填充比的构造函数，默认使用0.75. 如上面解释的那样，元素并没有按顺序进行存储 2018/12/29

21 HashSet(例 ) HashSet没有定义任何超过它的超类和接口提供的其他方法。重要的是，注意散列集合并没有确保其元素的顺序，因为散列法的处理通常不让自己参与创建排序集合。如果需要排序存储，另一种类集TreeSet将是一个更好的选择。 如上面解释的那样，元素并没有按顺序进行存储 2018/12/29

22 A Set Example import 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 added set.add(new Integer(4)); // duplicate, not added System.out.println(set);}} //Output:[one, second, 5.0, 3rd, 4] HashSet以哈希表形式存放,操作速度很快 2018/12/29

23 Iterator接口 Iterator接口定义了对Collection类型对象中所含元素的遍历等增强处理功能
可以通过Collection接口中定义的iterator()方法获得一个对应的Iterator(实现类)对象 Set (实现类)对象对应的Iterator仍然是无序的 List(实现类)对象对应的ListIterator对象可以实现对所含元素的双向遍历: 使用next()方法和previous()方法 2018/12/29

24 Iterator接口层次 Iterator +hasNext() : boolean +next() : object +remove()
<<interface>> Iterator +hasNext() : boolean +next() : object +remove() <<interface>> ListIterator +hasPrevious() : boolean +previous() : Object +add(element : Object) +set(element : Object) 2018/12/29

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

26 Iterator接口 boolean hasNext( ) 如果存在更多的元素，则返回true，否则返回false
Object next( ) 返回下一个元素。如果没有下一个元素，则引发NoSuchElementException异常 void remove( ) 删除当前元素，如果试图在调用next( )方法之后，调用remove( )方法，则引发IllegalStateException异常 2018/12/29

27 Iterator接口 hasPrevious（ ） 如果存在前一个元素，则返回true；否则返回false
int nextIndex（ ） 返回下一个元素的下标，如果不存在下一个元素，则返回列表的大小 Object previous（ ） 返回前一个元素，如果前一个元素不存在，则引发一个NoSuchElementException异常 int previousIndex（ ） 返回前一个元素的下标，如果前一个元素不存在，则返回-1 void set(Object obj) 将obj赋给当前元素。这是上一次调用next( )方法或previous( )方法最后返回的元素 void add(Object obj) 将obj插入列表中的一个元素之后，该元素在下一次调用next( )方法时，被返回 2018/12/29

28 Iterator next() 对于a,b,c,d,e这样一个5个元素的序列，有6个插入位置，每次next()是由一个插入位置移动到下一个插入位置，而不是元素的位置本身 2018/12/29

29 Iterator接口 在通过迭代函数访问类集之前，必须得到一个迭代函数。每一个Collection类都提供一个iterator（ ）函数，该函数返回一个对类集头的迭代函数。通过使用这个迭代函数对象，可以访问类集中的每一个元素，一次一个元素。通常，使用迭代函数循环通过类集的内容，步骤如下： 2018/12/29

30 Iterator接口 1. 通过调用类集的iterator( )方法获得对类集头的迭代函数。
2. 建立一个调用hasNext( )方法的循环，只要hasNext( )返回true，就进行循环迭代。 3. 在循环内部，通过调用next( )方法来得到每一个元素。 对于执行List的类集，也可以通过调用ListIterator来获得迭代函数。正如上面解释的那样，列表迭代函数提供了前向或后向访问类集的能力，并可让你修改元素。否则，ListIterator如同Iterator功能一样。 2018/12/29

31 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(new Student1(1, "zhangsan")); hs.add(new Student1(2, "lisi")); hs.add(new Student1(3, "wangwu")); Iterator it = hs.iterator(); while (it.hasNext()) { System.out.println(it.next()); }}} 2018/12/29

32 Iterator接口 class Student1 { int num; String name;
this.num = num; this.name = name; } public int hashCode() { return num * name.hashCode(); } public boolean equals(Object o) { Student1 s = (Student1) o; return num == s.num && name.equals(s.name); } public String toString() { return num + ":" + name; }} 2018/12/29

33 Iterator作为返回值 class IterTest31 { 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.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 = itt.tt(); while(it.hasNext()){ Person p1 = (Person)it.next(); System.out.println(p1); } }} 2018/12/29

34 多次调用对象xxx.iterator()获取的Iterator
class 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.add(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(aa); return it; } public static void main(String argc[]) { IterTest41 itt = new IterTest41(); Iterator it = itt.tt(); }} 2018/12/29

35 ConcurrentModificationException异常
获取叠代器后 通过Connection接口的实现类增加删除数据 通过叠代器自身增加删除数据 2018/12/29

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

37 HashMap HashMap类使用散列表实现Map接口。这允许一些基本操作如get（ ）和put（ ）的运行时间保持恒定，即便对大型集合，也是这样的。 HashMap( )构造一个默认的散列映射 HashMap(Map m)用m的元素初始化散列映射 HashMap(int capacity)将散列映射的容量初始化为capacity HashMap(int capacity, float fillRatio)用它的参数同时初始化散列映射的容量和填充比。容量和填充比的含义与前面介绍的HashSet中的容量和填充比相同。 2018/12/29

38 Map接口,HashMap 类 Map接口是Dictionary类的替代品。 HashMap是以哈希表的形式存储键值对，速度快。
2018/12/29

39 HashMap HashMap实现Map并扩展AbstractMap.它本身并没有增加任何新的方法。应该注意的是散列映射并不保证它的元素的顺序。因此，元素加入散列映射的顺序并不一定是它们被迭代函数读出的顺序。 该程序的输出如下所示： 　　 　　Todd Hall: 　　 　　Ralph Smith: 　　 　　John Doe: 　　 　　Jane Baker: 　　 　　Tom Smith: 　　 　　John Doe’s current balance: 2018/12/29

40 HashMap 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.println(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.iterator(); Map.Entry me = (Map.Entry) it.next(); System.out.println(me.getKey() + ":" + me.getValue()); } 该程序的输出如下所示： 　　 　　Todd Hall: 　　 　　Ralph Smith: 　　 　　John Doe: 　　 　　Jane Baker: 　　 　　Tom Smith: 　　 　　John Doe’s current balance: 2018/12/29

41 HashMap HashMap类: 实现Map接口及它的它的所有可选操作。允许空key和空value.
类似Hashtable,但Hashtable是线程安全的，且不允许空key和空value. 不保证元素的顺序 基本元素操作（put and get）速度恒定。（前提是各“桶”内分布的元素是均匀的） 线程不安全 2018/12/29

42 HashSet 和 HashMap HashMap可以看作三个视图：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为散列映射,它是基于hash table的一个实现,它可在常量时间内安插元素,或找出一组key-value pair. HashSet为散列集,它把查找时间看的很重要,其中所有元素必须要有hashCode() 2018/12/29

43 Dictionary和Hashtable类
Dictionary是个abstract的类，因此我们不直接使用它。直接使用的一般是Hashtable类。 Hashtable继承了dictionary类，称为哈希表类。快速寻址等 2018/12/29

44 Hashtable类 如果要取得并显示哈希表中所有记录值，应该用以下程序段
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 ->"+enum1.nextElement() ); 其中的table.keys 取得哈希表中所有关键字的值 2018/12/29

45 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)); mm.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()方法来访问Hashtable * Set ss = mm.keySet(); Iterator ii = ss.iterator(); * while(ii.hasNext()){ System.out.println(ii.next()); } // 也可以用早期提供的Enumeration访问 //elements()返回value的,keys()返回key的Enumeration , values()返回values的Collection Enumeration 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()){ System.out.println(kk.nextElement()); 2018/12/29

46 Properities 类 哈希表里存的关键字－值对可以是各种类型。而propeities就相对简单多了。它只存放字符串对
propeities用setProperty和getProperty来处理值，此类的值只能是String 2018/12/29

47 System Properties import java.util.Properties;
import java.util.Enumeration; public class TestProperties { public static void main(String[] args){ Properties props = System.getProperties(); Enumeration prop_names = props.propertyNames(); while ( prop_names.hasMoreElements() ) String prop_name = (String) prop_names.nextElement(); String property = props.getProperty(prop_name); System.out.println("property ’" + prop_name+ "’ is ’" + property + "’"); }}} 2018/12/29

48 Hashtable 与 HashMap Hashtable不允许null值(key和value都不可以),HashMap允许null值(key和value都可以)。 Hashtable的方法是同步的，HashMap未经同步，所以在多线程场合要手动同步HashMap这个区别就像Vector和ArrayList一样。 HashTable有一个contains(Object value)，功能和containsValue(Object value)功能一样。Hashtable使用Enumeration，HashMap使用Iterator。 2018/12/29

49 掌握重点 Collection接口及其实现类 Java数组有什么特点 数组列表和数组有什么不同
HashMap ,HashSet , HashTable 2018/12/29

50 课后练习 为ArrayTest添加为Employee数组排序的方法（提示：为Employee 实现）；
按ArrayTest设计ArrayListTest类，使用数组列表代替数组 2018/12/29

51 线程安全的集合 1.用老的Vector/Hashtable类
Vector/Hashtable所提供的所有方法都是 synchronized的 2.使用ArrayList/HashMap和同步包装器 1. List synchArrayList = Collections.synchronizedList(new ArrayList()); 2. Map synchHashMap = Collections.synchronizedMap(new HashMap()) 3.用java5.0新加入的ConcurrentLinkedQueue、ConcurrentHashMap、CopyOnWriteArrayList 和 CopyOnWriteArraySet 2018/12/29