集合(Collection / Map) - 一:
Collection
Java 集合繼承圖
Collection 繼承 → Iterable 有 iterator() 方法
顧 凡是繼承Collection的 都會(huì)有 iterator() 方法
iterator():
1. hasNext()
2. next()
3. remove()
Collection(接口)
1. List(接口) 繼承 Collection
a. ArrayList(實(shí)現(xiàn)類)
b. LinkedList(實(shí)現(xiàn)類)
c. Vector(實(shí)現(xiàn)類)
2. Set(接口) 繼承 Collection
a. HashSet(類)
b. SortedSet(接口)
1. TreeSet(實(shí)現(xiàn)類)
Collection 特點(diǎn):
1. 只能存儲(chǔ)引用類型, 并且只能單個(gè)存儲(chǔ)數(shù)據(jù)(一個(gè)一個(gè)存)
存 1, 2, 3 不報(bào)錯(cuò)是因?yàn)?自動(dòng)裝箱 轉(zhuǎn)成了 包裝類
類比數(shù)組:
定義:
存放同一類型, 在存儲(chǔ)空間中連續(xù)的一系列數(shù)據(jù)
數(shù)組尋址公式:
改數(shù)據(jù)地址 = 數(shù)組首數(shù)據(jù)地址 + 索引 * 該類型的字節(jié)數(shù)
為什么數(shù)組的索引是從 0 開始的?
因?yàn)槿绻麖?1 開始 或者其他開始, 就會(huì)多運(yùn)算后面的 乘法, 如果是 0 的話
效率高:
查詢
效率低:
添加刪除
List
特點(diǎn):
1. 有序
2. 可重復(fù)
3. 單個(gè)存儲(chǔ)
4. 存引用類型
原因: 由于繼承了Collection 所以特點(diǎn)也包括 Collection特點(diǎn)
ArrayList
底層數(shù)據(jù)結(jié)構(gòu):
數(shù)組, 顧適合 查詢
特點(diǎn):
1. 適合 查詢
2. 不適合 增刪
原因: 底層采用數(shù)組存儲(chǔ)元素的 而數(shù)組底層是有規(guī)律的順序的存儲(chǔ)的.
LinkedList
底層數(shù)據(jù)結(jié)構(gòu):
雙向鏈表, 顧適合頻繁增刪, 不適合查詢
特點(diǎn):
1. 合適 增刪
2. 不適合 查詢
Vector
底層數(shù)據(jù)結(jié)構(gòu):
數(shù)組, 也只適合查詢
特點(diǎn):
1. 適合多線程, 因?yàn)槭蔷€程安全的
2. 效率不高
一般情況不會(huì)使用集合自帶的安全機(jī)制, Vector 效率不高, 現(xiàn)在用的比較少
Set
特點(diǎn):
1. 無序
2. 不可重復(fù)
HashSet
底層數(shù)據(jù)結(jié)構(gòu):
哈希散列表
SortedSet(接口)
底層數(shù)據(jù)結(jié)構(gòu)
特點(diǎn):
1. 無序
2. 不可重復(fù)
3. 排序 → 根據(jù)大小
原因:
實(shí)現(xiàn)類:
TreeMap
TreeMap特點(diǎn):
1. key 就是 一個(gè) TreeSet
Map
Map(接口):
1. SortedMap(接口)
2. HashMap(實(shí)現(xiàn)類)
a. LinkedMap
3. Hashtable(實(shí)現(xiàn)類) → 線程安全, 效率不高, 用的少
4. ConcurrentHashMap(實(shí)現(xiàn)類) → 并發(fā)編程
特點(diǎn):
鍵值對(duì)
HashMap ?
特點(diǎn):
1. 無序
2. key 不可重復(fù), 類似于 Set 的不可重復(fù)
Hashtable
Hashtable 本身用的不多, 但是他的子類 Properties 用的多, 用于配置文件.
Properties 特點(diǎn):
1. key 和 value存儲(chǔ)
2. 存儲(chǔ)類型只能是 字符串
Hashtable
特點(diǎn):
1. 無序
2. 不可重復(fù)
3. 排序 → 按照 key 大小排序, 類似于 SortedSet
UML
繼承 → 空心箭頭
實(shí)現(xiàn) → 虛線空心
擴(kuò)展
單向鏈表:
單向鏈表:
每個(gè)元素都稱作結(jié)點(diǎn) Entry(JDK 1.5) / Node(JDK 1.8)
特點(diǎn):
1. 單項(xiàng)鏈表每個(gè)結(jié)點(diǎn)字內(nèi)存中的存儲(chǔ)空間沒有規(guī)律
問題:
1. 為什么單項(xiàng)鏈表查詢效率低?
答: 因?yàn)閱雾?xiàng)鏈表在內(nèi)存中存儲(chǔ)的空間上面是沒有規(guī)律的, 也沒有順序, 如果我們想要獲得到摸個(gè)元素, 要從頭開始往后遍歷, 找到為止
2. 為什么單向鏈表增刪效率高?
答: 因?yàn)閱雾?xiàng)鏈表在內(nèi)存中存儲(chǔ)的空間上面沒有規(guī)律, 刪除或者隨機(jī)增加元素, 只要讓指針重新指向即可, 不要將后面元素位移.
雙向鏈表:
頭部內(nèi)存地址 是上一個(gè)元素的內(nèi)存地址, 尾部的內(nèi)存地址是下一個(gè)元素的內(nèi)存地址
import java.util.ArrayList;
import java.util.Collection;
/**
* description: 集合的基本操作
*
* @author Lomonkey
* @date 2019/2/22
*/
/**
* add() 添加元素
* clear() 清空集合
* contains() 判斷元素是否存在
* isEmpty() 判斷是否為空, 為空 返回 true
* iterator() 創(chuàng)建迭代器
* remove() 刪除元素
* retainAll() 交集
* size() 集合長度
* toArray() 轉(zhuǎn)換成數(shù)組
*
* */
public class ConnectionTest1 {
public static void main(String[] args) {
// 創(chuàng)建一個(gè) 集合
// 父類型引用 指向子類對(duì)象 → 多態(tài)
Collection collection = new ArrayList();
// 添加元素 → 只能添加引用類型
collection.add(123321);
collection.add("的說法");
collection.add(true);
// 泛型集合
Collection<String> collection1 = new ArrayList<String>();
// 只能添加 String 類型
collection1.add("大家好!");
collection1.add("你們好!");
/*
* 在編譯階段, 對(duì)代碼進(jìn)行檢查
* */
// 能直接打印出 → 大家好!
System.out.println(collection1);
// collection1 指向的是 ArrayList集合的對(duì)象
// 調(diào)用 println() 方法的時(shí)候, 把 collection1 的變量值, 即ArrayList的對(duì)象的引用
// 判斷非空
System.out.println(collection1.isEmpty());
// 長度
System.out.println(collection1.size());
// 判斷元素是否存在
System.out.println(collection1.contains("da"));
// 刪除元素
collection1.remove("大家好");
System.out.println(collection1);
// 轉(zhuǎn)化成數(shù)組
Object[] arr = collection1.toArray();
for(Object o : arr){
System.out.print(o);
}
}
}
作業(yè):
java 來模擬單鏈表
public class Linked{
// 結(jié)點(diǎn)
Entry entry;
// 構(gòu)造
Linked(){
entry = new Entry(null, null);
}
// 元素的添加 → add
// 元素的刪除 → remove
// 元素的查找 → find
// 元素
// 內(nèi)部類 幾點(diǎn)
static class Entry{
Object data;
Entry next;
Entry(Object data, Entry next){
this.data = data;
this.next = next;
}
}
}
