《Lesson6集合类.ppt》由会员分享，可在线阅读，更多相关《Lesson6集合类.ppt（26页珍藏版）》请在三一办公上搜索。
1、Lesson6 集合类,主讲人：孙鑫,http:/www.sunxin.org,集合框架中的接口,所谓框架就是一个类库的集合。集合框架就是一个用来表示和操作集合的统一的架构，包含了实现集合的接口与类。,http:/www.sunxin.org,集合框架中的接口,Collection：集合层次中的根接口，JDK没有提供这个接口直接的实现类。Set：不能包含重复的元素。SortedSet是一个按照升序排列元素的Set。List：是一个有序的集合，可以包含重复的元素。提供了按索引访问的方式。Map：包含了key-value对。Map不能包含重复的key。SortedMap是一个按照升序排列key的M
2、ap。,http:/www.sunxin.org,集合框架中的实现类,SortedSet,Set,List,Map,HashSet,LinkedHashSet,TreeSet,ArrayList,LinkedList,SortedMap,HashMap,TreeMap,http:/www.sunxin.org,ArrayList,ArrayList：我们可以将其看作是能够自动增长容量的数组。利用ArrayList的toArray()返回一个数组。Arrays.asList()返回一个列表。迭代器(Iterator)给我们提供了一种通用的方式来访问集合中的元素。,http:/www.sunxin
3、.org,迭代器的工作原理,返回的元素,删除的元素,next(),remove(),next(),http:/www.sunxin.org,Collections类,排序：Collections.sort()（1）自然排寻(natural ordering)；（2）实现比较器(Comparator)接口。取最大和最小的元素：Collections.max()、Collections.min()。在已排序的List中搜索指定的元素：Collectons.binarySearch()。,http:/www.sunxin.org,LinkedList,LinkedList是采用双向循环链表实现的。利
4、用LinkedList实现栈(stack)、队列(queue)、双向队列(double-ended queue)。,http:/www.sunxin.org,数据结构,一般将数据结构分为两大类：线性数据结构和非线性数据结构。线性数据结构有线性表、栈、队列、串、数组和文件；非线性数据结构有树和图。,http:/www.sunxin.org,线性表,线性表的逻辑结构是n个数据元素的有限序列:(a1,a2,a3,an)n为线性表的长度(n0)，n=0的表称为空表。数据元素呈线性关系。必存在唯一的称为“第一个”的数据元素；必存在唯一的称为“最后一个”的数据元素；除第一个元素外，每个元素都有且只有一个前
5、驱元素；除最后一个元素外，每个元素都有且只有一个后继元素。所有数据元素在同一个线性表中必须是相同的数据类型。,http:/www.sunxin.org,线性表,线性表按其存储结构可分为顺序表和链表。用顺序存储结构存储的线性表称为顺序表；用链式存储结构存储的线性表称为链表。将线性表中的数据元素依次存放在某个存储区域中,所形成的表称为顺序表。一维数组就是用顺序方式存储的线性表。,http:/www.sunxin.org,链表,单向链表,data,next,data,next,data,nextnull,head节点,http:/www.sunxin.org,链表,data,next,data,ne
6、xt,data,nextnull,head节点,插入,data,next,data,next,data,next,data,nextnull,head节点,删除,http:/www.sunxin.org,链表,循环链表,data,next,data,next,data,next,head节点,http:/www.sunxin.org,链表,双向循环链表,data,next,data,next,data,next,head节点,previous,previous,previous,http:/www.sunxin.org,栈,栈(Stack)也是一种特殊的线性表，是一种后进先出(LIFO)的结构
7、。栈是限定仅在表尾进行插入和删除运算的线性表，表尾称为栈顶(top)，表头称为栈底(bottom)。栈的物理存储可以用顺序存储结构，也可以用链式存储结构。,a1,a2,an,栈底,栈顶,出栈,进栈,http:/www.sunxin.org,队列,队列(Queue)是限定所有的插入只能在表的一端进行，而所有的删除都在表的另一端进行的线性表。表中允许插入的一端称为队尾(Rear)，允许删除的一端称为队头(Front)。队列的操作是按先进先出(FIFO)的原则进行的。队列的物理存储可以用顺序存储结构，也可以用链式存储结构。,a1 a2 a3 an,队头,队尾,出队,入队,http:/www.sunx
8、in.org,ArrayList和LinkedList的比较,ArrayList底层采用数组完成，而LinkedList则是以一般的双向链表(double-linked list)完成，其内每个对象除了数据本身外，还有两个 引用，分别指向前一个元素和后一个元素。如果我们经常在List的开始处增加元素，或者在List中进行插入和删除操作，我们应该使用LinkedList，否则的话，使用ArrayList将更加快速。,http:/www.sunxin.org,HashSet,实现Set接口的hash table(哈希表)，依靠HashMap来实现的。我们应该为要存放到散列表的各个对象定义hashC
9、ode()和equals()。,http:/www.sunxin.org,散列表,散列表又称为哈希表。散列表算法的基本思想是：以结点的关键字为自变量，通过一定的函数关系（散列函数）计算出对应的函数值，以这个值作为该结点存储在散列表中的地址。当散列表中的元素存放太满，就必须进行再散列，将产生一个新的散列表，所有元素存放到新的散列表中，原先的散列表将被删除。在Java语言中，通过负载因子(load factor)来决定何时对散列表进行再散列。例如：如果负载因子是0.75，当散列表中已经有75%的位置已经放满，那么将进行再散列。负载因子越高(越接近1.0)，内存的使用效率越高，元素的寻找时间越长。负
10、载因子越低(越接近0.0)，元素的寻找时间越短，内存浪费越多。HashSet类的缺省负载因子是0.75。,http:/www.sunxin.org,TreeSet,TreeSet是依靠TreeMap来实现的。TreeSet是一个有序集合，TreeSet中元素将按照升序排列，缺省是按照自然顺序进行排列，意味着TreeSet中元素要实现Comparable接口。我们可以在构造TreeSet对象时，传递实现了Comparator接口的比较器对象。,http:/www.sunxin.org,HashSet和TreeSet的比较,HashSet是基于Hash算法实现的，其性能通常都优于TreeSet。我
11、们通常都应该使用HashSet，在我们需要排序的功能时，我们才使用TreeSet。,http:/www.sunxin.org,HashMap,HashMap对key进行散列。keySet()、values()、entrySet()。,http:/www.sunxin.org,TreeMap,TreeMap按照key进行排序。,http:/www.sunxin.org,HashMap和TreeMap的比较,和Set类似，HashMap的速度通常都比TreeMap快，只有在需要排序的功能的时候，才使用TreeMap。,http:/www.sunxin.org,Java1.0/1.1的集合类,Vector：用ArrayList代替Vector。Hashtable：用HashMap代替Hashtable。Satck：用LinkedList代替Stack。Properties,http:/www.sunxin.org,
