Java集合中Collection和Map

Java的集合框架有哪幾種：

兩種：collection和map，其中collection分為set和List，

Collection 
    ├List 
       ├LinkedList 
       ├ArrayList 
       ├Vector 
           ├Stack 
       ├-Set
           ├HashSet 
           ├LinkedSet
           └ TreeSet 
Map 
　　├Hashtable 
　　├HashMap 
　　└WeakHashMap

List你使用過哪些：

ArrayList和linkedList使用的最多，也最具代表性，

Collection 和 Collections 有什么區別？

1、java.util.Collection 是一個集合介面，它提供了對集合物件進行基本操作的通用介面方法，Collection介面在Java 類別庫中有很多具體的實作，Collection介面的意義是為各種具體的集合提供了最大化的統一操作方式，
2、java.util.Collections 是一個包裝類，它包含有各種有關集合操作的靜態多型方法，此類不能實體化，就像一個工具類，服務于Java的Collection框架，

你知道ArrayList和linkedList和vector 的區別嘛：

• ArrayList實作是一個陣列，可變陣列，默認初始化長度為10，也可以我們設定容量，但是沒有設定的時候是默認的空陣列，只有在第一步add的時候會進行擴容至10（重新創建了陣列），后續擴容按照3/2的大小進行擴容，是執行緒不安全的，適用多讀取，少插入的情況
• linkedList是基于雙向鏈表的實作，使用了尾插法的方式，內部維護了鏈表的長度，以及頭節點和尾節點，所以獲取長度不需要遍歷，適合一些插入/洗掉頻繁的情況，
• Vector是執行緒安全的，實作方式和ArrayList相似，也是基于陣列，但是方法上面都有synchronized關鍵詞修飾，其擴容方式是原來的兩倍，

hashMap和hashTable和ConcurrentHashMap的區別

hashMap是map型別的一種最常用的資料結構，其底部實作是陣列+鏈表（在1.8版本后變為了陣列+鏈表/紅黑樹的方式），其key是可以為null的，默認hash值為0，擴容以2的冪等次（為什么，，，因為只有是2的冪等次的時候（n-1）&x==x%n，當然不一定只有一個原因），是執行緒不安全的，

hashTable的實作形式和hashMap差不多，它是執行緒安全的，是繼承了Dictionary，也是key-value的模式，但是其key不能為null，

ConcurrentHashMap是JUC并發包的一種，在hashMap的基礎上做了修改，因為hashmap其實是執行緒不安全的，那在并發情況下使用hashTable嘛，但是hashTable是全程加鎖的，性能不好，所以采用分段的思想，把原本的一個陣列分成默認16段，就可以最多容納16個執行緒并發操作，16個段叫做Segment，是基于ReetrantLock來實作的，

說說你了解的hashmap吧

hashMap是Map的結構，內部用了陣列+鏈表的方式，在1.8后，當鏈表長度達到8的時候，會變成紅黑樹，這樣子就可以把查詢的復雜度變成O（nlogn）了，默認負載因子是0.75，為什么是0.75呢？

我們知道當負載因子太小，就很容易觸發擴容，如果負載因子太大就容易出現碰撞，所以這個是空間和時間的一個均衡點，在1.8的hashmap介紹中，就有描述了，貌似是0.75的負載因子中，能讓隨機hash更加滿足0.5的泊松分布，

除此之外，1.7的時候是頭插法，1.8后就變成了尾插法，主要是為了解決rehash出現的死回圈問題，而且1.7的時候是先擴容后插入，1.8則是先插入后擴容(為什么？正常來說，如果先插入，就有可能節點變為樹化，那么是不是多做一次樹轉化，比1.7要多損耗，個人猜測，因為讀寫問題，因為hashmap并不是執行緒安全的，如果說是先擴容，后寫入，那么在擴容期間，是訪問不到新放入的值的，是不是不太合適，所以會先放入值，這樣子在擴容期間，那個值是在的），

1.7版本的時候用了9次擾動，5次異或，4次位移，減少hash沖突，但是1.8就只用了兩次，覺得就足夠了一次異或，一次位移，

說下hashMap的put方法的程序

判斷key是否是null，如果是null對應的hash值就是0，獲得hash值過后則進行擾動，（1.7是9次，5次異或，4次位移，1.8是2次），獲取到的新hash值找出所在的index，（n-1）&hash，根據下標找到對應的Node/entity，然后遍歷鏈表/紅黑樹，如果遇到hash值相同且equals相同，則覆寫值，如果不是則新增，如果節點數大于8了，則進行樹化（1.8），完成后，判斷當前的長度是否大于閥值，是就擴容（1.7是先擴容在put），

為什么修改hashcode方法要修改equals

都是map惹的禍，我們知道在map中判斷是否是同一個物件的時候，會先判斷hash值，在判斷equals的，如果我們只是重寫了hashcode，沒有順便修改equals，比如Intger，hashcode就是value值，如果我們不改寫equals，而是用了Object的equals，那么就是判斷兩者指標是否一致了，那就會出現valueOf和new出來的物件會對于map而言是兩個物件，那就是個問題了，

concurrentHashMap呢

concurrentHashMap是執行緒安全的map結構，它的核心思想是分段鎖，在1.7版本的時候，內部維護了segment陣列，默認是16個，segment中有一個table陣列（相當于一個segmeng存放著一個hashmap，，，），segment繼承了reentrantlock，使用了互斥鎖，map的size其實就是segment陣列的count和，而在1.8的時候做了一個大改版，廢除了segment，采用了cas加synchronize方式來進行分段鎖（還有自旋鎖的保證），而且節點物件改用了Node不是之前的HashEntity，

Node可以支持鏈表和紅黑樹的轉化，比如TreeBin就是繼承了Node，這樣子可以直接用instanceof來區分，1.8的put就很復雜來，會先計算出hash值，然后根據hash值選出Node陣列的下標（默認陣列是空的，所以一開始put的時候會初始化，指定負載因子是0.75，不可變），判斷是否為空，如果為空，則用cas的操作來賦值首節點，如果失敗，則因為自旋，會進入非空節點的邏輯，這個時候會用synchronize加鎖頭節點（保證整條鏈路鎖定）這個時候還會進行二次判斷，是否是同一個首節點，在分首節點到底是鏈表還是樹結構，進行遍歷判斷，

concurrentHashMap的擴容方式

1.7版本的concurrentHashMap是基于了segment的，segment內部維護了HashEntity陣列，所以擴容是在這個基礎上的，類比hashmap的擴容，

1.8版本的concurrentHashMap擴容方式比較復雜，利用了ForwardingNode,先會根據機器內核數來分配每個執行緒能分到的busket數，（最小是16），這樣子可以做到多執行緒協助遷移，提升速度，然后根據自己分配的busket數來進行節點轉移，如果為空，就放置ForwardingNode，代表已經遷移完成，如果是非空節點（判斷是不是ForwardingNode，是就結束了），加鎖，鏈路回圈,進行遷移，

TreeMap了解嘛

TreeMap是Map中的一種很特殊的map，我們知道Map基本是無序的，但是TreeMap是會自動進行排序的，也就是一個有序Map(使用了紅黑樹來實作），如果設定了Comparator比較器，則會根據比較器來對比兩者的大小，如果沒有則key需要是Comparable的子類（代碼中沒有事先check，會直接拋出轉化例外，有點坑啊），

LinkedHashMap了解嘛

LinkedHashMap是HashMap的一種特殊分支，是某種有序的hashMap，和TreeMap是不一樣的概念，是用了HashMap+鏈表的方式來構造的，有兩者有序模式：訪問有序，插入順序，插入順序是一直存在的，因為是呼叫了hashMap的put方法，并沒有多載，但是多載了newNode方法，在這個方法中，會把節點插入鏈表中，訪問有序默認是關閉的，如果打開，則在每次get的時候都會把鏈表的節點移除掉，放到鏈表的最后面，這樣子就是一個LRU的一種實作方式，