一.集合概述

1 為什么需要使用集合？
引入案例:存儲每天產(chǎn)生的新聞。
是要解決數(shù)組的局限性（定長），由于數(shù)組定長，可能會導(dǎo)致內(nèi)存浪費或者內(nèi)存不夠。
需要一種技術(shù)：能夠根據(jù)數(shù)據(jù)量而動態(tài)伸縮內(nèi)存空間一種技術(shù)。

與數(shù)組不同，沒有長度限制
與數(shù)組不同，集合提供更多方便操作的方法
與數(shù)組不同，集合可以裝不同類型的對象

2 什么是集合？
集合也叫容器，是用來裝其它類型的對象元素的數(shù)據(jù)結(jié)構(gòu)，有點類似數(shù)組
jdk提供一套容器框架，用來操作多個或者一組元素的容器
沒有長度(元素個數(shù))限制
集合提供一套各 種各樣的api供我們選擇，達到不同的操作目的
集合中的方法封裝了一些算法，以便我們快速查找或者增刪，或者排序。。。。
集合本身也是一個對象

?

二.如何研究集合？集合的API體系

?

?

除了上面的集合圖之外，還需學(xué)習以下接口和工具類
比較排序接口
Comparable
Comparator
遍歷迭代接口
Iterable
Iterator
工具類
Collections
Arrays
面試題：Collection和Collections區(qū)別

11個接口7個實現(xiàn)類2個工具類

Collection VS Map
Collection - 元素是一個一個對象
Map - 元素是一對對的，由key對象與value對象組成

?

?

三.Collection

1 概述
Collection分支的根接口

所有這個分支下面的實現(xiàn)都具有該接口中的方法

在某些場合，使用Collection具有更普遍的適應(yīng)性
Collection coll = new ?();

public void fn(Collection coll){
//.....
}
fn(?);

2 方法介紹
add() - 添加一個元素
addAll() - 添加一組元素
clear() - 清空整個集合
contains() -判斷 是否包含某個元素
containsAll() - 判斷 是否包含一組元素
equals() - 比較一個集合與另一個集合是否相同，挨個比較集合中所有元素
hashCode() - 返回此集合的哈希碼
isEmpty() - 是不是size為0，元素的個數(shù)是不是為0
iterator() - 獲得此集合的迭代器，用來遍歷集合
remove() - 刪除指定的元素
removeAll() - 刪除一組指定的元素
retainAll() - 當前集合與指定集合(參數(shù))求交集
size() - 返回元素個數(shù)
toArray() - 將集合轉(zhuǎn)為數(shù)組

?

?

?

?

?

?

四.List

1 概述
有序的可重復(fù)的 collection（也稱為序列）。內(nèi)部維護一個索引(下標)。
此接口的用戶可以對列表中每個元素的插入位置進行精確地控制。
用戶可以根據(jù)元素的整數(shù)索引（在列表中的位置）訪問元素，并搜索列表中的元素
有序，就是插入順序（位置）

2 示意圖

?

3 List的操作
除了具有Collection的所有方法外，還提供通過下標來操作的方法
add(int index, E element) - 將某個元素添加到指定的下標處
addAll(int index, Collection<? extends E> c) - 將一組元素添加到指定的下標處
get(int index) - 通過下標來獲得某個具體的元素
indexOf(Object o) -獲得指定元素的下標，從集合的頭開始找
lastIndexOf(Object o) - 獲得指定元素的下標，集合的尾部開始找
listIterator() - 返回List的特有的迭代器(ListIterator)，ListIterator功能比較強大
remove(int index) -通過下標來刪除元素
set(int index, E element) - 替換指定下標位置的元素
subList(int fromIndex, int toIndex) - 通過下標截取子集

五.ArrayList和LinkedList

1 概述
List 接口存儲一組不唯一(里面元素可重復(fù))，有序（插入順序）的對象
ArrayList(順序表)類實現(xiàn)了長度可變的數(shù)組，在內(nèi)存中分配連續(xù)的空間。遍歷元素和隨機訪問元素的效率比較高

?

LinkedList類采用鏈表存儲方式。插入、刪除元素時效率比較高

?

這2個類是List的實現(xiàn)類，但并不是直接實現(xiàn)

?

?

2 ArrayList 和LinkedList的相關(guān)操作
public ArrayList(int initialCapacity)//創(chuàng)建集合時，給定初始容量，以避免多余的數(shù)組重建。
int newCapacity = oldCapacity (oldCapacity >> 1);
public void ensureCapacity(int minCapacity)//給集合重新設(shè)置容量，以避免多余的數(shù)組重建。
public void trimToSize() //ArrayList的尺寸是按照2的冪指數(shù)來增長的.比如你有17個元素,其實ArrayList是分了32空間,
//其中有15個是空的? trimToSize就是把這15個給砍掉了...
在List中有很多操作都要判斷指定的元素是否在集合中，例如contains(Object o), remove(Object o),indexOf(Object o),
這些方法內(nèi)部都使用eqauls()來比較是否相同

3 ArrayList 和 LinkedList的區(qū)別
ArrayList-查找快，增刪慢
底層用數(shù)組實現(xiàn)，數(shù)組本身有下標，通過下標查找特別快，但是增刪的因為要移動元素，所以很慢
LinkedList - 查找慢，增刪快
底層用雙向鏈表實現(xiàn)，本身沒有下標，需要額外的維護下標索引，導(dǎo)致查找非常慢。但是因為使用鏈表，增刪只改變一下引用，不需要移動元素就可以做到增刪，所以特別快

?

?

六.ArrayList與Vector區(qū)別：

相同點：
回顧：StringBuffer(線程安全) 與 StringBuilder(線程不安全)
1.兩者都實現(xiàn)了List接口（List接口繼承了Collection接口）。
2.兩者都是有序集合，即存儲在這兩個集合中的元素的位置都是有順序的，相當于一種動態(tài)的數(shù)組。
3.存放的數(shù)據(jù)都允許重復(fù)。
不同點：
1.同步性：
Vector是線程安全的，也就是說是它的方法之間是線程同步的，適用于多線程訪問集合，訪問效率低。
ArrayList是線程序不安全的，它的方法之間是線程不同步的，適用于單線程訪問集合，不考慮線程安全，訪問效率高。
2.數(shù)據(jù)增長：
Vector默認增長原來的一倍，可以手工設(shè)置增長空間的大小。
ArrayList默認增加原來的0.5倍，不可以手工設(shè)置增長空間的大小。
newCapacity = oldCapacity oldCapacity >>1;//相當于 oldCapacity oldCapacity /2

七.Queue與Stack

1 概述
叫隊列，這種數(shù)據(jù)結(jié)構(gòu)有一種特點，先進先出（FIFO）
與Stack(棧)相對，棧是先進后出(FILO)

?

2 API方法
拋出異常 返回特殊值
插入 add(e) offer(e)
移除 remove() poll()
檢查 element() peek()

八.LinkedList的隊列的特點

public class TestQueue{
  public static void main(String[] args){
     //Queue q = new ArrayBlockingQueue(2);//有容量限制的隊列
     
     Queue q = new LinkedList();
     /*
     q.add("haha");
     q.add("hehe");
     q.add("xixi");
     */
     q.offer("haha");
     q.offer("hehe");
     q.offer("xixi");
     
     /*
     System.out.println("==========1============>" q);
     Object o1 = q.remove();
     System.out.println(o1 "==========2============>" q);
     Object o2 = q.remove();
     System.out.println(o2 "==========3============>" q);
     Object o3 = q.remove();
     System.out.println(o3 "==========4============>" q);
     Object o4 = q.remove();
     */
     
     /*
     System.out.println("==========1============>" q);
     Object o1 = q.poll();
     System.out.println(o1 "==========2============>" q);
     Object o2 = q.poll();
     System.out.println(o2 "==========3============>" q);
     Object o3 = q.poll();
     System.out.println(o3 "==========4============>" q);
     Object o4 = q.poll();
     */
     
     /*
     System.out.println("==========1============>" q);
     Object o1 = q.element();
     System.out.println(o1 "==========2============>" q);
     q.clear();//清空隊列
     Object o2 = q.element();
     System.out.println(o2 "==========2============>" q);
     */
     
     System.out.println("==========1============>" q);
     Object o1 = q.peek();
     System.out.println(o1 "==========2============>" q);
     q.clear();//清空隊列
     Object o2 = q.peek();
     System.out.println(o2 "==========2============>" q);
  }
}

?

九.Set

1 Set概述
它是Collection子接口
特點是：無序的，不可重復(fù)
與List不同，Set沒有下標

2 Set的API
全部方法都繼承自Collection,沒有自己擴展的方法

十.HashSet

（1）HashSet概述

是Set體系中比較常用的一個實現(xiàn)類
HashSet底層用的就是HashMap
HashMap是采用Hash算法的一種數(shù)據(jù)結(jié)構(gòu)
Hash算法用快速尋找堆中的對象

（2）HashSet數(shù)據(jù)結(jié)構(gòu)

?

構(gòu)造方法
1）初始容量 - 也叫桶
2）加載因子 - 擴充容量用的
當桶數(shù)用完時，需要擴展當前容量*加載因子

（3）HashSet的add方法的流程

?

?

（4）equals()和hashCode的約定

hashCode()是Object中的方法 ，該方法是根據(jù)對象的地址值通過某種算法算出來的值
如果對象不同，則hashCode()返回的值一定不同

但是，作為開發(fā)者，我們經(jīng)常需要主觀上認為2個不同的對象為同一個，比如說姓名和年齡相同就認為是同一個，此前我們是用equals()定制這個主觀的認同規(guī)則

api中equals方法的約定;注意：當equals方法被重寫時，通常有必要重寫 hashCode 方法，以維護 hashCode 方法的常規(guī)協(xié)定，該協(xié)定聲明相等對象必須具有相等的哈希碼

api中hashCode的約定：equals中比較了哪些字段(屬性)，就用那些屬性來生成hashCode就可以了

十一.Iterator

1 概述
迭代器，用于遍歷集合，只要是實現(xiàn)了Collection接口，都一定具有iterator()方法，或者foreach方式遍歷集合。該方法就是返回Iterator接口一個實例

2 Iterator操作

十二.LinkedHashSet

1 概述
Set接口下的一特例，它能夠維持插入的順序
此實現(xiàn)可以讓客戶免遭未指定的、由 HashSet 提供的通常雜亂無章的排序工作，而又不致引起與 TreeSet 關(guān)聯(lián)的成本增加

2 LinkedHashSet操作
它的底層就是使用LinkedHashMap.

3 使用場合
如果我們的需求是元素不能重復(fù)，然后順序是固定（插入順序），此時就可以用LinkedHashSet

十三.排序樹：TreeSet

1 概述
TreeSet底層就是使用TreeMap,它會按照自然順序或比較器提供的順序進行排序。
以二叉樹的方式進行自然排序一個Set
Example:7, 5,2,4,12,13,8,15, 10,1
排序后：1 2 4 5 7 8 10 12 13 15
二叉樹遍歷方式：前序，中序，后序（遞歸算法）

?

?

如果要使用TreeSet，則添加到里面的元素必須實現(xiàn)Comparable接口
或者提供定制的Comparator接口的實現(xiàn)，提供這了Comparator接口的實現(xiàn)后可以不用再實現(xiàn)Comparable接口?。。?/p>

十四.Comparable

1 概述
叫做可比較接口
實現(xiàn)該接口，表示這個類的對象是可以排序的，這種排序被稱為類的自然排序，接口中的 compareTo 方法被稱為它的自然比較方法
實際就是我們的類可以實現(xiàn)這個接口來定制自己的排序比較規(guī)則，例如Person是按age來排序

2 API方法
//開發(fā)者可以實現(xiàn)該方法來定制比較規(guī)則
//如果該對象小于、等于或大于指定對象，則分別返回負整數(shù)、零或正整數(shù)
int compareTo(T o)

/**
重寫定制自己的比較規(guī)則
先按年齡倒敘，如果年齡相等則按分數(shù)升序。
*/
public int compareTo(Object o) {
Student student = (Student) o;
if (this.age!=student.getAge()) {
return -(this.age-student.getAge());//按年齡倒敘
}else {
return this.score - student.getScore();//升序
}
}

?

十五.Comparator

1 概述
 比較器接口，可以讓開發(fā)者更加精確和靈活的控制排序
 Collections.sort(Comparator)
 Arrays.sort(Comparator)
 TreeSet(Comparator)


2 API方法
/**
  比較器1 ，按年齡倒敘
*/
class MyComparator  implements Comparator<Student>{
  public int compare(Student o1, Student o2) {
     return -(o1.getAge()-o2.getAge());
  }
}
/**
  比較器2 ，按年齡倒敘，如果年齡相等，則按分數(shù)升序
*/
class MyComparator2  implements Comparator<Student>{
  public int compare(Student o1, Student o2) {
     if (o1.getAge()!=o2.getAge()) {
       return -(o1.getAge()-o2.getAge());
     }else {
       return o1.getScore()-o2.getScore();
     }
  }
}

?

?

十六.Map

1 概述
映射，key - value
一個鍵(key) 決定一個值(value)
key不能重復(fù)，value可以重復(fù)
key沒有順序

2 Api方法
clear() - 清空Map
containsKey(Object key) - 是否包含指定的key
containsValue(Object value) - 是否包含指定的valie
entrySet() - 返回映射項(Map.Entry)組成的Set
equals(Object o) - 比較2個Map
get(Object key) - 通過key來獲得value
hashCode() - 返回hash碼
isEmpty() - 判斷是否為空，其實就是判斷 size==0
keySet() - 返回由key組成 的Set
put(K key, V value) - 將key和value添加到Map中
putAll(Map<? extends K,? extends V> m) - 將另一個Map中的所有key-value添加到本Map中
remove(Object key) -通過key來刪除一對Entry
values() - 返回由所有的value組成的Collection
size() - 返回Map中的Entry的個數(shù)

十七.HashMap

1 概述
HashMap實現(xiàn)了Map接口
key也是跟HashSet一樣，采用了哈希算法
HashSet底層用的就是HashMap

2 API操作

十八.HashMap和Hashtable區(qū)別：

1.同步性：
Hashtable是線程安全的，也就是說是它的方法之間是線程同步的，適用于多線程訪問集合，訪問效率低。
HashMap是線程序不安全的，它的方法之間是線程不同步的，適用于單線程訪問集合，不考慮線程安全，訪問效率高。
2.值
只有HashMap可以讓你將null值作為一個表的條目的key或value
Hashtable是不允許的,運行時拋NullPointerException
3.Hashtable是Dictionary的子類，HashMap是Map接口的一個實現(xiàn)類；

十九.LinkedHashMap

可以對照著LinkedHashSet來學(xué)習，它的底層就是使用LinkedHashMap.
可以維持key-value插入的順序

二十.TreeMap

參照TreeSet來學(xué)習,TreeSet底層就是使用TreeMap,它會按照自然順序或比較器提供的順序進行排序。

默認按照key的自然順序排序

如果想更精確更活的排序，可以采用Comparator接口

二十一.Iterable：可迭代的

可迭代的接口
與Iterator有關(guān)系 ，實現(xiàn)了Iterable接口的類，必定會返回一個Iterator
所有的Collection都實現(xiàn)了Iterable
Iterable 創(chuàng)建 Iterator

?

實現(xiàn)Iterable接口的類，都可以用ForEach來遍歷
for(Object v : 實現(xiàn)了Iterable接口的類){

}

二十二.Collections

1 概述
Collections 是操作Collection的工具類，里面的方法都是static的，包括二分查找法，排序，反轉(zhuǎn)，填充，打亂，生成不可變的集合。。。。

2 重點學(xué)習
binarySeach()-快速在List集合中查找指定的對象，前提是查找之前要對List先進行正排序，返回-1表示找不到指定的元素
sort() - 按自然排序
sort(Comparator) - 按比較器定制的規(guī)則來排序,可以用自定義比較器來實現(xiàn)排序，比如是倒敘排序。
reverse() - 將List集合的元素反轉(zhuǎn)
fill() - 填充
shuffle() -打亂，打紙牌。

面試題：
Collection 和 Collections的區(qū)別。
Collections是個java.util下的類，它包含有各種有關(guān)集合操作的靜態(tài)方法。
Collection是個java.util下的接口，它是各種集合結(jié)構(gòu)的父接口。

public class TestCollections {
public static void main(String[] args) {
List list = new ArrayList();
list.add(2);
list.add(1);
list.add(5);
Collections.sort(list,new MyComparator());//按照比較器排序
System.out.println(list);
}
}
class MyComparator implements Comparator{
@Override
public int compare(Object o1, Object o2) {
int i1 = (Integer)o1;
int i2 = (Integer)o2;
return -(i1-i2);
}
}

?

?

二十三.Arrays

1 概述
用來操作數(shù)組的工具為在，包括填充，排序等等

2 API方法
asList(T[] a) - 將一個數(shù)組轉(zhuǎn)的轉(zhuǎn)換成List，與Collection的toArray()方法

?

binarySearch() - 二分查找
copyOf() - 復(fù)制指定數(shù)組的指定個數(shù)的元素，形成一個新的數(shù)組
copyOfRange() - 復(fù)制指定數(shù)組的指定范圍的元素，形成一個新的數(shù)組
equals()- 比較2個數(shù)組是否"相同"
fill() - 用指定的元素來填充數(shù)組
sort() - 排序，如果不傳比較器(Comparator)，則按自然排序(Comparable)，如果傳了Comparator，就按比較器規(guī)則排序
toString（） - 將數(shù)組轉(zhuǎn)成字符的格式

二十四.枚舉接口：Enumeration

public static void main(String[] args) {
    Vector v = new Vector();
    v.add("java");
    v.add("oracle");
    v.add("linux");
    v.add("html");
    //Iterator
    Enumeration<String> e = v.elements();
    while(e.hasMoreElements()){
      String s = e.nextElement();
      System.out.println(s);
    }
    String s = null;
    for(Enumeration<String> e2 = v.elements();e2.hasMoreElements();){
     s = e2.nextElement();
      System.out.println(s);
    }
 }
 

?

二十五.包裝類

（1）概述

在java里，我們有八個基本數(shù)據(jù)類型，它們可以做各種運算，例如加減乘除。。。
但是這些基本數(shù)據(jù)類型沒有更多的方法給開發(fā)者使用，所以Java對每個基本數(shù)據(jù)類型都提供一個包裝類與之對應(yīng)
byte - Byte
short - Short
int - Integer
long - Long
float - Float
double - Double
char - Character
boolean - Boolean

這也體現(xiàn)了java是一種完全面向?qū)ο蟮恼Z言。
面試題：java提供了八大基本數(shù)據(jù)型的包裝類，為什么還保留原來的基本數(shù)據(jù)類型？
1） 包裝類型沒有提供相應(yīng)的（ ，—，*，/等）運算方法
2） 包裝類的對象比基本類型占用更多的內(nèi)存
3）基本數(shù)據(jù)類型操作起來更加簡單方便。

?

（2）封箱解箱

?

自動封箱解箱，是Jdk1.5開始提供的新特性

自動封箱：將基本類型自動包裝成包裝類，這個過程是由編譯器自動完成
//想調(diào)用基本數(shù)據(jù)類型的更多功能，必須轉(zhuǎn)換為相應(yīng)的包裝類型
Integer i = 6;//編譯器：Integer i = new Integer(6);//自動封箱
System.out.println(i);


自動解箱：將包裝類型自動轉(zhuǎn)換成基本類型，這個過程是由編譯器自動完成
//想更方便的操作，就解箱為基本數(shù)據(jù)類型， -*/
Integer i2 = new Integer(7);
int i3 = i2;//編譯器：int i3 = i2.intValue();//自動解箱
System.out.println(i3);
list.add(7);//自動封箱，相當于list.add(new Integer(7));
int i = list.get(0); //自動解箱，相當于int i = list.get(0).intValue(); 小心預(yù)防拋nullPoiterException

以下要小心，這樣會拋nullPoiterException
Integer i = null;
int b = i;//相當于int b = null.intValude(); 所以拋nullPoiterException

?

（3）使用

/*
     String s = "123";
     int i1 = Integer.parseInt(s);
     Integer i2 = Integer.valueOf(s);
     */
     
     Scanner scan = new Scanner(System.in);
     while(true){
       String iStr = scan.nextLine();
       int i = Integer.parseInt(iStr);
       System.out.println("----->" i);
       String line = scan.nextLine();
       System.out.println("String類型的:" line);
     }

?

（4）常量池

Integer這個包裝類內(nèi)部維護了一個常量池，類似String了維護常量池。
這個常量池能夠緩存-128 ~ 127 這個范圍的包裝類對象，可以通過IntegerCatch查看常量池源碼。
當我們創(chuàng)建一個新的在-128~127之間的值時，實際上是直接到常量池里去取。
Integer i3 = 112; //new Integer(112)，會被放入常量池
Integer i4 = 112; //直接從常量池中取出已有對象
System.out.println(i3==i4);//true 同一個對象

Integer i3 = 130; //不會放入常量池，常量池只裝-128 ~ 127的對象
Integer i4 = 130;
System.out.println(i3==i4);//false 注意：超過127不會被存到常量池中，會重新new一個對象。
而下面這2個代碼不會去常量池去取
Integer i5 = new Integer(112);
Integer i6= new Integer(112);
System.out.println(i5==i6);
作用：
是為了方便快捷地創(chuàng)建某些對象而出現(xiàn)的，當需要一個對象時，就可以從池中取一個出來（如果池中沒有則創(chuàng)建一個），則在需要重復(fù)重復(fù)創(chuàng)建相等變量時節(jié)省了很多時間。
要比較2個Integer對象是否相等，要用equals()方法