`

Java集合类库

    博客分类:
  • java
 
阅读更多
http://jiangzhengjun.iteye.com/blog/553191(转载)

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),元素会通过哈希转换函数将元素的哈希地址转换成数组中存放的索引,如果有冲突,则使用散列链表的形式将所有相同哈希地址的元素串起来,可能通过查看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、集合中键值是否允许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); 
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.        //... 
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.} 
分享到:
评论

相关推荐

    JAVA集合类库

    java的集合中的各个常用类的介绍以及一些经常使用到的用法

    java核心类库使用大全

    Java核心类库是Java编程语言的核心组成部分,包含了丰富的API(应用程序接口)和工具,使得开发者能够构建各种类型的应用程序,从简单的控制台程序到复杂的分布式系统。这份"java核心类库使用大全"深入探讨了Java ...

    java2类库 java类库的源文件

    1. **基础类库**:这部分包含 Java 语言的基本数据类型、异常处理、输入/输出、集合框架等核心功能。例如,`java.lang` 包提供了诸如 `String`、`Integer` 和 `Object` 等基本类,而 `java.io` 包则提供了文件操作和...

    Java标准类库PDF

    Java标准类库是Java编程语言的一个重要组成部分,它包含了大量的预定义类和接口,这些类和接口为Java程序员提供了一系列的功能强大的工具和实用功能,使得开发人员能够更加高效地编写高质量的Java应用程序。...

    java类库java类库.doc

    Java 类库是 Java API 的一部分,是系统提供的已实现的标准类的集合。这些类和方法都是精心设计的,其运行效率高、质量高。类库中的这些类和方法包含在几乎所有的 Java 软件中,所以具有很好的移植性。 Java 类库的...

    Java2 类库 Java2 类库

    2. **集合框架**:Java2类库引入了强大的集合框架,如List(ArrayList、LinkedList)、Set(HashSet、TreeSet)和Map(HashMap、TreeMap),它们为数据存储和处理提供了统一的接口和实现。 3. **I/O流**:Java的I/O...

    java常用类库java常用类库java常用类库

    Java常用类库是Java编程语言的核心组成部分,它们提供了一系列预定义的类和接口,使得开发者可以方便地进行各种常见任务的处理,而无需从零开始编写所有代码。这些类库覆盖了输入输出、网络通信、数据处理、集合框架...

    Java2 类库详解

    2. **集合框架**:Java2类库中的集合框架是实现数据结构和算法的重要工具,包括ArrayList、LinkedList、HashSet、HashMap等。这些类和接口提供了对数据的存储、检索和操作,使得处理复杂数据变得简单。 3. **I/O流*...

    java 2类库3

    同时,`java.util`包中的`Collections`框架提供了各种集合类,如`List`、`Set`、`Map`,以及它们的实现,如`ArrayList`、`HashSet`、`HashMap`,这些都是日常开发中不可或缺的部分。 对于网络编程,`java.net`包...

    Java SE 类库查询手册

    首先,让我们聚焦于Java集合框架。集合框架是Java SE中最基础也是最核心的部分之一,它提供了一组接口(如List、Set、Queue)和实现这些接口的类(如ArrayList、HashSet、LinkedList等),以及对它们进行操作的工具...

    java常用类库手册

    Java 类库,也就是Java API(Application Programming Interface),是Java平台提供的一系列已经实现的标准类的集合。这些类库包含了丰富的功能,如字符串处理、绘图、网络应用、数学计算等,覆盖了软件开发中的大...

    通用Java开发类库

    1. **集合框架**:Java集合框架是Java API的核心部分,它提供了多种数据结构如List(列表)、Set(集合)、Queue(队列)和Map(映射)。例如ArrayList、LinkedList、HashSet、HashMap等,它们为存储和操作对象提供...

    Java程序设计:Java标准类库.ppt

    Java集合框架是一组接口和类,用于存储和操作对象。它包括List、Set、Map接口,以及ArrayList、LinkedList、HashSet、HashMap等实现。此外,还有Iterator和Iterable接口,以及Collections工具类,用于集合的遍历和...

    c、c++、java标准类库+mfc类库详解+Win32API大全 中文版 chm文件

    Java的类库强大而全面,如集合框架(ArrayList、HashMap等)、IO流、多线程、网络编程等。比如,`java.util.ArrayList`是一个动态数组,`java.io.File`类用于文件操作,`java.net.Socket`用于网络通信。 MFC...

    Java2 类库--技术手册

    1. **核心类库**:这是Java的基石,包括了基础数据类型、异常处理、输入/输出流、字符串处理、集合框架等。例如,`java.lang`包中的`String`类用于创建和操作字符串,`ArrayList`和`HashMap`分别代表可变大小的顺序...

    java基本类库结构图.zip

    Java基本类库是Java开发的核心组成部分,它包含了丰富的类和接口,为开发者提供了大量功能,使得我们可以构建出高效、稳定的应用程序。这个压缩包“java基本类库结构图.zip”显然是一个可视化工具,用于展示Java类库...

    java常用类库中文速查表

    fastutil库是针对Java集合框架的扩展,它提供了小内存占用和快速访问的特定类型的集合类,如map、set、list和queue,也包括大(64位)array、set和list,以及快速、实用的二进制文件和文本文件的I/O类。fastutil特别...

    Java 常见类库的介绍

    在Java的`java.util`包中,类库主要关注数据结构和集合框架。其中,集合框架是Java类库中最重要的一部分,它提供了一种高效管理对象的方式。集合框架的核心接口包括`Collection`、`Map`和`Iterator`。 1. `...

    Java类库中文手册

    2. **集合框架**:Java集合框架是处理对象集合的核心工具,包括`List`、`Set`和`Map`接口,以及实现这些接口的类如`ArrayList`、`HashSet`和`HashMap`。它们为数据存储、排序、遍历等提供了高效且灵活的方法。 3. *...

Global site tag (gtag.js) - Google Analytics