1.1為什么會(huì)出現(xiàn)集合框架
[1] 之前的數(shù)組作為容器時(shí)，不能自動(dòng)拓容
[2] 數(shù)值在進(jìn)行添加和刪除操作時(shí)，需要開(kāi)發(fā)者自己實(shí)現(xiàn)添加和刪除。
1.2Collection接口
1.2.1Collection基礎(chǔ)API
Java集合框架提供了一套性能優(yōu)良、使用方便的接口和類(lèi)，它們位于java.util包中。
Collection表示集合的根接口，可以看成一個(gè)容器，存儲(chǔ)了很多對(duì)象，這些對(duì)象稱(chēng)為Collection元素。Collection要求元素必須是引用數(shù)據(jù)類(lèi)型。
Collection 根據(jù)其元素的特征可以分為
List接口->元素有序、可重復(fù)
Set 接口-> 元素?zé)o序、不可重復(fù)
思考:Collection提供了具備什么能力？=> 對(duì)容器增刪改查
public class Test01 {
public static void main(String[] args) {
/**
* 增:add/addAll
* 刪:clear/remove/removeAll/retainAll
* 改:
* 查:contains/constainsAll/size/isEmpty
* 其他:equals
* 遍歷:iterator()
*/
Collection col1 = new ArrayList();
col1.add("apple"); // Object obj = "apple" 多態(tài)
col1.add("banana"); // Integer i = 1; 裝箱
// 注意:Collection可以添加任意類(lèi)型的數(shù)據(jù)，最好添加統(tǒng)一類(lèi)型的數(shù)據(jù)方便未來(lái)統(tǒng)一訪(fǎng)問(wèn)。
Collection col2= new ArrayList();
col2.add("apple");
col2.add("banana");
// col1.addAll(col2);
//System.out.println(col1);
//col1.clear(); // 清空集合
//col1.remove("apple"); // 移除指定元素
//col1.removeAll(col2); // 移除指定集合中的多個(gè)元素
//col1.retainAll(col2); // 保留指定集合col2中的元素，其他刪除
//System.out.println(col1);
//col1.remove(1); // [apple, banana, 2]
//System.out.println(col1.contains("apple"));
//System.out.println(col1.containsAll(col2));
//System.out.println(col1.size()); // 返回元素個(gè)數(shù)
//System.out.println(col1.isEmpty());
boolean r = col1.equals(col2);
System.out.println(r);
}
}
1.2.2遍歷和Iterable
Iterable 表示可遍歷的，具備遍歷的能力。其定義了一個(gè)方法iterator用于返回集合上的迭代器，該迭代器用于foreach快速遍歷。
1.2.2遍歷和Iterable
Iterable 表示可遍歷的，具備遍歷的能力。其定義了一個(gè)方法iterator用于返回集合上的迭代器，該迭代器用于foreach快速遍歷。
public static void main(String[] args) {
Collection col1 = new ArrayList();
col1.add("apple");
col1.add("coco");
col1.add("banana");
// 遍歷集合中的元素
/*
* Object 表示迭代元素類(lèi)型
* item 表示迭代變量
* */
// 快速遍歷
for (Object item : col1) {
System.out.println(item);
}
// 迭代器遍歷
Iterator it1 = col1.iterator(); // 返回集合的迭代器
while(it1.hasNext()) {
String item = (String)it1.next();
System.out.println(item);
}
// 寫(xiě)法(更節(jié)省內(nèi)存)
for(Iterator it2 = col1.iterator();it2.hasNext();) {
String item = (String)it2.next();
System.out.println(item);
}
}
1.3List接口
List 接口稱(chēng)為有序的序列，提供了索引(index)對(duì)容器中的元素進(jìn)行增、刪、改、查。
index讓List集合中的元素有序、可重復(fù)。
1.3.1List接口常用方法
public static void main(String[] args) {
/**
* 增:add(index,e)/addAll(index,c)/add(e)/addAll(c)/
* 刪:remove(index)/clear()/remove(e)/removeAll(c)/retainAll(c)
* 改:set(index,e);
* 查:get(index)/indexOf(e)/lastIndexOf(e)/contains/constainsAll/size/isEmpty
* 其他:equals
* 遍歷:iterator() / listIterator()
*/
List list1 = new ArrayList();
// 【1】添加
// 追加
list1.add("apple");
list1.add("banana");
// 在指定index位置添加元素coco
list1.add(0,"coco");
List list2 = new ArrayList();
list2.add(1);
list2.add(2);
list1.addAll(0, list2);
System.out.println(list1);
// 【2】移除
//list1.remove(0);
//System.out.println(list1);
// 【3】修改
list1.set(0, 100);
System.out.println(list1);
// 【4】查看元素 可能產(chǎn)生IndexOutOfBoundsException
// System.out.println(list1.get(6));
System.out.println(list1.indexOf(200));
// list1.add(2);
// System.out.println(list1.lastIndexOf(2));
}
1.3.2List接口遍歷
List接口中提供了一個(gè)listIterator方法，返回列表的列表迭代器，屬于ListIterator接口，提供以任意方向(正向、逆向)遍歷列表，同時(shí)在遍歷列表的過(guò)程中還可以操作列表。
public static void main(String[] args) {
// List 集合的遍歷
List list = new ArrayList();
list.add("apple");
list.add("banana");
list.add("coco");
// 【1】 for 循環(huán)
for(int i=0;i<list.size();i++) {
String item = (String) list.get(i);
System.out.println(item);
}
// 【2】 快速遍歷
for(Object item:list) {
System.out.println(item);
}
// 【3】iterator
Iterator it1 = list.iterator();
while(it1.hasNext()) {
System.out.println(it1.next());
}
// 【4】listIterator 獲取列表的迭代器
ListIterator it2 = list.listIterator();
// 正向遍歷(A)
while(it2.hasNext()) {
System.out.println(it2.next());
}
// 逆向遍歷(B)
while(it2.hasPrevious()) {
System.out.println(it2.previous());
}
// 【5】從指定位置開(kāi)始迭代(C)
System.out.println("--listIterator(index)--");
ListIterator it3 = list.listIterator(1);
while(it3.hasNext()) {
System.out.println(it3.next());
}
}
思考:Iterator和ListIterator區(qū)別？
1.4數(shù)據(jù)結(jié)構(gòu)(補(bǔ)充知識(shí))
1.4.1線(xiàn)性表
根據(jù)物理空間是否連續(xù)，可以把線(xiàn)性表分為數(shù)組和鏈表。
數(shù)組:物理上連續(xù)、邏輯上也連續(xù)的內(nèi)存空間，通過(guò)index來(lái)訪(fǎng)問(wèn)元素。
鏈表:物理上不連續(xù)、邏輯上連續(xù)的內(nèi)存空間，也可以通過(guò)index來(lái)訪(fǎng)問(wèn)元素。
1.4.2隊(duì)列
隊(duì)列是以一個(gè)方向先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)
1.4.3棧
棧是一種先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)
1.5ArrayList、 LinkedList、Vector
1.5.1ArrayList
ArrayList 類(lèi)是List接口的實(shí)現(xiàn)類(lèi)，底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組。
ArrayList 是數(shù)組的包裝類(lèi)，jdk1.2出現(xiàn)，提供了操作底層數(shù)據(jù)的很多方法，同時(shí)向ArrayList中添加元素時(shí)，容器可以自動(dòng)拓容。
ArrayList 是線(xiàn)程不安全。
API和List接口一樣。
1.5.2Vector
Vector 類(lèi)是List接口的實(shí)現(xiàn)類(lèi)，底層數(shù)據(jù)結(jié)構(gòu)也是數(shù)組。
Vector是數(shù)組的包裝類(lèi)，jdk1.0出現(xiàn)，提供了操作底層數(shù)據(jù)的很多方法，同時(shí)向Vector中添加元素時(shí)，容器可以自動(dòng)拓容，也提供了自身特有的方法xxxElement等方法。
Vector 是線(xiàn)程安全。
面試題:ArrayList和Vector有什么區(qū)別？
相同點(diǎn):
[1] 都是List接口的實(shí)現(xiàn)類(lèi)、底層數(shù)據(jù)結(jié)構(gòu)都是數(shù)組
不同點(diǎn)
[1] ArrayList jdk1.2;Vector jdk1.0
[2] ArrayList 線(xiàn)程不安全，效率高;Vector 線(xiàn)程安全，效率低
[3] Vector較ArrayList擁有特有的方法。
1.5.3LinkedList
LinkedList 是List接口的實(shí)現(xiàn)類(lèi)，底層數(shù)據(jù)結(jié)構(gòu)是鏈表。
LinkedList是鏈表的包裝類(lèi)，jdk1.2出現(xiàn)，提供了操作底層數(shù)據(jù)的很多方法，當(dāng)向LinkedList中添加元素時(shí)，通過(guò)鏈入元素增加容量。
LinkedList線(xiàn)程不安全。
public class Test01 {
public static void main(String[] args) {
List list1 = new LinkedList();
// 【1】添加
list1.add("apple");
list1.add("banana");
list1.add("coco");
System.out.println(list1);
// 【2】刪除
list1.remove("apple");
// 【3】修改
list1.set(0, "banana x");
System.out.println(list1);
// 【4】查看
System.out.println(list1.get(0));
}
}
LinkedList也實(shí)現(xiàn)了棧、隊(duì)列、雙向隊(duì)列接口。
以棧的方式訪(fǎng)問(wèn)LinkedList
public class Test02 {
public static void main(String[] args) {
// 以棧形式訪(fǎng)問(wèn)
LinkedList stack1 = new LinkedList();
// 入棧
stack1.push("apple");
stack1.push("banana");
// 出棧
System.out.println(stack1.pop());
System.out.println(stack1.pop());
// 如果棧中沒(méi)有元素，拋出NoSuchElementException
System.out.println(stack1.pop());
}
}
以隊(duì)列(Queue接口)的方式訪(fǎng)問(wèn)LinkedList
public static void main(String[] args) {
// 以隊(duì)列形式訪(fǎng)問(wèn)
LinkedList queue = new LinkedList();
// 入隊(duì)
/*
頭(出口)<----------尾(入口)
---------------------
apple banana coco
---------------------
*/
//queue.add("apple");
//queue.add("banana");
//queue.add("coco");
//System.out.println(queue);
// 出隊(duì)
//queue.remove();
//queue.remove();
//queue.remove();
// 拋出NoSuchElementException
//queue.remove();
//System.out.println(queue);
// 檢測(cè)元素:獲取但不移除此列表的頭（第一個(gè)元素）
//System.out.println(queue.element());
//System.out.println(queue.element());
/*queue.offer("apple");
queue.offer("banana");
queue.offer("coco");*/
System.out.println(queue);
//queue.poll();
//System.out.println(queue);
//queue.poll();
//queue.poll();
// 如果隊(duì)列為空，返回null
//String item = (String)queue.poll();
//System.out.println(item);
System.out.println(queue.peek());
}
以雙向隊(duì)列(DeQue接口)方式訪(fǎng)問(wèn)LinkedList
public static void main(String[] args) {
// 以雙向隊(duì)列形式訪(fǎng)問(wèn)
LinkedList queue = new LinkedList();
/*
*
頭 尾
<-------------------
---------------------
apple banana coco
---------------------
------------------->
*/
queue.addFirst("apple");
queue.addLast("banana");
queue.addLast("coco");
//queue.removeFirst();
//queue.removeLast();
//queue.removeLast();
// NoSuchElementException
//queue.removeLast();
//System.out.println(queue);
System.out.println(queue.getFirst());
System.out.println(queue.getLast());
}
1.6泛型（generic）
1.6.1泛型概念(A)
泛型允許程序員在強(qiáng)類(lèi)型程序設(shè)計(jì)語(yǔ)言中編寫(xiě)代碼時(shí)定義一些可變部分。
那些可變部分在使用前必須作出指明。形式
ArrayList<T> list = null;
表示聲明了一個(gè)ArrayList容器，容器中存儲(chǔ)的數(shù)據(jù)類(lèi)型是T類(lèi)型，T類(lèi)型此時(shí)就是泛型。
T表示一種數(shù)據(jù)類(lèi)型，但現(xiàn)在還不確定。
泛型在使用時(shí)，一定要確定類(lèi)型。
ArrayList<String> list2 = new ArrayList<String>();
表示聲明了一個(gè)ArrayList容器，容器中存儲(chǔ)的數(shù)據(jù)類(lèi)型是String類(lèi)型。
泛型只在編譯器起作用，運(yùn)行時(shí)不知道泛型的存在。
1.6.2泛型擦除(C)
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<Integer>();
System.out.println(list instanceof ArrayList);
System.out.println(list instanceof ArrayList<?>);
System.out.println(list instanceof ArrayList<Integer>); //error
}
Cannot perform instanceof check against parameterized type ArrayList<Integer>. Use the form ArrayList<?> instead since further generic type information will be erased at runtime
泛型就是程序設(shè)計(jì)過(guò)程中將類(lèi)型參數(shù)化。
1.6.3泛型類(lèi)(A)
當(dāng)一個(gè)類(lèi)中的屬性類(lèi)型不確定時(shí)，此時(shí)可以把該屬性聲明為泛型。
public class Student<T> {
private T t;
public T getT() {
return t;
}
public void setT(T t) {
this.t = t;
}
}
思考:請(qǐng)?jiān)O(shè)計(jì)一個(gè)容器，提供增刪改查的方法？
1.6.4泛型方法(A)
當(dāng)一個(gè)方法的形參參數(shù)類(lèi)型不確定時(shí)，可以使用泛型。
public class Student{
/*
public void add(int a,int b) {
System.out.println(a+b);
}
public void add(float a,float b) {
System.out.println(a+b);
}
public void add(char a,char b) {
System.out.println(a+b);
}
public void add(String a,String b) {
System.out.println(a+b);
}
*/
public <T> void add(T a,T b) {
System.out.println(a.toString()+b.toString());
}
}
泛型方法在一定程度上優(yōu)化了方法重載，不能取代。
泛型的可變參數(shù)
// 方法的可變參數(shù)
/public void add(int...args) {
// 方法的可變參數(shù)在方法調(diào)用時(shí)，以args數(shù)組形式存在于方法中
System.out.println(Arrays.toString(args));
}/
public <T> void add(T...args) {
System.out.println(Arrays.toString(args));
}
泛型的可變參數(shù)方法進(jìn)一步優(yōu)化了方法重載，不能完全取代。
1.6.5泛型接口(C)
當(dāng)泛型接口中的方法類(lèi)型(返回值、形參)不太確定，可以使用泛型接口。
public interface MyInterface<T> {
public void showInfo(T a);
}
實(shí)現(xiàn)類(lèi)知道操作接口中方法的參數(shù)類(lèi)型
public class ImplClass implements MyInterface<String>{
@Override
public void showInfo(String a) {
// TODO Auto-generated method stub
}
}
實(shí)現(xiàn)類(lèi)不知道實(shí)現(xiàn)接口中方法的參數(shù)類(lèi)型，實(shí)現(xiàn)類(lèi)繼續(xù)泛下去。
public class ImplClass2<T> implements MyInterface<T>{
@Override
public void showInfo(T a) {
// TODO Auto-generated method stub
}
}
1.6.6泛型的上限和下限(C)
[1]泛型上限
public static void print(ArrayList<? extends Pet> list) {
for(Pet pet:list) {
pet.showInfo();
}
}
<? extends A> 表示?必須A的子類(lèi)，A作為上限已經(jīng)確定。
ArrayList<? extends A> list 表示聲明了一個(gè)容器list，list中存儲(chǔ)的元素必須是A的子類(lèi)。
[2]泛型下限
<? super A> 表示?必須A的父類(lèi)，A作為下限已經(jīng)確定。
ArrayList<? super A> list 表示聲明了一個(gè)容器list，list中存儲(chǔ)的元素必須是A的父類(lèi)。
1.7Iterator和ListIterator (s)
讀Iterator實(shí)現(xiàn)類(lèi)源碼(hasNext、next)
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
list.add("apple");
list.add("banana");
list.add("coco");
// 需求:在遍歷的過(guò)程中，添加元素
Iterator<String> it = list.iterator();
while(it.hasNext()) {
String item = it.next();
if(item.equals("banana")) {
// list.add("test");
}
}
System.out.println(list);
ListIterator<String> it2 = list.listIterator();
while(it2.hasNext()) {
String item = it2.next();
if(item.equals("banana")) {
it2.add("test");
}
}
System.out.println(list);
}
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayListItr.next(ArrayList.java:859)
at cn.sxt06.iterator.Test01.main(Test01.java:18)
當(dāng)遍歷一個(gè)集合時(shí)，不能對(duì)集合進(jìn)行添加操作，可能會(huì)出現(xiàn)并發(fā)修改異常。如果要對(duì)其進(jìn)行添加操作，需要使用ListIterator接口。
1.8Set接口
Set接口表示的集合元素是無(wú)序、唯一的。
public static void main(String[] args) {
/**
* 增:add/addAll
* 刪:clear/remove/removeAll/retainAll
* 改:
* 查:contains/containsAll/isEmpty/equals/size
* 遍歷:iterator
*/
Set<String> set = new HashSet<String>();
// 【1】添加
boolean r;
r = set.add("apple");
System.out.println(r);
set.add("coco");
set.add("banana");
r = set.add("apple"); // 沒(méi)有添加成功
System.out.println(r);
// 【2】刪除
// set.clear();
set.remove("coco");
System.out.println(set);
}
set遍歷
public static void main(String[] args) {
Set<String> set = new HashSet<String>();
set.add("apple");
set.add("coco");
set.add("banana");
// foreach
for(String str:set) {
System.out.println(str);
}
Iterator<String> it = set.iterator();
while(it.hasNext()) {
System.out.println(it.next());
}
}
1.8.1HashSet
HashSet是Set接口的實(shí)現(xiàn)類(lèi)，底層數(shù)據(jù)結(jié)構(gòu)是哈希表。
HashSet 線(xiàn)程不安全。
1.8.1.1HashSet的工作原理
HashSet底層數(shù)據(jù)結(jié)構(gòu)是哈希表/散列表
HashSet存儲(chǔ)元素時(shí)
[1] 求元素的hash碼
[2] equals比較集合是否存在相同元素。
思考:如何把自定義對(duì)象存入HashSet中？
package cn.sxt02.hashset;
public class Student {
private String id;
private String name;
private int age;
// …
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + age;
result = prime * result + ((id == null) ? 0 : id.hashCode());
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Student other = (Student) obj;
if (age != other.age)
return false;
if (id == null) {
if (other.id != null)
return false;
} else if (!id.equals(other.id))
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
@Override
public String toString() {
return "Student [id=" + id + ", name=" + name + ", age=" + age + "]";
}
}
總結(jié):
[1]存入HashSet中的元素必須實(shí)現(xiàn)hashCode和equals方法
[2]元素的hashCode一樣,經(jīng)過(guò)y=k(x)散列出來(lái)的位置一定一樣。元素的hashCode不一樣,經(jīng)過(guò)y=k(x)散列出來(lái)的位置有可能一樣。
[3] 散列函數(shù)多半是 hashCode % 空間長(zhǎng)度。為什么？
1.8.2LinkedHashSet
LinkedHashSet 是Set接口的實(shí)現(xiàn)類(lèi)，底層數(shù)據(jù)結(jié)構(gòu)是哈希表+鏈表，其中鏈表應(yīng)用維持添加次序。
畫(huà)LinkedHashSet工作原理圖？
1.8.3TreeSet
TreeSet 是Set接口的實(shí)現(xiàn)類(lèi)，底層數(shù)據(jù)結(jié)構(gòu)是二叉樹(shù)，按照自然升序存儲(chǔ)。
TreeSet實(shí)現(xiàn)線(xiàn)程不安全的。
1.8.3.1TreeSet工作原理
TreeSet<Integer> set = new TreeSet<Integer>();
set.add(2);
set.add(3);
set.add(1);
set.add(4);
set.add(3);
System.out.println(set);
當(dāng)向TreeSet存入一個(gè)元素時(shí)，
[1]把待添加的元素T和根節(jié)點(diǎn)比較，如果T小于根節(jié)點(diǎn)，T存入左子樹(shù)；如果T大于根節(jié)點(diǎn)，T存入右子樹(shù)
[2]一旦確定子樹(shù)后，T元素要和子樹(shù)根節(jié)點(diǎn)比較，重復(fù)[1]步驟，如果需要相等，丟棄T。
需求: 把自定義對(duì)象按年齡存入TreeSet中？
把自定義對(duì)象存入TreeSet中一定要提供比較策略，否則會(huì)出現(xiàn)ClassCastException異常。
比較策略分為兩種，一種是內(nèi)部比較器，一種是外部比較器。
1.8.3.2內(nèi)部比較器
內(nèi)部比較器就是實(shí)現(xiàn)Comparable接口
package cn.sxt04.treeset;
public class Student implements Comparable<Student>{
private String id;
private String name;
private int age;
// . . .
@Override
public int compareTo(Student o) {
// 按照年齡比較
if(this.getAge() < o.getAge()) {
return -1;
}else if(this.getAge() == o.getAge()) {
return 0;
}else {
return 1;
}
}
}
思考:把自定義對(duì)象按年齡升序存入treeset中，如果年齡一樣，再按照名字自然升序。
@Override
public int compareTo(Student o) {
// return this.getAge() - o.getAge();
// 按照年齡比較
if(this.getAge() < o.getAge()) {
return -1;
}else if(this.getAge() == o.getAge()) {
/*if(this.getName().compareTo(o.getName()) < 0) {
return -1;
}else if(this.getName().compareTo(o.getName()) == 0) {
return 0;
}else {
return 1;
}*/
return this.getName().compareTo(o.getName());
}else {
return 1;
}
}
1.8.3.3外部比較器
當(dāng)開(kāi)發(fā)者不知道添加元素類(lèi)的源代碼時(shí)，此時(shí)可以使用外部比較策略。外部比較器就是Compartor接口。
public class Test04 {
public static void main(String[] args) {
LenCompare lenCompare = new LenCompare();
TreeSet<String> set = new TreeSet<String>(lenCompare);
set.add("alex");
set.add("ben");
set.add("cocos");
set.add("scott");
// 需求：按照字符串的長(zhǎng)度升序？
System.out.println(set);
}
}
class LenCompare implements Comparator<String> {
@Override
public int compare(String o1, String o2) {
// [1] 按名稱(chēng)長(zhǎng)度升序
// System.out.println("o1:"+o1);
// System.out.println("o2:"+o2);
// return o1.length() - o2.length();
// [2] 先按照名稱(chēng)長(zhǎng)度，如果相等，按名稱(chēng)自然順序
/*if (o1.length() == o2.length()) {
return o1.compareTo(o2);
}
return o1.length() - o2.length();*/
// [3]按照長(zhǎng)度降序
return o2.length() - o1.length();
}
}
package cn.sxt04.treeset;
import java.util.Comparator;
import java.util.TreeSet;
public class Test05 {
public static void main(String[] args) {
LenCompare lenCompare = new LenCompare();
TreeSet<String> set = new TreeSet<String>(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o1.length() - o2.length();
}
});
set.add("alex");
set.add("ben");
set.add("cocos");
set.add("scott");
// 需求：按照字符串的長(zhǎng)度升序？
System.out.println(set);
}
}
