|
我们都知道当想要保存一组基本类型数据时数组是最有效的保存方式也是推荐使用这种方式的但是数组是固有大小的当运行时才知道大小的程序这种方式使用就受限制了这就是Java容器类产生的原因Java集合类有几个特点首先这种容器是高性能的对基本数据集合（动态数组链接表树和散列表）的实现是高效率的第二容器类允许不同类型的类集合以相同的方式和高度互操作方式工作第三容器类是容易扩展或修改的容器类的常用的基本类型有ListSet和Map这些对象类型也称为集合类但是在Java中使用了Collection这个名字来指代该类库的一个特殊子集所以业界使用了范围更广泛的容器来称呼 Collection是一个接口它位于集合框架层次结构的顶层继承自Iterable接口说明是可以用Iterator迭代器来访问该集合中的元素的又有ListSet和Queue接口继承Collection接口直接实现该接口的是一个叫AbstractCollection的抽象类该抽象类以最大限度地减少了实现此接口所需的工作 List继承自Collection接口表示有序的可包括重复元素的列表同时拥有Collection内的方法外还添加了大量的方法使得可以在List的中间插入和删除元素实现该接口的基本类有ArrayList和LinkedList ArrayList擅长于对元素的随机访问但是在插入和删除元素时效率较慢其实看看ArrayList类实现的源代码就知道ArrayList是以线性表的数据结构形式存取数据的初始化的表大小为下面就有几个经常用到的核心方法add（E e）在当前表的末尾插入元素如果在前面表不满的情况下也是很高效的直接插入到末尾但是如果在当前表已经满的情况下就要重新生成一个比当前表大小更大的新表新表的大小是当前表大小的倍加比如当前表长度为的新表的大小就为还需要把当前表元素复制到新表中去然后把当前表引用指向新表最后把数值插入到表末尾所以这种操作是非常低效的 add（int indexE element）在指定索引位置插入元素检查表大小和重新追加表大小和上面的add（E e）方式是一样的最后是要把index以后的元素都是要依次往后移一个大小然后把元素插入到index位置上去涉及到表的复制和表内元素的移动所以效率也是比add（E e）方法还要低 remove（int index）在指定索引位置删除元素就是把index位置后的所有元素都往前移一个大小也是涉及到表内元素的移动效率也是很低的 remove（Object o）删除指定的元素也就需要查找出该元素在表中出现第一次的位置查找是用到顺序一个一个进行匹配的方法找出后就把该元素后面的所有元素往前移一个大小该方法涉及到顺序查找和表内元素移动比remove（int index）方法更低效 set（int indexE element）替换表中索引为index的元素值返回被替换的值直接用下标索引访问元素所以效率非常高 get（int index）获取索引为index的元素直接用下标索引访问所以效率也是非常高 indexOf（Object o）获取元素的索引号也就是需要查找虽然用到了顺序查找法但效率还是比较高的 LinkedList擅长于对元素的插入和删除操作但对于随机访问元素比较慢该类的实现是以双向链表的数据结构为基础的所以是比较消耗内存的但它的特定集比ArrayList更大双向链表每个节点都有三个域两个域是存放前后节点的内存地址引用的一个域是存放数据元素的在LinkedList类中有一个叫Entry的内部类是private的里面三个属性分别是elementnext和previous分别对应了双向链表中的三个域在ArrayList类中每实例化一个Entry就生成一个节点下面看看它的核心方法add（E e）把元素插入到链表末尾首先要实例化一个节点新节点previous域存放链表中最后一个节点地址next域存放链表中第一个节点地址element域存放元素值链表中最后一个节点的next域存放新节点的地址第一个元素的previous域存放新节点的地址这样这个元素就插入到该链表中去了没有涉及到复杂的操作所以是非常高效的 add（int indexE element）在index位置插入元素这就需要先查找到该位置查到后这里就把查到的节点的前一个节点叫为A实例化新的节点为B查到index的节点为CB的next域等于A的next值（也就是C的内存地址）B的previous域等于C的previous值（也就是A的内存地址）B的element域存放元素值然后把A的next域和C的previous域都等于B的内存地址这样也就把元素插入到链表的index位置中去了但涉及到了查询所以效率虽然高但也没有add（E e）那么高 remove（int index）删除在index位置的元素首先也是要找到该位置的节点然后把该节点的下一个节点（也就是该节点next域的内存地址那个节点）的previous值等于该节点的previous值该节点的上一个节点（也就是该节点previous域的内存地址那个节点）的next值等于该节点的next值这样就把该节点从这条链表删除了过程中虽然涉及到了查找但没有涉及到像ArrayList类中的remove方法要移动表中元素所以该方法的效率还是很高的 remove（Object o）删除在链表中第一个元素为o的节点也是需要查找到该节点然后就跟remove（int index）思路一样把元素删除所以效率也是很高的 set（int indexE element）把在链表中第index个元素值改为element这也需要找到该节点来修改元素值但涉及到了查找节点ArrayList中的set方法就不用查找就可以修改所以相对于ArrayList中的set方法LinkedList方法set方法效率就没那么高了 get（int index）获取第index位置的元素值也是要找到该节点所以就也没ArrayList中的get方法那么高效率了因为该方法需要查找链表 indexOf（Object o）获取该链表中第一o元素的位置也是要查找链表但ArrayList中的indexOf方法也是需要查找的所以这两个类的indexOf的效率都差不多 所以在编程中如果要进行大量的随机访问就使用ArrayList如果要经常从表中插入或删除元素的就应该使用LinkedList Set继承自Collection接口表示无序的无重复元素的集合Set中最常使用的是测试归属性可以很容易测试某个对象是否在某个Set中所以查找就成为了Set中最重要的操作因此通常会选择一个HashSet的实现查找因为有比较复杂的哈希表支持它专门对快速查找进行了优化 迭代器迭代器是一种设计模式在这里是一个对象它的作用就是遍历并选择列表和操作列表中的对象迭代器的创佳的代价小所以通常被称为轻量级对象迭代器统一了对各种容器的访问方式很方便Java中的迭代器有两种一种是Iterator另一种是继承了Iterator只能用于各种List访问的ListIterator Iterator只能用于单向移动方法有iterator（）要求容器返回一个IteratorIterator将准备好返回序列的第一元素next（）获得列表中的下一个元素hasNext（）检查列表中是否还有元素remove（）将迭代器新近返回的元素删除 ListIterator只能用于各种的List类的访问但能用于双向的移动有一个hasPrevious（）检查时候有前一个元素的这种操作很像数据库的游标 import javautilArrayList; import javautilArrays; import javautilCollection; import javautilIterator; import javautilLinkedList; import javautilList; import javautilListIterator; public class ListTest { public static void main(String [] args) { Collection<Integer> col = new ArrayList<Integer>(ArraysasList()); List<Integer> list = new LinkedList<Integer>(); listaddAll(col); listadd(); listadd(); listadd(); displayIterator(list); listremove(); displayListIterator(list); } public static void displayIterator(Collection<Integer> list) { Iterator<Integer> it = erator(); Integer i; while(ithasNext()) { i = itnext(); Systemoutprint(i + ); if(i==) { itremove(); } } Systemoutprintln(); } public static void displayListIterator(List<Integer> list) { ListIterator<Integer> li = listlistIterator(); /** *//**以下注释代码为死循环永远输入表中的第一个数据*/ /** *//**while(lihasNext()) { Systemoutprintln(linext()); Systemoutprintln(liprevious()); }*/ while(lihasNext()) { Systemoutprint(linext() + ); } Systemoutprintln(); while(lihasPrevious()) { Systemoutprint(liprevious() + ); } } } Map也是一个映射存储键/值对的接口但跟Collection没有任何关系的也没有继承任何接口所以不能用Iterator迭代器来访问该集合中的元素给定一个关键字和一个值可以存储这个值到一个Map对象中存储以后就可以使用它的关键字来检索它映射经常使用到的两个基本操作get()和put()使用put()方法可以将一个指定了关键字和值的项加入映射为了得到值可以通过将关键字作为参数来调用get()方法 import javautilHashMap; import javautilMap; public class TestMap { public static void main(String [] args) { Map<StringInteger> hm = new HashMap<StringInteger>(); hmput(a ); hmput(b ); hmput(c ); hmput(d ); hmput(e ); display(hm); Systemoutprintln(ntainsKey(c)); hmremove(c); Systemoutprintln(ntainsValue()); Systemoutprintln(hmsize()); } public static void display(Map<StringInteger> m) { for(String s : mkeySet()) { Systemoutprintln(s + : + mget(s)); } } } |
