數(shù)組
- 1 長度開始必須指定，一旦指定不能修改
- 2 保存的必須為同一類型元素
- 3 使用數(shù)字增加刪除比較麻煩
集合
好處
- 可以動態(tài)保存多個對象
-
方便增加刪除
image.png
image.png
Collection接口
使用Iterator（迭代器）
image.png
- Iterator對象稱為迭代器，主要用于遍歷Collection集合中的元素
- 使用Collection接口都用Iterator方法
- Iterator僅用于遍歷集合，不存放數(shù)據(jù)
ArrayList
- ArrayList中維護了一個Object類型的數(shù)組elementData，transient Object[] elementData //transient 表示瞬間短暫的，表示該屬性不會被序列號
- 當(dāng)創(chuàng)建ArrayList對象時，如果使用的是無參構(gòu)造器，則初始容量為0，第一次添加擴容elementData為10，如果需要再擴容，則擴容elementData為1.5倍
-
如果使用的是指定大小的構(gòu)造器，則初始elementData容量為指定大小，如果需要擴容，則直接擴容為1.5倍
image.png
LinkedList
image.png
- 線程都是不安全的
-
remo是默認刪除第一個
image.png
HashSet
- 底層是hashmap
- 添加順序是不一定按照執(zhí)行順序
- 添加一個元素時，先得到hash值->會轉(zhuǎn)成->索引值
- 找到存儲數(shù)據(jù)表table，看這個索引位置是否已經(jīng)存放的有元素
- 沒有則直接加入，有就調(diào)用equal比較，相同就放棄添加，不相同就添加到最后
1. 執(zhí)行 HashSet()
public HashSet() {
map = new HashMap<>();
}
2. 執(zhí)行 add()
public boolean add(E e) {//e = "java"
return map.put(e, PRESENT)==null;//(static) PRESENT = new Object();
}
3.執(zhí)行 put()
該方法會執(zhí)行 hash(key) 得到key對應(yīng)的hash值 算法h = key.hashCode()) ^ (h >>> 16)
public V put(K key, V value) {//key = "java" value = PRESENT 共享
return putVal(hash(key), key, value, false, true);
}
4.執(zhí)行 putVal
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i; //定義了輔助變量
//table 就是 HashMap 的一個數(shù)組，類型是 Node[]
//if 語句表示如果當(dāng)前table 是null, 或者 大小=0
//就是第一次擴容，到16個空間.
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//(1)根據(jù)key，得到hash 去計算該key應(yīng)該存放到table表的哪個索引位置
//并把這個位置的對象，賦給 p
//(2)判斷p 是否為null
//(2.1) 如果p 為null, 表示還沒有存放元素, 就創(chuàng)建一個Node (key="java",value=PRESENT)
//(2.2) 就放在該位置 tab[i] = newNode(hash, key, value, null)
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//一個開發(fā)技巧提示： 在需要局部變量(輔助變量)時候，在創(chuàng)建
Node<K,V> e; K k; //
//如果當(dāng)前索引位置對應(yīng)的鏈表的第一個元素和準備添加的key的hash值一樣
//并且滿足 下面兩個條件之一:
//(1) 準備加入的key 和 p 指向的Node 結(jié)點的 key 是同一個對象
//(2) p 指向的Node 結(jié)點的 key 的equals() 和準備加入的key比較后相同
//就不能加入
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//再判斷 p 是不是一顆紅黑樹,
//如果是一顆紅黑樹，就調(diào)用 putTreeVal , 來進行添加
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//如果table對應(yīng)索引位置，已經(jīng)是一個鏈表, 就使用for循環(huán)比較
//(1) 依次和該鏈表的每一個元素比較后，都不相同, 則加入到該鏈表的最后
// 注意在把元素添加到鏈表后，立即判斷 該鏈表是否已經(jīng)達到8個結(jié)點
// , 就調(diào)用 treeifyBin() 對當(dāng)前這個鏈表進行樹化(轉(zhuǎn)成紅黑樹)
// 注意，在轉(zhuǎn)成紅黑樹時，要進行判斷, 判斷條件
// if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY(64))
// resize();
// 如果上面條件成立，先table擴容.
// 只有上面條件不成立時，才進行轉(zhuǎn)成紅黑樹
//(2) 依次和該鏈表的每一個元素比較過程中，如果有相同情況,就直接break
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD(8) - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//size 就是我們每加入一個結(jié)點Node(k,v,h,next), size++
if (++size > threshold)
resize();//擴容
afterNodeInsertion(evict);
return null;
}
image.png
HashMap
- 執(zhí)行構(gòu)造器 new HashMap()
初始化加載因子 loadfactor = 0.75
HashMap$Node[] table = null
- 執(zhí)行構(gòu)造器 new HashMap()
- 執(zhí)行put 調(diào)用 hash方法，計算 key的 hash值 (h = key.hashCode()) ^ (h >>> 16)
public V put(K key, V value) {//K = "java" value = 10
return putVal(hash(key), key, value, false, true);
}
- 執(zhí)行 putVal
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;//輔助變量
//如果底層的table 數(shù)組為null, 或者 length =0 , 就擴容到16
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//取出hash值對應(yīng)的table的索引位置的Node, 如果為null, 就直接把加入的k-v
//, 創(chuàng)建成一個 Node ,加入該位置即可
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;//輔助變量
// 如果table的索引位置的key的hash相同和新的key的hash值相同，
// 并 滿足(table現(xiàn)有的結(jié)點的key和準備添加的key是同一個對象 || equals返回真)
// 就認為不能加入新的k-v
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)//如果當(dāng)前的table的已有的Node 是紅黑樹，就按照紅黑樹的方式處理
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//如果找到的結(jié)點，后面是鏈表，就循環(huán)比較
for (int binCount = 0; ; ++binCount) {//死循環(huán)
if ((e = p.next) == null) {//如果整個鏈表，沒有和他相同,就加到該鏈表的最后
p.next = newNode(hash, key, value, null);
//加入后，判斷當(dāng)前鏈表的個數(shù)，是否已經(jīng)到8個，到8個，后
//就調(diào)用 treeifyBin 方法進行紅黑樹的轉(zhuǎn)換
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && //如果在循環(huán)比較過程中，發(fā)現(xiàn)有相同,就break,就只是替換value
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value; //替換，key對應(yīng)value
afterNodeAccess(e);
return oldValue;
}
}
++modCount;//每增加一個Node ,就size++
if (++size > threshold[12-24-48])//如size > 臨界值，就擴容
resize();
afterNodeInsertion(evict);
return null;
}
- 關(guān)于樹化(轉(zhuǎn)成紅黑樹)
//如果table 為null ,或者大小還沒有到 64，暫時不樹化，而是進行擴容.
//否則才會真正的樹化 -> 剪枝
- 關(guān)于樹化(轉(zhuǎn)成紅黑樹)
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
}
image.png
image.png
集合 和MAP選擇對比
image.png
