Java06数组与集合框架.ppt
数组与集合框架金杰目标数组的拷贝数组的排序、查找Java的集合框架List接口实现类ArrayList和LinkedListSet接口实现类HashSet和TreeSetMap接口实现类HashMap和TreeMap历史集合类的用法怎样保存你的对象?数组-简单的线性序列高效率 容量固定(动态数组)类型识别 类型相同能保存基本类型如果程序的对象数量有限，且寿命可知，那么这个程序是相当简单的。数组的长度改变注意：数组在创建之后，其长度就不能再改变。但可以把数组的引用指向一个新的数组。举例：intmyArray=newint6;myArray=newint10;注意：如果没有别的引用指向第一个数组，则在第一个数组中的数据将会全部丢失(被垃圾回收器给回收)。数组间的复制publicstaticvoidarraycopy(Objectsrc,intsrcPos,Objectdest,intdestPos,intlength)参数：参数：nsrc-源数组。nsrcPos-源数组中的起始位置。ndest-目标数组。ndestPos-目标数据中的起始位置。nlength-要复制的数组元素的数量。举例：intsource=1,2,3;intdest=5,6,7,8;System.arraycopy(source,1,dest,1,source.length-1);复制结果：dest:5,2,3,8数组的内存分配图基本数据类型一维数组内存分配栈内存堆内存num0088:44000088:4400123new int3产生的对象num20088:4406123new int3产生的对象0088:4406对象数组的内存分配堆内存ss0088:44000088:4400Student ss;ss=new Student3;new students3产生的对象nullnullnull栈内存对象数组的内存分配堆内存ss0088:4400Student ss;ss=new Student3;ss0=new Student(“lisi”,18);0088:4400new students3产生的对象nullnullstudent0标识的Student对象lisi180088:46600088:4660栈内存0088:4480ss2nullnull0088:46600088:4480数组的相关操作数组的排序：Arrays.sort()。对象数组的排序需要定义自然比较规则或实现比较器在已排序的数组中查找某个元素：Arrays.binarySearch()。注:在使用Arrays.binarySearch()搜索数组之前请确保数组已经过了排序.数组的缺陷一般来说，程序都是根据具体情况在不断地创建新的对象，而这些情况又只有在程序运行的时候才能确定。不到运行时你是不会知道你到底需要多少对象，甚至是什么类型的对象。所以你不能指望用命名的reference来持有每个对象：MyObjectmyReference;原因就在于，你不可能知道究竟需要多少这样的对象。数组的不足不能自动调整大小不能实现快速的添加和删除对象不能存放不同类型的对象不能实现key_value如何解决这个问题?集合框架集合是包含一组相关数据元素的对象，它提供了对其所包含的各种元素的操作。所谓框架就是一个类库的集合。集合框架就是一个用来表示和操作集合的统一的架构，包含了实现集合的接口与类。集合框架 接口接口是表示集合的抽象数据类型 算法算法是对实现接口的对象执行计算的方法 实现实现是接口的实际实现集合框架包含三个组件集合框架中的接口所谓框架就是一个类库的集合。集合框架就是一个用来表示和操作集合的统一的架构，包含了实现集合的接口与类。集合框架中的接口Collection：集合层次中的根接口，JDK没有提供这个接口直接的实现类。Set：不能包含重复的元素。SortedSet是一个按照升序排列元素的Set。List：是一个有序的集合，可以包含重复的元素。提供了按索引访问的方式。Map：包含了key-value对。Map不能包含重复的key。SortedMap是一个按照升序排列key的Map。集合框架中的实现类SortedSetSetListMapHashSet LinkedHashSet TreeSet ArrayList LinkedList SortedMapHashMap TreeMap ArrayListArrayList：我们可以将其看作是能够自动增长容量的数组。利用ArrayList的toArray()返回一个数组。Arrays.asList()返回一个列表。迭代器(Iterator)给我们提供了一种通用的方式来访问集合中的元素。迭代器的工作原理返回的元素删除的元素next()remove()next()TheIteratorinterfaceisshownbelow:publicinterfaceIteratornbooleanhasNext();nObjectnext();nvoidremove();/Optional可以认为迭代器是指向两个元素之间的位置.在调用remove()方法的时候,必须调用一次next()方法.remove()方法实际上是删除上一个返回的元素.算法Collections类排序：Collections.sort()（1）自然排序(natural ordering)；（2）实现比较器(Comparator)接口。(3)混排功能取最大和最小的元素：Collections.max()、Collections.min()。在已排序的List中搜索指定的元素：Collectons.binarySearch()。算法3-2class 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);LinkedListLinkedList是采用双向循环链表实现的。利用LinkedList实现栈(stack)、队列(queue)、双向队列(double-endedqueue)。链表单向链表datanextdatanextdatanextnullhead节点链表datanextdatanextdatanextnullhead节点插入插入datanextdatanextdatanextdatanextnullhead节点删除删除链表循环链表datanextdatanextdatanexthead节点链表双向循环链表datanextdatanextdatanexthead节点previouspreviousprevious用LinkedList实现队列队列(Queue)是限定所有的插入只能在表的一端进行，而所有的删除都在表的另一端进行的线性表。表中允许插入的一端称为队尾(Rear)，允许删除的一端称为队头(Front)。队列的操作是按先进先出(FIFO)的原则进行的。队列的物理存储可以用顺序存储结构，也可以用链式存储结构。a1 a2 a3 ana1 a2 a3 an队头队尾出队 入队用LinkedList实现栈栈(Stack)也是一种特殊的线性表，是一种后进先出(LIFO)的结构。栈是限定仅在表尾进行插入和删除运算的线性表，表尾称为栈顶(top)，表头称为栈底(bottom)。栈的物理存储可以用顺序存储结构，也可以用链式存储结构。a1a1a2a2anan栈底栈顶出栈进栈ArrayList和LinkedList的比较ArrayList底层采用数组完成，而LinkedList则是以一般的双向链表(double-linkedlist)完成，其内每个对象除了数据本身外，还有两个引用，分别指向前一个元素和后一个元素。如果我们经常在List的开始处增加元素，或者在List中进行插入和删除操作，我们应该使用LinkedList，否则的话，使用ArrayList将更加快速。Set扩展Collection接口不允许重复元素对 add()、equals()和 hashCode()方法添加了限制HashSet和TreeSet是Set的实现HashSet实现Set接口的hashtable(哈希表)，依靠HashMap来实现的。我们应该为要存放到散列表的各个对象定义hashCode()和equals()。HashSet散列表又称为哈希表。散列表算法的基本思想是：以结点的关键字为自变量，通过一定的函数关系（散列函数）计算出对应的函数值，以这个值作为该结点存储在散列表中的地址。当散列表中的元素存放太满，就必须进行再散列，将产生一个新的散列表，所有元素存放到新的散列表中，原先的散列表将被删除。在Java语言中，通过负载因子(load factor)来决定何时对散列表进行再散列。例如：如果负载因子是0.75，当散列表中已经有75%的位置已经放满，那么将进行再散列。负载因子越高(越接近1.0)，内存的使用效率越高，元素的寻找时间越长。负载因子越低(越接近0.0)，元素的寻找时间越短，内存浪费越多。TreeSetTreeSet是依靠TreeMap来实现的。TreeSet是一个有序集合，TreeSet中元素将按照升序排列，缺省是按照自然顺序进行排列，意味着TreeSet中元素要实现Comparable接口。我们可以在构造TreeSet对象时，传递实现了Comparator接口的比较器对象。SetSet(interface)加至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()HashMapHashMap对key进行散列。keySet()、values()、entrySet()。Map视图操作entrySet()返回Map中所包含映射的Set视图。Set中的每个元素都是一个Map.Entry对象，可以使用getKey()和getValue()方法（还有一个setValue()方法）访问后者的键元素和值元素keySet()返回Map中所包含键的Set视图。删除Set中的元素还将删除Map中相应的映射（键和值）values()返回map中所包含值的Collection视图。删除Collection中的元素还将删除Map中相应的映射（键和值）TreeMapTreeMap按照key进行排序。MapMap(interface)维护key-value的关联性，使你可以使用key来查找valueHashMap基于hashtable(哈希表)完成的一个实现品。可用它来取代Hashtable(Java2以前的一种container)。可在常量时间内插入元素，或找出一组key-valuepair。通过其构造函数，使用者可调整效能表现。因为它允许你设定capacity（容量）和loadfactor(负载因子)TreeMap当你检查其中的key或key-valuepairs时，会以排序形式出现（前后次序由Comparable或Comparator决定）。TreeMap的特色便是让你得以排序形式得到结果。TreeMap是唯一具有subMap()的一种Map，这个函数让你得以返回tree中的部分组成。HashMap和TreeMap的比较和Set类似，HashMap的速度通常都比TreeMap快，只有在需要排序的功能的时候，才使用TreeMap。Java1.0/1.1的集合类Vector：用ArrayList代替Vector。Hashtable：用HashMap代替Hashtable。Satck：用LinkedList代替Stack。PropertiesVector类实现可变长度的对象数组组件可以使用整型下标访问构造函数nVector()nVector(Collectionc)nVector(intcap)nVector(intcap,intinc)Properties用于存取*.Properties文件对中文支持有问题集合框架关系图(简)思考和作业Collection各子类之间怎样实现转换各子类之间怎样实现转换?Collection与与Map之间能否互相转换之间能否互相转换?证明往一个证明往一个List中是放对象值还是放引用中是放对象值还是放引用研究Arrays.asList()方法利用利用LinkedList构造自己的构造自己的Stack和和Queue类。类。自己实现洗牌算法自己实现洗牌算法,再通过再通过Collections类提供的算法实现洗牌类提供的算法实现洗牌.比比较两者的效率较两者的效率熟练掌握集合框架中各种的接口熟练掌握集合框架中各种的接口和类的用法和类的用法
