集合

一、集合框架

1.集合框架設(shè)計(jì)的目標(biāo)

• 該框架必須是高性能的。基本集合(動(dòng)態(tài)數(shù)組、鏈表、樹、哈希表)的實(shí)現(xiàn)也必須是高效的。
• 該框架允許不同類型的集合，以類似的方式工作，具有高度的互操作性。
• 對(duì)一個(gè)集合的擴(kuò)展和適應(yīng)必須是簡(jiǎn)單的。

2.集合框架的類型

• 一種是集合(Collection)，存儲(chǔ)一個(gè)元素集合
• 另一種是圖(Map),存儲(chǔ)鍵/值(key-value)對(duì)映射

3.集合框架包含的內(nèi)容

• 接口:是代表集合的抽象數(shù)據(jù)類型。例如Collection、List、Set、Map等。之所以定義為接口，是為了以不同的方式操作集合對(duì)象。
• 實(shí)現(xiàn)(類):是集合接口的具體實(shí)現(xiàn)。從本質(zhì)上面講他是可以重復(fù)的數(shù)據(jù)接口，例如ArraryList,LinkedList,Hashset,HashMap。
• 算法:是實(shí)現(xiàn)集合接口對(duì)象里的方法執(zhí)行一些有用的計(jì)算。例如搜索，計(jì)算。這些算法被稱為多態(tài)，那是因?yàn)橄嗨频姆椒梢栽谙嗨频慕涌谏嫌兄煌膶?shí)現(xiàn)。

4.集合框架的優(yōu)點(diǎn)

• 使用核心集合類降低開發(fā)成本，而非實(shí)現(xiàn)我們自己的集合類
• 隨著使用嚴(yán)格的集合框架類，代碼質(zhì)量得到提高
• 通過使用JDK附帶的集合類，可以降低代碼的維護(hù)成本
• 復(fù)用性和可操作性

5.集合框架中泛型有什么優(yōu)點(diǎn)

• jdk1.5之后引入泛型，所有集合的接口和實(shí)現(xiàn)都大量的使用了它，泛型允許我們?yōu)榧咸峁┮粋€(gè)可以容納的對(duì)象集合。因此你添加其它任何類型的任何元素，他會(huì)在編譯時(shí)候報(bào)錯(cuò)。避免運(yùn)行的時(shí)候出現(xiàn)ClassCastException，他會(huì)在編譯時(shí)候報(bào)錯(cuò)。
• 泛型使得代碼變得整潔。不需要使用顯示轉(zhuǎn)換和使用instanceof操作符。運(yùn)行時(shí)不會(huì)產(chǎn)生泛型檢查類型的字節(jié)碼。

二、集合接口

                SortedSet ss = new TreeSet();
        ss.add("aa");
        ss.add("bb");
        ss.add("aa");
        ss.add("ee");
        ss.add("dd");
        System.out.println("SortedSet-->,"+ss); // SortedSet-->,[aa, bb, dd, ee]
        System.out.println("first-->,"+ss.first());// first-->,aa
        System.out.println("end-->,"+ss.last()); // end-->,ee
        System.out.println("spliterator-->"+ss.spliterator()); //Java8新增，生成Spliterator接口

    public static void testMapEntry() {
        Map<String, Object> map = new HashMap<>();
        map.put("hah", "11");
        map.put("hehe", "22");
        map.put("xixi", "33");

        for (String key : map.keySet()) {
            System.out.println("key:" + key + ",value:" + map.get(key));
        }

        Iterator<Map.Entry<String, Object>> it = map.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry<String, Object> entry = it.next();
            System.out.println("key:" + entry.getKey() + ",value:" + entry.getValue());
        }

        // 大容量時(shí)
        for(Map.Entry<String,Object> entry:map.entrySet()){
            System.out.println("key:" + entry.getKey() + ",value:" + entry.getValue());
        }
    }

// Enumeration用法
public static void testEnumeration() {
    Enumeration<String> days ;
    Vector<String> list = new Vector<>();
    list.add("monday");
    list.add("tuesday");
    list.add("wednesday");
    days = list.elements();
    while (days.hasMoreElements()){
      System.out.println(days.nextElement());
    }
}

三、集合實(shí)現(xiàn)類

Java提供了一套實(shí)現(xiàn)Collection接口的標(biāo)準(zhǔn)集合類。一些具體的類可以直接拿來使用。另一些抽象類，提供了接口的部分實(shí)現(xiàn)

java.util包中定義的類

四、迭代器(Iterator)

    Iteratior接口，提供了很多對(duì)集合元素進(jìn)行迭代的方法。每一個(gè)集合都包含了可以返回迭代器實(shí)例的迭代方法。迭代器可以在迭代的過程中刪除底層集合迭代的元素，不可以直接調(diào)用集合的 **#remove()**方法刪除，可以通過迭代器的**#remove()**方法刪除

1.Iteator和ListIteratio區(qū)別

• Iterator可以來遍歷List和Set集合，而ListIterator只可以對(duì)List進(jìn)行遍歷
• Iterator對(duì)集合只能是前向遍歷，ListIterator既可以向前也可以向后
• ListIterator繼承了Iterator接口，并包含其他功能增加元素#add(),替換元素#set(E e),獲取前一個(gè)元素#previousIndex()，后一個(gè)元素的索引#nextIndex()等。

    public static void testListIterator(){
        List<String> list = new ArrayList<>();
        list.add("a");
        list.add("b");
        list.add("c");
        list.add("d");
        list.add("e");
        ListIterator iterator = list.listIterator();
        while (iterator.hasNext()){
            if(iterator.nextIndex()==3){
                iterator.set("3");
            }
            System.out.print(iterator.next()+"--");
        }
        iterator.add("f");
        iterator.add("g");
        System.out.println(list);
    }
// print  a--b--c--d--e--[a, b, 3, d, e, f, g]

2.快速失敗(fail-fast)和安全失敗(fail-safe)區(qū)別

    差別在于ConcurrentModification異常:

• 快速失敗:當(dāng)你在迭代一個(gè)集合的時(shí)候，如果有另一個(gè)線程在訪問并且修改這個(gè)集合，就會(huì)拋出ConcurrentModification異常，在java.util包中都是快速失敗
• 安全失敗:當(dāng)你在迭代的時(shí)候回去底層集合做一個(gè)拷貝，所以在修改的時(shí)候不會(huì)受影響，不會(huì)拋出ConcurrentModification異常，在java.util.concurrent包中都是安全失敗的

五、區(qū)別

1.List和Set區(qū)別

• List儲(chǔ)存有序可重復(fù)的元素，Set存儲(chǔ)無序不可重復(fù)元素
• Set檢索效率低下，刪除和插入效率高，插入和刪除不會(huì)改變?cè)匚恢?實(shí)現(xiàn)類有HashSet,TreeSet)
• List和數(shù)組類似，可以動(dòng)態(tài)增長(zhǎng)，根據(jù)實(shí)際存儲(chǔ)數(shù)據(jù)的長(zhǎng)度自動(dòng)增長(zhǎng)list的長(zhǎng)度。檢索元素效率高，插入刪除效率低，因?yàn)闀?huì)引起其他元素位置的改變

2.List和Map區(qū)別

• List是對(duì)象集合，允許對(duì)象重復(fù)
• Map是鍵值對(duì)集合，key不允許重復(fù)

3.Array和ArrayList區(qū)別

• Array可以容納基本數(shù)據(jù)類型和對(duì)象,而ArrayList只能容納對(duì)象
• Array是指定大小的，而ArrayList大小是固定的，而且可自動(dòng)擴(kuò)容。
• Array沒有提供ArrayList那么多功能，如add,removeAll,Iterator等方法

Array在以下情況下，會(huì)更適用

• 1.多維數(shù)組使用array[][][][]比list好用
• 2.如果列表大小已經(jīng)指定，大部分情況下存儲(chǔ)或者遍歷他們
• 3.對(duì)于遍歷基本數(shù)據(jù)結(jié)構(gòu)類型，盡管Collections使用自動(dòng)裝箱來減輕編碼任務(wù)，在指定大小的基本類型的列表上工作也會(huì)變得很慢。

4.ArrayList和LinkedList

• 	優(yōu)點(diǎn)	缺點(diǎn)	適用場(chǎng)景
  ArrayList	ArrayList是實(shí)現(xiàn)了基于動(dòng)態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)，因?yàn)榈刂愤B續(xù)，一旦存儲(chǔ)好了，查詢效率會(huì)比較高(在內(nèi)存里是連續(xù)放的)	因?yàn)榈刂愤B續(xù)，ArrayList要移動(dòng)數(shù)據(jù)，所以刪除和插入操作小路比較低	當(dāng)需對(duì)數(shù)據(jù)進(jìn)行隨機(jī)訪問時(shí)，選用ArrayList，查詢效率高
  LinkedList	LinkedList是基于鏈表的數(shù)據(jù)結(jié)構(gòu)，地址是任意的，所以在開辟新的空間的時(shí)候不需要等一個(gè)連續(xù)的地址，對(duì)于新增和刪除操作，LinkedList優(yōu)勢(shì)較大，LinkedList是用于頭尾操作和插入指定位置的操作。	LinkedList需要移動(dòng)指針，查詢操作效率較低	需要對(duì)數(shù)據(jù)進(jìn)行多次增加，刪除，編輯的時(shí)候，采用LInkedList

5.ArrayList和Vector

• 1.Vector是線程安全的，線程安全就是說多線程訪問同一代碼，不會(huì)產(chǎn)生不確定結(jié)果，而ArrayList不是。Vector類源碼中可以看到，多個(gè)方法都是通過synchronized進(jìn)行修飾，這樣就導(dǎo)致效率上無法和ArrayList相比較。

Vector是一種老的動(dòng)態(tài)數(shù)組，是線程同步的，效率低，一般不推薦使用。

• 2.兩個(gè)都是采用線性連續(xù)空間存儲(chǔ)，但是當(dāng)空間不足時(shí)，兩個(gè)類的增加方式是不通的。

//ArrayList.java  1.5倍擴(kuò)容
  private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
//Vector.java  
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

• 3.Vector可以設(shè)置增長(zhǎng)因子，ArrayList 不可以。// Vector v = new Vector(3,2);

 public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement; // 增長(zhǎng)因子
 }

使用場(chǎng)景:

1.Vector是線程同步的，線程安全，效率低，ArrayList是非線程同步的，不安全，如不考慮線程安全使用ArrayList效率更高，實(shí)際情況如果需要多線程反問數(shù)組，使用CopyOnWriteArrayList

2.如果集合中的元素的數(shù)目大于目前集合數(shù)組的長(zhǎng)度，在集合中使用數(shù)據(jù)量較大的數(shù)據(jù)，用Vector有一定優(yōu)勢(shì)。這種情況下使用LinkedList更合適。

6.HasMap和Hashtable

• 1.Hashtable是繼承Dictionary，HashMap繼承的是java2.0的Map接口
• 2.HashMap去掉了Hashtable中的contains方法，而添加了containsKey和containsValue方法。
• 3.HashMap允許空鍵值，而Hashtable不允許
• 【重點(diǎn)】4.Hashtable是同步的,而HashMap是非同步的，效率上比Hashtable要高。因此HashMap適用于單線程環(huán)境，而Hashtable更適用于多線程環(huán)境。
• 5.HashMap的Iterator迭代器是fail-fase快速失敗的迭代器，而Hashtable的enumerator迭代器不是fail-fast的。
• 【重點(diǎn)】6.Hashtable中的默認(rèn)數(shù)組大小為11，擴(kuò)容方法是old*2+1，HashMap的默認(rèn)大小為16，擴(kuò)容每次為2的指數(shù)大小。

一般不建議使用Hashtable

• 1.Hashtable是遺留類，內(nèi)部很多沒有優(yōu)化和冗余。
• 2.即使在多線程的情況下，現(xiàn)在有同步的ConcurrentHashMap代替，沒有必要因?yàn)槎嗑€程而使用Hashtable。

7.HashSet和HashMap區(qū)別

• 1.Set是線性結(jié)構(gòu)值不能重復(fù)，HashSet是Set的hash實(shí)現(xiàn)，HashSet中值不能重復(fù)是用HashMap中的key來實(shí)現(xiàn)的。
• 2.Map是鍵值對(duì)映射，可以是空鍵值對(duì)。HashMap是Map的hash實(shí)現(xiàn)，key的唯一性是通過key的hashcode的唯一來確定的，value的值則是鏈表結(jié)構(gòu)。

因?yàn)椴煌膋ey可能有相同的hashcode，所以value的值是鏈表結(jié)構(gòu)；

8.HashSet和TreeSet區(qū)別

• 1.HashSet是用一個(gè)hash表的實(shí)現(xiàn)的，因此它的元素時(shí)無序的。添加，刪除和HashSet包含的方法的持續(xù)時(shí)間的復(fù)雜度為O(1)。
• 2.TreeSet是用一個(gè)樹狀結(jié)構(gòu)來實(shí)現(xiàn)的，因此它是有序的。添加、刪除和TreeSet包含的方法的持續(xù)時(shí)間的復(fù)雜度是o(logn)。

如何旋轉(zhuǎn)HashSet和TreeSet

1.對(duì)于在Map中插入，刪除和定位元素這類的操作的時(shí)候，HashMap是最好的選擇。

2.如果需要對(duì)一個(gè)有序的key集合進(jìn)行遍歷，TreeMap是更好的選擇。

9. HashMap和ConcurrentHashMap的區(qū)別

ConcurrentHashMap是線程安全的HashMap的實(shí)現(xiàn)。

• 1.ConcurrentHashMap對(duì)整個(gè)桶數(shù)組進(jìn)行了分割分段(Segment)，然后每一個(gè)分段上都用lock鎖進(jìn)行保護(hù)，相對(duì)于Hashtable的sync關(guān)鍵字的粒度更加精細(xì)了一點(diǎn)，并性能更好。而HashMap沒有鎖機(jī)制，不是線程安全的。JDK1.8之后ConcurrentHashMap啟用了一種全新的方式實(shí)現(xiàn)，利用CAS算法。
• 2.HashMap的鍵值對(duì)允許有null，而ConcurrentHashMap都不允許。

六、問題

1.ArrayList插入1w條數(shù)據(jù)，如何提高效率？

ArrayList的默認(rèn)長(zhǎng)度為10，要插入大量數(shù)據(jù)時(shí)候，需要不斷去擴(kuò)容，擴(kuò)容是非常影響性能的，現(xiàn)在數(shù)據(jù)大小明確，所以可以初始化的時(shí)候設(shè)置ArrayList的容量

    private static void testArrayListContains() {
        Long t1 = System.currentTimeMillis();
        List<Integer> list1 = new ArrayList<Integer>();
        for (int i = 0; i < 100000; i++) {
            list1.add(i);
        }
        Long t2 = System.currentTimeMillis();
        System.out.println("第一種耗時(shí)" + (t2 - t1) + "ms");
        Long t3 = System.currentTimeMillis();
        List<Integer> list2 = new ArrayList<Integer>(100000);
        for (int i = 0; i < 100000; i++) {
            list2.add(i);
        }
        Long t4 = System.currentTimeMillis();
        System.out.println("第2種耗時(shí)" + (t4 - t3) + "ms");
    }
// 第一種耗時(shí)16ms
// 第2種耗時(shí)9ms

2.ConcurrentHashMap為何讀不用加鎖

JDK1.7

• 1).HashEntry中的key、hash、next均為final類型，只能表頭插入、刪除節(jié)點(diǎn)
• 2).HashEntry類的value域被聲明為volatile型
• 3).不允許null作為鍵和值，當(dāng)讀線程讀到一個(gè)HashEntry的value域的值為null的時(shí)候，便知道產(chǎn)生了沖突-發(fā)生了重排序現(xiàn)象(put設(shè)置新value對(duì)象的字節(jié)碼指令，重排序)，需要加鎖后重新讀入這個(gè)新的value值

JDK1.8

• 1.Node的val和next均為volatile型
• 2.tabAt和casTabAt對(duì)應(yīng)的unsafe操作實(shí)現(xiàn)了volatile語(yǔ)義

3.list中可以存放重復(fù)字符串，如何刪除某個(gè)字符串

• 1.調(diào)用iterator相關(guān)方法刪除，
• 2.倒刪，防止正序刪除導(dǎo)致的數(shù)組重排，index跳過數(shù)組等問題