java核心课件2-第3章.ppt

第3章 集合框架 v熟悉java2之前的容器类的继承关系，熟练使 用其中的类和接口； v熟悉java集合框架，熟练使用其中的相关类 和接口； v熟练使用集合类的泛型用法。 v我们在解决问题时，通常需要选择一种数据 结构； v本章主要讲述Java技术是如何帮助你建立进 行重大编程时所需要的传统数据结构； v这就是“集合框架”，一个集合就是一组对象的 容器。 3.1 java2之前的容器类 v左图中两条线分别表示两种不同 的数据结构： v第1条线：Vector代表线性结构 ，特点是元素有序存储，支持下 标访问，元素在容器中可重复出 现； v第2条线：Dictionary代表映射结 构，存储的是“健/值对”，特点是 无序存储，不支持下标访问，通 过健快速映射到值，其中健是唯 一的，值可以不唯一，且所有键 值不能为null。 Vector Stack Dictionary Hashtable Properties 3.1.1 长度和容量的概念 v容量:能够存储元素个数的能力，通常会自动增加; v长度:实际存储的元素个数; 3.1.1 Enumeration接口 vEnumertation接口提供了一种抽象机制，用 于访问任意一个容器中的各个元素； v目前这个接口已经基本被Iterator接口替 代了。 3.2 集合框架概述 v从图中可以看出，整个集合框架是建立在两个接口之上，它 们是Collection和Map，一共包含四种类型的集合，它们是 List、Queue、Set、Map； vList代表线性结构，特点是元素有序存储，支持下标访问， 元素在容器中可重复出现； vQueue代表队列结构，特点是先进先出，不支持下标访问； vSet代表集合结构，特点是无序存储，不支持下标访问，元 素在集合中是唯一的； vMap代表映射结构，特点是，通过键/值对存储。 Iterable Collection QueueListSet MapIterator ListIterator 3.3 集合框架的迭代器 vJava每个Collection集合都提供了iterator()方法来返回一个 迭代器； v通过反复调用next方法，可以逐个访问集合中的各个元素； v如果到了集合尾部，next方法将抛出一个 NoSuchElementException异常； v由上图可以看出：应该将java迭代器看成是位于各个元素之 间的，当调用next方法时，迭代器便越过下一个元素，并返 回它刚刚越过的那个元素的引用； v当迭代器刚创建时，它位于第一个元素之前，并不指向任何 一个元素。 3.3.1 Iterator接口 返回元素 迭代器 3.3.2 ListIterator 接口 v它是Iterator接口的子接 口； v除了继承了其父接口的 正向遍历方法next外， 还提供了反向遍历方法 previous； v因此它是一个双向迭代 器； v还提供了add方法添加 元素。 vList a = new LinkedList( ); a.add(“Amy“); a.add(“Carl“); a.add(“Erica“); Iterator aIter = a.iterator(); ListIterator aLIter = a.listIterator(); 3.4 Collection接口 vCollection接口是集合框架的基础；声明了多 数集合类都有的核心方法； v因此应当熟悉这些方法； v见书或api文档。 3.5 List结构 v线性表结构； v重载了父接口的add等方法，增加了set、get等方法 ，以支持下标访问； vList中的元素可以重复出现。 ListListIteratorQueue AbstractList AbstractSequentialList CopyOnWriteArrayList ArrayListVector Stack LinkedList 3.5.3 Vector类 vVector又称“向量”，实现了一个动态数组的功能。 它的特点是： v底层以数组实现，支持下标运算，下标从0开始； v容易维护元素的顺序，是按添加的顺序进行维护的 ； v所有方法都是同步的，是线程安全的； v通常扩展容量的方式是倍增的； v与数组的区别：它的容量可变，数组的容量是定的 。 3.5.4 Stack类 vStack类是实现了标准的后进先出的栈，是Vector的子类； vVector可用的方法，Stack都可用，但实际应用中尽量不使用继承的方法 ； v下标从1开始，栈顶下标为1，栈底下标为size； vpush是压栈，pop是出栈。 栈 栈顶 栈 栈顶 数据 栈 栈顶 栈 栈顶 数据 入栈操作 出栈操作 ArrayList类 v其特点是： v底层是以数组实现的，所以它适合反复遍历 ，不适合作频繁的元素插入和删除操作； v可以动态的增减大小，当长度超过时，集合 自动增加原来容量的50%，删除对象时，集 合自动变小； v不是同步的。 3.5.8 LinkedList类 v与ArrayList不同的是：LinkedList是链表结构； v因此它的删除、插入方便； v底层是双向链表实现的，适合频繁的插入和删除； v在JDK5.0中，其实现了Queue接口。 链表 头部 节点 数据 后继 前驱 节点 数据 后继 前驱 3.6 比较器 3.6.1 Comparable接口 vComparable接口强行对实 现它的每个类的对象进行整 体排序； v此排序被称为该类的自然排 序，其方法被称为它的自然 比较方法； v实现此接口的对象列表可以 通过Arrays.sort, collections.sort等方法进行 自动排序，是它们的默认比 较器； v其方法： public int compareTo(T o); 3.6.2 Comparator接口 v此接口的方法强行对某些对 象collection进行整体排序 ； v可以将Comparator作为参 数传递给sort方法，从而允 许在排序顺序上实现精确控 制； v还可以使用Comparator来 控制TreeSet等数据结构的 顺序； v其方法： public int compare(T o1,To 2); 3.7 Queue结构 Queue ArrayBlockingQueue DelayQueue LikedBlockingQueue PriorityBlockingQueue SynckronousQueue PriorityQueue ConcurrentLinkedQueue BlockingQueueAbstractQueue 3.7.1 Queue接口 v如下图所示，队列通常以先进先出（FIFO）的方式 排列各个元素，不过优先级队列例外； v优先级队列根据提供的比较器或元素的自然顺序对 元素进行排序； v无论使用哪种排序方式，队列的头都是调用remove 和poll方法所移除的元素； vFIFO队列中，所有新元素都插入队尾。 a1 a2 a3 an 队尾队头 入列出列 3.8 Set结构 vSet结构的特点： 元素在集合中无序存储； 集合中不允许存在相同的元素。 Set SortedSetAbstractSet TreeSet HashSet CopyOnWriteArraySet EnumSet LinkedHashSet 3.8.4 EnumSet类 vEnumSet是与枚举类型一起使用的专用Set实 现； v由iterator方法返回的迭代器按枚举声明常量 的顺序遍历这些元素； v可以防止枚举中出现重复值。 3.8.5 HashSet类 vHashSet创建一个使用哈希表存储的集合； vHashSet的特点： 它是一种把查找时间看得很重要的Set； 集合中元素是无序存放的； 所有的值必须覆盖hashCode和equals方法 v关于hashCode和equals方法： 系统在判断是否加入相同对象时，会调用对象的 hashCode和equals方法来判断； 在Object类中它们返回的或比较的都是对象的内存 地址，不能反映它们是否是相同对象，因此都必须 覆盖； 好的hashCode方法所产生的值应该均匀分布。 TreeSet类 v实现SortedSet接口，可以实现对集合自 动排序，必须满足以下两点中的其一： 1、创建集合时不指定比较器时，集合中的对象 必须实现Comparable接口，按其指定的 方式排序； 2、创建集合时指定比较器Comparator， 则按指定的比较器的方式排序； v注意匿名内部类的使用。 3.9 Map结构 Map Map.Entry AbstractMap WeekHashMap IdentityHashMap EnumMap TreeMap ConcurrentHashMap HashMap LinkedHashMap SortedMap ConcurrentMap Dictionary Hashtable Properties 3.9.1 Map vMap（映射）是一种把键对象和值对象进行映射的 集合，它的每一个元素都包含一对键对象和值对象 ； v向Map集合中加入元素时，必须提供一对键对象和 值对象，从Map集合中检索元素时，只要给出键对 象，就会返回对应的值对象； vMap.Entry接口是Map的内部接口，它封装 了一个key/value，也就是说一个Map.Entry对象就