集合的特點：

• 存儲的數(shù)據(jù)量可變
• 存儲的數(shù)據(jù)類型可變（通過泛型可以添加不同類型的數(shù)據(jù)）
• 只能存儲引用類型
  上述三點都是對應(yīng)于數(shù)組的特點伏蚊。

集合的分類：

基本接口collection和map
collection實現(xiàn)了Iterable接口梆掸，包含list氛魁、set赐写、queue
list：可以包含重復(fù)元素恩闻，取出和放入的順序一致
set：不包含重復(fù)元素右蒲，最多包含一個null葫录，取出和放入的順序不一致
queue：
其中collection繼承了Iterable接口着裹，其iterator()方法返回一個迭代器，而該方法乃至迭代器的具體實現(xiàn)在collection的子類中米同。

迭代器是接口的原因骇扇，每種集合的數(shù)據(jù)結(jié)構(gòu)不一樣，其遍歷的實現(xiàn)方式不一樣面粮，所以抽象為接口少孝，真正的實現(xiàn)是以內(nèi)部類方式實現(xiàn)“静裕可參見ArrayList中的iterator()方法稍走。這里作為java多態(tài)和繼承的很好的體現(xiàn)實例

基本方法：

自行查詢api，不過有以下注意的點

• addAll(Collection collection)柴底， 實質(zhì)是將地址值賦值給另一個列表婿脸。
• retainAll(Collection collection)，保留與給定集合中共有的元素似枕，如果集合被改變盖淡，則返回true。
• toArray() 方法凿歼，返回一個包含該集合中所有元素的數(shù)組褪迟，是新建的數(shù)組冗恨，原有集合不會對該數(shù)組產(chǎn)生引用，所以對集合的操作不會影響該數(shù)組味赃。這也是遍歷集合的一種解決方案

關(guān)鍵接口：

• Iterator
  Iterator it = list.iterator();
  遍歷方法除了常見的while(it.hasNext())掀抹，還可以是for循環(huán)

for(Iterator it = list.iterator();it.hasNext();) {
        Student s = (Student) it.next();
        //Do something about s;
}

迭代器遍歷集合時候，除非使用迭代器的remove方法心俗，不能同時對集合進(jìn)行增刪操作傲武，因為迭代器是基于iterator()方法被創(chuàng)建的，后續(xù)對集合的改變不能被同步上城榛。即當(dāng)多個線程揪利，或多個任務(wù)對Collection進(jìn)行操作時，若其中某一個任務(wù)通過Iterator遍歷集合時狠持，同時該集合的內(nèi)容被其他迭代器或者集合自身的方法修改類疟位，會拋出ConcurrentModificationException異常。
此外迭代器中next方法和remove方法是緊緊關(guān)聯(lián)的喘垂，remove是刪除上次調(diào)用next時返回的元素甜刻，所以調(diào)用remove前沒有調(diào)用next是非法的。

為什么要使用迭代器正勒？
不同集合的數(shù)據(jù)結(jié)構(gòu)不一樣得院，比如set，就不能使用for循環(huán)章贞。使用迭代器作為接口祥绞，在不同集合中根據(jù)集合數(shù)據(jù)結(jié)構(gòu)實現(xiàn)遍歷的功能。此外阱驾，Iterator訪問方式把對不同集合類的訪問邏輯抽象出來就谜，使得不用暴露集合內(nèi)部的結(jié)構(gòu)而達(dá)到循環(huán)遍歷集合的效果怪蔑。再者里覆，Iterator能夠讓訪問者同時遍歷并操作列表元素，如使用其remove方法缆瓣，如果在fori循環(huán)中遍歷并刪除元素喧枷，會導(dǎo)致指針偏移。

• List
  有序的collection（存儲和取出順序一致）弓坞，用戶可以控制插入的位置隧甚，根據(jù)元素索引訪問元素，允許重復(fù)的元素渡冻。

• ListIterator list特有的迭代器戚扳，繼承了Iterator迭代器，特有逆向遍歷功能和其他新特性族吻，但是使用前必須先經(jīng)過過正向遍歷帽借，所以實際用處不大珠增。
• list集合特有用for(int i = 0;i < list.size(); x++)循環(huán)功能

根據(jù)之前敘說的迭代器遍歷數(shù)組時修改數(shù)組異常——ConcurrentModificationException砍艾，一種思路蒂教，兩種方案，思路就是將修改和遍歷合并到一個線程脆荷，方案分別是僅僅用迭代器或者僅僅用集合凝垛，實踐中推薦ListIterator，但修改位置受限（見api）蜓谋，而使用for循環(huán)遍歷梦皮，會有隱藏的風(fēng)險：

for(int i = 0;i<arrayList2.size(); i++) {
            Student student = (Student)arrayList2.get(i);
            System.out.println(student.getOfficialName());
            System.out.println(arrayList2.size());
            if(student.getOfficialName().equals("hugo")) {
                arrayList2.remove(1);
            }
        }//此時原來數(shù)組中下標(biāo)為2的元素將不能被訪問到

List的數(shù)據(jù)結(jié)構(gòu)

• ArrayList 底層實現(xiàn)是數(shù)組，查詢快桃焕，增刪慢届氢，線程不安全，效率高
• Vector 底層實現(xiàn)是數(shù)組覆旭，查詢快退子，增刪慢，線程安全型将，效率低
• LinkedList 底層實現(xiàn)是鏈表寂祥，查詢慢，增刪快七兜，線程不安全丸凭，效率高

如果有很多元素的增加刪除，需要用LinkedList腕铸，因為用Arraylist會有大量元素的移動惜犀，且會遇到擴(kuò)容的問題

不建議使用Vector，理由如下

• Vector 對每個方法都加上了鎖狠裹，損耗性能
• 遍歷列表時虽界，為保證同步往往通過將不同的方法整合起來，再加鎖涛菠。Vector同步單個操作的特點并不能保證多線程操作列表時線程安全莉御，此時其鎖就成為了負(fù)擔(dān)
• vector容量達(dá)到上限時其容量增量是100%，ArrayList是50%俗冻，它更耗內(nèi)存

LinkedList有添加元素的特有方法礁叔，add/get~last/first，removeFirst/Last迄薄，Vector也有特有addElement(E obj)琅关、elementAt(int index)、elements()功能讥蔽，被iterator替代

代碼示例： 從列表中抽出重復(fù)項

ArrayList oldList = new TestClass("ss").mArrayList;
        oldList.add("aaaa");
        oldList.add("bbbb");
        oldList.add("aaaa");
        oldList.add("gggg");
        oldList.add("cccc");
        oldList.add("cccc");
//solution 1
        ArrayList<String> newList = new ArrayList<>();
        newList.add((String) oldList.get(0));
        for (int i = 0; i < oldList.size(); i++) {
            boolean shouldAdd = true;
            for (int j = 0; j < newList.size(); j++) {
                if(oldList.get(i).equals(newList.get(j))) {
                    shouldAdd = false;
                }
            }
            if(shouldAdd) {
                newList.add((String) oldList.get(i));
            }
        }
// solution 2
Iterator iterator = oldList.iterator();
        while(iterator.hasNext()) {
            String str = (String) iterator.next();
            if(!newList.contains(str)) {
                newList.add(str);
            }
        }
// solution 3
 for (int i = 0; i < oldList.size() - 1; i++) {
            for (int j = i+1; j < oldList.size(); j++) {
                if(oldList.get(i).equals(oldList.get(j))){
                    oldList.remove(j);
                    y--;
                }
            }
        }

去除重復(fù)元素的方式
//如何利用Comparator工具去除重復(fù)元素涣易？人乓？

用LinkedList創(chuàng)建棧結(jié)構(gòu)的集合

private class MyStack extends LinkedList<String> {
        
        private LinkedList<String> mList;
        
        public MyStack() {
            mList = new LinkedList<>();
        }
        
        public String get() {
            return mList.removeFirst();
        }
        
        public void addFirst(String string) {
            mList.addFirst(string);
        }
        
        public boolean isEmpty() {
            return mList.isEmpty();
        }
    }

• Set
  不包含重復(fù)元素，最多包含一個null都毒，取出和放入的順序不一致
  常見實現(xiàn)類
  HashSet色罚，由一個hash table支持（實際上為hashMap實例），不保證迭代的順序账劲，特別是不保證每次迭代的順序都相同戳护。
  hashSet添加元素流程

public boolean add(E var1) {
        return this.map.put(var1, PRESENT) == null;
//PRESENT是全國人民final的同一代表
    }

當(dāng)你把對象加入HashSet時，HashSet會先計算對象的hashcode值（其實是通過hashCode經(jīng)過位運算獲得的hash值）來判斷對象加入的位置瀑焦，同時也會與其他加入的對象的hashcode值作比較腌且，如果沒有相符的hashcode，HashSet會假設(shè)對象沒有重復(fù)出現(xiàn)榛瓮，直接添加元素铺董。但是如果發(fā)現(xiàn)有相同hashcode值的對象，這時會調(diào)用equals（）方法來檢查hashcode相等的對象是否真的相同禀晓。不同會添加精续，這屬于處理哈希沖突的范疇；相同粹懒，就不能添加重付。

自定義的hashCode方法必須與equals兼容，如果equals方法返回true凫乖，兩個對象的hashCode值必須相同确垫。
先看下面這個例子

我們知道不同的對象地址值不同，哪怕其成員完全一致帽芽，所以它們的hashCode當(dāng)然不一樣删掀，這是上述所有對象都能被添加的原因。但是如果開發(fā)需求類型和成員一致的對象應(yīng)被視為相同导街，即equals方法需要被重寫披泪，這時候hashCode方法也應(yīng)該適配。

LinkedhashSet
鏈表和hash表組成菊匿，用于保證數(shù)據(jù)的有序性和唯一性付呕，底層實現(xiàn)是LinkedHashMap

TreeSet
與散列集類似计福，但有所改進(jìn)跌捆，能夠?qū)υ剡M(jìn)行排序，
兩種排序方式：
自然排序象颖，子類必須實現(xiàn)Comparable接口佩厚，即重寫compareTo方法
public class Stuff implements Comparable
自定義的實現(xiàn)了Comparator接口的類,關(guān)鍵在于重寫其compare方法
TreeSet<Stuff> treeSet = new TreeSet<Stuff>(new StuffComparator<Stuff>());
具體采用哪種方式取決于構(gòu)造器
有的類官方設(shè)定為Comparable接口實現(xiàn)類，可以進(jìn)行自然排序说订，如Integer和String
由此可知抄瓦，不同于HashMap唯一性主要取決于hashCode和equals方法潮瓶，TreeMap&TreeSet的排序結(jié)果主要取決于子元素的對比方式
TreeSet的實現(xiàn)依賴的是TreeMap，TreeMap是基于紅黑樹實現(xiàn)的(一種自平衡的二叉樹)钙姊。

TreeSet的add方法毯辅，實現(xiàn)依靠TreeMap的put方法，過程基本是找到根節(jié)點煞额，然后二選一排序方式思恐，循環(huán)比較最后找到合適插入位置。
獲取元素膊毁，依靠二叉樹里前序遍歷方式遍歷胀莹，
這邊截取put方法中的一段

Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);

依賴TreeSet的添加元素機(jī)制能夠?qū)⑼娉龅尿}操作
將子元素的compareTo方法固定返回一個int值，比如-1婚温，就能讓元素一直添加到父元素的left描焰，實現(xiàn)一個單項鏈表結(jié)構(gòu)。

由此可見栅螟，TreeSet的本質(zhì)是一個TreeMap荆秦，
有序性依賴：二叉樹結(jié)構(gòu)
唯一性依賴：子元素實現(xiàn)的對比方式

實踐中偏向哪種方式——個人傾向重寫Comparator接口，因為比較邏輯和bean對象分離力图，且能使用new Comparator的匿名內(nèi)部類方式讓快捷變換比較邏輯萄凤。

Queue
實現(xiàn)在尾部添加，在頭部刪除一個元素搪哪；對于雙端隊列靡努，可以有效

地同時添加或者刪除元素，不支持在隊列中間增刪元素

Map集合

以鍵值對出現(xiàn)的數(shù)據(jù)結(jié)構(gòu)晓折，Map集合鍵是唯一的惑朦，其數(shù)據(jù)結(jié)構(gòu)與鍵有關(guān)，跟值無關(guān)漓概。
特有的方法有

containsKey();
containsValue(); 
get(Object key); return the value
Collection<V> values() 
keySet() 
put(K key, V value) 除了添加還可以替換同鍵的值;
entrySet() ; Returns a Set view of the mappings contained in this map.

運用舉例

Map<String, String> map = new HashMap();
        map.put("Jay", "Kun");
        map.put("Jolin", "???");
        map.put("kotlin", "java");
//獲取所有鍵
        Set<String> set = map.keySet();
        for (String str :
                set) {
            System.out.println(str+"");
        }
//獲取所有值
Collection<String> collection = map.values();
        for (String str :
                collection) {
            System.out.println(str);
        }
//this set is java.util.HashMap$KeySet
//this collection is java.util.HashMap$Values

//遍歷集合
//solution 1
Set<String> set = map.keySet();
        for (String str :
                set) {
            System.out.println(map.get(str));
        }

//solution 2
Set<Map.Entry<String, String>> entries = map.entrySet();
        for (Map.Entry<String, String> entry :
                entries) {
            System.out.println(entry);
        }

關(guān)鍵實現(xiàn)類
HashMap
hash存儲優(yōu)勢在于：對于沒有實現(xiàn)RandomAccess接口與的集合漾月，當(dāng)忘記了數(shù)據(jù)的位置時，想快速查找一個數(shù)據(jù)很低效胃珍。如果不在意元素的順序梁肿，散列表就可以實現(xiàn)快速查找功能。
hashMap底層實現(xiàn)是hash表觅彰，實質(zhì)是元素為鏈表的數(shù)組吩蔑，我們習(xí)慣把數(shù)組元素稱為桶（比較形象）
hashMap以鍵值對的方式存儲數(shù)據(jù)，關(guān)鍵是key要保持唯一填抬，而value雖然功能上是我們真正想要的數(shù)據(jù)烛芬，但在該數(shù)據(jù)結(jié)構(gòu)的存取中根本沒有考慮value的存在，可以當(dāng)做key的一個附屬品來使用。

hashMap添加元素的過程
當(dāng)你把對象加入hashMap時赘娄，hashMap會先計算對象的hashcode值（其實是通過hashCode經(jīng)過位運算獲得的hash值）來判斷對象加入的位置仆潮，同時也會與其他加入的對象的hashcode值作比較，如果沒有相符的hashcode遣臼，HashSet會假設(shè)對象沒有重復(fù)出現(xiàn)性置，直接添加元素。但是如果發(fā)現(xiàn)有相同hashcode值的對象揍堰，這時會調(diào)用equals（）方法來檢查hashcode相等的對象是否真的相同蚌讼。不同會添加，這屬于處理哈希沖突的范疇个榕；相同篡石，就不能添加。

通過為不同對象生成一個整數(shù)西采，成為hash code（該值能快速生成）凰萨，不同對象擁有不同的散列碼。
java中械馆，散列表用鏈表數(shù)組實現(xiàn)胖眷，每個鏈表被稱為桶，要想查找對象的位置霹崎，首先計算其散列碼珊搀，然后與桶的總數(shù)取余，結(jié)果就是元素所在桶的索引尾菇。
實際開發(fā)中的一個問題：
hash 沖突：有時候境析，桶會出現(xiàn)被占滿的情況，即不同的對象產(chǎn)生了相同的hash值派诬。解決這個問題通常是兩種方法：鏈表法和開放地址法劳淆。鏈表法就是將相同hash值的對象組織成一個鏈表放在hash值對應(yīng)的槽位；開放地址法是通過一個探測算法默赂，當(dāng)某個槽位已經(jīng)被占據(jù)的情況下繼續(xù)查找下一個可以使用的槽位沛鸵。java.util.HashMap采用的鏈表法的方式，鏈表是單向鏈表缆八，相同hash值得不同對象存儲在同一個槽位的鏈表中曲掰。

hashSet和HashMap在使用的時候，需要保證添加進(jìn)去的元素是不可變的奈辰，api只能保證元素添加進(jìn)去的時候是不可變的栏妖，但無法控制元素后面是否會變

hashMap的get(Object key)方法參數(shù)不是泛型，因為只需要用到equals和hashcode方法冯挎。返回值類型是泛型類型

實際開發(fā)中的另一個問題：

HashSet<Stuff> stuffs = new HashSet<>();
        Stuff stuff1 = new Stuff(23,"Leonardo");
        Stuff stuff2 = new Stuff(23,"Leonardo");
        Stuff stuff3 = new Stuff(24,"Hugo");
        stuffs.add(stuff1);
        stuffs.add(stuff2);
        stuffs.add(stuff3);
        for (Stuff employee:stuffs) {
            System.out.println(employee.toString());
        }
/**
     * console:
     * Stuff{ID=23, mName='Leonardo'}
     Stuff{ID=24, mName='Hugo'}
     Stuff{ID=23, mName='Leonardo'}
     */

我們知道不同的對象地址值不同底哥，哪怕其成員完全一致咙鞍，所以它們的hashCode理論上是不一樣的房官，這是上述所有對象都能被添加的原因趾徽。但是如果開發(fā)需求類型和成員一致的對象應(yīng)被視為相同，即equals方法需要被重寫翰守，這時候hashCode方法也應(yīng)該適配孵奶，否則會出現(xiàn)equals返回true的兩個對象hashCode不同。所以我們要同時自定義hashCode和equals方法——

自定義的hashCode方法必須與equals兼容蜡峰，如果equals方法返回true了袁，兩個對象的hashCode值必須相同。
既然如此湿颅，hashCode的生成就不在依賴于第一無二的對象载绿，而是考慮到了成員變量，其變化范圍就會縮小油航，縮小就增加了hash沖突的可能性崭庸，導(dǎo)致性能下降，所以又要盡量random化hashCode谊囚，看下面的一種方案怕享。
** 核心需求：適配equals同時盡量不會出現(xiàn)hash沖突 **

@Override
    public boolean equals(Object o) {
        if (this == o)
            return true;
        if (!(o instanceof Stuff))
            return false;

        Stuff stuff = (Stuff) o;

        if (ID != stuff.ID)
            return false;
        return mName.equals(stuff.mName);
    }

    @Override
    public int hashCode() {
        int result = ID;
        result = 31 * result + mName.hashCode();
        return result;
    }

如果散列碼分布均勻，桶的數(shù)目也足夠大镰踏，需要比較的次數(shù)就少函筋，hashMap的效率就很高；所以想保證性能奠伪，就要指定初始桶的數(shù)目跌帐，太少會增加散列沖突的可能性，一般建議設(shè)置為元素個數(shù)的75%~150%绊率，如果散列表太滿含末，就需要再散列。

58e67eae921e4b431782c07444af824e_r.jpg

HashMap和HashTable的區(qū)別即舌，前者線程不安全佣盒，后者方法用synchronized修飾；前者能夠出現(xiàn)一個唯一的null鍵顽聂，且可以有多個鍵對應(yīng)null值肥惭，但后者中鍵值不能有null;初始容量大小和每次擴(kuò)充容量大小的不同.
jdk 1.8實現(xiàn)方式稍有不同
相比于之前的版本， JDK1.8之后在解決哈希沖突時有了較大的變化紊搪，當(dāng)鏈表長度大于閾值（默認(rèn)為8）時蜜葱，將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時間

LinkedHashMap
由一個雙向鏈表和hash表組成耀石，具備HashMap鍵唯一的特點牵囤，同時保證存取順序一致

TreeMap
依賴一個紅黑樹實現(xiàn)數(shù)據(jù)唯一和排序

HashMap和Hashtable的區(qū)別

• 線程不安全，效率高vs線程安全，效率低揭鳞；HashTable 內(nèi)部的方法基本都經(jīng)過synchronized 修飾炕贵。（如果你要保證線程安全的話就使用 ConcurrentHashMap 吧！）
• 允許使用最多一個null鍵和多個null值vs不允許使用null作為鍵值
• 初始容量大小和每次擴(kuò)充容量大小的不同 ： ①創(chuàng)建時如果不指定容量初始值野崇，Hashtable 默認(rèn)的初始大小為11称开，之后每次擴(kuò)充，容量變?yōu)樵瓉淼?n+1乓梨。HashMap 默認(rèn)的初始化大小為16鳖轰。之后每次擴(kuò)充，容量變?yōu)樵瓉淼?倍扶镀。②創(chuàng)建時如果給定了容量初始值回挽，那么 Hashtable 會直接使用你給定的大小威沫，而 HashMap 會將其擴(kuò)充為2的冪次方大小（HashMap 中的tableSizeFor()方法保證，下面給出了源代碼）捉捅。也就是說 HashMap 總是使用2的冪作為哈希表的大小,后面會介紹到為什么是2的冪次方忙干。
• JDK1.8 以后的 HashMap 在解決哈希沖突時有了較大的變化物赶，當(dāng)鏈表長度大于閾值（默認(rèn)為8）時室梅，將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時間菱肖。Hashtable 沒有這樣的機(jī)制
  總之客冈，不要使用Hashtable

其他補(bǔ)充

1.遍歷集合
使用Lambda表達(dá)式遍歷集合

public static void main(String[] args) {
        List<String> names = new ArrayList<String>();
        names.add("aa");
        names.add("bb");
        names.add("cc");
        names.forEach(name -> System.out.println(name));
    }

lambda表達(dá)式的目標(biāo)類型是Consumer，并將集合的元素類型作為生成Consumer對象的泛型參數(shù)稳强，然后自動將集合元素作為方法參數(shù)傳遞給Consumer對象的accept方法场仲。foreach方法中會調(diào)用一個for-each循環(huán)。上面這一句代碼可以看做是下面代碼的極簡形式：

Consumer<String> printConsumer= new Consumer<String>() {
            public void accept(String name) {
                System.out.println(name);
            }
        };
        names.forEach(printConsumer);

其等效于手寫一個foreach循環(huán)退疫，并沒有在線程安全性上做改進(jìn)渠缕。
更多內(nèi)容，可以參考網(wǎng)頁https://www.baeldung.com/foreach-java

2褒繁、Collections
對集合進(jìn)行操作的工具類亦鳞，有對集合進(jìn)行二分查找和排序的方法。

public static <T> void sort(List<T> list)默認(rèn)按照自然順序排序
public static <T> int binarySearch(List<?> list,T key)二分查找
public static <T> T max(Collection<?> coll)最大值
public static void reverse(List<?> list)翻轉(zhuǎn)
public static void shuffle(List<?> list)洗牌棒坏，隨機(jī)置換