- 1.Collection接口
- 2.List接口
- 2.1ArrayList
- 2.2LinkedList
- 2.3Vector
- 2.4Stack
- 3.Set接口
- 4.Map接口
- 4.1HashMap
- 4.2Hashtable
- 4.3TreeMap
- 4.4WeakHashMap
- 5.Fail-Fast機(jī)制簡(jiǎn)單了解
- 6.遍歷集合代碼示例
(親愛(ài)的你，如果知道簡(jiǎn)書(shū)上如何制作頁(yè)內(nèi)可跳轉(zhuǎn)的目錄，麻煩分享一下披蕉，謝謝楷掉！)
<h6 id="1">1. Collection接口</h6>
Collection接口是java集合類(lèi)最基本的接口懒叛，而Collections是針對(duì)集合類(lèi)的一個(gè)幫助類(lèi)闰歪，他提供了一系列的靜態(tài)方法實(shí)現(xiàn)對(duì)各種集合的搜索畜挨、排序贰盗、線程安全化等操作许饿，對(duì)ArrayList、LinkedList安全化也是借助該工具類(lèi)
List和Set接口是繼承自Collection接口的子接口舵盈，對(duì)于集合類(lèi)中的boolean add(Object o)方法陋率，返回的布爾值不表示添加的成功與否球化，而是表示執(zhí)行add()操作后，集合的內(nèi)容（元素的數(shù)量瓦糟、位置）是否被改變了筒愚，其余addAll、remove菩浙、removeAll巢掺、remainAll方法的返回值也是如此。
遍歷集合可以使用集合類(lèi)本身提供的iterator()方法芍耘，該方法返回當(dāng)前集合類(lèi)的迭代子址遇，該迭代子是采用工廠方法產(chǎn)生的，典型的用法如下：
Iterator it = collection.iterator();
while(it.hasNext()) {
Object o = it.next();
}
但要確保遍歷過(guò)程順利完成必須保證遍歷過(guò)程中不更改集合中的內(nèi)容斋竞，因此遍歷時(shí)要保證只在一個(gè)線程中使用該集合或者在多線程中對(duì)遍歷代碼進(jìn)行同步處理倔约。
<h6 id = "2">2. List接口</h6>
List是有序的Collection，有序是指元素的次序而非大小順序坝初，同時(shí)也是允許有相同元素的Collection浸剩。實(shí)現(xiàn)List接口的常用類(lèi)有ArrayList、LinkedList鳄袍、Vector绢要、Stack。
<h6 id="2.1">2.1 ArrayList</h6>
擴(kuò)容： ArrayList是動(dòng)態(tài)數(shù)組拗小，可以根據(jù)插入的元素的數(shù)量自動(dòng)擴(kuò)充容量重罪，而使用者不需要關(guān)心它是什么時(shí)候擴(kuò)容的，只要把它當(dāng)成足夠大的數(shù)組來(lái)使用就行了哀九。ArrayList在插入元素的時(shí)候都會(huì)檢查當(dāng)前的數(shù)組大小是否足夠剿配，如果不夠，就會(huì)進(jìn)行擴(kuò)容阅束，然后將原先數(shù)組中的元素全部復(fù)制到新數(shù)組中呼胚，這個(gè)操作比較耗時(shí)，因此在創(chuàng)建ArrayList對(duì)象時(shí)如果能預(yù)估元素的數(shù)量Capactity息裸，最好指定ArrayList的初始容量（過(guò)大則帶來(lái)了空間上的損耗）蝇更。
訪問(wèn)與插入刪除操作： ArrayList可以直接根據(jù)下標(biāo)索引訪問(wèn)元素，因此get()方法是O(1)呼盆，而插入和刪除時(shí)可能需要發(fā)生元素的移動(dòng)年扩，因此add()和remove()方法時(shí)間復(fù)雜度是O(n)。
非線程安全： ArrayList沒(méi)有同步宿亡，屬于非線程安全常遂，在多線程環(huán)境下如果出現(xiàn)多個(gè)線程需要同時(shí)訪問(wèn)ArrayList對(duì)象并且存在修改其中元素的操作時(shí)，需要自行實(shí)現(xiàn)同步機(jī)制或者創(chuàng)建ArrayList實(shí)例時(shí)通過(guò)Collections.synchronizedList(new ArrayList()); 方法返回一個(gè)同步的實(shí)例
<h6 id= "2.2">2.2 LinkedList</h6>
訪問(wèn)與插入刪除操作： LinkedList 內(nèi)部實(shí)現(xiàn)是使用雙向鏈表的方式來(lái)保存元素，因此插入與刪除元素的性能較ArrayList好克胳，但隨機(jī)訪問(wèn)元素就需要遍歷鏈表才能找到平绩，性能上比ArrayList差。因此在需要頻繁隨機(jī)訪問(wèn)元素的情況下建議使用ArrayList漠另，在需要頻繁隨機(jī)插入和刪除的情況下建議使用LinkedList捏雌。
可用來(lái)實(shí)現(xiàn)棧、隊(duì)列笆搓、雙向隊(duì)列：LinkedList增加了addFirst()性湿、addLast()、removeFirst()满败、removeLast()等方法肤频，可以將LinkedList當(dāng)成棧（后進(jìn)先出）、隊(duì)列（先進(jìn)先出）算墨、雙向隊(duì)列來(lái)使用宵荒，但此時(shí)不能使用多態(tài)，因?yàn)長(zhǎng)ist接口沒(méi)有定義這些方法.
非線程安全：LinkedList與ArrayList同樣屬于非線程安全净嘀。
<h6 id="2.3">2.3 Vector</h6>
Vector是ArrayList的線程安全版本报咳，支持多線程訪問(wèn)，默認(rèn)初始容量與ArrayList一樣是10挖藏，擴(kuò)容算法上也不同
<h6 id="2.4">2.4 Stack</h6>
Stack暑刃，即棧結(jié)構(gòu)，其特點(diǎn)是后進(jìn)先出膜眠，繼承自Vector類(lèi)岩臣，所以是順序棧，同時(shí)也是線程安全的宵膨，要使用鏈椥隽常可以使用LinkedList
PS：ArrayList、Vector柄驻、Stack是順序存儲(chǔ)結(jié)構(gòu)，LinkedList是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),都允許插入null元素
<h6 id="3">3. Set接口</h6>
Set是無(wú)序的Collection焙压，同時(shí)也是不允許有相同元素的Collection（這里的相同是指調(diào)用equals方法返回true）鸿脓。接口相當(dāng)于一個(gè)契約，規(guī)定了實(shí)現(xiàn)該接口的類(lèi)需要遵循的行為涯曲，Set接口規(guī)定了其實(shí)現(xiàn)類(lèi)是"元素是不重復(fù)的集合"野哭，而對(duì)順序不做保證，不做限制幻件，有序無(wú)序的實(shí)現(xiàn)都可以拨黔，比如HashSet在保存數(shù)據(jù)的時(shí)候是根據(jù)哈希函數(shù)計(jì)算按照一定順序放入數(shù)組中的，但這個(gè)順序不是用戶(hù)能控制的绰沥，所以對(duì)用戶(hù)來(lái)說(shuō)就是無(wú)序的篱蝇。
又比如Set接口的一個(gè)子接口SortedSet接口就規(guī)定了其中的元素必須是有序的贺待，能按照用戶(hù)指定的方式排序的集合。TreeSet就是SortedSet接口的唯一實(shí)現(xiàn)零截，因此TreeSet就是有序的麸塞。另外一個(gè)常用的Set是LinkedHashSet，是HashSet的子類(lèi)涧衙，迭代訪問(wèn)元素的速度比HashSet快哪工，并且能按插入順序排序（利用鏈表維護(hù)元素的次序），但插入的速度較HashSet慢弧哎。
所有的Set都是線程不安全的雁比，多線程并發(fā)訪問(wèn)情況下需要自行實(shí)現(xiàn)同步控制或者使用Collections的靜態(tài)方法返回安全的實(shí)例。
HashSet的底層是基于HashMap實(shí)現(xiàn)的（LinkedHashSet基于LinkedHashMap撤嫩，TreeSet基于TreeMap）偎捎，其元素其實(shí)是放在了底層HashMap的Key上，而value是一個(gè)Object對(duì)象標(biāo)志非洲，相關(guān)的HashSet的操作也是直接調(diào)用HashMap來(lái)完成的鸭限。
<h6 id="4">4. Map接口（沒(méi)有繼承Collection接口）</h6>
Map是一種"鏈表數(shù)組"的結(jié)構(gòu)，提供key到value的映射两踏。一個(gè)Map中key是唯一的败京，每個(gè)key只能映射一個(gè)value。你也可以把Map看出一組Key集合或一組Value集合或一組Key-Value集合梦染。
HashMap存儲(chǔ)鍵值對(duì)赡麦。當(dāng)程序試圖將一個(gè)key-value對(duì)放入 HashMap 中時(shí)，程序首先根據(jù)該key的hashCode()返回值決定該Entry的存儲(chǔ)位置：如果兩個(gè)Entry的key的hashCode()返回值相同帕识，那它們的存儲(chǔ)位置相同泛粹。如果這兩個(gè)Entry的key通過(guò)equals比較返回true，新添加Entry的value將覆蓋集合中原有Entry的 value肮疗，但key不會(huì)覆蓋晶姊。如果這兩個(gè)Entry的key通過(guò)equals比較返回false，新添加的Entry將與集合中原有Entry形成Entry 鏈伪货，而且新添加的 Entry 位于 Entry 鏈的頭部(使用頭插法插入效率會(huì)比較高们衙，尾插法需要遍歷鏈表或需要記住鏈尾)。常用的Map有HashMap碱呼、Hashtable蒙挑。
<h6 id="4.1">4.1 HashMap</h6>
HashMap是非線程安全的，允許Key和Value都為空愚臀，其Key使用的哈希值是內(nèi)部另外實(shí)現(xiàn)的方法計(jì)算而來(lái)忆蚀，默認(rèn)初始容量是16，當(dāng)容量達(dá)到負(fù)載因子大小時(shí)重新分配空間進(jìn)行再散列擴(kuò)容，而且一定是以2的指數(shù)去擴(kuò)容馋袜。
迭代HashMap的時(shí)間復(fù)雜度跟其容量是成正比關(guān)系男旗，如果把HashMap的容量設(shè)置得過(guò)高，或者負(fù)載因子（load factor）過(guò)低會(huì)使迭代性能下降 桃焕。
遍歷一個(gè)map常用的有兩種方式：
//方式一：先獲取key,然后根據(jù)key去獲取value剑肯，需要遍歷兩次不建議使用
Iterator i = map.keySet().iterator();
while(i.hasNext()) {
Object key = i.next();
Object value = map.get(key);
}
//方式二：只遍歷一次，建議使用這種方式
Iterator i = map.entrySet().iterator();
while(i.hasNext()) {
Entry entry = (Entry) i.next();
Object key = entry.getKey();
Object value = entry.getValue();
}
<h6 id="4.2">4.2 Hashtable</h6>
Hashtable是HashMap的線程安全版本观堂，其不同之處在于其默認(rèn)大小是11让网，不允許空的Key和Value，存儲(chǔ)時(shí)使用的hash值是直接使用對(duì)象的hashCode师痕，再散列擴(kuò)容時(shí)增長(zhǎng)的方式是原本的長(zhǎng)度*2+1溃睹。
<h6 id="4.3">4.3 TreeMap</h6>
TreeMap是jdk提供的唯一有序Map實(shí)現(xiàn)類(lèi),是利用紅黑樹(shù)來(lái)實(shí)現(xiàn)的,所以其最壞的插入、刪除胰坟、查找的時(shí)間復(fù)雜度是O(logn);
TreeMap默認(rèn)情況下是根據(jù)key的自然順序進(jìn)行排序因篇，也可以在構(gòu)造函數(shù)中指定自己的比較器,同時(shí)它也是線程非安全的，支持fail-fast機(jī)制笔横。
TreeMap的鍵值不能為空竞滓，value值可以為空
<h6 id="4.4">4.4 WeakHashMap</h6>
WeakHashMap與HashMap最大的不同是WeakHashMap的鍵是弱鍵（WeakReference）,當(dāng)某個(gè)鍵不再被使用時(shí)，會(huì)從WeakHashMap中自動(dòng)移除吹缔。
WeakHashMap是通過(guò) WeakReference 和 ReferenceQueue (隊(duì)列)實(shí)現(xiàn)的：
- 新建WeakHashMap,將key-value添加進(jìn)WeakHashMap中商佑，即保存進(jìn)WeakHashMap的table數(shù)組中
- 當(dāng)某個(gè)鍵不再被其他對(duì)象引用后，在GC進(jìn)行回收的時(shí)候會(huì)將該弱鍵回收厢塘，并同時(shí)將該弱鍵加入到ReferenceQueue中,即queue屬性中
- 當(dāng)我們?cè)俅尾僮鱓eakHashMap時(shí)茶没，會(huì)先同步table和queue，table保存了全部的鍵值對(duì)晚碾，而queue中保存的是被GC回收的鍵值對(duì)抓半，即刪除table中被GC回收的鍵值對(duì)。
<h6 id="5"> Fail-Fast機(jī)制簡(jiǎn)單了解</h6>
Fail-Fast機(jī)制(快速失敗機(jī)制)是一種集合類(lèi)的錯(cuò)誤檢測(cè)機(jī)制,直白的說(shuō)就是當(dāng)出現(xiàn)遍歷和修改操作同時(shí)進(jìn)行時(shí)能快速的報(bào)錯(cuò)格嘁，比如當(dāng)多個(gè)線程對(duì)同一個(gè)集合進(jìn)行操作時(shí)笛求，如果有線程對(duì)該集合進(jìn)行添加或刪除元素的操作 ,那么其他線程在訪問(wèn)該集合時(shí)就會(huì)拋出ConcurrentModificationException異常,產(chǎn)生Fail-Fast事件; 或者當(dāng)使用Iterator遍歷集合時(shí)對(duì)該集合進(jìn)行添加或刪除也會(huì)發(fā)生Fail-Fast事件。
Fail-Fast與是否線程安全無(wú)直接關(guān)系
產(chǎn)生Fail-Fast事件的原因：AbstractList中定義了一個(gè)modCount和expectedModCount屬性糕簿，都表示該集合對(duì)象元素個(gè)數(shù)修改的次數(shù)涣易，只要涉及到修改集合中的元素個(gè)數(shù)時(shí),都會(huì)改變他們的值,在使用迭代器遍歷的時(shí)候需要判斷他們是否相等，如果不相等就會(huì)拋出ConcurrentModificationException冶伞，而在獲取迭代子之后迭代子中的expectedModCount就不會(huì)再發(fā)生改變了。
如果在多線程環(huán)境下使用fail-fast機(jī)制的集合步氏，建議使用java.util. concurrent包下的線程安全類(lèi)去取代java .util包下的類(lèi)响禽。因?yàn)檫@些類(lèi)不會(huì)產(chǎn)生Fail-Fast事件：CopyOnWriteArrayList不會(huì)拋ConcurrentModificationException，是因?yàn)樗懈淖兤鋬?nèi)容的操作（add、remove芋类、clear等）隆嗅，都會(huì)copy一份現(xiàn)有數(shù)據(jù)，在現(xiàn)有數(shù)據(jù)上修改好侯繁，再把原有數(shù)據(jù)的引用改成指向修改后的數(shù)據(jù)胖喳，而不是在讀的時(shí)候copy。
<h6 id="6">6. 遍歷集合代碼示例</h6>
package com.liang.list;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/**
* @Description 遍歷ArrayList有三種方式：迭代器訪問(wèn)贮竟、數(shù)組下標(biāo)訪問(wèn)丽焊、for-each循環(huán)（底層也是迭代器）
* @Date 2016年3月29日 下午3:11:48
*/
public class AccessArrayList {
/**
* 使用迭代器遍歷
*
* @param list
*/
public static void access1(List<Integer> list) {
long begin = System.currentTimeMillis();
Iterator<Integer> i = list.iterator();
while (i.hasNext()) {
i.next();
}
System.out.println("迭代器" + (System.currentTimeMillis() - begin));
}
/**
* 使用list迭代器,專(zhuān)門(mén)用于遍歷list，相比Iterator它新增了額添加咕别、是否存在上一個(gè)元素技健，獲取上一個(gè)元素等方法
*
* @param list
*/
public static void access4(List<Integer> list) {
long begin = System.currentTimeMillis();
Iterator<Integer> i = list.listIterator();
while (i.hasNext()) {
i.next();
}
System.out.println("list迭代器" + (System.currentTimeMillis() - begin));
}
/**
* 使用數(shù)組下標(biāo)遍歷
*
* @param list
*/
public static void access2(List<Integer> list) {
long begin = System.currentTimeMillis();
for (int i = 0; i < list.size(); i++) {
// 這里改變list內(nèi)容不會(huì)產(chǎn)生fail-fast事件
}
System.out.println("數(shù)組下標(biāo)" + (System.currentTimeMillis() - begin));
}
/**
* 使用for-each循環(huán)遍歷
*
* @param list
*/
@SuppressWarnings("unused")
public static void access3(List<Integer> list) {
long begin = System.currentTimeMillis();
for (Integer i : list) {
}
System.out.println("for-each" + (System.currentTimeMillis() - begin));
}
public static void main(String[] args) {
List<Integer> list = new ArrayList<Integer>(10000000);
for (int i = 0; i < 10000000; i++) {
list.add(i);
}
access1(list); // 迭代器
access2(list); // 數(shù)組下標(biāo)遍歷
access3(list); // for-each遍歷
access4(list); // list迭代器
}
}
package com.liang.list;
import java.util.Enumeration;
import java.util.Iterator;
import java.util.List;
import java.util.Vector;
/**
* @Description 1. Vector是ArrayList的線程安全版本，同時(shí)也可作為順序結(jié)構(gòu)的隊(duì)列來(lái)使用
*
* 2. 遍歷Vector有四種方式：for-each循環(huán)惰拱、迭代器雌贱、下標(biāo)索引、使用elements()
* 方法返回Enumeration對(duì)象遍歷
*
* @Date 2016年3月30日 下午2:08:00
*/
public class AccessVector {
/**
* 使用Enumeration對(duì)象遍歷
*
* @param vec
*/
public static void accessWithEnumeration(List<Integer> vec) {
Vector<Integer> v = (Vector<Integer>) vec;
long begin = System.currentTimeMillis();
Enumeration<Integer> e = v.elements();
while (e.hasMoreElements()) {
e.nextElement();
}
System.out.println("use Enumeration: "
+ (System.currentTimeMillis() - begin));
}
public static void main(String[] args) {
List<Integer> vec = new Vector<Integer>();
for (int i = 0; i < 1000000; i++) {
vec.add(i);
}
accessWithEnumeration(vec);
}
}
package com.liang.map;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
/**
* @Description
* HashMap是一個(gè)數(shù)組鏈表的結(jié)構(gòu)（說(shuō)明了當(dāng)發(fā)生哈希沖突時(shí)采用的是“拉鏈法”解決沖突）,即散列表的結(jié)構(gòu)偿短，其每個(gè)鏈表的結(jié)點(diǎn)都是一個(gè)鍵值對(duì)
* 欣孤，每一個(gè)鍵值對(duì)存放的位置由key的哈希值（與數(shù)組的長(zhǎng)度-1）參與哈希函數(shù)運(yùn)算決定。
*
* 完整遍歷Map有兩種方式：1. 使用迭代器遍歷keySet昔逗，然后根據(jù)key去獲取value降传，實(shí)際上發(fā)生了兩次查找遍歷，不建議使用
* 2. 使用迭代器遍歷entrySet纤子，建議使用這種方式搬瑰。
*
* 若只需要獲取value集合，可以使用values()方法遍歷
* @Date 2016年3月30日 下午6:15:18
*/
public class AccessHashMap {
/**
* 使用KeySet的迭代器遍歷
*
* @param map
*/
public static void accessWithKeySet(Map<Integer, Object> map) {
long begin = System.currentTimeMillis();
Iterator<Integer> it = map.keySet().iterator();
while (it.hasNext()) {
Integer key = it.next();
System.out.print(" key = " + key + ", value = " + map.get(key)
+ "\t");
}
System.out.println("\n accessWithKeySet: "
+ (System.currentTimeMillis() - begin));
}
/**
* 使用EntrySet的迭代器遍歷
*
* @param map
*/
public static void accessWithEntrySet(Map<Integer, Object> map) {
long begin = System.currentTimeMillis();
Iterator<Entry<Integer, Object>> it = map.entrySet().iterator();
while (it.hasNext()) {
Entry<Integer, Object> e = it.next();
System.out.print(" key = " + e.getKey() + ", value = "
+ e.getValue() + "\t");
}
System.out.println("\n accessWithEntrySet: "
+ (System.currentTimeMillis() - begin));
}
/**
* 只遍歷value集合
* @param map
*/
public static void accessWithValues(Map<Integer, Object> map) {
long begin = System.currentTimeMillis();
Iterator<Object> it = map.values().iterator();
while (it.hasNext()) {
System.out.print("value = " + it.next() + "\t");
}
System.out.println("\n accessWithValues: "
+ (System.currentTimeMillis() - begin));
}
public static void main(String[] args) {
/**
* HashMap有兩個(gè)參數(shù)影響其性能：初始容量與負(fù)載因子控硼，當(dāng)Map中的Entry數(shù)量大于初始容量與負(fù)載因子之積的時(shí)候會(huì)進(jìn)行“再哈显舐郏”的操作，
* 擴(kuò)大數(shù)組容量卡乾，并重新散列所有Entry翼悴。
*/
Map<Integer, Object> map = new HashMap<Integer, Object>(2000, 0.6f);// 負(fù)載因子默認(rèn)是0.75
for (int i = 1; i < 1000; i++) {
map.put(i, i * 2);
}
map.put(null, null);
accessWithEntrySet(map);
accessWithKeySet(map);
accessWithValues(map);
}
}
