Java 集合 Collection List Set Map 区别

package com.suypower.chengyu.collection;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;

public class CollectionTest {

	/**
	 * @author chengYu
	 * @return collection
	 * Collections是针对集合类的一个帮助类。提供了一系列静态方法实现对各种集合的搜索、排序、线程完全化等操作。
	 * 			  相当于对Array进行类似操作的类——Arrays。
	 */
	/*
	 * 集合机构图
	 * Collection
		├List
		│├LinkedList
		│├ArrayList
		│└Vector
		│　└Stack
		└Set HashSet , TreeSet , LinkedHashSet
		Map
		├Hashtable
		├HashMap
		└WeakHashMap
	 */
/*
 * ArrayList
 * 随即访问速度快
 * 非同步 List list = Collections.synchronizedList(new ArrayList(...)); 
 * *****************************集合差操作
	 List a = Arrays.asList(lista.toArray());
     List b = Arrays.asList(listb.toArray());
     Collection subtract = CollectionUtils.subtract(a,b);
 */
	
	public ArrayList toArrayList(ArrayList<String> arrayList)
	{
		System.out.println();
		System.out.println("------------------ArrayList----------------------------------");
		arrayList.add(null); //允许包括 null 在内的所有元素
		arrayList.add(2,"A"); //将指定的元素插入此列表中的指定位置
		System.out.println
		("arrayList.contains(\"A\")="+(arrayList.contains("A")==true?"真":"假").toString());
//		arrayList.clear(); 清空集合
		System.out.println("arrayList.get(2)="+arrayList.get(2));
		System.out.println("返回A的小标 :"+arrayList.indexOf("A"));
		if(arrayList.indexOf("A") != -1)
		{
			System.out.println("arrayList.indexOf(\"A\") != -1"+" 此集合里面找到A");
		}
		System.out.println("测试此列表中是否没有元素:"+arrayList.isEmpty());
		arrayList.remove("a");  // 从此列表中移除指定元素 
		arrayList.remove(1);	// 移除此列表中指定位置上的元素(移除第二个元素)
//		遍历元素 iterator
		Iterator<String> iterator = arrayList.iterator();
		while(iterator.hasNext())
		{
			System.out.print(iterator.next());
		}
		System.out.println();
		for(String str:arrayList)System.out.print(str);//打印集合
		System.out.println();
		System.out.println("-----------------------LinkedList-----------------------------");
		return arrayList;
	}
	/*
	 * LinkedList 用法
	 * 快速插入和删除
	 */
	public LinkedList toLinkedList (LinkedList<String> linkedList)
	{
		linkedList.add("h");
		linkedList.add(null); //允许包括 null 在内的所有元素
		linkedList.addFirst("-addFirst-");
//		linkedList.clear();   清除 linkedlist
		System.out.println("linkedList.contains(\"d\")="+linkedList.contains("d"));
		System.out.println("获取第一个元素:"+linkedList.element());
		System.out.println("获取第一个元素:"+linkedList.peek()); //找到不移除此列表的头
		System.out.println("获取第一个元素:"+linkedList.poll());//找到并移除此列表的头
		System.out.println("获取指定下标元素:"+linkedList.get(1));
		System.out.println("获取元素的下标="+linkedList.indexOf("a"));
		System.out.println("测试此列表中是否没有元素;"+linkedList.isEmpty());
		linkedList.remove();//找到并移除此列表的头（第一个元素）
		linkedList.remove(2); //移除指定下标元素
//		linkedList.removeAll(linkedList); 移除所有集合内元素
		
		//打印 linkedList 集合
		for(String str:linkedList)
		{
			System.out.print(str);
		}
		System.out.println();
		System.out.println("-----------------------set-----------------------------");
		return linkedList;
	}
	/*
	 * Set是一种不包含重复的元素的Collection，即任意的两个元素e1和e2都有e1.equals(e2)=false，Set最多有一个null元素。
	 * Set HashSet , TreeSet , LinkedHashSet(外部按成员的插入顺序遍历成员)
	 * ArrayList arrayList = new ArrayList(set); 
	 */ 
	public Set<String> toSet(Set<String> set)
	{
		/*
		 * HashSet
		 */
		HashSet<String> hashSet = new HashSet<String>();
		hashSet.add("hashSet");
		hashSet.add("H");
		hashSet.add("H");
		System.out.println("isEmpty="+hashSet.isEmpty());
		System.out.println("size="+hashSet.size());
		System.out.println("contains:"+hashSet.contains("hashSet"));
//		hashSet.removeAll(hashSet);
		/*
		 * 遍历集合 hashSet
		 */
		Iterator it = hashSet.iterator();
		while(it.hasNext())
		{
			System.out.print(it.next().toString());
		}
		System.out.println("\n"+"----------------------");
		for(String str:hashSet)
		{
			System.out.println(str);
		}
		/*
		 * LinkedHashSet
		 */
		LinkedHashSet<String> lhs = new LinkedHashSet<String>();
		lhs.add("1");
		lhs.add("3");
		lhs.add("8");
		lhs.add("1");
		lhs.add("3");
		lhs.add("3");
		for(String str:lhs)
		{
			System.out.println(str);
		}
		return set;
	}
	/*
	 * 请注意，Map没有继承Collection接口
	 * Map提供key到value的映射
	 * 一个Map中不能包含相同的key
	   每个key只能映射一个 value
	    Map接口提供3种集合的视图
	    Map的内容可以被当作一组key集合，一组value集合，或者一组key-value映射。
	 */
	public Map<String,String> toMap(Map<String,String> map)
	{
		/*
		 * hashMap
		 * HashMap是非同步的，并且允许null，即null value和null key。
		 */
		System.out.println("\n"+"------------map------------");
		Map<String , String > hashMap = new HashMap<String, String>();
		hashMap.put("a","valueA");
		hashMap.put("b","valueB");
		hashMap.put("c","valueC");
		System.out.println("hashMap.containsKey(\"a\")="+hashMap.containsKey("a"));
		System.out.println("hashMap.containsValue(\"valueA\")="+hashMap.containsValue("valueA"));
		System.out.println("hashMap.get(\"b\")="+hashMap.get("b"));
		// 遍历 hashMap
		Iterator it = hashMap.entrySet().iterator();
		while(it.hasNext())
		{
			System.out.println(it.next());
		}
		/*
		 * HashTable 同步
		 * 这里就不举例啦
		 */
		
		return map;
	}
	public static void main(String[] args) {
		CollectionTest collectionTest = new CollectionTest();
		/*
		 * 声明公用数据
		 */
				String[] array = 
					new String[]{"a","b","c","d","e","f","g"};
//		数组转换成集合  (集合转换数组 toArray() )	
		collectionTest.toArrayList(new ArrayList<String>(Arrays.asList(array)));
		collectionTest.toLinkedList(new LinkedList<String>(Arrays.asList(array)));
		collectionTest.toSet(new HashSet<String>(Arrays.asList(array))); // -list => set
		collectionTest.toMap(new HashMap<String,String>());
	}
/*
 *
 <error-page> 
        <error-code>404</error-code> 
        <location>/error.jsp</location> 
 </error-page>

 <error-page> 
        <exception-type>java.lang.NullPointerException</exception-type> 
        <location>/error.jsp</location> 
 </error-page>
 */
}

线性表，链表，哈希表是常用的数据结构，在进行Java开发时，JDK已经为我们提供了一系列相应的类来实现基本的数据结构。这些类均在java.util包中。本文试图通过简单的描述，向读者阐述各个类的作用以及如何正确使用这些类。

Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│　└Stack
└Set HashSet , TreeSet , LinkedHashSet
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时，客户端代码不用改变。这就是针对抽象编程。

同步性
Vector 是同步的。这个类中的一些方法保证了Vector中的对象是线程安全的。而ArrayList则是异步的，因此ArrayList中的对象并不是线程安全 的。因为同步的要求会影响执行的效率，所以如果你不需要线程安全的集合那么使用ArrayList是一个很好的选择，这样可以避免由于同步带来的不必要的 性能开销。

数据增长
从内部实现机制来讲ArrayList和Vector都是使用数组(Array)来控制集合中的对象。当你向这两种类型中增加元素的时候，如果元素的数目 超出了内部数组目前的长度它们都需要扩展内部数组的长度，Vector缺省情况下自动增长原来一倍的数组长度， ArrayList是原来的50%,所以最后你获得的这个集合所占的空间总是比你实际需要的要大。所以如果你要在集合中保存大量的数据那么使用 Vector有一些优势，因为你可以通过设置集合的初始化大小来避免不必要的资源开销。
使用模式
在ArrayList和Vector中，从一个指定的位置（通过索引）查找数据或是在集合的末尾增加、移除一个元素所花费的时间是一样的，这个时间我们用 O(1)表示。但是，如果在集合的其他位置增加或移除元素那么花费的时间会呈线形增长：O(n-i)，其中n代表集合中元素的个数，i代表元素增加或移除 元素的索引位置。为什么会这样呢？以为在进行上述操作的时候集合中第i和第i个元素之后的所有元素都要执行位移的操作。这一切意味着什么呢？

这意味着，你只是查找特定位置的元素或只在集合的末端增加、移除元素，那么使用Vector或ArrayList都可以。如果是其他操作，你最好选择其他 的集合操作类。比如，LinkList集合类在增加或移除集合中任何位置的元素所花费的时间都是一样的?O(1)，但它在索引一个元素的使用缺比较慢－O (i),其中i是索引的位置.使用 ArrayList也很容易，因为你可以简单的使用索引来代替创建iterator对象的操作。LinkList也会为每个插入的元素创建对象，所有你要 明白它也会带来额外的开销。
最后，在《Practical Java》一书中Peter Haggar建议使用一个简单的数组（Array）来代替Vector或ArrayList。尤其是对于执行效率要求高的程序更应如此。因为使用数组 (Array)避免了同步、额外的方法调用和不必要的重新分配空间的操作。

Java基本概念：集合类（Collection） List/Set/Map... 的区别和联系
Collection：List、Set
Map：HashMap、HashTable
如何在它们之间选择
一、Array ， Arrays
Java所有“存储及随机访问一连串对象”的做法，array是最有效率的一种。
1、效率高，但容量固定且无法动态改变。
array还有一个缺点是，无法判断其中实际存有多少元素，length只是告诉我们array的容量。
2、Java中有一个Arrays类，专门用来操作array。
    arrays中拥有一组static函数，equals()：比较两个array是否相等。array拥有相同元素个数，且所有对应元素两两相等。
fill()：将值填入array中。
sort()：用来对array进行排序。
binarySearch()：在排好序的array中寻找元素。
System.arraycopy()：array的复制。

二、Collection ， Map
若撰写程序时不知道究竟需要多少对象，需要在空间不足时自动扩增容量，则需要使用容器类库，array不适用。
1、Collection 和 Map 的区别
容器内每个为之所存储的元素个数不同。
Collection类型者，每个位置只有一个元素。
Map类型者，持有 key-value pair，像个小型数据库。
2、各自旗下的子类关系
Collection
    --List：将以特定次序存储元素。所以取出来的顺序可能和放入顺序不同。
          --ArrayList / LinkedList / Vector
    --Set ： 不能含有重复的元素
          --HashSet / TreeSet
Map
    --HashMap
    --HashTable
    --TreeMap
3、其他特征
* List，Set，Map将持有对象一律视为Object型别。
* Collection、List、Set、Map都是接口，不能实例化。
   继承自它们的 ArrayList, Vector, HashTable, HashMap是具象class，这些才可被实例化。
* vector容器确切知道它所持有的对象隶属什么型别。vector不进行边界检查。

三、Collections
Collections是针对集合类的一个帮助类。提供了一系列静态方法实现对各种集合的搜索、排序、线程完全化等操作。
相当于对Array进行类似操作的类——Arrays。
如，Collections.max(Collection coll); 取coll中最大的元素。
    Collections.sort(List list); 对list中元素排序
四、如何选择？
1、容器类和Array的区别、择取
   * 容器类仅能持有对象引用（指向对象的指针），而不是将对象信息copy一份至数列某位置。
   * 一旦将对象置入容器内，便损失了该对象的型别信息。
2、* 在各种Lists中，最好的做法是以ArrayList作为缺省选择。当插入、删除频繁时，使用LinkedList()；Vector总是比ArrayList慢，所以要尽量避免使用。
   * 在各种Sets中，HashSet通常优于HashTree（插入、查找）。只有当需要产生一个经过排序的序列，才用TreeSet。
     HashTree存在的唯一理由：能够维护其内元素的排序状态。
* 在各种Maps中:HashMap用于快速查找。
* 当元素个数固定，用Array，因为Array效率是最高的。
结论：最常用的是ArrayList，HashSet，HashMap，Array。
注意：
1、Collection没有get()方法来取得某个元素。只能通过iterator()遍历元素。
2、Set和Collection拥有一模一样的接口。
3、List，可以通过get()方法来一次取出一个元素。使用数字来选择一堆对象中的一个，get(0)...。(add/get)
4、一般使用ArrayList。用LinkedList构造堆栈stack、队列queue。
5、Map用 put(k,v) / get(k)，还可以使用containsKey()/containsValue()来检查其中是否含有某个key/value。
   HashMap会利用对象的hashCode来快速找到key。
    * hashing
       哈希码就是将对象的信息经过一些转变形成一个独一无二的int值，这个值存储在一个array中。
       我们都知道所有存储结构中，array查找速度是最快的。所以，可以加速查找。 发生碰撞时，让array指向多个values。即，数组每个位置上又生成一个梿表。
6、Map中元素，可以将key序列、value序列单独抽取出来。
使用keySet()抽取key序列，将map中的所有keys生成一个Set。
使用values()抽取value序列，将map中的所有values生成一个Collection。
为什么一个生成Set，一个生成Collection？那是因为，key总是独一无二的，value允许重复。

Collection List Set Map 区别记忆

这些都代表了Java中的集合，这里主要从其元素是否有序，是否可重复来进行区别记忆，以便恰当地使用，当然还存在同步方面的差异，见上一篇相关文章。

List 接口对Collection进行了简单的扩充，它的具体实现类常用的有ArrayList和LinkedList。你可以将任何东西放到一个List容器 中，并在需要时从中取出。ArrayList从其命名中可以看出它是一种类似数组的形式进行存储，因此它的随机访问速度极快，而LinkedList的内 部实现是链表，它适合于在链表中间需要频繁进行插入和删除操作。在具体应用时可以根据需要自由选择。前面说的Iterator只能对容器进行向前遍历，而 ListIterator则继承了Iterator的思想，并提供了对List进行双向遍历的方法。

Set接口也是 Collection的一种扩展，而与List不同的时，在Set中的对象元素不能重复，也就是说你不能把同样的东西两次放入同一个Set容器中。它的常 用具体实现有HashSet和TreeSet类。HashSet能快速定位一个元素，但是你放到HashSet中的对象需要实现hashCode()方 法，它使用了前面说过的哈希码的算法。而TreeSet则将放入其中的元素按序存放，这就要求你放入其中的对象是可排序的，这就用到了集合框架提供的另外 两个实用类Comparable和Comparator。一个类是可排序的，它就应该实现Comparable接口。有时多个类具有相同的排序算法，那就 不需要在每分别重复定义相同的排序算法，只要实现Comparator接口即可。集合框架中还有两个很实用的公用类：Collections和Arrays。Collections提供了对一个Collection容器进行诸如排序、复制、查找和填充等一些非常有用的方法，Arrays则是对一 个数组进行类似的操作。

Map是一种把键对象和值对象进行关联的容器，而一个值对象又可以是一个Map，依次类推，这样就可 形成一个多级映射。对于键对象来说，像Set一样，一个Map容器中的键对象不允许重复，这是为了保持查找结果的一致性;如果有两个键对象一样，那你想得 到那个键对象所对应的值对象时就有问题了，可能你得到的并不是你想的那个值对象，结果会造成混乱，所以键的唯一性很重要，也是符合集合的性质的。当然在使 用过程中，某个键所对应的值对象可能会发生变化，这时会按照最后一次修改的值对象与键对应。对于值对象则没有唯一性的要求。你可以将任意多个键都映射到一 个值对象上，这不会发生任何问题（不过对你的使用却可能会造成不便，你不知道你得到的到底是那一个键所对应的值对象）。Map有两种比较常用的实现： HashMap和TreeMap。HashMap也用到了哈希码的算法，以便快速查找一个键，TreeMap则是对键按序存放，因此它便有一些扩展的方 法，比如firstKey(),lastKey()等，你还可以从TreeMap中指定一个范围以取得其子Map。键和值的关联很简单，用pub (Object key,Object value)方法即可将一个键与一个值对象相关联。用get(Object key)可得到与此key对象所对应的值对象。