Java集合拓展01

1、List，Set，Map三者的區別

List：一個有序（元素存入集合的順序和取出的順序一致）容器，元素可以重復，可以插入多個null元素，元素都有索引。常用的實現類有 ArrayList、LinkedList 和 Vector。
Set：一個無序（存入和取出順序有可能不一致）容器，不可以存儲重復元素，只允許存入一個null元素，必須保證元素唯一性。Set 接口常用實現類是 HashSet、LinkedHashSet 以及 TreeSet。
Map是一個鍵值對集合，存儲鍵、值和之間的映射。 Key無序，唯一；value 不要求有序，允許重復。Map 的常用實現類：HashMap、TreeMap、HashTable、LinkedHashMap、ConcurrentHashMap。

2、集合框架底層的數據結構

List集合：

Arraylist和Vector使用的是 Object 數組， LinkedList使用雙向循環鏈表

Set集合：

HashSet（無序，唯一）：基于 HashMap 實現的，HashSet的值作為key，value是Object類型的常量
LinkedHashSet繼承HashSet，并且通過 LinkedHashMap 來實現的
TreeSet（有序，唯一）：紅黑樹(自平衡的排序二叉樹。

Map集合：

HashMap由數組+鏈表+紅黑樹組成的，數組是HashMap的主體，鏈表則是主要為了解決哈希沖突而存在的，當鏈表長度大于閾值（默認為8）并且數組長度大于64時，將鏈表轉化為紅黑樹
LinkedHashMap（有序）繼承自 HashMap，底層仍然是數組+鏈表+紅黑樹組成。另外，LinkedHashMap 在此基礎上，節點之間增加了一條雙向鏈表，使得可以保持鍵值對的插入順序
HashTable無序，數組+鏈表組成的，數組是 HashTable的主體，鏈表則是主要為了解決哈希沖突而存在的
TreeMap有序，紅黑樹

3、集合框架的擴容

?ArrayList和Vector默認初始容量為10，當元素個數超過容量長度時都進行進行擴容，ArrayList擴容為原來的1.5倍，而Vector擴容為原來的2倍
HashSet和HashMap默認初始容量為16，加載因子為0.75：即當元素個數超過容量長度的0.75倍時，進行擴容，擴容為原來的2倍。HashSet基于 HashMap 實現的，因此兩者相同
HashTable：默認初始容量為11，加載因子為0.75，擴容策略是2倍+1，如初始的容量為11，一次擴容后是容量為23

4、HashMap 的實現原理以及JDK1.7和JDK1.8的區別

????????實現原理

????????數組的特點是：尋址容易，插入和刪除困難；而鏈表的特點是：尋址困難，插入和刪除容易。我們綜合兩者的特性，做出一種尋址容易，插入刪除也容易的數據結構哈希表。并且使用最常用的一種方法—— 拉鏈法來實現哈希表。

????????數組存儲的元素是一個Entry類，這個類有三個數據域，key、value（鍵值對），next(指向下一個Entry)。當兩個key經過計算得到的index（索引）相同時，即產生哈希沖突時，用鏈地址法來解決哈希沖突，即通過next屬性將索引值相同的鏈接在一起。隨著map的容量或者鏈表長度越來越大，在進行進一步的優化，比如使用紅黑樹。

????????存儲過程

????????HashMap個put()方法：

????????第一步首先將k,v封裝成Node節點。第二步調用hashCode()方法得出hash值并將hash值轉換成數組的下標，下標位置上如果沒有任何元素（沒有碰撞），就把Node節點添加到這個位置上。如果說下標對應的位置上有值（hash碰撞）。碰撞的元素與要插入的元素key值相等，直接進行value的更新；如果key值不相同，于是增長鏈表或者樹節點的增加。插入之后判斷是否進行擴容。

????????HashMap個get()方法：

????????先調用k的hashCode()方法得出哈希值，并轉換成數組的下標。第二步：通過數組下標快速定位到某個位置上。如果該位置上什么都沒有，則返回null。如果這個位置上有數據，那么它就會拿著參數k和單向鏈表上(紅黑樹)的每一個節點的k進行equals，如果所有equals方法都返回false，則get方法返回null。如果其中一個節點的k和參數k進行equals返回true，那么返回該節點的value。

????????區別

????????JDK1.7是數組+鏈表，無沖突時，存放數組；沖突時，存放鏈表；采用頭插法。

????????JDK1.8是數組 + 鏈表 + 紅黑樹，無沖突時，存放數組；有沖突存放鏈表或者紅黑樹，當鏈表長度大于閾值（默認為8）并且數組長度大于64時，將鏈表轉化為紅黑樹；樹元素小于等于6時，樹結構還原成鏈表形式。

5、Arraylist與LinkedList區別

ArrayList是數組的數據結構，LinkedList是鏈表的數據結構。
隨機訪問的時候，ArrayList的效率比較高，因為LinkedList要移動指針，而ArrayList是基于索引(index)的數據結構，可以直接映射到。
插入、刪除數據時，LinkedList的效率比較高，因為ArrayList要移動數據。
LinkedList比ArrayList開銷更大，因為LinkedList的節點除了存儲數據，還需要存儲引用。

6、HashMap 的擴容過程?

第一步把數組長度變為原來的兩倍，
第二步把舊數組的元素重新計算hash插入到新數組中。
jdk8時，不用重新計算hash，只用看看原來的hash值新增的一位是零還是1，如果是1這個元素在新數組中的位置，是原數組的位置加原數組長度，如果是零就插入到原數組中。擴容過程第二步一個非常重要的方法是transfer方法，采用頭插法，把舊數組的元素插入到新數組中。

?7、哪些集合類是線程安全的？哪些不安全

線性安全的

Vector：比Arraylist多了個同步化機制。
Hashtable：比Hashmap多了個線程安全。
ConcurrentHashMap:是一種高效但是線程安全的集合。
Stack：棧，也是線程安全的，繼承于Vector。

線性不安全的

Hashmap
Arraylist
LinkedList
HashSet
TreeSet
TreeMap

?8、ArrayList 和 Vector 的區別是什么

Vector是線程安全的，ArrayList不是線程安全的。
ArrayList在底層數組不夠用時在原來的基礎上擴展0.5倍，Vector是擴展1倍。
Vector只要是關鍵性的操作，方法前面都加了synchronized關鍵字，來保證線程的安全性。

?9、Collection與Collections的區別是什么

Collection是Java集合框架中的基本接口，如List接口也是繼承于它

publicinterfaceList<E>extendsCollection<E>{}

Collections是Java集合框架提供的一個工具類，其中包含了大量用于操作或返回集合的靜態方法。如下：

publicstatic<T extendsComparable<?super T>>void sort(List<T> list){list.sort(null);
}

10、如何決定使用 HashMap 還是TreeMap？

這個點，主要考察HashMap和TreeMap的區別。

TreeMap實現SortMap接口，能夠把它保存的記錄根據鍵排序，默認是按key的升序排序，也可以指定排序的比較器。當用Iterator遍歷TreeMap時，得到的記錄是排過序的。

11、數組和 List之間的轉換

List 轉Array：必須使用集合的 toArray(T[] array)，如果直接使用 toArray 無參方法，返回值只能是 Object[] 類，強轉其他類型可能有問題。

Array 轉List：使用Arrays.asList() 把數組轉換成集合時，不能使用修改集合相關的方法。

PS：需要注意的是，asList() 返回的是一個視圖（view），所以對該 List 進行添加、刪除操作會直接影響到原數組的值，而且還不支持 add()、remove()、clear() 操作，不然會拋出 UnsupportedOperationException 異常，該方法適用于只需要讀取數組中數據的情況。如果想要對集合修改元素，應該通過創建新的 List 進行修改。
可以這樣使用彌補這個缺點：

//方式一：
ArrayList<String> arrayList =newArrayList<String>(strArray.length);
Collections.addAll(arrayList, strArray);
//方式二：
ArrayList<String> list =newArrayList<String>(Arrays.asList(strArray));

12、迭代器 Iterator 是什么？怎么用，有什么特點？

publicinterfaceCollection<E>extendsIterable<E>{
Iterator<E> iterator();

方法如下：

next()方法獲得集合中的下一個元素
hasNext()檢查集合中是否還有元素
remove()方法將迭代器新返回的元素刪除
forEachRemaining(Consumer<?super E> action)方法，遍歷所有元素

Iterator 主要是用來遍歷集合用的，它的特點是更加安全，因為它可以確保，在當前遍歷的集合元素被更改的時候，就會拋出 ConcurrentModificationException 異常。

使用demo如下：

List<String> list =newArrayList<>();
Iterator<String> it = list. iterator();
while(it. hasNext()){String obj = it.next();System.out. println(obj);
}

13、ArrayList集合加入1萬條數據，應該怎么提高效率

因為ArrayList的底層是數組實現,并且數組的默認值是10,如果插入10000條要不斷的擴容,耗費時間,所以我們調用ArrayList的指定容量的構造器方法ArrayList(int size) 就可以實現不擴容,就提高了性能。