关于Java集合类List等等


就只会点就只会点Java 永久域名 http://jiangzhengjun.javaeye.com Java集合框架之LinkedList及ListIterator实 ... | Java命令参数说明大全2009-12-21 Java集合框架之小集合框架之小结结 文章分文章分类类:Java编编程程 1、Java容器类库的简化图,下面是集合类库更加完备的图。包括抽象类和遗留构件(不包括Queue的实现): 2、ArrayList初始化时不可指定容量,如果以new ArrayList()方式创建时,初始容量为10个;如果以new ArrayList(Collection c)初 始化时,容量为c.size()*1.1,即增加10%的容量;当向ArrayList中添加一个元素时,先进行容器的容量调整,如果容量不够时,则 增加至原来的1.5倍加1,再然后把元素加入到容器中,即以原始容量的0.5倍比率增加。 3、Vector:初始化时容量可以设定,如果以new Vector()方式创建时,则初始容量为10,超过容量时以2倍容量增加。如果以new Vector(Collection c)方式创建时,初始容量为c.size()*1.1,超过时以2倍容量增加。如果以new Vector(int initialCapacity, int capacityIncrement),则以capacityIncrement容量增加。 4、集合特点: List:保证以某种特定插入顺序来维护元素顺序,即保持插入的顺序,另外元素可以重复。 ArrayList:是用数组实现的,读取速度快,插入与删除速度慢(因为插入与删除时要移动后面的元素),适合于随机访问。 Vector:功能与ArrayList几乎相同,也是以数组实现,添加,删除,读取,设置都是基于线程同步的。 LinkedList:双向链表来实现,删除与插入速度快,读取速度较慢,因为它读取时是从头向尾(如果节点在链的前半部分), 或尾向头(如果节点在链的后半部分)查找元素。因此适合于元素的插入与删除操作。 Set:维持它自己的内部排序,随机访问不具有意义。另外元素不可重复。 HashSet:是最常用的,查询速度最快,因为 内部以HashMap来实现,所以插入元素不能保持插入次序。 LinkedHashSet:继承了HashSet,保持元素的插入次序,因为内部使用LinkedHashMap实现,所以能保持元素插入次序。 TreeSet:基于TreeMap,生成一个总是处于排序状态的set,它实现了SortedSet接口,内部以 TreeMap来实现 TreeMap:键以某种排序规则排序,内部以red-black(红-黑)树数据结构实现,实现了SortedMap接口,具体可参《RED- BLACK(红黑)树的实现TreeMap源码阅读 》 HashMap: 以哈希表数据结构实现,查找对象时通过哈希函数计算其位置,它是为快速查询而设计的,其内部定义了一 个hash表数组(Entry[] table),元素会通过哈希转换函数将元素的哈希地址转换成数组中存放的索引,如果有冲突,则使用 xie041 a123159521 wl_86129 ottoliu junJZ_2008 浏览: 96268 次 性别: 来自: 湖南澧縣 详细资料 留言簿 搜索本博客搜索本博客 搜索 最近最近访访客客 >>更多访客 博客分博客分类类 全部博客 (244) JavaScript (71) Java (76) 设计模式 (2) Effective Java (4) Java编程思想 (16) Java解惑系列 (3) Java并发编程 (2) XML (18) Linux (3) 软件开发管理 (9) 其他 (7) 数据结构 (12) 网络 (3) db (1) 字符集编码 (19) bytebuffer (0) 我的相册我的相册 首页 新闻 论坛 问答 博客 招聘 更多 ▼ 您您还还未登未登录录 ! 我的应用 登录 注册 converted by Web2PDFConvert.com 散列链表的形式将所有相同哈希地址的元素串起来,可能通过查看HashMap.Entry的源码它是一个单链表结构。 Hashtable:也是以哈希表数据结构实现的,解决冲突时与HashMap也一样也是采用了散列链表的形式,不过性能 比HashMap要低。 LinkedHashMap:继承HashMap,内部实体LinkedHashMap.Entry继承自HashMap.Entry,LinkedHashMap.Entry 在HashMap.Entry的基础上新增了两个实体引用(Entry before, after),这样实体可以相互串链起来形成链,并且 在LinkedHashMap中就定义了一个头节点(Entry header)用来指向循环双向链的第一个元素(通过after指向)与最后一个 元素(通过before指向)。在添加一个元素时,先会通过父类HashMap将元素加入到hash表数组里,然后再会在链 尾(header.before指向位置)添加(当然这一过程只是调整LinkedHashMap.Entry对象内部的before, after而已,而不是真真 创建一个什么新的链表结构向里加那样);删除先从hash表数组中删除,再将被删除的元素彻底的从双向链中断开。其实在 链中添加与删除操作与LinkedList是一样的,可以参考《Java集合框架之LinkedList及ListIterator实现源码分析 》 5、Hashtable和HashMap的区别: Hashtable中的方法是同步的,而HashMap中的方法在缺省情况下是非同步的。在多线程应用程序中,我们应该使 用Hashtable;而对于HashMap,则需要额外的同步机制。但HashMap的同步问题可通过Collections的一个静态方法得到 解决:Map Collections.synchronizedMap(Map m),当然与可以自己在使用地方加锁。 在HashMap中,可以允许null作为键,且只可以有一个,否则覆盖,但可以有一个或多个值为null。因为当get()方法返回null 值时,即可以表示 HashMap中没有该键,也可以表示该键所对应的值为null,所以HashMap不能由get()方法来判断否存在 某个键,而应该用containsKey()方法来判断;而Hashtable不允许null键与null值。 HashTable使用Enumeration,HashMap使用Iterator。 Hashtable是Dictionary的子类,HashMap是Map接口的一个实现类; HashTable中hash table数组默认大小是11,增加的方式是 int newCapacity = oldCapacity * 2 + 1;,即增加至2倍(而不是2 倍加1,因为扩容是在增加元素前进行的,在扩容后会将新增元素放入容器中)。HashMap中hash数组的默认大小是16,而 且一定是2的多少次方;另外两者的默认负载因子都是0.75。 求哈希地址与哈希地址转hash数组(Entry table[])索引方法不同: HashTable直接使用对象的hashCode: Java代代码码 1. int hash = key.hashCode();//直接使用键的hashCode方法求哈希值 2. //哈希地址转hash数组索引,先使用最大正int数与,这样将负转正数,再与数组长度求模得到存入的hash数组索引位置 3. int index = (hash & 0x7FFFFFFF) % tab.length; 而HashMap重新计算hash值,而且用位运算&代替求模: Java代代码码 1. int hash = hash(k); 2. int i = indexFor(hash, table.length); 3. 4. static int hash(Object x) { 5. //以键本身的hash码为基础求哈希地址,但看不懂是什么意思 6.   int h = x.hashCode(); 7.   h += ~(h << 9); 8.   h ^= (h >>> 14); 9.   h += (h << 4); 10.   h ^= (h >>> 10); 11.   return h; 12. } 13. static int indexFor(int h, int length) { 14.   return h & (length-1);//将哈希地址转换成哈希数组中存入的索引号 15. } HashMap实现图: 太极 共 6 张 我的留言簿我的留言簿 >>更多留言 看到你总结的各种排序算法很 不错,非常感谢。 -- by Gloomsky 谢谢关注 -- by junJZ_2008 多谢分享 -- by coollifer 其他分其他分类类 我的收藏 (18) 我的书籍 (1) 我的论坛主题贴 (21) 我的所有论坛贴 (53) 我的精华良好贴 (1) 最近加入圈子最近加入圈子 JavaEye站务讨论 存档存档 2010-06 (5) 2010-05 (28) 2010-04 (14) 更多存档... 评论评论排行榜排行榜 java解惑你知多少(一) 单例模式与双重检测 java解惑你知多少(八) protected,这个错了吗? 平衡二叉树实现 converted by Web2PDFConvert.com 6、集合中键值是否允许null小结 List:可以有多个null,可以有重复值。 HashSet:能插入一个null(因为内部是以 HashMap实现 ),忽略不插入重复元素。 TreeSet:不能插入null (因为内部是以 TreeMap 实现 ) ,元素不能重复,如果待插入的元素存在,则忽略不插入,对元素进 行排序。 HashMap:允许一个null键与多个null值,若重复键,则覆盖以前值。 TreeMap:不允许null键(实际上可以插入一个null键,如果这个Map里只有一个元素是不会报错的,因为一个元素时没有进 行排序操作,也就不会报空指针异常,但如果插入第二个时就会立即报错),但允许多个null值,覆盖已有键值。 HashTable:不允许null键与null值(否则运行进报空指针异常)。也会覆盖以重复值。基于线程同步。 7、对List的选择: 对于随机查询与迭代遍历操作,数组比所有的容器都要快。 从中间的位置插入和删除元素,LinkedList要比ArrayList快,特别是删除操作。 Vector通常不如ArrayList快,则且应该避免使用,它目前仍然存在于类库中的原因是为了支持过去的代码。 最佳实践:将ArrayList作为默认首选,只有当程序的性能因为经常从list中间进行插入和删除而变差的时候,才去选 择LinkedList。当然了,如果只是使用固定数量的元素,就应该选择数组了。 8、对Set的选择: HashSet的性能总比TreeSet好(特别是最常用的添加和查找元素操作)。 TreeSet存在的唯一原因是,它可以维持元素的排序状态,所以只有当你需要一个排好序的Set时,才应该使用TreeSet。 对于插入操作,LinkedHashSet比HashSet略微慢一点:这是由于维护链表所带来额外开销造成的。不过,因为有了链表, 遍历LinkedHashSet会比HashSet更快。 9、对Map的选择: Hashtable和HashMap的效率大致相同(通常HashMap更快一点,所以HashMap有意取代Hashtable)。 TreeMap通常比HashMap慢,因为要维护排序。 HashMap正是为快速查询而设计的。 LinkedHashMap比HashMap慢一点,因为它维护散列数据结构的同时还要维护链表。 10、Stack基于线程安全,Stack类是用Vector来实现的(public class Stack extends Vector),但最好不要用集合API里的这个实 现栈,因为它继承于Vector,本就是一个错误的设计,应该是一个组合的设计关系。 11、Iterator对ArrayList(LinkedList)的操作限制: 刚实例化的迭代器如果还没有进行后移(next)操作是不能马上进行删除与修改操作的。 可以用ListIterator对集合连续添加与修改,但不能连续删除。 进行添加操作后是不能立即进行删除与修改操作的。 进行删除操作后可以进行添加,但不能进行修改操作。 进行修改后是可以立即进行删除与添加操作的。 12、当以自己的对象做为HashMap、、HashTable、、LinkedHashMap、、HashSet 、、LinkedHashSet 的键时,一定要重 写hashCode ()与equals ()方法,因为Object的hashCode()是返回内存地址,且equals()方法也是比较内存地址,所以当要在这 些hash集合中查找时,如果是另外new出的新对象是查不到的,除非重写这两个方法。因为AbstractMap类 的containsKey(Object key)方法实现如下: Java代代码码 1. if (e.hash == hash && eq(k, e.key))//先比对hashcode,再使用equals 2. return true; 3. 4. static boolean eq(Object x, Object y) { 5. return x == y || x.equals(y); converted by Web2PDFConvert.com 6. } String对象是可以准确做为键的,因为已重写了这两个方法。 因此,Java中的集合框架中的哈希是以一个对象查找另外一个对象,所以重写hasCode与equals方法很重要。 13、重写hashCode()与equals()这两个方法是针对哈希类,至于其它集合,如果要用public boolean contains(Object o) 或containsValue(Object value)查找时,只需要实现equals()方法即可,他们都只使用对象的 equals方法进行比对,没有使用 hashCode方法。 14、TreeMap/TreeSet:放入其中的元素一定要具有自然比较能力(即要实现java.lang.Comparable接口)或者在构 造TreeMap/TreeSet时传入一个比较器(实现java.util.Comparator接口),如果在创建时没有传入比较器,而放入的元素也没有自 然比较能力时,会出现类型转换错误(因为在没有较器时,会试着转成Comparable型)。 两种比较接口: Java代代码码 1. //自然比较器 2. public interface java.lang.Comparable { 3. public int compareTo(Object o); 4. } 5. 6. public interface java.util.Comparator { 7. int compare(Object o1, Object o2); 8. boolean equals(Object obj); 9. } 15、Collection或Map的同步控制:可以使用Collections类的相应静态方法来包装相应的集合类,使他们具线程安全,如public static Collection synchronizedCollection (Collection c)方法实质返回的是包装后的SynchronizedCollection子类,当然你也 可以使用Collections的synchronizedList、synchronizedMap、synchronizedSet方法来获取不同的经过包装了的同步集合,其代 码片断: Java代代码码 1. public class Collections { 2. 3. //... 4. 5. static Collection synchronizedCollection(Collection c, Object mutex) { 6. return new SynchronizedCollection(c, mutex); 7. } 8. 9. public static List synchronizedList(List list) { 10. //... 11. } 12. 13. static Set synchronizedSet(Set s, Object mutex) { 14. //... 15. } 16. 17. public static Map synchronizedMap(Map m) { 18. return new SynchronizedMap(m); 19. } 20. 21. //... 22. static class SynchronizedCollection implements Collection, Serializable { 23. 24. Collection c; // 对哪个集合进行同步(包装) 25. Object mutex; // 对象锁,可以自己设置 26. 27. //... 28. SynchronizedCollection(Collection c, Object mutex) { 29. this.c = c; 30. this.mutex = mutex; 31. } 32. 33. public int size() { 34. synchronized (mutex) { 35. return c.size(); 36. } 37. } 38. 39. public boolean isEmpty() { 40. synchronized (mutex) { 41. return c.isEmpty(); 42. } 43. } 44. //... converted by Web2PDFConvert.com 23:03 浏览 (323) 评论 (0) 分类: Java 相关推荐 表情表情图标图标 B I U Quote Code List Img URL Flash Table 字体颜色: 标准 字体大小: 标准 对齐: 标准 Java集合框架之LinkedList及ListIterator实 ... | Java命令参数说明大全 45. } 46. 47. static class SynchronizedList extends SynchronizedCollection implements List { 48. 49. List list; 50. 51. SynchronizedList(List list, Object mutex) { 52. super(list, mutex); 53. this.list = list; 54. } 55. 56. public Object get(int index) { 57. synchronized (mutex) { 58. return list.get(index); 59. } 60. } 61. //... 62. } 63. 64. static class SynchronizedSet extends SynchronizedCollection implements Set { 65. SynchronizedSet(Set s) { 66. super(s); 67. } 68. //... 69. } 70. //... 71. } 由包装的代码可以看出只是把原集合的相应方法放在同步块里调用罢了。 16、通过迭代器修改集合结构 在使用迭代器遍历集合时,我们不能通过集合本身来修改集合的结构(添加、删除),只能通过迭代器来操作,下面是拿对HashMap删除操 作的测试,其它集合也是这样: Java代代码码 1. public static void main(String[] args) { 2. Map map = new HashMap(); 3. map.put(1, 1); 4. map.put(2, 3); 5. Set entrySet = map.entrySet(); 6. Iterator it = entrySet.iterator(); 7. while (it.hasNext()) { 8. Entry entry = (Entry) it.next(); 9. /* 10. * 可以通过迭代器来修改集合结构,但前提是要在已执行过 next 或 11. * 前移操作,否则会抛异常:IllegalStateException 12. */ 13. // it.remove(); 14. /* 15. * 抛异常:ConcurrentModificationException 因为通过 迭代 器操 16. * 作时,不能使用集合本身来修 17. * 改集合的结构 18. */ 19. // map.remove(entry.getKey()); 20. } 21. System.out.println(map); 22. } 查看图片附件 评论评论 发发表表评论评论 converted by Web2PDFConvert.com 声明:JavaEye文章版权属于作者,受法律保护。没有作者书面许可不得转载。若作者同意转载,必须以超链接形式标明文章原始出处和作者。 © 2003-2010 JavaEye.com. All rights reserved. 上海炯耐计算机软件有限公司 [ 沪ICP备05023328号 ] 字体颜色: 标准 字体大小: 标准 对齐: 标准 提示:选择您需要装饰的文字, 按上列按钮即可添加上相应的标签 您还没有登录,请登录后发表评论(快捷键 Alt+S / Ctrl+Enter) 提交 converted by Web2PDFConvert.com
还剩5页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 10 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

skyliving

贡献于2012-02-20

下载需要 10 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf