基礎(chǔ)概念

Collection：統(tǒng)計(jì)大小、插入或刪除數(shù)據(jù)糠亩、清空虐骑、是否包含某條數(shù)據(jù)，等等削解。而Collection就是對這些常用操作進(jìn)行提取富弦，只是其很全面、很通用氛驮。size(),isEmpty(),contains(),add(),remove,clear(),hashCode()

AbstractCollection:在Collection得基礎(chǔ)上腕柜，在泛型上實(shí)現(xiàn)了一些方法，add拋出一個異常矫废，addAll獲得一個迭代器遍歷添加盏缤，clear獲得一個迭代器遍歷刪除，contains獲得一個迭代器遍歷查找蓖扑，tostring集合內(nèi)容

list：和collection相比唉铜，比較針對線性表來設(shè)計(jì)add，addAll律杠，sort潭流，get竞惋，set，indexOf灰嫉，lastIndexOf拆宛，listIterator（）返回一個先前遍歷得迭代器

AbstractList<e>：iterator方法返回了一個內(nèi)部類Itr對象，合理的處理hasNext讼撒，next浑厚，remove方法，還有個ListItr實(shí)現(xiàn)了ListIterator接口根盒，equals和hashcode的實(shí)現(xiàn)钳幅，所以在定義數(shù)據(jù)元素時，也應(yīng)該復(fù)寫這兩個方法炎滞，以保證程序的正確運(yùn)行

queue：繼承自敢艰，collection，有offer（add）册赛，poll（remove）盖矫，peek（element）操作，返回null不拋出異常

AbstractQueue：在泛型上實(shí)現(xiàn)了add击奶，remove辈双，element

map接口：put，get柜砾，size湃望，remove，clear痰驱，希望我們完成hashcode和equal

AbstractMap：在泛型上幫我們實(shí)現(xiàn)上面方法

String的方法:
hashcode：hash = 31 * hash+ a[i]
equals：對比是不是同一個引用证芭，對比是不是長度相同，再一個個字母對比
compareTo：實(shí)現(xiàn)了Comparable<t>的int compareTo(T t)方法担映，先對比長度废士，小的作為循環(huán)數(shù)，比較到a和b某個字母不相同蝇完，返回他們兩個相減

數(shù)組

• 創(chuàng)建一個數(shù)組官硝，必須聲明其長度，以在內(nèi)存中尋找合適的一段連續(xù)存儲單元短蜕。這也意味著數(shù)組的大小是固定的氢架，我們無法動態(tài)調(diào)整其大小。
• 想要獲取數(shù)組中第i個元素朋魔，其時間復(fù)雜度是 O(1)岖研，因?yàn)榭梢愿鶕?jù)其地址直接找到它。同理修改也是警检。
• 因?yàn)榈刂愤B續(xù)孙援，想要在數(shù)組中插入一個元素是復(fù)雜的害淤，因?yàn)閺牟迦胛恢闷穑筮叺乃性囟夹枰蚝笠苿右晃煌厥邸Ｍ韯h除也是筝家，只是移動方向?yàn)橄蚯啊２⑶伊诨裕?dāng)數(shù)組存滿時，就無法繼續(xù)插入了腮鞍。

鏈表

• 鏈表的每個元素都分為數(shù)據(jù)域和指針域值骇，前者是實(shí)際存儲的數(shù)據(jù)，后者則指向下一個元素的地址移国。和數(shù)組相比吱瘩，每個元素需要占用的內(nèi)存更大了。
• 增加與刪除一個元素更方便了迹缀，因?yàn)闆]有對內(nèi)存地址的限制使碾，我們只需要在對應(yīng)節(jié)點(diǎn)合理處理下指針域的值，就可以把一個元素插入鏈表或者從鏈表刪除祝懂。
• 鏈表對查詢表現(xiàn)也一般票摇，需要遍歷，時間復(fù)雜度為O(n)砚蓬。

紅黑樹：紅黑樹和AVL樹的思想是類似的矢门，都是在插入過程中對二叉排序樹進(jìn)行調(diào)整，從而提升性能灰蛙，它的增刪改查均可以在O(lg n)內(nèi)完成祟剔。紅黑樹的插入與刪除和AVL樹類似，也是每插入一個結(jié)點(diǎn)摩梧，都檢查是否破壞了樹的結(jié)構(gòu)物延，然后進(jìn)行調(diào)整。紅黑樹每個結(jié)點(diǎn)插入時默認(rèn)都為紅色仅父，這樣做可以降低黑高叛薯，也可以減少調(diào)整的次數(shù)。

1.Iterator

• Iterable<E>：collection繼承的接口笙纤，代表要實(shí)現(xiàn)Iterator<T> iterator()接口案训，有了獲得一個迭代器的能力，獲得一個迭代器

• Iterator<E>：Iterator是foreach遍歷的主體粪糙，有核心next强霎，remove，hasNext

• ArrayList和linkedList：ListItr增加了hasPrevious,previous,nextIndex,add,set

2.ArrayList

• 默認(rèn)是10蓉冈，添加第一個的時候創(chuàng)建城舞，添加元素時使用 ensureCapacityInternal() 方法來保證容量足夠轩触，如果不夠時，需要使用 grow() 方法進(jìn)行擴(kuò)容家夺，新容量的大小為 oldCapacity + (oldCapacity >> 1)脱柱，也就是舊容量的 1.5 倍。
• 擴(kuò)容操作需要調(diào)用 Arrays.copyOf() 把原數(shù)組整個復(fù)制到新數(shù)組中拉馋，這個操作代價很高榨为，因此最好在創(chuàng)建 ArrayList 對象時就指定大概的容量大小，減少擴(kuò)容操作的次數(shù)煌茴。
• 需要調(diào)用 System.arraycopy() 將 index+1 后面的元素都復(fù)制到 index 位置上随闺，該操作的時間復(fù)雜度為 O(N)，可以看出 ArrayList 刪除元素的代價是非常高的蔓腐。
• ArrayList 基于數(shù)組實(shí)現(xiàn)矩乐，并且具有動態(tài)擴(kuò)容特性，因此保存元素的數(shù)組不一定都會被使用回论，那么就沒必要全部進(jìn)行序列化散罕。ArrayList 實(shí)現(xiàn)了 writeObject() 和 readObject() 來控制只序列化數(shù)組中有元素填充那部分內(nèi)容。
• Fail-Fast傀蓉，modCount 用來記錄 ArrayList 結(jié)構(gòu)發(fā)生變化的次數(shù)欧漱。結(jié)構(gòu)發(fā)生變化是指添加或者刪除至少一個元素的所有操作，或者是調(diào)整內(nèi)部數(shù)組的大小葬燎，僅僅只是設(shè)置元素的值不算結(jié)構(gòu)發(fā)生變化硫椰。
  在進(jìn)行序列化或者迭代等操作時，需要比較操作前后 modCount 是否改變萨蚕，如果改變了需要拋出 ConcurrentModificationException靶草。

3.linked list

• LinkedList既繼承了List，又繼承了Deque岳遥，那它必然有一堆a(bǔ)dd奕翔、remove、addFirst浩蓉、addLast等方法派继。
• Node<e>作為她的內(nèi)部類，有e數(shù)據(jù)域捻艳，和上下節(jié)點(diǎn)的指針
  因?yàn)殒湵頉]有長度方面的問題驾窟，所以也不會涉及到擴(kuò)容等問題，其構(gòu)造函數(shù)也十分簡潔了认轨。
• 果要遍歷绅络，也最好使用foreach，也就是Iterator提供的方式。
• 非常適合大量數(shù)據(jù)的插入與刪除恩急，但其對處于中間位置的元素杉畜，無論是增刪還是改查都需要折半遍歷，這在數(shù)據(jù)量大時會十分影響性能衷恭。

4.treemap

• TreeMap是根據(jù)key進(jìn)行排序的此叠，它的排序和定位需要依賴比較器或覆寫Comparable接口，也因此不需要key覆寫hashCode方法和equals方法随珠，就可以排除掉重復(fù)的key灭袁，而HashMap的key則需要通過覆寫hashCode方法和equals方法來確保沒有重復(fù)的key。
• TreeMap的查詢窗看、插入茸歧、刪除效率均沒有HashMap高，一般只有要對key排序時才使用TreeMap烤芦。
• TreeMap的key不能為null，而HashMap的key可以為null析校。
• TreeMap不是同步的构罗。如果多個線程同時訪問一個映射，并且其中至少一個線程從結(jié)構(gòu)上修改了該映射智玻，則其必須 外部同步遂唧。

5.hashmap

• 初始化沒有設(shè)定值的時候，初始值1《《4=16吊奢，最大為1《《30盖彭，負(fù)載因?yàn)?.75的時候擴(kuò)容，也是2次冪
• 鏈表長度為8的時候變成紅黑樹页滚，小于6的時候變回鏈表
• 設(shè)計(jì)的key對象一定要實(shí)現(xiàn)hashCode方法
• 如果可以預(yù)先估計(jì)數(shù)量級召边，可以指定initial capacity，以減少rehash的過程裹驰。

• JDK 1.8 使用了 CAS 操作來支持更高的并發(fā)度隧熙，在 CAS 操作失敗時使用內(nèi)置鎖 synchronized。

  
  
  image

6.Collections.sort(list幻林，comparator<User>)贞盯，默認(rèn)升序

 Collections.sort(userList, new Comparator<User>() {
    public int compare(User u1, User u2) {
       return new Double(u1.getSalary()).compareTo(new Double(u2.getSalary())); 升序
       return new Double(u2.getSalary()).compareTo(new Double(u2.getSalary())); 降序
      }
  });

int[] intArray = new int[] { 4, 1, 3, -23 };
        Arrays.sort(intArray);

7.集合和數(shù)組轉(zhuǎn)化

list轉(zhuǎn)數(shù)組
List<String> list = new ArrayList<String> ();
        list.add("str1");
        list.add("str2");
        int size = list.size();
        String[] arr = (String[]) list.toArray(new String[size]);

數(shù)組轉(zhuǎn)集合
List<String> list = new ArrayList<>(arr.length);
        Collections.addAll(list, arr);

8.數(shù)組和list復(fù)制

數(shù)組復(fù)制
System.arraycopy(a1, 1, a2, 3, 3);
        System.out.println(Arrays.toString(a1)); // [1, 2, 3, 4, 5]
        System.out.println(Arrays.toString(a2)); // [0, 0, 0, 2, 3, 4, 0, 0, 0, 0]

list復(fù)制
1、遍歷循環(huán)復(fù)制
List<Person> destList=new ArrayList<Person>(srcList.size());  
for(Person p : srcList){  
    destList.add(p);  
}  

2沪饺、使用List實(shí)現(xiàn)類的構(gòu)造方法
List<Person> destList=new ArrayList<Person>(srcList);  

3躏敢、使用list.addAll()方法
List<Person> destList=new ArrayList<Person>();  
destList.addAll(srcList);

4、使用System.arraycopy()方法
Person[] srcPersons=srcList.toArray(new Person[0]);  
Person[] destPersons=new Person[srcPersons.length];  
System.arraycopy(srcPersons, 0, destPersons, 0, srcPersons.length);