注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

断尘居

温柔的男人像海洋。

 
 
 
 
 

日志

 
 

Java常用集合介绍  

2011-09-15 18:37:24|  分类: JDK |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
线性表,链表,哈希表是常用的数据结构,在进行Java开发时,JDK已经为我们提供了一系列相应的类来实现基本的数据结构。这些类均在
>java.util包中。本文试图通过简单的描述,向读者阐述各个类的作用以及如何正确使用这些类。    
>   
> Collection  
> ├List  
> │├LinkedList  
> │├ArrayList  
> │└Vector  
> │ └Stack  
> └Set  
> Map  
> ├Hashtable  
> ├HashMap  
> └WeakHashMap  
>   
> Collection接口  
>   Collection是最基本的集合接口,一个Collection代表一组Object,即Collection的元素(Elements)。一些Collection允许相同的元
>素而另一些不行。一些能排序而另一些不行。Java   SDK不提供直接继承自Collection的类,Java   SDK提供的类都是继承自Collection的“
>子接口”如List和Set。  
>   所有实现Collection接口的类都必须提供两个标准的构造函数:无参数的构造函数用于创建一个空的Collection,有一个Collection参
>数的构造函数用于创建一个新的Collection,这个新的Collection与传入的Collection有相同的元素。后一个构造函数允许用户复制一个
>Collection。  
>   如何遍历Collection中的每一个元素?不论Collection的实际类型如何,它都支持一个iterator()的方法,该方法返回一个迭代子,使
>用该迭代子即可逐一访问Collection中每一个元素。典型的用法如下:  
>     Iterator   it   =   collection.iterator();   //   获得一个迭代子  
>     while(it.hasNext())   {  
>       Object   obj   =   it.next();   //   得到下一个元素  
>     }  
>   由Collection接口派生的两个接口是List和Set。  
>   
> List接口  
>   List是有序的Collection,使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引(元素在List中的位置,类似于数组下
>标)来访问List中的元素,这类似于Java的数组。  
> 和下面要提到的Set不同,List允许有相同的元素。  
>   除了具有Collection接口必备的iterator()方法外,List还提供一个listIterator()方法,返回一个ListIterator接口,和标准的
>Iterator接口相比,ListIterator多了一些add()之类的方法,允许添加,删除,设定元素,还能向前或向后遍历。  
>   实现List接口的常用类有LinkedList,ArrayList,Vector和Stack。  
>   
> LinkedList类  
>   LinkedList实现了List接口,允许null元素。此外LinkedList提供额外的get,remove,insert方法在LinkedList的首部或尾部。这些操
>作使LinkedList可被用作堆栈(stack),队列(queue)或双向队列(deque)。  
>   注意LinkedList没有同步方法。如果多个线程同时访问一个List,则必须自己实现访问同步。一种解决方法是在创建List时构造一个同
>步的List:  
>     List   list   =   Collections.synchronizedList(new   LinkedList(...));  
>   
> ArrayList类  
>   ArrayList实现了可变大小的数组。它允许所有元素,包括null。ArrayList没有同步。  
> size,isEmpty,get,set方法运行时间为常数。但是add方法开销为分摊的常数,添加n个元素需要O(n)的时间。其他的方法运行时间为线性
>。  
>   每个ArrayList实例都有一个容量(Capacity),即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加,但是增长
>算法并没有定义。当需要插入大量元素时,在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。  
>   和LinkedList一样,ArrayList也是非同步的(unsynchronized)。  
>   
> Vector类  
>   Vector非常类似ArrayList,但是Vector是同步的。由Vector创建的Iterator,虽然和ArrayList创建的Iterator是同一接口,但是,因
>为Vector是同步的,当一个Iterator被创建而且正在被使用,另一个线程改变了Vector的状态(例如,添加或删除了一些元素),这时调用
>Iterator的方法时将抛出ConcurrentModificationException,因此必须捕获该异常。  
>   
> Stack   类  
>   Stack继承自Vector,实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop方法,还
>有peek方法得到栈顶的元素,empty方法测试堆栈是否为空,search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。  
>   
> Set接口  
>   Set是一种不包含重复的元素的Collection,即任意的两个元素e1和e2都有e1.equals(e2)=false,Set最多有一个null元素。  
>   很明显,Set的构造函数有一个约束条件,传入的Collection参数不能包含重复的元素。  
>   请注意:必须小心操作可变对象(Mutable   Object)。如果一个Set中的可变元素改变了自身状态导致Object.equals(Object)=true将
>导致一些问题。  
>   
> Map接口  
>   请注意,Map没有继承Collection接口,Map提供key到value的映射。一个Map中不能包含相同的key,每个key只能映射一个value。Map接
>口提供3种集合的视图,Map的内容可以被当作一组key集合,一组value集合,或者一组key-value映射。  
>   
> Hashtable类  
>   Hashtable继承Map接口,实现一个key-value映射的哈希表。任何非空(non-null)的对象都可作为key或者value。  
>   添加数据使用put(key,   value),取出数据使用get(key),这两个基本操作的时间开销为常数。  
> Hashtable通过initial   capacity和load   factor两个参数调整性能。通常缺省的load   factor   0.75较好地实现了时间和空间的均衡
>。增大load   factor可以节省空间但相应的查找时间将增大,这会影响像get和put这样的操作。  
> 使用Hashtable的简单示例如下,将1,2,3放到Hashtable中,他们的key分别是”one”,”two”,”three”:  
>     Hashtable   numbers   =   new   Hashtable();  
>     numbers.put(“one”,   new   Integer(1));  
>     numbers.put(“two”,   new   Integer(2));  
>     numbers.put(“three”,   new   Integer(3));  
>   要取出一个数,比如2,用相应的key:  
>     Integer   n   =   (Integer)numbers.get(“two”);  
>     System.out.println(“two   =   ”   +   n);  
>   由于作为key的对象将通过计算其散列函数来确定与之对应的value的位置,因此任何作为key的对象都必须实现hashCode和equals方法。
>hashCode和equals方法继承自根类Object,如果你用自定义的类当作key的话,要相当小心,按照散列函数的定义,如果两个对象相同,即
>obj1.equals(obj2)=true,则它们的hashCode必须相同,但如果两个对象不同,则它们的hashCode不一定不同,如果两个不同对象的hashCode
>相同,这种现象称为冲突,冲突会导致操作哈希表的时间开销增大,所以尽量定义好的hashCode()方法,能加快哈希表的操作。  
>   如果相同的对象有不同的hashCode,对哈希表的操作会出现意想不到的结果(期待的get方法返回null),要避免这种问题,只需要牢记
>一条:要同时复写equals方法和hashCode方法,而不要只写其中一个。  
>   Hashtable是同步的。  
>   
> HashMap类  
>   HashMap和Hashtable类似,不同之处在于HashMap是非同步的,并且允许null,即null   value和null   key。,但是将HashMap视为
>Collection时(values()方法可返回Collection),其迭代子操作时间开销和HashMap的容量成比例。因此,如果迭代操作的性能相当重要的话
>,不要将HashMap的初始化容量设得过高,或者load   factor过低。  
>   
> WeakHashMap类  
>   WeakHashMap是一种改进的HashMap,它对key实行“弱引用”,如果一个key不再被外部所引用,那么该key可以被GC回收。  
>   
> 总结  
>   如果涉及到堆栈,队列等操作,应该考虑用List,对于需要快速插入,删除元素,应该使用LinkedList,如果需要快速随机访问元素,
>应该使用ArrayList。  
>   如果程序在单线程环境中,或者访问仅仅在一个线程中进行,考虑非同步的类,其效率较高,如果多个线程可能同时操作一个类,应该
>使用同步的类。  
>   要特别注意对哈希表的操作,作为key的对象要正确复写equals和hashCode方法。  
>   尽量返回接口而非实际的类型,如返回List而非ArrayList,这样如果以后需要将ArrayList换成LinkedList时,客户端代码不用改变。
>这就是针对抽象编程

Collection接口,包含list和set子接口
Collection和Map接口之间的主要区别在于:Collection中存储了一组对象,而Map存储关键字/值对。
在Map对象中,每一个关键字最多有一个关联的值。
Map:不能包括两个相同的键,一个键最多能绑定一个值。null可以作为键,这样的键只有一个;可以有一个或多个键所对应的
值为null。当get()方法返回null值时,即可以表示Map中没有该键,也可以表示该键所对应的值为null。因此,在Map中不能由get()方法来判断Map中是否存在某个键,而应该用containsKey()方法来判断。
继承Map的类有:HashMap,HashTable
HashMap:Map的实现类,缺省情况下是非同步的,可以通过Map Collections.synchronizedMap(Map m)来达到线程同步
HashTable:Dictionary的子类,确省是线程同步的。不允许关键字或值为null

当元素的顺序很重要时选用TreeMap,当元素不必以特定的顺序进行存储时,使用HashMap。Hashtable的使用不被推荐,因为HashMap提供了所有类似的功能,并且速度更快。当你需要在多线程环境下使用时,HashMap也可以转换为同步的。


以下引用:
  • 为什么要使用集合类

当你事先不知道要存放数据的个数,或者你需要一种比数组下标存取机制更灵活的方法时,你就需要用到集合类。

  • 理解集合类

集合类存放于java.util包中。
集合类存放的都是对象的引用,而非对象本身,出于表达上的便利,我们称集合中的对象就是指集合中对象的引用(reference)。
集合类型主要有3种:set(集)、list(列表)和map(映射)。

(1)集
集(set)是最简单的一种集合,它的对象不按特定方式排序,只是简单的把对象加入集合中,就像往口袋里放东西。
对集中成员的访问和操作是通过集中对象的引用进行的,所以集中不能有重复对象。
集也有多种变体,可以实现排序等功能,如TreeSet,它把对象添加到集中的操作将变为按照某种比较规则将其插入到有序的对象序列中。它实现的是 SortedSet接口,也就是加入了对象比较的方法。通过对集中的对象迭代,我们可以得到一个升序的对象集合。

(2)列表
列表的主要特征是其对象以线性方式存储,没有特定顺序,只有一个开头和一个结尾,当然,它与根本没有顺序的集是不同的。
列表在数据结构中分别表现为:数组和向量、链表、堆栈、队列。
关于实现列表的集合类,是我们日常工作中经常用到的,将在后边的笔记详细介绍。

(3)映射
映射与集或列表有明显区别,映射中每个项都是成对的。映射中存储的每个对象都有一个相关的关键字(Key)对象,关键字决定了对象在映射中的存储位置,检索对象时必须提供相应的关键字,就像在字典中查单词一样。关键字应该是唯一的。
关键字本身并不能决定对象的存储位置,它需要对过一种散列(hashing)技术来处理,产生一个被称作散列码(hash code)的整数值,散列码通常用作一个偏置量,该偏置量是相对于分配给映射的内存区域起始位置的,由此确定关键字/对象对的存储位置。理想情况下,散列 处理应该产生给定范围内均匀分布的值,而且每个关键字应得到不同的散列码。

  • 集合类简介

java.util中共有13个类可用于管理集合对象,它们支持集、列表或映射等集合,以下是这些类的简单介绍

集:
HashSet:
使用HashMap的一个集的实现。虽然集定义成无序,但必须存在某种方法能相当高效地找到一个对象。使用一个HashMap对象实现集的存储和检索操作是在固定时间内实现的.
TreeSet: 在集中以升序对对象排序的集的实现。这意味着从一个TreeSet对象获得第一个迭代器将按升序提供对象。TreeSet类使用了一个TreeMap.
列表:
Vector: 实现一个类似数组一样的表,自动增加容量来容纳你所需的元素。使用下标存储和检索对象就象在一个标准的数组中一样。你也可以用一个迭代器从一个Vector中检索对象。Vector是唯一的同步容器类??当两个或多个线程同时访问时也是性能良好的。
Stsck: 这个类从Vector派生而来,并且增加了方法实现栈??一种后进先出的存储结构。
LinkedList: 实现一个链表。由这个类定义的链表也可以像栈或队列一样被使用。
ArrayList: 实现一个数组,它的规模可变并且能像链表一样被访问。它提供的功能类似Vector类但不同步。
映射:
HashTable:
实现一个映象,所有的键必须非空。为了能高效的工作,定义键的类必须实现hashcode()方法和equal()方法。这个类是前面java实现的一个继承,并且通常能在实现映象的其他类中更好的使用。
HashMap: 实现一个映象,允许存储空对象,而且允许键是空(由于键必须是唯一的,当然只能有一个)。
WeakHashMap: 实现这样一个映象:通常如果一个键对一个对象而言不再被引用,键/对象对将被舍弃。这与HashMap形成对照,映象中的键维持键/对象对的生命周期,尽管使用映象的程序不再有对键的引用,并且因此不能检索对象。
TreeMap: 实现这样一个映象,对象是按键升序排列的。

Set和List都是由公共接口Collection扩展而来,所以它们都可以使用一个类型为Collection的变量 来引用。这就意味着任何列表或集构成的集合都可以用这种方式引用,只有映射类除外(但也不是完全排除在外,因为可以从映射获得一个列表。)所以说,把一个 列表或集传递给方法的标准途径是使用Collection类型的参数。

Java容器类Collection、List、ArrayList、Vector及map、HashTable、HashMap区别 2009-02-21 19:45 Collection是List和Set两个接口的基接口 List在Collection之上增加了"有序" Set在Collection之上增加了"唯一" 而ArrayList是实现List的类...所以他是有序的. 它里边存放的元素在排列上存在一定的先后顺序 而且ArrayList是采用数组存放元素 另一种List LinkedList采用的则是链表。 Collection和Map接口之间的主要区别在于:Collection中存储了一组对象,而Map存储关键字/值对。 在Map对象中,每一个关键字最多有一个关联的值。 Map:不能包括两个相同的键,一个键最多能绑定一个值。null可以作为键,这样的键只有一个;可以有一个或多个键所对应的 值为null。当get()方法返回null值时,即可以表示Map中没有该键,也可以表示该键所对应的值为null。因此,在Map中不能由get() 方法来判断Map中是否存在某个键,而应该用containsKey()方法来判断。 继承Map的类有:HashMap,HashTable HashMap:Map的实现类,缺省情况下是非同步的,可以通过Map Collections.synchronizedMap(Map m)来达到线程同步 HashTable:Dictionary的子类,确省是线程同步的。不允许关键字或值为null 当元素的顺序很重要时选用TreeMap,当元素不必以特定的顺序进行存储时,使用HashMap。Hashtable的使用不被推荐,因为 HashMap提供了所有类似的功能,并且速度更快。当你需要在多线程环境下使用时,HashMap也可以转换为同步的。 为什么要使用集合类当你事先不知道要存放数据的个数,或者你需要一种比数组下标存取机制更灵活的方法时,你就需要用到集合类。 理解集合类集合类存放于java.util包中。 集合类存放的都是对象的引用,而非对象本身,出于表达上的便利,我们称集合中的对象就是指集合中对象的引用(reference)。 集合类型主要有3种:set(集)、list(列表)和map(映射)。 (1)集 集(set)是最简单的一种集合,它的对象不按特定方式排序,只是简单的把对象加入集合中,就像往口袋里放东西。 对集中成员的访问和操作是通过集中对象的引用进行的,所以集中不能有重复对象。 集也有多种变体,可以实现排序等功能,如TreeSet,它把对象添加到集中的操作将变为按照某种比较规则将其插入到有序的对象序列中。它实现的是 SortedSet接口,也就是加入了对象比较的方法。通过对集中的对象迭代,我们可以得到一个升序的对象集合。 (2)列表 列表的主要特征是其对象以线性方式存储,没有特定顺序,只有一个开头和一个结尾,当然,它与根本没有顺序的集是不同的。 列表在数据结构中分别表现为:数组和向量、链表、堆栈、队列。 关于实现列表的集合类,是我们日常工作中经常用到的,将在后边的笔记详细介绍。 (3)映射 映射与集或列表有明显区别,映射中每个项都是成对的。映射中存储的每个对象都有一个相关的关键字(Key)对象,关键字决定了对象在映射中的存储位置,检 索对象时必须提供相应的关键字,就像在字典中查单词一样。关键字应该是唯一的。 关键字本身并不能决定对象的存储位置,它需要对过一种散列(hashing)技术来处理,产生一个被称作散列码(hash code)的整数值,散列码通常用作一个偏置量,该偏置量是相对于分配给映射的内存区域起始位置的,由此确定关键字/对象对的存储位置。理想情况下,散列 处理应该产生给定范围内均匀分布的值,而且每个关键字应得到不同的散列码。 集合类简介 java.util中共有13个类可用于管理集合对象,它们支持集、列表或映射等集合,以下是这些类的简单介绍 集: HashSet: 使用HashMap的一个集的实现。虽然集定义成无序,但必须存在某种方法能相当高效地找到一个对象。使用一个HashMap对象实现集的存储和检索操作 是在固定时间内实现的. TreeSet: 在集中以升序对对象排序的集的实现。这意味着从一个TreeSet对象获得第一个迭代器将按升序提供对象。TreeSet类使用了一个TreeMap. 列表: Vector: 实现一个类似数组一样的表,自动增加容量来容纳你所需的元素。使用下标存储和检索对象就象在一个标准的数组中一样。你也可以用一个迭代器从一个 Vector中检索对象。Vector是唯一的同步容器类??当两个或多个线程同时访问时也是性能良好的。(同步即同时只能一个进程访问,其他等待) Stack: 这个类从Vector派生而来,并且增加了方法实现栈??一种后进先出的存储结构。 LinkedList: 实现一个链表。由这个类定义的链表也可以像栈或队列一样被使用。 ArrayList: 实现一个数组,它的规模可变并且能像链表一样被访问。它提供的功能类似Vector类但不同步。 映射: HashTable: 实现一个映象,所有的键必须非空。为了能高效的工作,定义键的类必须实现hashcode()方法和equal()方法。这个类是前面java实现的一个 继承,并且通常能在实现映象的其他类中更好的使用。 HashMap: 实现一个映象,允许存储空对象,而且允许键是空(由于键必须是唯一的,当然只能有一个)。 WeakHashMap: 实现这样一个映象:通常如果一个键对一个对象而言不再被引用,键/对象对将被舍弃。这与HashMap形成对照,映象中的键维持键/对象对的生命周期,尽 管使用映象的程序不再有对键的引用,并且因此不能检索对象。 TreeMap: 实现这样一个映象,对象是按键升序排列的。 下图是集合类所实现的接口之间的关系: Set和List都是由公共接口Collection扩展而来,所以它们都可以使用一个类型为Collection的变量来引用。这就意味着任何列表或集 构成的集合都可以用这种方式引用,只有映射类除外(但也不是完全排除在外,因为可以从映射获得一个列表。)所以说,把一个列表或集传递给方法的标准途径是 使用Collection类型的参数。
List接口   List是有序的Collection,使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引(元素在List中的位置,类似于数组下标) 来访问List中的元素,这类似于Java的数组。 和下面要提到的Set不同,List允许有相同的元素。   除了具有Collection接口必备的iterator()方法外,List还提供一个listIterator()方法,返回一个 ListIterator接口,和标准的Iterator接口相比,ListIterator多了一些add()之类的方法,允许添加,删除,设定元素, 还能向前或向后遍历。   实现List接口的常用类有LinkedList,ArrayList,Vector和Stack。 ArrayList类   ArrayList实现了可变大小的数组。它允许所有元素,包括null。ArrayList没有同步。 size,isEmpty,get,set方法运行时间为常数。但是add方法开销为分摊的常数,添加n个元素需要O(n)的时间。其他的方法运行时间为 线性。  每个ArrayList实例都有一个容量(Capacity),即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加,但是增 长算法并没有定义。当需要插入大量元素时,在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。   和LinkedList一样,ArrayList也是非同步的(unsynchronized)。 Map接口   请注意,Map没有继承Collection接口,Map提供key到value的映射。一个Map中不能包含相同的key,每个key只能映射一个 value。Map接口提供3种集合的视图,Map的内容可以被当作一组key集合,一组value集合,或者一组key-value映射。 HashMap类   HashMap和Hashtable类似,不同之处在于HashMap是非同步的,并且允许null,即null value和null key。,但是将HashMap视为Collection时(values()方法可返回Collection),其迭代子操作时间开销和HashMap 的容量成比例。因此,如果迭代操作的性能相当重要的话,不要将HashMap的初始化容量设得过高,或者load factor过低。 ---------------------------------------------------------------------------- 1. List是接口,List特性就是有序,会确保以一定的顺序保存元素. ArrayList是它的实现类,是一个用数组实现的List. Map是接口,Map特性就是根据一个对象查找对象. HashMap是它的实现类,HashMap用hash表实现的Map,就是利用对象的hashcode(hashcode()是Object的方法)进 行快速散列查找.(关于散列查找,可以参看<<数据结构>>) 2. 一般情况下,如果没有必要,推荐代码只同List,Map接口打交道. 比如:List list = new ArrayList(); 这样做的原因是list就相当于是一个泛型的实现,如果想改变list的类型,只需要: List list = new LinkedList();//LinkedList也是List的实现类,也是ArrayList的兄弟类这样,就不需要修改其它代码,这就是接口编程 的优雅之处. 另外的例子就是,在类的方法中,如下声明: private void doMyAction(List list){} 这样这个方法能处理所有实现了List接口的类,一定程度上实现了泛型函数. 3. 如果开发的时候觉得ArrayList,HashMap的性能不能满足你的需要,可以通过实现List,Map(或者Collection)来定制你的自 定义类
  评论这张
 
阅读(2444)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017