Java06数组与集合框架.ppt

数组与集合框架 金杰 目标 数组的拷贝 数组的排序、查找 Java的集合框架 List接口实现类ArrayList和LinkedList Set接口实现类HashSet和TreeSet Map接口实现类HashMap和TreeMap 历史集合类的用法 怎样保存你的对象? 数组-简单的线性序列 高效率 容量固定(动态数组) 类型识别 类型相同 能保存基本类型 如果程序的对象数量有限，且寿命可知，那么 这个程序是相当简单的。 数组的长度改变 注意：数组在创建之后，其长度就不能再改变。 但可以把数组的引用指向一个新的数组。 举例： int myArray=new int6; myArray=new int10; 注意：如果没有别的引用指向第一个数组，则在第一个数组中的 数据将会全部丢失(被垃圾回收器给回收)。 数组间的复制 public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length) 参数： n src - 源数组。 n srcPos - 源数组中的起始位置。 n dest - 目标数组。 n destPos - 目标数据中的起始位置。 n length - 要复制的数组元素的数量。 举例： int source = 1,2,3; int dest =5,6,7,8; System.arraycopy(source, 1, dest, 1,source.length-1); 复制结果： dest:5,2,3,8 数组的内存分配图 基本数据类型一维数组内存分配 栈内存 堆内存 num 0088:4400 0088:4400 1 2 3 new int3产 生的对象 num2 0088:4406 1 2 3 new int3产 生的对象 0088:4406 对象数组的内存分配 堆内存 ss0088:4400 0088:4400 Student ss; ss=new Student3; new students3 产生的对象 null null null 栈内存 对象数组的内存分配 堆内存 ss 0088:4400 Student ss; ss=new Student3; ss0=new Student(“lisi”,18); 0088:4400 new students3 产生的对象 null null student0 标识的 Student对象 lisi 18 0088:4660 0088:4660 栈内存 0088:4480 ss2 null null 0088:4660 0088:4480 数组的相关操作 数组的排序：Arrays.sort()。 对象数组的排序需要定义自然比较规则或实现 比较器 在已排序的数组中查找某个元素： Arrays.binarySearch()。 注:在使用Arrays.binarySearch()搜索数组之前 请确保数组已经过了排序. 数组的缺陷 一般来说，程序都是根据具体情况在不断地创建新的对象，而这些 情况又只有在程序运行的时候才能确定。不到运行时你是不会知道 你到底需要多少对象，甚至是什么类型的对象。所以你不能指望用 命名的reference 来持有每个对象：MyObject myReference; 原因就在于，你不可能知道究竟需要多少这样的对象。 数组的不足 不能自动调整大小 不能实现快速的添加和删除对象 不能存放不同类型的对象 不能实现key_value 如何解决这个问题? 集合框架 集合是包含一组相关数据元素的对象，它提供 了对其所包含的各种元素的操作。 所谓框架就是一个类库的集合。集合框架就是 一个用来表示和操作集合的统一的架构，包含 了实现集合的接口与类。 集合框架 接口 是表示集合的 抽象数据类型 算法 是对实现接口的对 象执行计算的方法 实现 是接口的实际实现 集合框架包含三个组件 集合框架中的接口 所谓框架就是一个类库的集合。集合框架就是一个用来表示和操作集合的统 一的架构，包含了实现集合的接口与类。 集合框架中的接口 Collection：集合层次中的根接口，JDK没有 提供这个接口直接的实现类。 Set：不能包含重复的元素。SortedSet是一个 按照升序排列元素的Set。 List：是一个有序的集合，可以包含重复的元 素。提供了按索引访问的方式。 Map：包含了key-value对。Map不能包含重复 的key。SortedMap是一个按照升序排列key的 Map。 集合框架中的实现类 SortedSet Set List Map HashSet LinkedHashSet TreeSet ArrayList LinkedList SortedMap HashMap TreeMap ArrayList ArrayList：我们可以将其看作是能够自动增长 容量的数组。 利用ArrayList的toArray()返回一个数组。 Arrays.asList()返回一个列表。 迭代器(Iterator) 给我们提供了一种通用的方式 来访问集合中的元素。 迭代器的工作原理 返回的元素删除的元素 next() remove() next() The Iterator interface is shown below: public interface Iterator n boolean hasNext(); n Object next(); n void remove(); / Optional 可以认为迭代器是指向两个元素之间的位置. 在调用remove()方法的时候, 必须调用一次next()方法. remove()方法实际上是删除上一个返回的元素. 算法Collections类 排序：Collections.sort() （1）自然排序(natural ordering )； （2）实现比较器(Comparator)接口。 (3) 混排功能 取最大和最小的元素：Collections.max()、 Collections.min()。 在已排序的List中搜索指定的元素： Collectons.binarySearch()。 算法 3-2 class AlgorithmExample public static void main(String args) LinkedList link = new LinkedList(); link.add(new Integer(10); link.add(new Integer(35); link.add(new Integer(23); link.add(new Integer(54); link.add(new Integer(36); Comparator cmp = Collections.reverseOrder(); Collections.sort(link, cmp); Iterator it = link.iterator(); System.out.println(“逆序排序的列表为： “); while (it.hasNext() System.out.println(it.next(); System.out.println(“给定列表中的最大值为：“+Collections.max(link); System.out.println(“给定列表中的最小值为：“+Collections.min(link); LinkedList LinkedList是采用双向循环链表实现的。 利用LinkedList实现栈(stack)、队列(queue)、 双向队列(double-ended queue )。 链表 单向链表 datanextdatanextdatanextnull head节点 链表 datanextdatanextdatanextnull head节点 插入 datanext datanextdatanextdatanextnull head节点 删除 链表 循环链表 datanextdatanextdatanext head节点 链表 双向循环链表 datanext datanextdatanext head节点 previous previousprevious 用LinkedList实现队列 队列(Queue)是限定所有的插入只能在表的一端进行，而所有的删 除都在表的另一端进行的线性表。 表中允许插入的一端称为队尾(Rear)，允许删除的一端称为队头 (Front)。 队列的操作是按先进先出(FIFO)的原则进行的。 队列的物理存储可以用顺序存储结构，也可以用链式存储结构。 a1 a2 a3 ana1 a2 a3 an 队头队尾 出队 入队 用LinkedList实现栈 栈(Stack)也是一种特殊的线性表， 是一种后进先出(LIFO)的结构。 栈是限定仅在表尾进行插入和删除 运算的线性表，表尾称为栈顶(top) ，表头称为栈底(bottom)。 栈的物理存储可以用顺序存储结构 ，也可以用链式存储结构。 a1a1 a2a2 anan 栈底 栈顶 出栈进栈 ArrayList和LinkedList的比较 ArrayList底层采用数组完成，而LinkedList则 是以一般的双向链表(double-linked list)完成， 其内每个对象除了数据本身外，还有两个 引 用，分别指向前一个元素和后一个元素。 如果我们经常在List的开始处增加元素，或者 在List中进行插入和删除操作，我们应该使用 LinkedList，否则的话，使用ArrayList将更加 快速。 Set 扩展Collection接口 不允许重复元素 对 add()、equals() 和 hashCode() 方法添加了限 制 HashSet和TreeSet是Set的实现 HashSet 实现Set接口的hash table(哈希表)，依靠 HashMap来实现的。 我们应该为要存放到散列表的各个对象定义 hashCode()和equals()。 HashSet 散列表又称为哈希表。散列表算法的基本思想是： 以结点的关键字为自变量，通过一定的函数关系（散 列函数）计算出对应的函数值，以这个值作为该结点 存储在散列表中的地址。 当散列表中的元素存放太满，就必须进行再散列，将 产生一个新的散列表，所有元素存放到新的散列表中 ，原先的散列表将被删除。在Java语言中，通过负载 因子(load factor)来决定何时对散列表进行再散列 。例如：如果负载因子是0.75，当散列表中已经有 75%的位置已经放满，那么将进行再散列。 负载因子越高(越接近1.0)，内存的使用效率越高， 元素的寻找时间越长。负载因子越低(越接近0.0)， 元素的寻找时间越短，内存浪费越多。 TreeSet TreeSet是依靠TreeMap来实现的。 TreeSet是一个有序集合，TreeSet中元素将按照升序 排列，缺省是按照自然顺序进行排列，意味着 TreeSet中元素要实现Comparable接口。 我们可以在构造TreeSet对象时，传递实现了 Comparator接口的比较器对象。 Set Set (interfac e) 加至Set内的每个元素都必须独一无二，不与其 它元素重复；Set不允许持有重复元素，每个元 素都必须定义equals()以判断所谓的独一性， Set具有和Collection一样的interface。Set interface并不保证以任何和特定次序来维护其 元素 HashSet 一种把查找时间看得很重要的Sets。所有与元 素都必须定义HashCode() TreeSet 底层结构为tree的一种有序(ordered)Set。这 么一来你便可以自Set中萃取出一个带次序性的 序列（ordered squence） HashSet和TreeSet的比较 HashSet是基于Hash算法实现的，其性能通常都优于 TreeSet。我们通常都应该使用HashSet，在我们需要 排序的功能时，我们才使用TreeSet。 Map 将键映射至值的对象 n 每个键最多都只能映射至一个值 重要方法 n 基本操作 put()、get()、remove()、containsKey()、 containsValue()、size() 和 isEmpty() n 批操作 putAll() 和 clear() n 集合视图 keySet()、values() 和 entrySet() HashMap HashMap对key进行散列。 keySet()、values()、entrySet()。 Map视图操作 entrySet() 返回 Map 中所包含映射的 Set 视图。 Set 中的每个元素都 是一个 Map.Entry 对象，可以使用 getKey() 和 getValue() 方法（ 还有一个 setValue() 方法）访问后者的键元素和值元素 keySet() 返回 Map 中所包含键的 Set 视图。 删除 Set 中的元素还将 删除 Map 中相应的映射（键和值） values() 返回 map 中所包含值的 Collection 视图。 删除 Collection 中的元素还将删除 Map 中相应的映射（键和值） TreeMap TreeMap按照key进行排序。 Map Map (interface) 维护 key-value的关联性，使你可以使用key来查找value HashMap 基于hash table(哈希表)完成的一个实现 品。可用它来取 代Hashtable(Java2以前的一种container)。可在常量时间 内插入元素，或找出一组key-value pair。 通过其构造函数，使用者可调整效能表现。因为它允许 你设定capacity（容量）和load factor(负载 因子) TreeMap 当你检查 其中的key或key-value pairs时，会以排序形式 出现（前后次序由Comparable或Comparator