集合框架源码分析三(实现类篇ArrayList,LinkedList,HashMap)
一。ArrayList，可自動擴充容量的動態數組?
public class ArrayList<E> extends AbstractList<E> implements List<E>,
RandomAccess, Cloneable, java.io.Serializable {private static final long serialVersionUID = 8683452581122892189L;
/**
*?
* 所有ArrayList的元素都存儲在此對象數組當中
* ArrayList的容量就是此數組的長度
*/
private transient Object[] elementData;
/**
* 實際擁有的元素的數量
*?
* @serial
*/
private int size;
/**
* 構造方法一，指定elementData數組初始長度
*/
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0) //小于0則拋出IllegalArgumentException
throw new IllegalArgumentException("Illegal Capacity: "
+ initialCapacity);
this.elementData = new Object[initialCapacity];
}
/**
* 構造方法二，默認elementData數組初始長度為10
*/
public ArrayList() {
this(10);
}
/**
* 構造方法三，構造一個包含指定 collection 的元素的List
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray(); //toArray方法由AbstractCollection實現，返回一個對象數組
size = elementData.length; ? ? ?//元素的順序是由迭代器迭代順序決定的,詳情見toArray方法實現
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class) //如果返回的不是一個數組對象
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
/**
* 修剪ArrayList的容量為實際size長度
*/
public void trimToSize() {
modCount++; //此方法改變了數組結構，需要檢測是否同步
int oldCapacity = elementData.length;
if (size < oldCapacity) {
elementData = Arrays.copyOf(elementData, size);
}
}
/**
*?
* 擴充數組容量，并指定其最小的容量，即至少容量大小為minCapacity
*/
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) { //指定最小容量比原來容量大才擴充
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3) / 2 + 1; //擴充原容量的1.5倍加1
if (newCapacity < minCapacity) //擴充后還是小于要求的最小容量，則擴充容量為最小容量
newCapacity = minCapacity;
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
/**
* 返回List中的元素個數
*/
public int size() {
return size;
}
/**
* List是否不含元素
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 查看o是否包含在ArrayList中，內部調用了indexOf方法實現
*/
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
/**
* 父類AbstractList的indexOf方法使用的是list迭代器遍歷元素
* 這里重寫了indexOf方法直接遍歷數組即可
* 返回指定元素第一次在數組中出現的索引
* 如果找不到此元素則返回-1
*/
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i] == null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
/**
* 基本同上
*/
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size - 1; i >= 0; i--)
if (elementData[i] == null)
return i;
} else {
for (int i = size - 1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
/**
*?
* 返回ArrayList的淺拷貝實例對象，包含所有元素
*/
public Object clone() {
try {
ArrayList<E> v = (ArrayList<E>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) { //如果未實現Cloneable則會拋出CloneNotSupportedException
throw new InternalError();
}
}
/**
*?
* 返回的對象數組是安全的，因為它是一個全新的對象
* 操作返回的數組并不會影響到ArrayList對象
*
*/
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
/**
* 返回一個指定類型的包含List所有元素的數組
*/
public <T> T[] toArray(T[] a) {
if (a.length < size) //如果a的長度小于List元素個數
return (T[]) Arrays.copyOf(elementData, size, a.getClass()); //以指定類型返回一個新數組，長度為size
System.arraycopy(elementData, 0, a, 0, size); //否則把elementData中元素復制到a
if (a.length > size) //如果a的長度大于size則在最后位置加一個null元素，等于的話就不用加了
a[size] = null; //這對了解它的實際長度很有效
return a;
}
// Positional Access Operations
public E get(int index) {
RangeCheck(index); //檢查是否越界
return (E) elementData[index]; //直接返回數組某位置的元素即可
}
/**
* 對數組指定所有的值進行替換，并返回上一個值
*/
public E set(int index, E element) {
RangeCheck(index); //檢查是否越界
E oldValue = (E) elementData[index]; //so easy
elementData[index] = element;
return oldValue;
}
/**
* 在數組size位置添加一個元素
*?
*/
public boolean add(E e) {
ensureCapacity(size + 1); // modCount++,并檢查是否需要擴充容量
elementData[size++] = e; //size++
return true;
}
/**
*?
* 在指定位置添加一個元素，當前在此位置的元素以及其后面的元素都要向后移動一個位置
* 此方法的效率較低
*
*/
public void add(int index, E element) {
if (index > size || index < 0) //檢查是否越界
throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
+ size);
ensureCapacity(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1, size
- index); //把原來index位置的元素，復制到index+1的位置，后面的size-index-1長度的元素依次復制
elementData[index] = element; //空出的index位置的元素設為element
size++;
}
/**
*?
* 移除指定位置的元素，其后面的元素都要向左移動一個位置
* 此方法的效率較低
*/
public E remove(int index) {
RangeCheck(index);
modCount++; //modCount是為了檢測是否發生了并發操作，詳細見AbstractList類
E oldValue = (E) elementData[index];
int numMoved = size - index - 1; //與add相比少移一個元素
if (numMoved > 0) //是否移除的是最后一個元素
System.arraycopy(elementData, index + 1, elementData, index,
numMoved); //index位置的元素被移除了，原來index+1位置的元素復制到index位置，隨后的元素依次復制
elementData[--size] = null; // Let gc do its work，size位置的元素空出來了
return oldValue;
}
/**
*?
* 如果o在List中存在，移除第一次出現在List中的o元素
* 如果o在List中不存在，不做任何操作
*
*/
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++) //直接遍歷數組
if (elementData[index] == null) {
fastRemove(index); //快速移除此元素
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
/*
*?
* 與remove(int index)方法差不多，
* 不過不用檢測是否越界與返回原來的index位置的值
*/
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index + 1, elementData, index,
numMoved);?
elementData[--size] = null; // Let gc do its work
}
/**
* 移除所有元素，即把所有元素設為null，size=0
*/
public void clear() {
modCount++;
// Let gc do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
/**
* 把a中所有元素添加到數組尾部
*/
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacity(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew); //從size位置開始復制a
size += numNew; //size增加
return numNew != 0;
}
/**
*?
* 在指定位置開始添加指定集合c中的所有元素
* 當前位置及其隨后位置的元素后移
*/
public boolean addAll(int index, Collection<? extends E> c) {
if (index > size || index < 0) //檢測是否越界
throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
+ size);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacity(size + numNew); // Increments modCount
int numMoved = size - index; //移動元素數量
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved); //把原來index位置的元素，復制到index+numNew的位置，后面的size-index-1長度的元素依次復制
System.arraycopy(a, 0, elementData, index, numNew); //空出來的位置填充c
size += numNew;
return numNew != 0;
}
/**
*?
* 移除所有從fromIndex(包含)到toIndex(不包含)范圍內的元素，
* 左移隨后的元素.如果toIndex=fromIndex，此操作無影響
*
*/
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved); //把toIndex位置的元素復制到fromIndex，隨后的元素依次復制，總共復制numMoved個元素
// Let gc do its work
int newSize = size - (toIndex - fromIndex);
while (size != newSize) //這里是為了讓gc工作，不直接把size設為newSize
elementData[--size] = null;
}
/**
*?
* 這里并沒有檢測index小于0的情況
* 它總是由數組自己檢測，拋出的異常也不同,為ArrayIndexOutOfBoundsException
*/
private void RangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
+ size);
}
/**
* 序列化ArrayList，保存ArrayList實例狀態
* 保存的是數組長度，及其所有元素
*
*/
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// 寫入數組長度
s.writeInt(elementData.length);
// 按順序寫入所有元素
for (int i = 0; i < size; i++)
s.writeObject(elementData[i]);
if (modCount != expectedModCount) { //檢測到了并發操作
throw new ConcurrentModificationException();
}
}
/**
* Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
* deserialize it).
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in size, and any hidden stuff
s.defaultReadObject();
// 讀出數組長度
int arrayLength = s.readInt();
Object[] a = elementData = new Object[arrayLength]; //保存
// 依次讀出所有元素
for (int i = 0; i < size; i++)
a[i] = s.readObject();
}
}
二。LikedList(雙向循環鏈表)?
public class LinkedList<E> extends AbstractSequentialList<E> implements
List<E>, Deque<E>, Cloneable, java.io.Serializable {
//在第一個節點之前附設的一個節點稱為頭結點，有元素添加會重設值
//此變量在序列化時不保存
private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0; //List存儲的Entry對象個數
/**
* 構造方法一，空鏈表
*/
public LinkedList() {
header.next = header.previous = header; //只有一個頭結點的鏈表
}
/**
* 構造方法二，構造含有指定集合c中所有元素的鏈表
* 具體見addAll方法
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
/**
* 獲取第一個元素的值，即頭結點的下一個元素的數據部分
*/
public E getFirst() {
if (size == 0)
throw new NoSuchElementException();
return header.next.element;
}
/**
* 雙向循環鏈表，你懂得
*/
public E getLast() {
if (size == 0)
throw new NoSuchElementException();
return header.previous.element;
}
/**
* 移除第一個元素，具體見remove()方法
*/
public E removeFirst() {
return remove(header.next);
}
/**
* 移除最后一個元素
*/
public E removeLast() {
return remove(header.previous);
}
/**
*?
* 在鏈表開始位置添加一個元素
* 詳情見addBefore()
*/
public void addFirst(E e) {
addBefore(e, header.next);
}
/**
* 在鏈表最后位置添加一個元素
* 詳情見addBefore()
*/
public void addLast(E e) {
addBefore(e, header);
}
/**
* 查看鏈表是否包含元素o
* 詳細見indexOf()方法
*/
public boolean contains(Object o) {
return indexOf(o) != -1;
}
/**
* 鏈表所含元素的數量
*/
public int size() {
return size;
}
/**
* 跟addLast()方法類似，添加成功返回true
*/
public boolean add(E e) {
addBefore(e, header);
return true;
}
/**
* 假如鏈表中含有一個或多個o對象，移除第一次出現的o
* 如果找不到o返回false
*/
public boolean remove(Object o) {
if (o == null) {
for (Entry<E> e = header.next; e != header; e = e.next) { //從第一個元素開始遍歷，每一個Entry對象都包含它下一個元素的信息
if (e.element == null) {
remove(e);
return true;
}
}
} else {
for (Entry<E> e = header.next; e != header; e = e.next) {
if (o.equals(e.element)) {
remove(e);
return true;
}
}
}
return false;
}
/**
*?
* 把c中所有元素按順序添加到鏈表尾部
*/
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
/**
*?
* 在指定位置按順序添加c中所有元素帶List中
*?
*/
public boolean addAll(int index, Collection<? extends E> c) {
if (index < 0 || index > size) //檢查是否越界，=size表示添加到最后
throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
+ size);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
modCount++; //對鏈表結構產生 影響的操作modCount都要加1，通過modCount可以檢查是否對鏈表進行了并發操作
Entry<E> successor = (index == size ? header : entry(index));
Entry<E> predecessor = successor.previous;
for (int i = 0; i < numNew; i++) { //這里不難，畫一個圖就出來了，主要是初始化c和修改指針
//暫時使其next為successor，因為e會賦給前驅,而每次遍歷都要修改其前驅的next
Entry<E> e = new Entry<E>((E) a[i], successor, predecessor); //把c中元素依次存入Entry，設置其前驅和后繼。
predecessor.next = e; ? //重新設置前驅的next指針
predecessor = e; //讓e變為前驅
}
successor.previous = predecessor; //successor的前驅為c中最后一個元素的引用
size += numNew; //長度加
return true;
}
/**
* 移除鏈表中所有元素
*/
public void clear() {
Entry<E> e = header.next;
while (e != header) { //表示不是只有一個頭結點的空鏈表
Entry<E> next = e.next;
e.next = e.previous = null; //let gc work
e.element = null;
e = next;
}
header.next = header.previous = header; //初始頭結點
size = 0;
modCount++;
}
// Positional Access Operations
/**
* 返回指定位置的元素時
*/
public E get(int index) {
return entry(index).element;
}
/**
* 設置指定位置的元素
*/
public E set(int index, E element) {
Entry<E> e = entry(index);
E oldVal = e.element;
e.element = element;
return oldVal;
}
/**
*?
* 把指定元素添加到指定位置，需先定位到此位置的節點
* 詳情見addBefore()
*/
public void add(int index, E element) {
addBefore(element, (index == size ? header : entry(index)));
}
/**
* 移除指定位置的元素
*/
public E remove(int index) {
return remove(entry(index));
}
/**
*?
* 返回指定索引位置的Entry對象，需要依次遍歷得到。
* 這里稍做了一下優化，如果index < size/2 從前面開始遍歷
* 如果index >= size/2 從后面開始遍歷
*/
private Entry<E> entry(int index) {
if (index < 0 || index >= size) //index在0(包含)到size(不包含)之間，索引從0開始
throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
+ size);
Entry<E> e = header;
if (index < (size >> 1)) {
for (int i = 0; i <= index; i++)
e = e.next; //依次調用e.next才能得到,需調用index+1次，因為它是從頭結點開始的
} else {
for (int i = size; i > index; i--)
e = e.previous; //依次調用e.previous才能得到
}
return e;
}
// Search Operations
/**
*?
* 返回o第一次出現的位置，如果在List中找不到o返回-1
*/
public int indexOf(Object o) {
int index = 0; //鏈表的索引也是從0開始
if (o == null) {
for (Entry e = header.next; e != header; e = e.next) { //從頭結點開始，依次遍歷
if (e.element == null)
return index;
index++;
}
} else {
for (Entry e = header.next; e != header; e = e.next) {
if (o.equals(e.element))
return index;
index++;
}
}
return -1;
}
/**
* 雙向循環鏈表，從后面開始遍歷即可
*/
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Entry e = header.previous; e != header; e = e.previous) {
index--;
if (e.element == null)
return index;
}
} else {
for (Entry e = header.previous; e != header; e = e.previous) {
index--;
if (o.equals(e.element))
return index;
}
}
return -1;
}
// Queue operations.有關隊列的基本操作
/**
* 如果鏈表長度不為空，獲取第一個元素
* 否則返回null
*/
public E peek() {
if (size == 0)
return null;
return getFirst();
}
/**
* 跟peek方法相似，不過這里size為0的話直接拋出異常
*/
public E element() {
return getFirst();
}
/**
* 如果鏈表長度不為空，移除第一個元素,并返回它
* 否則返回null
*/
public E poll() {
if (size == 0)
return null;
return removeFirst();
}
/**
* 與poll方法類似，不過長度為空，即header.next = header
* 拋出NoSuchElementException
*/
public E remove() {
return removeFirst();
}
/**
* 添加一個元素到鏈表尾部
*/
public boolean offer(E e) {
return add(e);
}
// Deque operations
/**
* 添加一個元素到頭結點之后，原來的第一個節點之前
*/
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
/**
* 在尾部添加一個元素
*/
public boolean offerLast(E e) {
addLast(e);
return true;
}
/**
* 獲取第一個元素，如果size為0，返回空
* 否則返回第一個元素
*/
public E peekFirst() {
if (size == 0)
return null;
return getFirst();
}
/**
* 獲取最后一個元素，如果size為0，返回空
* 否則返回最后一個元素
*/
public E peekLast() {
if (size == 0)
return null;
return getLast();
}
/**
*?
* 移除第一個元素并返回它
* 如果size為0則直接返回null
*/
public E pollFirst() {
if (size == 0)
return null;
return removeFirst();
}
/**
* 移除最后一個元素并返回它
* 如果size為0則直接返回null
*/
public E pollLast() {
if (size == 0)
return null;
return removeLast();
}
/**
* 在開始位置添加一個元素
*/
public void push(E e) {
addFirst(e);
}
/**
* 移除第一個元素
*/
public E pop() {
return removeFirst();
}
/**
*?
* 移除第一次出現的指定的元素
* 如果遍歷整個List后沒有找到o，則不做任何改變
*?
*/
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}
/**
* 這個差不多，從后面開始遍歷即可
*/
public boolean removeLastOccurrence(Object o) {
if (o == null) {
for (Entry<E> e = header.previous; e != header; e = e.previous) {
if (e.element == null) {
remove(e);
return true;
}
}
} else {
for (Entry<E> e = header.previous; e != header; e = e.previous) {
if (o.equals(e.element)) {
remove(e);
return true;
}
}
}
return false;
}
/**
*?
* 返回一個list-iterator.
*/
public ListIterator<E> listIterator(int index) {
return new ListItr(index);
}
/**
* 重新 實現ListIterator，使其跟符合鏈表的特性
* iterator方法由AbstractSequentialList實現了，
* 但是調用的還是本ListIterator。只不過只能使用iterator接口的方法
* */
private class ListItr implements ListIterator<E> {
private Entry<E> lastReturned = header; //上一次調用next或previous返回的元素，沒有調用next則為頭結點
private Entry<E> next; //下一次調用next方法返回的元素
private int nextIndex; //下一次調用next返回的元素的索引
private int expectedModCount = modCount; //用來檢測遍歷過程中是否產生了并發操作
ListItr(int index) { //構造器，是迭代器定位到index位置，要返回index位置的元素需調用一次next()方法時
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: " + index
+ ", Size: " + size);
if (index < (size >> 1)) { //從前面開始遍歷
next = header.next; //這是index為0的元素
for (nextIndex = 0; nextIndex < index; nextIndex++)
next = next.next; //最終next為第index個元素，index從0開始
} else { //從后面開始遍歷
next = header;
for (nextIndex = size; nextIndex > index; nextIndex--)
next = next.previous; //最終next為第index個元素，index從0開始
}
}
public boolean hasNext() { //size位置可沒有元素
return nextIndex != size;
}
public E next() {
checkForComodification();
if (nextIndex == size)
throw new NoSuchElementException();
lastReturned = next;
next = next.next; //這里與ArrayList中的cursor何其相似
nextIndex++;
return lastReturned.element;
}
public boolean hasPrevious() {
return nextIndex != 0;
}
public E previous() {
if (nextIndex == 0)
throw new NoSuchElementException();
lastReturned = next = next.previous;
nextIndex--;
checkForComodification();
return lastReturned.element;
}
public int nextIndex() { //返回下一次調用next返回的元素的索引
return nextIndex;
}
public int previousIndex() { //返回下一次調用previous返回的元素的索引
return nextIndex - 1;
}
public void remove() {
checkForComodification();
Entry<E> lastNext = lastReturned.next;
try {
LinkedList.this.remove(lastReturned); //移除上一層調用next()或previous返回的元素
} catch (NoSuchElementException e) {
throw new IllegalStateException();
}
if (next == lastReturned) //表明是調用previous后才調用remove方法
next = lastNext;
else
nextIndex--; //元素減少。nextIndex--
lastReturned = header; //重置lastReturned
expectedModCount++;
}
public void set(E e) {
if (lastReturned == header)
throw new IllegalStateException();
checkForComodification();
lastReturned.element = e;
}
public void add(E e) {
checkForComodification();
lastReturned = header;
addBefore(e, next); //在上一次調用next返回的元素之后，在上次調用previous返回的元素之前添加e
nextIndex++; //元素增加，索引增加，保證下次調用next()不是返回添加的元素
expectedModCount++;
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
/**
* LinkedList的元素節點，保存當前節點的元素
* 以及下一個節點，和上一個節點的引用
* 由此看出LinkedList是一個雙向鏈表
*/
private static class Entry<E> {
E element; //當前節點元素
Entry<E> next; //下一個節點引用
Entry<E> previous; //上一個節點引用
Entry(E element, Entry<E> next, Entry<E> previous) {
this.element = element;
this.next = next;
this.previous = previous;
}
}
/**
* ?在entry之前添加一個節點e
*?
*/
private Entry<E> addBefore(E e, Entry<E> entry) {
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous); //新節點的前驅和后繼，只有一個元素的話前驅和后繼都為header
newEntry.previous.next = newEntry; //新節點的前驅的后繼為新節點，只包含newEntry一個元素的話修改的是頭結點的next
newEntry.next.previous = newEntry; //新節點的后繼的前驅為新節點,只包含newEntry一個元素的話修改的是頭結點的previous
size++;
modCount++;
return newEntry;
}
/**
* 移除指定節點?
*/
private E remove(Entry<E> e) {
if (e == header)
throw new NoSuchElementException();
E result = e.element;
//修改節點指針
e.previous.next = e.next; //e的前驅的后繼等于e的后繼
e.next.previous = e.previous; //e的后繼的前驅等于e的前驅
e.next = e.previous = null; //let gc work
e.element = null;
size--; //size--
modCount++;
return result;
}
/**
* 逆序返回所有元素的迭代器
*/
public Iterator<E> descendingIterator() {
return new DescendingIterator();
}
/** Adapter to provide descending iterators via ListItr.previous */
private class DescendingIterator implements Iterator {
final ListItr itr = new ListItr(size());
public boolean hasNext() {
return itr.hasPrevious();
}
public E next() {
return itr.previous();
}
public void remove() {
itr.remove();
}
}
/**
* 返回一個LikedList的淺拷貝對象
*/
public Object clone() {
LinkedList<E> clone = null;
try {
clone = (LinkedList<E>) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
// Put clone into "virgin" state，即重置其為初始狀態
clone.header = new Entry<E>(null, null, null);
clone.header.next = clone.header.previous = clone.header;
clone.size = 0;
clone.modCount = 0;
// 初始化克隆對象
for (Entry<E> e = header.next; e != header; e = e.next)
clone.add(e.element);
return clone;
}
/**
* 返回一個新建對象數組，包含鏈表中所有元素
*/
public Object[] toArray() {
Object[] result = new Object[size]; //新建一size長度對象數組
int i = 0;
for (Entry<E> e = header.next; e != header; e = e.next) //遍歷賦值
result[i++] = e.element;
return result;
}
/**
* 所有toArray方法都是一個思想...
* 只是遍歷方式不同
* */
public <T> T[] toArray(T[] a) {
if (a.length < size) //如果指定數組長度小于size，新建一數組
a = (T[]) java.lang.reflect.Array.newInstance(a.getClass()
.getComponentType(), size);
int i = 0;
Object[] result = a;
for (Entry<E> e = header.next; e != header; e = e.next)
result[i++] = e.element;
if (a.length > size) //同ArrayList
a[size] = null;
return a;
}
private static final long serialVersionUID = 876323262645176354L;
/**
* 序列化LikedList，保存其狀態
*/
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out any hidden serialization magic
//添加一些序列化的額外信息，表明它是一個序列化的文件
s.defaultWriteObject();
// 寫長度
s.writeInt(size);
// 寫元素
for (Entry e = header.next; e != header; e = e.next)
s.writeObject(e.element);
}
/**
* 從流中讀取
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden serialization magic
s.defaultReadObject();
// 讀長度
int size = s.readInt();
// 初始化header
header = new Entry<E>(null, null, null);
header.next = header.previous = header;
// 按順序寫入所有元素
for (int i = 0; i < size; i++)
addBefore((E) s.readObject(), header);
}
}
三。HashMap(數組加鏈表的結合體)?
/**
?* 作用：用于實現快速查找
?* HashMap實現的數據結構：動態數組和鏈表的結合體
?* */
public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>,
Cloneable, Serializable {
/**
* 默認初始數組容量，必須為2的冪
*/
static final int DEFAULT_INITIAL_CAPACITY = 16;
/**
*
* 最大容量為1 * 2^30 即2的30次方
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
*?
* hashMap的加載系數，當數組中的元素增多時，通過hash函數算出的數組下標
* 相同幾率增加。為保證查找的效率，當數組中的元素超過
* load_factor * table.length 時就要擴充容量
* 默認加載系數為0.75
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
*?
* 數組存放Entry對象，單向鏈表的第一個元素，
* 通過它可以遍歷整個鏈表。
* table長度會在需要時進行擴充，table長度始終為2的冪
*/
transient Entry[] table;
/**
* key-value鍵值對個數
*/
transient int size;
/**
* HashMap size >= threshlod時就擴充數組容量
*/
int threshold;
/**
* hash表加載因子
*/
final float loadFactor;
/**
*?
* hash表發生結構性改變的次數，這些方法包括，put，remove等對size進行改變的操作
* 用iterator遍歷時可以用來檢測是否對HashMap進行了并發操作
*/
transient volatile int modCount;
/**
* 根據指定的初始容量和加載系數構建hashMap
* 初始容量如果不是2的冪，會被構造成2的冪
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: "
+ initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: "
+ loadFactor);
//找到一個2的冪的數，使其大于等于初始容量
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1; // capacity = capacity << 1,左移一位?
this.loadFactor = loadFactor;
threshold = (int) (capacity * loadFactor);
table = new Entry[capacity];
init(); //所有構造方法都含有此空方法，做一些其他初始化操作。根據業務要求，可由其子類實現
}
/**
* 根據指定容量與默認加載系數構建HashMap
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 采用默認容量16與默認加載系數0.75構建HashMap
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
/**
*?
* 根據指定Map中的鍵值對,默認加載因子構建HashMap
*/
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, //size要小于容量*0.75
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
putAllForCreate(m);
}
// internal utilities
/**
*
* 在new table之后，在添加元素之前被調用
*/
void init() {
}
/**
*?
* hash算法，根據key的hashCode計算其hash值
* 此算法看的一知半解，大家有興趣可以查看其它資料
* >>>無符號右移 ? ? ^按位異或
*/
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
/**
* 根據hash值與數組長度計算其數組索引。
* length為2的冪，使不同hash通過h&(length-1)產生的索引盡量不同，即減少碰撞。
* 如果產生的索引都不同，通過找到索引就可以直接找到value，而不需要遍歷鏈表。
* 可以使產生的索引始終在table索引范圍之內
* 此方法詳細解析可見：http://www.iteye.com/topic/539465
*/
static int indexFor(int h, int length) {
return h & (length - 1);
}
/**
* 鍵值對數目
*/
public int size() {
return size;
}
/**
* 判斷hashMap是否為空
*/
public boolean isEmpty() {
return size == 0;
}
/**
*?
* 通過key值獲得value，如果沒有找到此key則返回null。
* 不過返回null也可能是其value為null
* 通過contain方法可判斷Map中是否含有此鍵
*?
*/
public V get(Object key) {
if (key == null) //空鍵另外處理
return getForNullKey();
int hash = hash(key.hashCode());
//定位到index，并查看e的下一個節點是否為null，否則繼續遍歷
for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
/**
*?
* 空鍵的hash值為0，所以其數組中的索引為0.
* 獨立把此方法分離出來是為了提高兩個最常用的方法get和put的性能，
* 但在其它情況下此方法被合并了.
*/
private V getForNullKey() {
for (Entry<K, V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
/**
* 如果Map中含有此key返回true.
* 具體見getEntry.
*/
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
/**
*?
* 通過返回Entry而不是value可確保Map中是否含有此key
*/
final Entry<K, V> getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key.hashCode());
for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
if (e.hash == hash
&& ((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
/**
*?
* replaced.
* 通過指定的key值存儲指定value，如果Map中含有此key則用指定value替換old value
*/
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this); //當你調用put并在替換老值時會調用此方法，假如你在這個時候想做一些額外操作可繼承Entry重寫此方法
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
private V putForNullKey(V value) {
for (Entry<K, V> e = table[0]; e != null; e = e.next) {
if (e.key == null) { //如果含有此null key替換老值
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0); //否則添加此Entry到數組
return null;
}
/**
*?
* 此方法用來替代put方法，不會調整table大小。
* 此方法在確認map鍵值對個數始終小于table.length * load_factor，
* 添加元素時調用。主要是為了提高性能
*/
private void putForCreate(K key, V value) {
int hash = (key == null) ? 0 : hash(key.hashCode());
int i = indexFor(hash, table.length);
/**
*?
* 查看是否存在同樣的key值，如果有就替換其value
*/
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash
&& ((k = e.key) == key || (key != null && key.equals(k)))) {
e.value = value;
return;
}
}
//否則添加一個Entry對象
createEntry(hash, key, value, i);
}
/**
* 依次遍歷添加
* */
private void putAllForCreate(Map<? extends K, ? extends V> m) {
for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m
.entrySet().iterator(); i.hasNext();) {
Map.Entry<? extends K, ? extends V> e = i.next();
putForCreate(e.getKey(), e.getValue());
}
}
/**
*?
* 當HashMap中元素越來越多時，發生碰撞的幾率增大，為提高效率，當元素超過
* threshold時就要對數組進行擴充，擴充后，原數組中所有數據都要重新計算
* 其在新數組中的位置，所以每擴充一次對性能影響是非常大的。
*/
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) { //如果數組容量已經最大，不再擴充。
threshold = Integer.MAX_VALUE; //使threshold = Integer.MAX_VALUE,使resize方法不再被調用
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int) (newCapacity * loadFactor);
}
/**
*?
* 把table中所有的Entry對象轉移到newTabel
*/
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry<K, V> e = src[j];
if (e != null) {
src[j] = null; //只置空第一個節點即可，因為此節點存在數組中
do {
Entry<K, V> next = e.next;
int i = indexFor(e.hash, newCapacity); ?//根據新容量重新計算index
e.next = newTable[i]; //最后添加的節點放最前面
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
/**
*
* 把所有元素從知道map中復制到本map
*/
public void putAll(Map<? extends K, ? extends V> m) {
int numKeysToBeAdded = m.size();
if (numKeysToBeAdded == 0)
return;
/*
*?
* 如果numKeysToBeAdded大于或等于threshold就擴展map
* 這是一個保守的方法。本來的條件應該是(m.size() + size) >= threshold,
* 但是如果所有被添加的元素的key值在本map中都存在，map擴充的容量將是
* 最佳容量的兩倍。這極大的浪費了空間，所以采用此保守的方法計算newCapacity。
* 否則不再此處擴充就在put方法中進行擴充
*/
if (numKeysToBeAdded > threshold) {
int targetCapacity = (int) (numKeysToBeAdded / loadFactor + 1);
if (targetCapacity > MAXIMUM_CAPACITY)
targetCapacity = MAXIMUM_CAPACITY;
int newCapacity = table.length;
while (newCapacity < targetCapacity)
newCapacity <<= 1;
if (newCapacity > table.length)
resize(newCapacity);
}
//依次遍歷添加
for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m
.entrySet().iterator(); i.hasNext();) {
Map.Entry<? extends K, ? extends V> e = i.next();
put(e.getKey(), e.getValue());
}
}
/**
* 根據知道key移除鍵值對，返回移除的元素
*/
public V remove(Object key) {
Entry<K, V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
/**
* 根據key移除Entry對象
*/
final Entry<K, V> removeEntryForKey(Object key) {
int hash = (key == null) ? 0 : hash(key.hashCode());
int i = indexFor(hash, table.length);
Entry<K, V> prev = table[i];
Entry<K, V> e = prev;
while (e != null) {
Entry<K, V> next = e.next;
Object k;
if (e.hash == hash
&& ((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e) //表明鏈表只有一個Entry對象
table[i] = next;
else
prev.next = next; //修改指針
e.recordRemoval(this); //在移除元素時調用
return e;
}
prev = e;
e = next;
}
return e;
}
/**
* 同remove方法基本相似
*/
final Entry<K, V> removeMapping(Object o) {
if (!(o instanceof Map.Entry))
return null;
Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
Object key = entry.getKey();
int hash = (key == null) ? 0 : hash(key.hashCode());
int i = indexFor(hash, table.length);
Entry<K, V> prev = table[i];
Entry<K, V> e = prev;
while (e != null) {
Entry<K, V> next = e.next;
if (e.hash == hash && e.equals(entry)) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
/**
* 移除所有元素
*/
public void clear() {
modCount++;
Entry[] tab = table;
for (int i = 0; i < tab.length; i++)
tab[i] = null; //只要把數組置空即可
size = 0;
}
/**
* 是否包含次value
*/
public boolean containsValue(Object value) {
if (value == null)
return containsNullValue();
Entry[] tab = table;
for (int i = 0; i < tab.length; i++)
for (Entry e = tab[i]; e != null; e = e.next)
if (value.equals(e.value))
return true;
return false;
}
/**
* 是否包含空值
*/
private boolean containsNullValue() {
Entry[] tab = table;
for (int i = 0; i < tab.length; i++)
for (Entry e = tab[i]; e != null; e = e.next)
if (e.value == null)
return true;
return false;
}
/**
* 返回HashMap的淺拷貝實例
*/
public Object clone() {
HashMap<K, V> result = null;
try {
result = (HashMap<K, V>) super.clone();
} catch (CloneNotSupportedException e) {
// assert false;
}
result.table = new Entry[table.length];
result.entrySet = null;
result.modCount = 0;
result.size = 0;
result.init();
result.putAllForCreate(this); //依次添加本map所有元素到淺拷貝的map實例中
return result;
}
static class Entry<K, V> implements Map.Entry<K, V> {
final K key;
V value;
Entry<K, V> next;
final int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K, V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
//Entry的equals方法，鍵值相等即Entry對象相等
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry) o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
/**
* 重寫hashCode方法，異或key與value的hashCode值
*/
public final int hashCode() {
return (key == null ? 0 : key.hashCode())
^ (value == null ? 0 : value.hashCode());
}
public final String toString() {
return getKey() + "=" + getValue();
}
/**
*
* 當添加一鍵值對，發現鍵已存在時調用此方法
* ?可以繼承Entry對象重寫此方法
*/
void recordAccess(HashMap<K, V> m) {
}
/**
* 當有Entry對象被移除時，此方法被調用。
* 可以繼承Entry對象重寫此方法
*/
void recordRemoval(HashMap<K, V> m) {
}
}
/**
*?
* 如果適當此方法會resize table
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K, V> e = table[bucketIndex]; ?
table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
if (size++ >= threshold) //如果size超過threshold就調整數組容量大小為原來的兩倍
resize(2 * table.length);
}
/**
*
* 與addEntry方法類似。但是方法不需要擔心容量的擴充
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K, V> e = table[bucketIndex]; //如果此節點已經有一個Entry對象，返回e，否則返回null
table[bucketIndex] = new Entry<K, V>(hash, key, value, e); //以新加入的節點作為第一個節點
size++;
}
/**
* 抽象類，next方法由其子類實現，
* 不同的next方法返回不同的迭代器
* 包括key，value，keySet迭代器
* */
private abstract class HashIterator<E> implements Iterator<E> {
Entry<K, V> next; // next entry to return
int expectedModCount; // For fast-fail
int index; // current slot
Entry<K, V> current; // current entry
HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
//遍歷直到獲取第一個Entry對象，因為有的索引可能為空
while (index < t.length && (next = t[index++]) == null)?
;
}
}
public final boolean hasNext() {
return next != null;
}
/**
* 返回下一個Entry對象
* */
final Entry<K, V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K, V> e = next;
if (e == null)
throw new NoSuchElementException();
if ((next = e.next) == null) {
Entry[] t = table;
//繼續找不為空的索引中的Entry對象
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
/**
* 移除當前Entry對象，即調用nextEntry返回的Entry對象
*/
public void remove() {
if (current == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Object k = current.key;
current = null;
HashMap.this.removeEntryForKey(k); //此方法會改變modCount
expectedModCount = modCount; //所以可以用此語句檢測是否產生了并發操作
}
}
//依次重寫next方法，返回不同的迭代器。
private final class ValueIterator extends HashIterator<V> {
public V next() {
return nextEntry().value;
}
}
private final class KeyIterator extends HashIterator<K> {
public K next() {
return nextEntry().getKey();
}
}
private final class EntryIterator extends HashIterator<Map.Entry<K, V>> {
public Map.Entry<K, V> next() {
return nextEntry();
}
}
// Subclass overrides these to alter behavior of views' iterator() method
Iterator<K> newKeyIterator() {
return new KeyIterator();
}
Iterator<V> newValueIterator() {
return new ValueIterator();
}
Iterator<Map.Entry<K, V>> newEntryIterator() {
return new EntryIterator();
}
// Views
private transient Set<Map.Entry<K, V>> entrySet = null;
/**
* 返回一個key集。
* 此Set集合只在第一次調用keySet()時被創建，此后返回的都是同一個Set。?
? ? ?* 此方法不是線程安全的，大量線程多次調用此方法返回的可能不是同一個Set（可能是重新new的）
? ? ?*?
? ? ?* 對map的修改會反應到Set當中，相反，對Set中key進行移除操作，比如?
? ? ?* Iterator.remove,Set.remove ,removeAll,retainAll,clear等操作時被移除的鍵?
? ? ?* 和它相關聯的值也將從map中被移除，但是此Set不支持任何添加操作?
*/
public Set<K> keySet() {
Set<K> ks = keySet;
return (ks != null ? ks : (keySet = new KeySet()));
}
private final class KeySet extends AbstractSet<K> {
public Iterator<K> iterator() {
return newKeyIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsKey(o);
}
/**
* 重寫了Set的remove方法，
* 父類remove都是調用迭代器的remove方法
* */
public boolean remove(Object o) {
return HashMap.this.removeEntryForKey(o) != null;
}
public void clear() {
HashMap.this.clear();
}
}
/**
* 同上
*/
public Collection<V> values() {
Collection<V> vs = values;
return (vs != null ? vs : (values = new Values()));
}
private final class Values extends AbstractCollection<V> {
public Iterator<V> iterator() {
return newValueIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsValue(o);
}
public void clear() {
HashMap.this.clear();
}
}
/**
* 同上
*/
public Set<Map.Entry<K, V>> entrySet() {
return entrySet0();
}
private Set<Map.Entry<K, V>> entrySet0() {
Set<Map.Entry<K, V>> es = entrySet;
return es != null ? es : (entrySet = new EntrySet());
}
private final class EntrySet extends AbstractSet<Map.Entry<K, V>> {
public Iterator<Map.Entry<K, V>> iterator() {
return newEntryIterator();
}
public boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<K, V> e = (Map.Entry<K, V>) o;
Entry<K, V> candidate = getEntry(e.getKey());
return candidate != null && candidate.equals(e);
}
public boolean remove(Object o) {
return removeMapping(o) != null;
}
public int size() {
return size;
}
public void clear() {
HashMap.this.clear();
}
}
/**
* 序列化hashMap對象
*/
private void writeObject(java.io.ObjectOutputStream s) throws IOException {
Iterator<Map.Entry<K, V>> i = (size > 0) ? entrySet0().iterator()
: null;
// 寫入默認信息
s.defaultWriteObject();
// 寫入可以存儲的容量
s.writeInt(table.length);
// 寫入實際長度
s.writeInt(size);
// Write out keys and values (alternating)
if (i != null) {
while (i.hasNext()) { //依次寫入鍵值對
Map.Entry<K, V> e = i.next();
s.writeObject(e.getKey());
s.writeObject(e.getValue());
}
}
}
private static final long serialVersionUID = 362498820763181265L;
/**
* 讀出HashMap對象
*/
private void readObject(java.io.ObjectInputStream s) throws IOException,
ClassNotFoundException {
//讀出默認信息
s.defaultReadObject();
// 讀容量
int numBuckets = s.readInt();
table = new Entry[numBuckets];
init(); // Give subclass a chance to do its thing.
// 讀長度
int size = s.readInt();
//讀鍵值對，并還原HashMap元素
for (int i = 0; i < size; i++) {
K key = (K) s.readObject();
V value = (V) s.readObject();
putForCreate(key, value);
}
}
// These methods are used when serializing HashSets
int capacity() {
return table.length;
}
float loadFactor() {
return loadFactor;
}
}
/**
?* 作用：用于實現快速查找
?* HashMap實現的數據結構：動態數組和鏈表的結合體
?* */
public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>,
Cloneable, Serializable {
/**
* 默認初始數組容量，必須為2的冪
*/
static final int DEFAULT_INITIAL_CAPACITY = 16;
/**
*
* 最大容量為1 * 2^30 即2的30次方
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
*?
* hashMap的加載系數，當數組中的元素增多時，通過hash函數算出的數組下標
* 相同幾率增加。為保證查找的效率，當數組中的元素超過
* load_factor * table.length 時就要擴充容量
* 默認加載系數為0.75
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
*?
* 數組存放Entry對象，單向鏈表的第一個元素，
* 通過它可以遍歷整個鏈表。
* table長度會在需要時進行擴充，table長度始終為2的冪
*/
transient Entry[] table;
/**
* key-value鍵值對個數
*/
transient int size;
/**
* HashMap size >= threshlod時就擴充數組容量
*/
int threshold;
/**
* hash表加載因子
*/
final float loadFactor;
/**
*?
* hash表發生結構性改變的次數，這些方法包括，put，remove等對size進行改變的操作
* 用iterator遍歷時可以用來檢測是否對HashMap進行了并發操作
*/
transient volatile int modCount;
/**
* 根據指定的初始容量和加載系數構建hashMap
* 初始容量如果不是2的冪，會被構造成2的冪
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: "
+ initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: "
+ loadFactor);
//找到一個2的冪的數，使其大于等于初始容量
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1; // capacity = capacity << 1,左移一位?
this.loadFactor = loadFactor;
threshold = (int) (capacity * loadFactor);
table = new Entry[capacity];
init(); //所有構造方法都含有此空方法，做一些其他初始化操作。根據業務要求，可由其子類實現
}
/**
* 根據指定容量與默認加載系數構建HashMap
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 采用默認容量16與默認加載系數0.75構建HashMap
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
/**
*?
* 根據指定Map中的鍵值對,默認加載因子構建HashMap
*/
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, //size要小于容量*0.75
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
putAllForCreate(m);
}
// internal utilities
/**
*
* 在new table之后，在添加元素之前被調用
*/
void init() {
}
/**
*?
* hash算法，根據key的hashCode計算其hash值
* 此算法看的一知半解，大家有興趣可以查看其它資料
* >>>無符號右移 ? ? ^按位異或
*/
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
/**
* 根據hash值與數組長度計算其數組索引。
* length為2的冪，使不同hash通過h&(length-1)產生的索引盡量不同，即減少碰撞。
* 如果產生的索引都不同，通過找到索引就可以直接找到value，而不需要遍歷鏈表。
* 可以使產生的索引始終在table索引范圍之內
* 此方法詳細解析可見：http://www.iteye.com/topic/539465
*/
static int indexFor(int h, int length) {
return h & (length - 1);
}
/**
* 鍵值對數目
*/
public int size() {
return size;
}
/**
* 判斷hashMap是否為空
*/
public boolean isEmpty() {
return size == 0;
}
/**
*?
* 通過key值獲得value，如果沒有找到此key則返回null。
* 不過返回null也可能是其value為null
* 通過contain方法可判斷Map中是否含有此鍵
*?
*/
public V get(Object key) {
if (key == null) //空鍵另外處理
return getForNullKey();
int hash = hash(key.hashCode());
//定位到index，并查看e的下一個節點是否為null，否則繼續遍歷
for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
/**
*?
* 空鍵的hash值為0，所以其數組中的索引為0.
* 獨立把此方法分離出來是為了提高兩個最常用的方法get和put的性能，
* 但在其它情況下此方法被合并了.
*/
private V getForNullKey() {
for (Entry<K, V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
/**
* 如果Map中含有此key返回true.
* 具體見getEntry.
*/
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
/**
*?
* 通過返回Entry而不是value可確保Map中是否含有此key
*/
final Entry<K, V> getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key.hashCode());
for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
if (e.hash == hash
&& ((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
/**
*?
* replaced.
* 通過指定的key值存儲指定value，如果Map中含有此key則用指定value替換old value
*/
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this); //當你調用put并在替換老值時會調用此方法，假如你在這個時候想做一些額外操作可繼承Entry重寫此方法
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
private V putForNullKey(V value) {
for (Entry<K, V> e = table[0]; e != null; e = e.next) {
if (e.key == null) { //如果含有此null key替換老值
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0); //否則添加此Entry到數組
return null;
}
/**
*?
* 此方法用來替代put方法，不會調整table大小。
* 此方法在確認map鍵值對個數始終小于table.length * load_factor，
* 添加元素時調用。主要是為了提高性能
*/
private void putForCreate(K key, V value) {
int hash = (key == null) ? 0 : hash(key.hashCode());
int i = indexFor(hash, table.length);
/**
*?
* 查看是否存在同樣的key值，如果有就替換其value
*/
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash
&& ((k = e.key) == key || (key != null && key.equals(k)))) {
e.value = value;
return;
}
}
//否則添加一個Entry對象
createEntry(hash, key, value, i);
}
/**
* 依次遍歷添加
* */
private void putAllForCreate(Map<? extends K, ? extends V> m) {
for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m
.entrySet().iterator(); i.hasNext();) {
Map.Entry<? extends K, ? extends V> e = i.next();
putForCreate(e.getKey(), e.getValue());
}
}
/**
*?
* 當HashMap中元素越來越多時，發生碰撞的幾率增大，為提高效率，當元素超過
* threshold時就要對數組進行擴充，擴充后，原數組中所有數據都要重新計算
* 其在新數組中的位置，所以每擴充一次對性能影響是非常大的。
*/
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) { //如果數組容量已經最大，不再擴充。
threshold = Integer.MAX_VALUE; //使threshold = Integer.MAX_VALUE,使resize方法不再被調用
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int) (newCapacity * loadFactor);
}
/**
*?
* 把table中所有的Entry對象轉移到newTabel
*/
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry<K, V> e = src[j];
if (e != null) {
src[j] = null; //只置空第一個節點即可，因為此節點存在數組中
do {
Entry<K, V> next = e.next;
int i = indexFor(e.hash, newCapacity); ?//根據新容量重新計算index
e.next = newTable[i]; //最后添加的節點放最前面
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
/**
*
* 把所有元素從知道map中復制到本map
*/
public void putAll(Map<? extends K, ? extends V> m) {
int numKeysToBeAdded = m.size();
if (numKeysToBeAdded == 0)
return;
/*
*?
* 如果numKeysToBeAdded大于或等于threshold就擴展map
* 這是一個保守的方法。本來的條件應該是(m.size() + size) >= threshold,
* 但是如果所有被添加的元素的key值在本map中都存在，map擴充的容量將是
* 最佳容量的兩倍。這極大的浪費了空間，所以采用此保守的方法計算newCapacity。
* 否則不再此處擴充就在put方法中進行擴充
*/
if (numKeysToBeAdded > threshold) {
int targetCapacity = (int) (numKeysToBeAdded / loadFactor + 1);
if (targetCapacity > MAXIMUM_CAPACITY)
targetCapacity = MAXIMUM_CAPACITY;
int newCapacity = table.length;
while (newCapacity < targetCapacity)
newCapacity <<= 1;
if (newCapacity > table.length)
resize(newCapacity);
}
//依次遍歷添加
for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m
.entrySet().iterator(); i.hasNext();) {
Map.Entry<? extends K, ? extends V> e = i.next();
put(e.getKey(), e.getValue());
}
}
/**
* 根據知道key移除鍵值對，返回移除的元素
*/
public V remove(Object key) {
Entry<K, V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
/**
* 根據key移除Entry對象
*/
final Entry<K, V> removeEntryForKey(Object key) {
int hash = (key == null) ? 0 : hash(key.hashCode());
int i = indexFor(hash, table.length);
Entry<K, V> prev = table[i];
Entry<K, V> e = prev;
while (e != null) {
Entry<K, V> next = e.next;
Object k;
if (e.hash == hash
&& ((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e) //表明鏈表只有一個Entry對象
table[i] = next;
else
prev.next = next; //修改指針
e.recordRemoval(this); //在移除元素時調用
return e;
}
prev = e;
e = next;
}
return e;
}
/**
* 同remove方法基本相似
*/
final Entry<K, V> removeMapping(Object o) {
if (!(o instanceof Map.Entry))
return null;
Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
Object key = entry.getKey();
int hash = (key == null) ? 0 : hash(key.hashCode());
int i = indexFor(hash, table.length);
Entry<K, V> prev = table[i];
Entry<K, V> e = prev;
while (e != null) {
Entry<K, V> next = e.next;
if (e.hash == hash && e.equals(entry)) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
/**
* 移除所有元素
*/
public void clear() {
modCount++;
Entry[] tab = table;
for (int i = 0; i < tab.length; i++)
tab[i] = null; //只要把數組置空即可
size = 0;
}
/**
* 是否包含次value
*/
public boolean containsValue(Object value) {
if (value == null)
return containsNullValue();
Entry[] tab = table;
for (int i = 0; i < tab.length; i++)
for (Entry e = tab[i]; e != null; e = e.next)
if (value.equals(e.value))
return true;
return false;
}
/**
* 是否包含空值
*/
private boolean containsNullValue() {
Entry[] tab = table;
for (int i = 0; i < tab.length; i++)
for (Entry e = tab[i]; e != null; e = e.next)
if (e.value == null)
return true;
return false;
}
/**
* 返回HashMap的淺拷貝實例
*/
public Object clone() {
HashMap<K, V> result = null;
try {
result = (HashMap<K, V>) super.clone();
} catch (CloneNotSupportedException e) {
// assert false;
}
result.table = new Entry[table.length];
result.entrySet = null;
result.modCount = 0;
result.size = 0;
result.init();
result.putAllForCreate(this); //依次添加本map所有元素到淺拷貝的map實例中
return result;
}
static class Entry<K, V> implements Map.Entry<K, V> {
final K key;
V value;
Entry<K, V> next;
final int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K, V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
//Entry的equals方法，鍵值相等即Entry對象相等
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry) o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
/**
* 重寫hashCode方法，異或key與value的hashCode值
*/
public final int hashCode() {
return (key == null ? 0 : key.hashCode())
^ (value == null ? 0 : value.hashCode());
}
public final String toString() {
return getKey() + "=" + getValue();
}
/**
*
* 當添加一鍵值對，發現鍵已存在時調用此方法
* ?可以繼承Entry對象重寫此方法
*/
void recordAccess(HashMap<K, V> m) {
}
/**
* 當有Entry對象被移除時，此方法被調用。
* 可以繼承Entry對象重寫此方法
*/
void recordRemoval(HashMap<K, V> m) {
}
}
/**
*?
* 如果適當此方法會resize table
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K, V> e = table[bucketIndex]; ?
table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
if (size++ >= threshold) //如果size超過threshold就調整數組容量大小為原來的兩倍
resize(2 * table.length);
}
/**
*
* 與addEntry方法類似。但是方法不需要擔心容量的擴充
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K, V> e = table[bucketIndex]; //如果此節點已經有一個Entry對象，返回e，否則返回null
table[bucketIndex] = new Entry<K, V>(hash, key, value, e); //以新加入的節點作為第一個節點
size++;
}
/**
* 抽象類，next方法由其子類實現，
* 不同的next方法返回不同的迭代器
* 包括key，value，keySet迭代器
* */
private abstract class HashIterator<E> implements Iterator<E> {
Entry<K, V> next; // next entry to return
int expectedModCount; // For fast-fail
int index; // current slot
Entry<K, V> current; // current entry
HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
//遍歷直到獲取第一個Entry對象，因為有的索引可能為空
while (index < t.length && (next = t[index++]) == null)?
;
}
}
public final boolean hasNext() {
return next != null;
}
/**
* 返回下一個Entry對象
* */
final Entry<K, V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K, V> e = next;
if (e == null)
throw new NoSuchElementException();
if ((next = e.next) == null) {
Entry[] t = table;
//繼續找不為空的索引中的Entry對象
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
/**
* 移除當前Entry對象，即調用nextEntry返回的Entry對象
*/
public void remove() {
if (current == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Object k = current.key;
current = null;
HashMap.this.removeEntryForKey(k); //此方法會改變modCount
expectedModCount = modCount; //所以可以用此語句檢測是否產生了并發操作
}
}
//依次重寫next方法，返回不同的迭代器。
private final class ValueIterator extends HashIterator<V> {
public V next() {
return nextEntry().value;
}
}
private final class KeyIterator extends HashIterator<K> {
public K next() {
return nextEntry().getKey();
}
}
private final class EntryIterator extends HashIterator<Map.Entry<K, V>> {
public Map.Entry<K, V> next() {
return nextEntry();
}
}
// Subclass overrides these to alter behavior of views' iterator() method
Iterator<K> newKeyIterator() {
return new KeyIterator();
}
Iterator<V> newValueIterator() {
return new ValueIterator();
}
Iterator<Map.Entry<K, V>> newEntryIterator() {
return new EntryIterator();
}
// Views
private transient Set<Map.Entry<K, V>> entrySet = null;
/**
* 返回一個key集。
* 此Set集合只在第一次調用keySet()時被創建，此后返回的都是同一個Set。?
? ? ?* 此方法不是線程安全的，大量線程多次調用此方法返回的可能不是同一個Set（可能是重新new的）
? ? ?*?
? ? ?* 對map的修改會反應到Set當中，相反，對Set中key進行移除操作，比如?
? ? ?* Iterator.remove,Set.remove ,removeAll,retainAll,clear等操作時被移除的鍵?
? ? ?* 和它相關聯的值也將從map中被移除，但是此Set不支持任何添加操作?
*/
public Set<K> keySet() {
Set<K> ks = keySet;
return (ks != null ? ks : (keySet = new KeySet()));
}
private final class KeySet extends AbstractSet<K> {
public Iterator<K> iterator() {
return newKeyIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsKey(o);
}
/**
* 重寫了Set的remove方法，
* 父類remove都是調用迭代器的remove方法
* */
public boolean remove(Object o) {
return HashMap.this.removeEntryForKey(o) != null;
}
public void clear() {
HashMap.this.clear();
}
}
/**
* 同上
*/
public Collection<V> values() {
Collection<V> vs = values;
return (vs != null ? vs : (values = new Values()));
}
private final class Values extends AbstractCollection<V> {
public Iterator<V> iterator() {
return newValueIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsValue(o);
}
public void clear() {
HashMap.this.clear();
}
}
/**
* 同上
*/
public Set<Map.Entry<K, V>> entrySet() {
return entrySet0();
}
private Set<Map.Entry<K, V>> entrySet0() {
Set<Map.Entry<K, V>> es = entrySet;
return es != null ? es : (entrySet = new EntrySet());
}
private final class EntrySet extends AbstractSet<Map.Entry<K, V>> {
public Iterator<Map.Entry<K, V>> iterator() {
return newEntryIterator();
}
public boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<K, V> e = (Map.Entry<K, V>) o;
Entry<K, V> candidate = getEntry(e.getKey());
return candidate != null && candidate.equals(e);
}
public boolean remove(Object o) {
return removeMapping(o) != null;
}
public int size() {
return size;
}
public void clear() {
HashMap.this.clear();
}
}
/**
* 序列化hashMap對象
*/
private void writeObject(java.io.ObjectOutputStream s) throws IOException {
Iterator<Map.Entry<K, V>> i = (size > 0) ? entrySet0().iterator()
: null;
// 寫入默認信息
s.defaultWriteObject();
// 寫入可以存儲的容量
s.writeInt(table.length);
// 寫入實際長度
s.writeInt(size);
// Write out keys and values (alternating)
if (i != null) {
while (i.hasNext()) { //依次寫入鍵值對
Map.Entry<K, V> e = i.next();
s.writeObject(e.getKey());
s.writeObject(e.getValue());
}
}
}
private static final long serialVersionUID = 362498820763181265L;
/**
* 讀出HashMap對象
*/
private void readObject(java.io.ObjectInputStream s) throws IOException,
ClassNotFoundException {
//讀出默認信息
s.defaultReadObject();
// 讀容量
int numBuckets = s.readInt();
table = new Entry[numBuckets];
init(); // Give subclass a chance to do its thing.
// 讀長度
int size = s.readInt();
//讀鍵值對，并還原HashMap元素
for (int i = 0; i < size; i++) {
K key = (K) s.readObject();
V value = (V) s.readObject();
putForCreate(key, value);
}
}
// These methods are used when serializing HashSets
int capacity() {
return table.length;
}
float loadFactor() {
return loadFactor;
}
}
四。HashSet?
/**
?* 散列集（hashSet）,就是不存在重復元素的集合。
?* HashSet是在HashMap的基礎上實現的，
?* 以HashSet的元素做Key值使其值不會重復
?* */
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable,
java.io.Serializable {
static final long serialVersionUID = -5024744406713321676L;
private transient HashMap<E, Object> map;
//以Object作為虛假的Value值
private static final Object PRESENT = new Object();
/**
*?
* 構造一個新的，空Set集；
* 實際是構造一個默認初始容量為16，加載因子為0.75的空HashMap
*/
public HashSet() {
map = new HashMap<E, Object>();
}
/**
*
* 構造一個包含指定集合c中所有元素的新的Set集。
* 實際是構造包含集合c中所有元素的HashMap.
* 初始大小必須大于容量*0.75
*?
*/
public HashSet(Collection<? extends E> c) {
map = new HashMap<E, Object>(Math.max((int) (c.size() / .75f) + 1, 16));
addAll(c);
}
/**
* 以指定初始容量和加載因子構造HashMap
*/
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<E, Object>(initialCapacity, loadFactor);
}
/**
* 以初始容量構造HashMap
*/
public HashSet(int initialCapacity) {
map = new HashMap<E, Object>(initialCapacity);
}
/**
*?
* 構造一個Linked hash set.
* 以指定初始容量，加載因子構造LinkedHashMap，dummy只是為了區別其他構造方法
*?
*/
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<E, Object>(initialCapacity, loadFactor);
}
/**
* 獲得HashMap的鍵集迭代器
*/
public Iterator<E> iterator() {
return map.keySet().iterator();
}
/**
* 返回元素個數
*/
public int size() {
return map.size();
}
/**
* 判斷Hash集是否為空
*/
public boolean isEmpty() {
return map.isEmpty();
}
/**
* 如果Map中含有此key則返回true
*/
public boolean contains(Object o) {
return map.containsKey(o);
}
/**
*?
* 如果e不存在于Set中則添加e到集合，
* 如果Map中key集不存在e，則添加并返回null，否則替換原來的value，返回oldValue
*
*/
public boolean add(E e) {
return map.put(e, PRESENT) == null;
}
/**
* 移除指定元素
*/
public boolean remove(Object o) {
return map.remove(o) == PRESENT;
}
/**
* 清空map
*/
public void clear() {
map.clear();
}
/**
* 返回HashSet的淺拷貝對象
*/
public Object clone() {
try {
HashSet<E> newSet = (HashSet<E>) super.clone();
newSet.map = (HashMap<E, Object>) map.clone();
return newSet;
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
}
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out any hidden serialization magic
s.defaultWriteObject();
//寫入HashMap的容量和加載系數
s.writeInt(map.capacity());
s.writeFloat(map.loadFactor());
//寫入size
s.writeInt(map.size());
//依次寫入鍵值
for (Iterator i = map.keySet().iterator(); i.hasNext();)
s.writeObject(i.next());
}
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden serialization magic
s.defaultReadObject();
//讀取容量和加載因子構造HashMap
int capacity = s.readInt();
float loadFactor = s.readFloat();
//判斷是LinkedHashMap還是HashMap
map = (((HashSet) this) instanceof LinkedHashSet ? new LinkedHashMap<E, Object>(
capacity, loadFactor)
: new HashMap<E, Object>(capacity, loadFactor));
// 讀size
int size = s.readInt();
//依次讀出所有元素
for (int i = 0; i < size; i++) {
E e = (E) s.readObject();
map.put(e, PRESENT);
}
}
}
總結
以上是生活随笔為你收集整理的集合框架源码分析三(实现类篇ArrayList,LinkedList,HashMap)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 集合框架源码分析——抽象类
- 下一篇： 集合框架源码分析四(Collection