框架——集合
1、arraylist和linkedList的區別
ArrayList和LinkedList的大致區別如下:
1.ArrayList是實現了基於動態數組的數據結構，LinkedList基於鏈表的數據結構。
2.對於隨機訪問get和set，ArrayList覺得優於LinkedList，因爲LinkedList要移動指針。
3.對於新增和刪除操作add和remove，LinedList比較佔優勢，因爲ArrayList要移動數據。
ArrayList繼承AbstractList類，並且實現了List,RandomAccess,Clonable,Serializable四個接口
然後LinkedList繼承AbstractSequentialList類，並且實現了List,Deque,Clonable,Serializable四個接口
Arraylist怎麼實現擴容
根據新的容量創建一個新的數組，再根據System.arrayCopy()方法進行數組的複製
2、hashmap、hashtable、concurrentHashmap
HashTable
- 底層數組+鏈表實現，無論key還是value都不能爲null，線程安全，實現線程安全的方式是在修改數據時鎖住整個HashTable，效率低，ConcurrentHashMap做了相關優化
- 初始size爲11，擴容：newsize = olesize*2+1
- 計算index的方法：index = (hash & 0x7FFFFFFF) % tab.length
HashMap
- 底層數組+鏈表實現，可以存儲null鍵和null值，線程不安全
- 初始size爲16，擴容：newsize = oldsize*2，size一定爲2的n次冪
- 擴容針對整個Map，每次擴容時，原來數組中的元素依次重新計算存放位置，並重新插入
- 插入元素後才判斷該不該擴容，有可能無效擴容（插入後如果擴容，如果沒有再次插入，就會產生無效擴容）
- 當Map中元素總數超過Entry數組的75%，觸發擴容操作，爲了減少鏈表長度，元素分配更均勻
- 計算index方法：index = hash & (tab.length – 1)
HashMap的初始值還要考慮加載因子:
- 哈希衝突：若干Key的哈希值按數組大小取模後，如果落在同一個數組下標上，將組成一條Entry鏈，對Key的查找需要遍歷Entry鏈上的每個元素執行equals()比較。
- 加載因子：爲了降低哈希衝突的概率，默認當HashMap中的鍵值對達到數組大小的75%時，即會觸發擴容。因此，如果預估容量是100，即需要設定100/0.75＝134的數組大小。
- 空間換時間：如果希望加快Key查找的時間，還可以進一步降低加載因子，加大初始大小，以降低哈希衝突的概率。
HashMap和Hashtable都是用hash算法來決定其元素的存儲，因此HashMap和Hashtable的hash表包含如下屬性：
- 容量（capacity）：hash表中桶的數量
- 初始化容量（initial capacity）：創建hash表時桶的數量，HashMap允許在構造器中指定初始化容量
- 尺寸（size）：當前hash表中記錄的數量
- 負載因子（load factor）：負載因子等於「size/capacity」。負載因子爲0，表示空的hash表，0.5表示半滿的散列表，依此類推。輕負載的散列表具有衝突少、適宜插入與查詢的特點（但是使用Iterator迭代元素時比較慢）
除此之外，hash表裏還有一個「負載極限」，「負載極限」是一個0～1的數值，「負載極限」決定了hash表的最大填滿程度。當hash表中的負載因子達到指定的「負載極限」時，hash表會自動成倍地增加容量（桶的數量），並將原有的對象重新分配，放入新的桶內，這稱爲rehashing。
HashMap和Hashtable的構造器允許指定一個負載極限，HashMap和Hashtable默認的「負載極限」爲0.75，這表明當該hash表的3/4已經被填滿時，hash表會發生rehashing。
「負載極限」的默認值（0.75）是時間和空間成本上的一種折中：
- 較高的「負載極限」可以降低hash表所佔用的內存空間，但會增加查詢數據的時間開銷，而查詢是最頻繁的操作（HashMap的get()與put()方法都要用到查詢）
- 較低的「負載極限」會提高查詢數據的性能，但會增加hash表所佔用的內存開銷
程序猿可以根據實際情況來調整「負載極限」值。
Hashtable與HashMap另一個區別是HashMap的迭代器（Iterator）是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以當有其它線程改變了HashMap的結構（增加或者移除元素），將會拋出ConcurrentModificationException，但迭代器本身的remove()方法移除元素則不會拋出ConcurrentModificationException異常
ConcurrentHashMap
- 底層採用分段的數組+鏈表實現，線程安全
- 通過把整個Map分爲N個Segment，可以提供相同的線程安全，但是效率提升N倍，默認提升16倍。(讀操作不加鎖，由於HashEntry的value變量是 volatile的，也能保證讀取到最新的值。)
- Hashtable的synchronized是針對整張Hash表的，即每次鎖住整張表讓線程獨佔，ConcurrentHashMap允許多個修改操作併發進行，其關鍵在於使用了鎖分離技術
- 有些方法需要跨段，比如size()和containsValue()，它們可能需要鎖定整個表而而不僅僅是某個段，這需要按順序鎖定所有段，操作完畢後，又按順序釋放所有段的鎖
- 擴容：段內擴容（段內元素超過該段對應Entry數組長度的75%觸發擴容，不會對整個Map進行擴容），插入前檢測需不需要擴容，有效避免無效擴容
ConcurrentHashMap默認將hash表分爲16個桶，諸如get、put、remove等常用操作只鎖住當前需要用到的桶。這樣，原來只能一個線程進入，現在卻能同時有16個寫線程執行，併發性能的提升是顯而易見的。
3、CAS算法的原理
1、什麼是CAS？
CAS：Compare and Swap，即比較再交換。
jdk5增加了併發包java.util.concurrent.*,其下面的類使用CAS算法實現了區別於synchronouse同步鎖的一種樂觀鎖。JDK 5之前Java語言是靠synchronized關鍵字保證同步的，這是一種獨佔鎖，也是是悲觀鎖。
2、CAS算法理解
對CAS的理解，CAS是一種無鎖算法，CAS有3個操作數，內存值V，舊的預期值A，要修改的新值B。當且僅當預期值A和內存值V相同時，將內存值V修改爲B，否則什麼都不做。
CAS比較與交換的僞代碼可以表示爲：
do{
備份舊數據；
基於舊數據構造新數據；
}while(!CAS( 內存地址，備份的舊數據，新數據 ))
4、CAS算法在JDK中的應用
在原子類變量中，如java.util.concurrent.atomic中的AtomicXXX，都使用了這些底層的JVM支持爲數字類型的引用類型提供一種高效的CAS操作，而在java.util.concurrent中的大多數類在實現時都直接或間接的使用了這些原子變量類。
Java 1.7中AtomicInteger.incrementAndGet()的實現源碼爲：
由此可見，AtomicInteger.incrementAndGet的實現用了樂觀鎖技術，調用了類sun.misc.Unsafe庫裏面的 CAS算法，用CPU指令來實現無鎖自增。所以，AtomicInteger.incrementAndGet的自增比用synchronized的鎖效率倍增。
4、volitate關鍵詞
作用：volatile關鍵字的作用是：使變量在多個線程間可見（具有可見性），但是僅靠volatile是不能保證線程的安全性，volatile關鍵字不具備synchronized關鍵字的原子性。
當多個線程之間需要根據某個條件確定 哪個線程可以執行時，要確保這個條件在 線程之間是可見的。因此，可以用volatile修飾。
volatile 與 synchronized 的比較：
①volatile輕量級，只能修飾變量。synchronized重量級，還可修飾方法
②volatile只能保證數據的可見性，不能用來同步，因爲多個線程併發訪問volatile修飾的變量不會阻塞。
synchronized不僅保證可見性，而且還保證原子性，因爲，只有獲得了鎖的線程才能進入臨界區，從而保證臨界區中的所有語句都全部執行。多個線程爭搶synchronized鎖對象時，會出現阻塞。
線程安全性包括兩個方面，①可見性。②原子性。
從上面自增的例子中可以看出：僅僅使用volatile並不能保證線程安全性。而synchronized則可實現線程的安全性。
5、arraylist怎麼進行深拷貝
淺拷貝和深拷貝的區別：
淺拷貝：被複制對象的任何變量都含有和原來的對象相同的值，而任何的對其他對象的引用仍然指向原來的對象。對拷貝後的引用的修改，還能影響原來的對象。
深拷貝：把要複製的對象所引用的對象都複製了一遍，對現在對象的修改不會影響原有的對象。
深拷貝的方法
1.使用序列化方法
public static <T> List<T> deepCopy(List<T> src) throws IOException, ClassNotFoundException {
ByteArrayOutputStream byteOut = new ByteArrayOutputStream();
ObjectOutputStream out = new ObjectOutputStream(byteOut);
out.writeObject(src);
ByteArrayInputStream byteIn = new ByteArrayInputStream(byteOut.toByteArray());
ObjectInputStream in = new ObjectInputStream(byteIn);
@SuppressWarnings("unchecked")
List<T> dest = (List<T>) in.readObject();
return dest;
}
List<Person> destList=deepCopy(srcList); //調用該方法
2.clone方法
public class A implements Cloneable {
public String name[];
public A(){
name=new String[2];
}
public Object clone() {
A o = null;
try {
o = (A) super.clone();
} catch (CloneNotSupportedException e) {
e.printStackTrace();
}
return o;
}
}
for(int i=0;i<n;i+=){
copy.add((A)src.get(i).clone());
}
Java對對象和基本的數據類型的處理是不一樣的。在Java中用對象的作爲入口參數的傳遞則缺省爲」引用傳遞」，也就是說僅僅傳遞了對象的一個」引用」，這個」引用」的概念同C語言中的指針引用是一樣的。當函數體內部對輸入變量改變時，實質上就是在對這個對象的直接操作。 除了在函數傳值的時候是」引用傳遞」，在任何用」＝」向對象變量賦值的時候都是」引用傳遞」。
在淺複製的情況下，源數據被修改破壞之後，使用相同引用指向該數據的目標集合中的對應元素也就發生了相同的變化。因此，在需求要求必須深複製的情況下，要是使用上面提到的方法，請確保List中的T類對象是不易被外部修改和破壞的。
6、紅黑樹原理
紅黑樹和平衡二叉樹的主要區別如下：
平衡二叉樹（AVL）樹是嚴格的平衡二叉樹，平衡條件必須滿足（所有節點的左右子樹高度差不超過1）。不管我們是執行插入還是刪除操作，只要不滿足上面的條件，就要通過旋轉來保持平衡，而旋轉非常耗時的。所以平衡二叉樹（AVL）適合用於插入與刪除次數比較少，但查找多的情況。
紅黑樹在二叉查找樹的基礎上增加了着色和相關的性質使得紅黑樹相對平衡，從而保證了紅黑樹的查找、插入、刪除的時間複雜度最壞爲O(log n)。所以紅黑樹適用於搜索，插入，刪除操作較多的情況。
紅黑樹的原理參照treemap的實現原理
新增或刪除節點後會進行左旋、右旋、着色操作。