概念
1.集合主要是兩組:單列集合(Collection) , 雙列集合(Map)
2.Collection 接口有兩個(gè)重要的子接口 List ,Set . 他們的實(shí)現(xiàn)子類都是單列集合
3.Map 接口的實(shí)現(xiàn)子類 是雙列集合，存放的 K-V
Iterable
單列集合的頂級(jí)接口,含有Iterator()方法,主要用于遍歷Collection集合中的元素
Collection的所有實(shí)現(xiàn)類都有Iterator()方法,返回值為調(diào)用該方法的實(shí)現(xiàn)類對(duì)象
1.常用方法:
Iterator iterator = collection.iterator();//獲取集合的迭代器
iterator.hasNext();//是否存在下一個(gè)元素,僅判斷
iterator.next();//返回集合中的當(dāng)前元素,初始指向集合中第一個(gè)元素,調(diào)用一次,指針往下挪一位
iterator.remove();//移除集合中的當(dāng)前元素,初始指向集合中第一個(gè)元素,調(diào)用一次,指針往下挪一位
2.常用一下方法遍歷集合
idea快捷鍵: itit | itco
Iterator<Integer> iterator = collection.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
遍歷完后,不可在調(diào)用iterator.next(),會(huì)拋出NoSuchElementException異常
如果還想使用,在使用collection.iterator()獲取一個(gè)迭代器即可
3.增強(qiáng)for循環(huán)就是簡(jiǎn)單版本的iterator(),底層是迭代器,集合,數(shù)組都可以使用
for (Object object: collection) {
System.out.println(object);
}
Collection接口
Collection 接口常用方法:
collection.add(1);//添加一個(gè)元素
collection.addAll();//添加一個(gè)集合中的所有元素
collection.remove();//刪除指定元素
collection.removeAll();//刪除傳入集合中的所有元素
collection.clear();//清空集合
collection.contains();//判斷集合是否含有傳入元素
collection.containsAll();//判斷集合是否包含傳入集合的所以有元素
collection.size();//集合大小
collection.isEmpty();//判斷集合是否為空
List接口
List中的元素是有序的,存入和取出順序一致,且元素可重復(fù)
List中所有元素都有索引(從0開始),可以根據(jù)索引取元素
1.List中的常用方法
list.get(index);//獲取指定索引的元素
list.indexOf(item);//獲取指定元素首次出現(xiàn)的索引
list.lastIndexOf(item);//獲取指定元素最后出現(xiàn)的索引
list.add(index,item);//在index 和 index-1 之間添加一個(gè)元素
list.remove(index);//根據(jù)指定索引刪除元素
list.set(index,item);//替換指定索引元素
list.subList(l,r);//返回 l<= i < r之間的元素
2.遍歷List的方法
1.簡(jiǎn)單for循環(huán)
2.增強(qiáng)for循環(huán)
3.iterator
ArrayList
可以存放一或多個(gè)null值,list.add(null);
有數(shù)組實(shí)現(xiàn)數(shù)據(jù)存儲(chǔ)
線程不安全
ArrayList list = new ArrayList();
//使用 for 給 list 集合添加 1-10 數(shù)據(jù)
for (int i = 1; i <= 10; i++) {
list.add(i);
}
//使用 for 給 list 集合添加 11-15 數(shù)據(jù)
for (int i = 11; i <= 15; i++) {
list.add(i);
}
list.add(100);
list.add(200);
list.add(null);
執(zhí)行流程 && 底層源碼分析:
擴(kuò)容機(jī)制:
transient Object[] elementData;//內(nèi)部維護(hù)的數(shù)組
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//空數(shù)組
private static final int DEFAULT_CAPACITY = 10;
1.
//無(wú)參構(gòu)造創(chuàng)建
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
2.
public boolean add(E e) {
ensureCapacityInternal(size + 1); //判斷當(dāng)前數(shù)組大小是否夠用,不夠進(jìn)行擴(kuò)容處理
elementData[size++] = e;
return true;
}
3.
private void ensureCapacityInternal(int minCapacity) {//此時(shí)minCapacity為1 ,是size+1傳遞過(guò)來(lái)的size初始為0
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)//判斷內(nèi)部數(shù)組長(zhǎng)度大于還是小于10);
}
4.1
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//判斷維護(hù)數(shù)組是否為空數(shù)組
//DEFAULT_CAPACITY為10
return Math.max(DEFAULT_CAPACITY, minCapacity);//返回10和原數(shù)組大小較大的一個(gè)
}
//首次長(zhǎng)度初始化為10
return minCapacity;
}
4.2
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//記錄集合被修改的次數(shù)
// overflow-conscious code
if (minCapacity - elementData.length > 0)//如果外部數(shù)組長(zhǎng)度大于內(nèi)部數(shù)組長(zhǎng)度,則擴(kuò)容
grow(minCapacity);//擴(kuò)容
}
5.
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;//oldCapacity 為 1
int newCapacity = oldCapacity + (oldCapacity >> 1);//擴(kuò)容為1.5倍
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;//無(wú)參構(gòu)造創(chuàng)建,首次擴(kuò)容為10
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);//將舊數(shù)組拷貝到新，如果新數(shù)組的長(zhǎng)度超過(guò)原數(shù)組的長(zhǎng)度,其余用默認(rèn)值填充
}
6.一步一步返回,如此循環(huán),滿了就1.5本擴(kuò)容,直到MAX_ARRAY_SIZE ,如果使用有參構(gòu)造傳入value,那么,就按照傳入的值1.5倍擴(kuò)容
//如果是有參構(gòu)造,就是將長(zhǎng)度初始化了,內(nèi)部數(shù)組為自定義長(zhǎng)度的數(shù)組
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];//內(nèi)部數(shù)組成了自定義長(zhǎng)度的數(shù)組
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
}
}
Vector
1.Vector是線程同步的即線程安全的,所有的方法都帶有synchronized
2.無(wú)參構(gòu)造創(chuàng)建: 默認(rèn)內(nèi)部數(shù)組為10 ,之后2倍擴(kuò)容,有參構(gòu)造指定長(zhǎng)度,按指定2倍長(zhǎng)度擴(kuò)容
1.Vector底層也是一個(gè)對(duì)象數(shù)組
protected Object[] elementData;
擴(kuò)容源碼分析:無(wú)參
1.
public Vector() {
this(10);//默認(rèn)內(nèi)部數(shù)組初始大小
}
2.
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
3.
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
this.elementData = new Object[initialCapacity];//創(chuàng)建初始值為10的內(nèi)部數(shù)組
this.capacityIncrement = capacityIncrement;
}
4.第一次add
protected int elementCount;//數(shù)組中有效元素個(gè)數(shù)
public synchronized boolean add(E e) {
modCount++;//記錄修改次數(shù)
ensureCapacityHelper(elementCount + 1);//
elementData[elementCount++] = e;
return true;
}
4.1
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)//數(shù)組有效元素長(zhǎng)度 - 數(shù)組總長(zhǎng)度
grow(minCapacity);
}
4.2由于數(shù)組初始長(zhǎng)度為10,add 10次后進(jìn)入grow方法
protected int capacityIncrement;//容器自增量,可以在創(chuàng)建集合是設(shè)置,為構(gòu)造器第二個(gè)參數(shù)
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);//默認(rèn)自增量為0,所以默認(rèn)擴(kuò)容兩倍
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
其他:
有參:
指定初始長(zhǎng)度
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
指定初始長(zhǎng)度和每次擴(kuò)容量
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
LinkedList
1.LinkedList底層維護(hù)一個(gè)雙向鏈表,更具索引獲取值時(shí),索引從0開始
2.內(nèi)部維護(hù)了一個(gè)靜態(tài)內(nèi)部類
private static class Node<E> {
E item;//當(dāng)前節(jié)點(diǎn)的值
Node<E> next;//指向下一個(gè)節(jié)點(diǎn)
Node<E> prev;//指向前一個(gè)節(jié)點(diǎn)
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;//
this.next = next;
this.prev = prev;
}
}
簡(jiǎn)單操作:
LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(1);
LinkedList初始化及CURD源碼分析:
幾個(gè)重要參數(shù):
transient int size = 0;//鏈表長(zhǎng)度
transient Node<E> first;//第一個(gè)結(jié)點(diǎn)位置
transient Node<E> last;//最后一個(gè)結(jié)點(diǎn)位置
protected transient int modCount = 0;//此列表在結(jié)構(gòu)上被修改的次數(shù),防止線程安全問(wèn)題,如果該字段的值意外變化，迭代器(或列表迭代器)將拋出ConcurrentModificationException異常來(lái)響應(yīng)next、remove、previous、set或add操作。這提供了快速失敗的行為，
//無(wú)參構(gòu)造初始化
public LinkedList() {
}
增加:
1.
public boolean add(E e) {
linkLast(e);
return true;
}
2.
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
調(diào)用靜態(tài)節(jié)點(diǎn)類的構(gòu)造方法
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;//給當(dāng)前節(jié)點(diǎn)賦值
this.next = next;//增加節(jié)點(diǎn)的next指向下一個(gè)節(jié)點(diǎn)
this.prev = prev;//prev指向上一個(gè)結(jié)點(diǎn)
}
刪除:
1.linkedList.removeFirst();//刪除頭節(jié)點(diǎn)
調(diào)用核心方法:private E unlinkFirst(Node<E> f)
2.linkedList.removeLast();//刪除尾節(jié)點(diǎn)
調(diào)用核心方法:private E unlinkLast(Node<E> l)
上述2個(gè)
3.linkedList.remove();//底層調(diào)用的是removeFirst
4.linkedList.remove(new Integer(4));//刪除指定對(duì)象節(jié)點(diǎn)
5.linkedList.remove(3);//更具索引刪
上述3個(gè)方法的核心都是在E unlink(Node<E> x)上進(jìn)行修改或加以限制,
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
//重新指定刪除結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的prev指向
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
//重新指定刪除結(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)的next指向
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
查找:
1.linkedList.get(1);//返回指定索引節(jié)點(diǎn)保存的數(shù)據(jù)值
2.linkedList.getLast();
3.linkedList.getFirst();
更改:
linkedList.set(index,value);更具指定索引,修改對(duì)應(yīng)的節(jié)點(diǎn)數(shù)據(jù)
ArrayList 和 LinkedList 比較
查找多,用ArrayList
修改多,用LinkedList
Set
無(wú)序(添加和取出元素順序,但取出順序固定不變),沒(méi)索引.
不允許有重復(fù)元素
遍歷方法:
迭代器
增強(qiáng)for循環(huán)
不能用索引方式
HashSet
1.HashSet底層實(shí)際上時(shí)HashMap
2.第一次添加是內(nèi)部的table數(shù)組擴(kuò)容到16,再次擴(kuò)容臨界值是16 * 加載因子(默認(rèn)0.75) 為12,下次擴(kuò)容臨界值是 2 乘以16 乘以0.75 為24
3.在Java8中如果一條鏈表的元素個(gè)數(shù) 達(dá)到 8 也就是>=7 且table數(shù)組大小大于64,就會(huì)進(jìn)行樹化(紅黑樹).否則仍采用數(shù)組擴(kuò)容機(jī)制
1.HashSet底層是HashMap
2.添加元素時(shí)，先計(jì)算得到hash值會(huì)轉(zhuǎn)成索引值,找到存儲(chǔ)數(shù)據(jù)表table,若果索引位置沒(méi)有元素則直接加入,若已經(jīng)存放有元素則調(diào)用equals比較,為true,就放棄添加,不相同，再判斷 p 是不是一顆紅黑樹, 如果是一顆紅黑樹，就調(diào)用 putTreeVal , 來(lái)進(jìn)行添加.不是紅黑樹,依次和該鏈表的每一個(gè)元素比較后，都不相同, 則加入到該鏈表的最后.
HashSet hashSet = new HashSet();
hashSet.add("java");
hashSet.add("java");
hashSet.add("php");
源碼分析:
無(wú)參構(gòu)造初始化
public HashSet() {
map = new HashMap<>();
}
1.添加 "java"
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
2.
public V put(K key, V value) {
return putVal(hash(key)//計(jì)算哈希值, key, value, false, true);
}
2.1
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
3.進(jìn)入putVall方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//if 語(yǔ)句表示如果當(dāng)前 table 是 null, 或者 大小=0
//table 就是 HashMap 的一個(gè)數(shù)組，類型是 Node[]
//if 語(yǔ)句表示如果當(dāng)前 table 是 null, 或者 大小=0
//就是第一次擴(kuò)容，到 16 個(gè)空間.
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;//剛開始tab為空,進(jìn)入resize()方法進(jìn)行第一次擴(kuò)容
//(1)根據(jù) key，得到 hash 去計(jì)算該 key 應(yīng)該存放到 table 表的哪個(gè)索引位置
//并把這個(gè)位置的對(duì)象，賦給 p
//(2)判斷 p 是否為 null
//(2.1) 如果 p 為 null, 表示還沒(méi)有存放元素, 就創(chuàng)建一個(gè) 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 {
//如果當(dāng)前索引位置對(duì)應(yīng)的鏈表的第一個(gè)元素和準(zhǔn)備添加的 key 的 hash 值一樣
//并且滿足 下面兩個(gè)條件之一:
//(1) 準(zhǔn)備加入的 key 和 p 指向的 Node 結(jié)點(diǎn)的 key 是同一個(gè)對(duì)象
//(2) p 指向的 Node 結(jié)點(diǎn)的 key 的 equals() 和準(zhǔn)備加入的 key 比較后相同
//就不能加入
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//再判斷 p 是不是一顆紅黑樹,
//如果是一顆紅黑樹，就調(diào)用 putTreeVal , 來(lái)進(jìn)行添加
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//(1) 依次和該鏈表的每一個(gè)元素比較后，都不相同, 則加入到該鏈表的最后
// 注意在把元素添加到鏈表后，立即判斷 該鏈表是否已經(jīng)達(dá)到 8 個(gè)結(jié)點(diǎn)
// , 就調(diào)用 treeifyBin() 對(duì)當(dāng)前這個(gè)鏈表進(jìn)行樹化(轉(zhuǎn)成紅黑樹)
// 注意，在轉(zhuǎn)成紅黑樹時(shí)，要進(jìn)行判斷, 判斷條件
// if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY(64))
// resize();
// 如果上面條件成立，先 table 擴(kuò)容. // 只有上面條件不成立時(shí)，才進(jìn)行轉(zhuǎn)成紅黑樹
//(2) 依次和該鏈表的每一個(gè)元素比較過(guò)程中，如果有相同情況,就直接 break
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 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;
if (++size > threshold)
resize();
afterNodeInsertion(evict);//留給子類重寫
return null;//返回null代表添加成功
}
3.1 第一次擴(kuò)容
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {//false
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold//false
newCap = oldThr;
else { // zero initial threshold signifies using defaults//初始化
newCap = DEFAULT_INITIAL_CAPACITY;//第一次擴(kuò)容大小: 16,默認(rèn)初始大小
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//當(dāng)數(shù)據(jù)大小為0.75 * 16時(shí)再次擴(kuò)容
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;//賦值,正真擴(kuò)容!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;//返回
}
LinkedHashSet
1.LinkedHashSet使用hashcode值來(lái)決定元素的存儲(chǔ)位置,使用雙向鏈表維護(hù)元素的次序,元素以插入順序保存.(加入和取出元素順序一致)
2.LinkedHashSet底層是一個(gè)LinkedHashMap(是HashMap的子類),底層維護(hù)一個(gè)數(shù)組加雙向鏈表
3.LinkedHashSet不能插入重復(fù)元素
4.第一次添加時(shí)將數(shù)組 table(table的類型是HashMap
N
o
d
e
[
]
)
擴(kuò)容到
16
,
存放的結(jié)點(diǎn)類型是
L
i
n
k
e
d
H
a
s
h
m
a
p
Node[]) 擴(kuò)容到 16 ,存放的結(jié)點(diǎn)類型是LinkedHashmap
Node[])擴(kuò)容到16,存放的結(jié)點(diǎn)類型是LinkedHashmapEntry
LinkedHashmap$Entry
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;//雙向鏈表記錄的前后結(jié)點(diǎn)
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
常用方法:
Map
Set 中 k-v k是添加值,v是present常量,只用了k
Map 中 k - v 都由用戶添加
1.Map與Collection并列存在。用于保存具有映射關(guān)系的數(shù)據(jù):Key-Value(雙列元素)
2.Hap中的 key 和 value 可以是任何引用類型的數(shù)據(jù)，會(huì)封裝到HashMap$Node對(duì)象中
3. Map中的key不允許重復(fù)，原因和HashSet一樣，前面分析過(guò)源碼。
4. Map中的value可以重復(fù),如果key相同,則覆蓋之前的value
5. Map 的 key 可以為 null, value 也可以為 null ，注意 key 為 null,
6. 常用 String 類作為 Map 的 key
7. key 和 value 之間存在單向一對(duì)一關(guān)系，即通過(guò)指定的 key 總能找到對(duì)應(yīng)的 value
常用方法:
Map map = new HashMap();
map.put(key, value);//替換-> 一會(huì)分析源碼
map.remove(key)根據(jù)鍵刪除映射關(guān)系
map.get(key)根據(jù)鍵獲取值
map.size();獲取元素個(gè)數(shù)
map.containsKey(key)是否包含指定key
map.isEmpty();判斷個(gè)數(shù)是否為空
map.clear();清空集合
遍歷:
//第一組: 先取出 所有的 Key , 通過(guò) Key 取出對(duì)應(yīng)的 Value
Set keyset = map.keySet();
//(1) 增強(qiáng) for
System.out.println("-----第一種方式-------");
for (Object key : keyset) {
System.out.println(key + "-" + map.get(key));
}
//(2) 迭代器
System.out.println("----第二種方式--------");
Iterator iterator = keyset.iterator();
while (iterator.hasNext()) {
Object key = iterator.next();
System.out.println(key + "-" + map.get(key));
}
//第二組: 把所有的 values 取出
Collection values = map.values();
//這里可以使用所有的 Collections 使用的遍歷方法
//(1) 增強(qiáng) for
System.out.println("---取出所有的 value 增強(qiáng) for----");
for (Object value : values) {
System.out.println(value);
}
//(2) 迭代器
System.out.println("---取出所有的 value 迭代器----");
Iterator iterator2 = values.iterator();
while (iterator2.hasNext()) {
Object value = iterator2.next()
System.out.println(value);
}
//第三組: 通過(guò) EntrySet 來(lái)獲取 k-v
Set entrySet = map.entrySet();// EntrySet<Map.Entry<K,V>>
//(1) 增強(qiáng) for
System.out.println("----使用 EntrySet 的 for 增強(qiáng)(第 3 種)----");
for (Object entry : entrySet) {
//將 entry 轉(zhuǎn)成 Map.Entry
Map.Entry m = (Map.Entry) entry;
System.out.println(m.getKey() + "-" + m.getValue());
}
//(2) 迭代器
System.out.println("----使用 EntrySet 的 迭代器(第 4 種)----");
Iterator iterator3 = entrySet.iterator();
while (iterator3.hasNext()) {
Object entry = iterator3.next();
//System.out.println(next.getClass());//HashMap$Node -實(shí)現(xiàn)-> Map.Entry (getKey,getValue)
//向下轉(zhuǎn)型 Map.Entry
Map.Entry m = (Map.Entry) entry;
System.out.println(m.getKey() + "-" + m.getValue());
}
}
HashMap
jdk8: 底層是數(shù)組+鏈表+紅黑樹
數(shù)組長(zhǎng)度大于64 且 鏈表長(zhǎng)度大于8 該節(jié)點(diǎn)的鏈表樹化
- HashMap底層維護(hù)了Node類型的數(shù)組table，默認(rèn)為null
2)當(dāng)創(chuàng)建對(duì)象時(shí)，將加載因子(loadfactor)初始化為0.75.
3)當(dāng)添加key-val時(shí)，通過(guò)key的哈希值得到在table的索引。然后判斷該索引處是否有元素,
如果沒(méi)有元素直接添加。如果該索引處有元素,繼續(xù)判斷該元素的key是否和準(zhǔn)備加入的key相等，如果相等，則直接替換val;如果不相等需要判斷是樹結(jié)構(gòu)還是鏈表結(jié)構(gòu)，做出相應(yīng)處理。如果添加時(shí)發(fā)現(xiàn)容量不夠，則需要擴(kuò)容。
4)第1次添加，則需要擴(kuò)容table容量為16，臨界值(threshold)為12.,以后再擴(kuò)容，則需要擴(kuò)容table容量為原來(lái)的2倍，臨界值為原來(lái)的2倍,即24,依次類推.
6)在Java8中,如果一條鏈表的元素個(gè)數(shù)超過(guò)TREEIFY_THRESHOLD(默認(rèn)是8)，粗table的大小>= MIN_TREEIFY_CAPACITY(默認(rèn)64),就會(huì)進(jìn)行樹化(紅黑樹)
1.k-v最后是 HashMap.Node node = newNode(hash,key,value,null)
2.k-v為了方便程序員的遍歷，創(chuàng)建了EntrySet集合，該集合存放的元素的類型Entry，而一個(gè)Entry對(duì)象就有k ,v EntrySet<Entry<K,V>>即: transient Set<Map. Entry<K, V>> entrySet;
3. entrySet中，定義的類型是Map.Entry ，但是實(shí)際上存放的還是 HashMap.Node,這是因?yàn)?HashMap.Node implements Map.Entry
4.當(dāng)把 HashMap.Node 對(duì)象存放到entrySet 就方便我們的遍歷，因?yàn)?Map.Entry 提供了重要方法K getKey V getValue();
5.實(shí)際上就是把所有HashMap$Node轉(zhuǎn)成Entry,然后把所有Entry放到EntrySet中(存放的是地址,不是實(shí)際數(shù)據(jù)),方便程序員遍歷,EntrySet中的數(shù)據(jù)實(shí)際指向的是類型為HashMap Node[] 的table表中的數(shù)據(jù)(存放的是地址,不是實(shí)際數(shù)據(jù))文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-485051.html
內(nèi)部節(jié)點(diǎn)
//實(shí)現(xiàn)implements Map.Entry<K,V>接口
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }//getKey
public final V getValue() { return value; }//getValue
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
EntrySet 中包含所有Entry,但是不能直接獲取Entry對(duì)象,可以使用增強(qiáng)for循環(huán)遍歷
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {......}
所以還提供了直接獲取所有key的內(nèi)部類
final class KeySet extends AbstractSet<K> {.......}
以及直接獲取所有Value的內(nèi)部類
final class Values extends AbstractCollection<V> {......}
解析 hashMap.put(key,value)
擴(kuò)容等機(jī)制和HashSet基本一樣文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-485051.html
1.
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
2.
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
//第一次擴(kuò)容
n = (tab = resize()).length;
//hash值對(duì)應(yīng)的數(shù)組索引為空,直接放入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))//判斷傳入的鍵是否和已有的相等
e = p;//相等就記錄,為后面對(duì)應(yīng)鍵的新值覆蓋舊值做鋪墊
else if (p instanceof TreeNode)//判斷是否已經(jīng)樹化
樹化后的添加方法
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//往鏈表中添加
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 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//不為空,說(shuō)明添加的鍵重復(fù)
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;//新值覆蓋舊值
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
細(xì)致分析
// 1. 執(zhí)行構(gòu)造器 new HashMap()
//初始化加載因子 loadfactor = 0.75
//HashMap$Node[] table = null
//2. 執(zhí)行 put 調(diào)用 hash 方法，計(jì)算 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);
}
3. 執(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 , 就擴(kuò)容到 16
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//取出 hash 值對(duì)應(yīng)的 table 的索引位置的 Node, 如果為 null, 就直接把加入的 k-v
//, 創(chuàng)建成一個(gè) 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é)點(diǎn)的 key 和準(zhǔn)備添加的 key 是同一個(gè)對(duì)象 || equals 返回真)
// 就認(rèn)為不能加入新的 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é)點(diǎn)，后面是鏈表，就循環(huán)比較
for (int binCount = 0; ; ++binCount) {//死循環(huán)
if ((e = p.next) == null) {//如果整個(gè)鏈表，沒(méi)有和他相同,就加到該鏈表的最后
p.next = newNode(hash, key, value, null);
//加入后，判斷當(dāng)前鏈表的個(gè)數(shù)，是否已經(jīng)到 8 個(gè)，到 8 個(gè)，后
//就調(diào)用 treeifyBin 方法進(jìn)行紅黑樹的轉(zhuǎn)換
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && //如果在循環(huán)比較過(guò)程中，發(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 對(duì)應(yīng) value
afterNodeAccess(e);
return oldValue;
}
}
++modCount;//每增加一個(gè) Node ,就 size++
if (++size > threshold[12-24-48])//如 size > 臨界值，就擴(kuò)容
resize();
afterNodeInsertion(evict);
return null;
}
5. 關(guān)于樹化(轉(zhuǎn)成紅黑樹)
//如果 table 為 null ,或者大小還沒(méi)有到 64，暫時(shí)不樹化，而是進(jìn)行擴(kuò)容. //否則才會(huì)真正的樹化 -> 剪枝
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();
}
*/
}
}
到了這里，關(guān)于Java集合-Collection & Map的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
