集合概述
a) 對(duì)多個(gè)數(shù)據(jù)進(jìn)行存儲(chǔ)，簡稱java容器
b) 動(dòng)態(tài)地把多個(gè)對(duì)象的引用放入容器中
c) 與數(shù)組對(duì)比
i. 數(shù)組初始化后，長度確定。
ii. 數(shù)組需要定義數(shù)組類型，定義后是確定的

Java集合兩種體系

Collection
a) 單列數(shù)據(jù)，定義了存取一組對(duì)象的方法的集合
i. List：元素有序，可重復(fù)集合
ii. Set：元素?zé)o序，不可重復(fù)集合

Map
a) 雙列數(shù)據(jù)，具有映射關(guān)系“key—value對(duì)”的集合

Collection API
a) Add(Object e): 將元素e添加到集合當(dāng)中
b) addAll(Collection coll)：將集合coll中的元素添加到當(dāng)前的集合中
c) Size(): 添加的元素的個(gè)數(shù)
d) Clear(): 清空集合元素
e) isEmpty(): 判斷當(dāng)前集合是否為空

Collection.List
a) ArrayList：Collection coll = new ArrayList();
i. Coll.contains(Object obj);判斷集合中是否包含object 默認(rèn)調(diào)用equals（）！！注意調(diào)用的object是否重寫了equals方法—>自定義類需要重寫equals()方法
ii. Coll.containAll(Collection coll1):判斷是否包含所有coll1的數(shù)據(jù)
iii. Coll.remove(Object obj): 移除obj數(shù)據(jù)，調(diào)用equals()方法
iv. Coll.removeAll(Object obj):
v. Coll.retainAll(Object obj): 求兩個(gè)集合的交集
vi. Object[] arr = Coll.toArray(); 集合轉(zhuǎn)化為數(shù)組
vii. List list = Arrays.asList(new String(){“aa”}); 數(shù)組轉(zhuǎn)化為集合 返回list（list想當(dāng)動(dòng)態(tài)數(shù)組，元素有序可重復(fù)集合）
viii. Iterator：返回iterator接口的實(shí)例，用于遍歷元素

Iterator
a) 其對(duì)象稱為迭代器，是一種設(shè)計(jì)模式，用于遍歷Collection集合中的元素
b) Iterator iterator = coll.iterator();
c) Iterator.next(); 返回下一個(gè)元素 –>異常：noSuchElementException
d) Iterator.hasNext(); 是否有下一個(gè)元素
e) Iterator.remove; 可以刪除集合的元素，使用的是迭代器對(duì)象的remove方法

Foreach循環(huán)遍歷—增強(qiáng)for循環(huán)
a) 可以遍歷集合Collection和數(shù)組
b) 底層調(diào)用的是Iterator來完成操作
c) 遍歷操作不需要Collection和數(shù)組的長度，無需使用索引訪問元素。
d) For(Object obj : coll){} // for (集合元素的類型 局部變量 : 集合對(duì)象) 代碼塊中修改obj 不會(huì)改變?cè)蟘oll的元素

List接口：存儲(chǔ)有序 可重復(fù)的數(shù)據(jù)
a) ArrayList：List接口的主要實(shí)現(xiàn)類，線程不安全，效率高，底層使用Object[]數(shù)組
b) LinkedList：對(duì)于頻繁的插入和刪除操作，其效率更高，底層使用雙向鏈表存儲(chǔ)
c) Vector：古老實(shí)現(xiàn)類，線程安全，效率低，底層使用Object[]數(shù)組
d) 三個(gè)的異同
i. 同：都是實(shí)現(xiàn)了List的接口，存儲(chǔ)數(shù)據(jù)特點(diǎn)相同
ii. 不同：同上

ArrayList源碼
a) ArrayList list = new Arraylist(); 創(chuàng)建了長度為10的Object[]數(shù)組elementData
b) 添加到第11次，底層數(shù)組容量不夠，則默認(rèn)擴(kuò)容為原來的1.5倍，length = old + (old>>1) 右移一位除于2，將原有的數(shù)組復(fù)制到新的數(shù)組
c) ArrayList list = new ArrayList(int initialCapacity)：初始化數(shù)組大小
d) JDK8 時(shí)，創(chuàng)建對(duì)象時(shí)底層elementData初始化為{}，在調(diào)用add方法才創(chuàng)建數(shù)組長度，節(jié)約資源。JDK7 時(shí)，對(duì)象創(chuàng)建立即創(chuàng)建長度為10的數(shù)組

LinkedList源碼
a) 是一個(gè)雙向鏈表
b) LinkedList LL = new LinkedList(); 內(nèi)部聲明了Node類型的first、last屬性，默認(rèn)為null
c) List.add(123); //將123封裝到node中

Vector源碼 不怎么用
a) 默認(rèn)擴(kuò)容為原來的2倍，線程安全的。
b) 創(chuàng)建對(duì)象是底層都創(chuàng)建了長度為10的Object[]數(shù)組

ArrayList方法
a) 是collection的子接口，Collection 中的方法都可以用
b) Void add(int index, Object ele); 在index位置插入ele元素
c) addAll(index index, Collections coll); 將集合coll中的所有元素加入
d) Object get(int index): 獲取指定index位置的元素
e) Int indexOf(Object obj): 返回首次出現(xiàn)的元素的索引，找不到返回-1
f) Object remove(int index):移除指定位置的元素，并返回該元素（和Collections對(duì)比是方法的重載，不同的參數(shù)列表）
g) Object set(index, obj);
h) List subList(int fromIndex, int toIndex): 返回子集合 左閉右開

Set接口
a) Set：元素?zé)o序，不可重復(fù)集合
b) 接口沒有提供額外的方法
c) 根據(jù)equals（）判斷兩個(gè)對(duì)象是否相同
d) HashSet：set接口的主要實(shí)現(xiàn)類；線程不安全；可以存儲(chǔ)null值 底層：數(shù)組加鏈表結(jié)構(gòu)
i. LinkedHashSet：作為HashSet子類，遍歷內(nèi)部數(shù)據(jù)可以按照添加的順序遍歷
e) TreeSet：放入的數(shù)據(jù)是同一個(gè)類，按照添加的對(duì)象的指定屬性進(jìn)行排序（comparable）

存儲(chǔ)無序性和不可重復(fù)性
a) 無序性：存儲(chǔ)的數(shù)據(jù)在底層數(shù)組中并非按照數(shù)組索引的順序添加，而是根據(jù)數(shù)據(jù)的哈希值決定。不等于隨機(jī)性
b) 不可重復(fù)性：保證添加的數(shù)據(jù)（利用到哈希值）按照equals()方法判斷時(shí)，不能返回true
c) 添加元素過程，HashSet為例：
i. 添加元素a，調(diào)用a所在類的hashCode（）方法，計(jì)算元素a的哈希值，此哈希值接著通過某種算法計(jì)算出在HashSet底層數(shù)組中的存放位置（即為索引位置）
ii. 判斷存放位置上是否有元素，若無元素，a直接添加
iii. 若存在其他元素b（或以鏈表形式存在的多個(gè)元素），則比較元素a和元素b的hash值，若不相同，則a添加（七上八下）

若hash值相同，則調(diào)用元素a所在類的equals()方法
a) 返回true，元素已經(jīng)存在，添加不成功
b) 返回false，添加成功
iv. Jdk7：元素a放到數(shù)組中，指向原來的元素
v. Jdk8：原來數(shù)組中的元素，指向元素a
d) 擴(kuò)容：若使用率超過75%，則擴(kuò)大為原來的兩倍（初始16，擴(kuò)容為32）

HashCode()重寫方法
a) 向set中添加數(shù)據(jù)，一定重寫equals和hashCode方法！！
b) 重寫的hashCode和equal方法盡可能保持一致性—相同的對(duì)象有相同的散列碼（hashcode）
c) 使用31乘
i. 可以減少哈希碼相同的沖突，增加了查找的概率
ii. 31只占用5bits，數(shù)據(jù)溢出概率小
iii. 算法效率高，相當(dāng)于i*31 == i<<5-1
iv. 31是一個(gè)素?cái)?shù)

LinkedHashSet
a) 作為hashSet的子類，在添加數(shù)據(jù)的同時(shí)維護(hù)了一對(duì)雙向鏈表，記錄前一個(gè)數(shù)據(jù)和后一個(gè)數(shù)據(jù)
b) 優(yōu)點(diǎn)：對(duì)于頻繁的遍歷操作，效率高。

TreeSet—底層采用紅黑樹，是一種二叉樹
a) 添加的對(duì)象，必須是同一個(gè)類的對(duì)象，使得可以從小到大排序
b)
c) 自然排序（實(shí)現(xiàn)comparable接口）和定制排序（實(shí)現(xiàn)comparator）
i. 自然排序

比較對(duì)象使用compareTo(),而不是equals。對(duì)類實(shí)現(xiàn)comparable接口
ii. 定制排序

Comparator com = new comparator(@override…) ; TreeSet ts = new TreeSet(com)；

比較對(duì)象使用compare()方法，不再是equals

HashSet底層實(shí)現(xiàn)原理
a) 新建一個(gè)HashMap的對(duì)象
b) 將數(shù)據(jù)存放在HashMap的key值中，value值為static final Object Present = new Object, 使得所有的value都為同一個(gè)靜態(tài)Object 對(duì)象PRESENT

Map --接口
a) 雙列數(shù)據(jù)
b) HashMap—Map的主要實(shí)現(xiàn)類；線程不安全，效率高；可以存儲(chǔ)null的key、value
i. LinkedHashMap—在遍歷map元素是，保證添加的順序進(jìn)行遍歷

原因：在原有的HashMap基礎(chǔ)上，添加了一對(duì)指針，指向前一個(gè)和后一個(gè)元素

頻繁的遍歷操作，效率更高

底層使用數(shù)組+鏈表+紅黑樹（jdk8）
c) TreeMap—根據(jù)添加的key、value對(duì)進(jìn)行排序，實(shí)現(xiàn)排序遍歷
i. 考慮key的自然排序和定制排序
ii. 底層使用紅黑樹
d) Hashtable—古老的實(shí)現(xiàn)類；線程安全；效率低；不可存儲(chǔ)null
i. Properties–常用來處理配置文件，key和value都是String類型

Map結(jié)構(gòu)
a) Map中的key：無序的、不可重復(fù)的，使用set存儲(chǔ)所有的key。HashMap重寫HashCode和equals。
b) Map中的value：無序的，可重復(fù)的，使用collection去存儲(chǔ)。Value所在類重寫equals
c) 一個(gè)鍵值對(duì)：構(gòu)成Entry對(duì)象
i. 無序的，不可重復(fù)的，利用set存儲(chǔ)所有entry

HashMap 在jdk7的底層原理
a) HashMap map = new HashMap()；
i. 實(shí)例化后，創(chuàng)建長度為16的一維數(shù)組Entry[] table。
b) Map.put(key1, value1):
i. 首先，調(diào)用key1所在類的hashCode()計(jì)算哈希值，得到存放位置
ii. 數(shù)據(jù)為空，添加成功
iii. 不為空，比較key1和已經(jīng)存在的數(shù)據(jù)的哈希值，若都不相同，添加成功
iv. 不為空，比較key1和已經(jīng)存在的數(shù)據(jù)的哈希值，存在相同，調(diào)用key1的equals(key2)方法，比較的是key，若不相同，添加。
v. 若調(diào)用equals方法返回true：使用value1替換原value，相當(dāng)于修改操作
c) 添加過程的擴(kuò)容問題，擴(kuò)容為原來的二倍，將原來的數(shù)據(jù)復(fù)制過來

HashMap 在jdk8的底層原理
a) New HashMap—底層沒有創(chuàng)建數(shù)組
b) 首次調(diào)用put(), 底層創(chuàng)建長度為16的數(shù)組
c) 底層的數(shù)組是Node[]，而非Entry[]
d) 底層結(jié)構(gòu)式數(shù)組+鏈表+紅黑樹
e) 當(dāng)數(shù)組的某一個(gè)索引位置上的元素以鏈表形式存在的數(shù)據(jù)個(gè)數(shù)>8 且數(shù)組長度大于64，則索引上的所有數(shù)據(jù)改為紅黑樹存儲(chǔ)。

HashMapJDK7源碼
a) 不管初始化的大小是什么，初數(shù)長度一定是2的幾次冪。
b) LoadFactor—加載因子0.75,用于計(jì)算臨界值。提前擴(kuò)容的原因?用于減少鏈表的產(chǎn)生，而且數(shù)組不一定全部放滿，都生成了鏈表了。
c) Threshold—臨界值，超過臨界值開始擴(kuò)容，為LoadFactorcapacity，第一次為0.7516 = 12；
d) 根據(jù)key存放到特定index中：使用&與的位運(yùn)算符
i. Return h&(length-1);?相對(duì)于取余數(shù)%效率高，保證位于數(shù)組中
e) 在不斷添加的過程中，當(dāng)超出臨界值且要存放的位置非空（形成鏈表），則擴(kuò)容到原來的二倍。數(shù)組復(fù)制到擴(kuò)容后的數(shù)組，被重新放各個(gè)數(shù)據(jù)。
f) CreatyEntry操作—table[bucketIndex] = new Entry<>(hash, key, value, e);
i. 其中 hash，key，value為新加入的鍵值對(duì)
ii. e為原來的bucketIndex位置的鍵值對(duì)，構(gòu)造器用next描述，表示新的鍵值對(duì)指向原來的鍵值對(duì)，形成鏈表

HashMapJDK8源碼
a) 對(duì)象創(chuàng)建時(shí)，只賦值了加載因子，沒有創(chuàng)建底層長度16數(shù)組
b) 不再是Entry 而是Node<K,V>[] table;
c) 當(dāng)一條鏈上的數(shù)據(jù)超過8（treeify_THRESHOLD）時(shí)，且當(dāng)前數(shù)組的長度大于64時(shí)，將鏈上的數(shù)據(jù)轉(zhuǎn)為樹結(jié)構(gòu)
d)

LinkedHashMap底層原理
a) 重寫了父類的newNode方法
b) 內(nèi)部類Entry繼承了父類HashMap的內(nèi)部類Node
i. 增加了before和after屬性，用于記錄添加元素的先后順序

Map中常用的方法
a) Map map = new HashMap();
b) 添加
i. Map.put(Object key, Object Value);
ii. Map.putAll(Map m): m中的所以鍵值對(duì)放到map中
c) 修改
i. Map.put(Object key, Object Value); 將原來key上的值改為Value的值
d) 刪除
i. removeValue = Map.remove（Object key）: 根據(jù)key值移除鍵值對(duì)，返回移除的value。不存在返回null
e) 清空
i. map.clear(): 不是將直接map = null（相當(dāng)于map.size()會(huì)有空指針異常），只是清空里面的數(shù)據(jù)
f) 元素查詢
i. Map.get(Object key)：返回value 沒有返回null
ii. Map.containKey(Obj key); Map.containValue(Obj value); 是否包含指定的key或者value
iii. Int size(); 返回多少對(duì)鍵值對(duì)
iv. Equals(Obj obj): 判斷當(dāng)前map和參數(shù)對(duì)象obj是否相等
g) 元試圖操作方法—不用迭代器遍歷（用于collection方法）
i. 所有key構(gòu)成set，value構(gòu)成collection，鍵值對(duì)構(gòu)成Entry對(duì)象，也是set
ii. 將上面的調(diào)用迭代器iterator即可遍歷
iii. 遍歷key

Set set = map.keySet(); ->Iterator it = ser.Iterator();
iv. 遍歷value

Collection values = map.values();
v. 遍歷key—value

Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
a) Entry是map中的內(nèi)部接口

Iterator<Map.Entry<String,Integer>> it = entry.Iterator();

Object obj = it.nextValue();

得到的是entry對(duì)象，進(jìn)行強(qiáng)轉(zhuǎn)

Map.Entry entry = (Map.Entry)obj;

或者直接Map.Entry<String, Integer> entry = it.next();

調(diào)用Entry類的getKey和getValue方法

TreeMap方法
a) 向treeMap中添加keyValue，key必須為同一對(duì)象，用于排序
b) 自然排序：類中實(shí)現(xiàn)的comparable和定制排序構(gòu)造器重寫comparator

Properties
a) 用于配置文件，key和value都是String類型

Collections工具類
a) 操作Set，list，Map等集合的工具類
b) 多為靜態(tài)方法
c) Collection是集合接口，Collections是工具類
d) Reverse(list), sort(list), shuffle(list): 對(duì)list進(jìn)行處理，反轉(zhuǎn)，排序（自然排序or定制排序），隨機(jī)排序
e) Object max(Collection, comparator): 獲取collection中最大值
f) Int frequency(Collection, Object): Object出現(xiàn)了幾次
g) List dest = Arrays.asList(new Object[list.size()]);
i. 先將兩個(gè)數(shù)組的size設(shè)成相同
ii. Collections.copy(dest, list)復(fù)制操作
h) 線程安全方法ArrayList和HashMap都不安全
i) Collections.synChronizedXxxx() 方法
j) List list1 = Collections.synchronizedList(list);