Java基础SE(二) 集合

// add时候传入最小扩容长度为size + 1，空列表时为10
private void ensureExplicitCapacity(int minCapacity) {
	// 版本号++
	modCount++;

	// overflow-conscious code
	if (minCapacity - elementData.length > 0)
		grow(minCapacity);
}

// 内部用数组维护
transient Object[] elementData;

private void grow(int minCapacity) {
	// overflow-conscious code
	int oldCapacity = elementData.length;
	// 默认增加一半，即原值的1.5倍
	int newCapacity = oldCapacity + (oldCapacity >> 1);
	if (newCapacity - minCapacity < 0)
		newCapacity = minCapacity;
	if (newCapacity - MAX_ARRAY_SIZE > 0)
		newCapacity = hugeCapacity(minCapacity);
	// minCapacity is usually close to size, so this is a win: 
	// 拷贝到新列表，底层还是用的System.arraycopy本地方法
	elementData = Arrays.copyOf(elementData, newCapacity);
}

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private static int hugeCapacity(int minCapacity) {
	if (minCapacity < 0) // overflow
		throw new OutOfMemoryError();
	return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

private static class Node<E> {
	E item;
	Node<E> next;
	Node<E> prev;
}	

int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);

public E remove(int index) {
	rangeCheck(index);
	
	// transient 修改版本号
	modCount++;
	E oldValue = elementData(index);
	int numMoved = size - index - 1;
	if (numMoved > 0)
		// 拷贝后面的到前面
		System.arraycopy(elementData, index+1, elementData, index,
						 numMoved);
	// 最后一位置为null，然后size-1
	elementData[--size] = null; // clear to let GC do its work

	return oldValue;
}

public boolean add(E e) {
	// HashMap# return putVal(hash(key), key, value, false, true);
	return map.put(e, PRESENT)==null;
}

public V put(K key, V value) {
	return putVal(hash(key), key, value, false, true);
}

public boolean add(E e) {
	// TreeMap#put
	return m.put(e, PRESENT)==null;
}

static class Node<K,V> implements Map.Entry<K,V> {
	final int hash;
	final K key;
	V value;
	Node<K,V> next;
}

transient Node<K,V>[] table;

// 哈希算法
static final int hash(Object key) {
	int h;
	return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

public V put(K key, V value) {
	return putVal(hash(key), key, value, false, true);
}

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) {
		// 超过最大值不再扩充
		if (oldCap >= MAXIMUM_CAPACITY) {
			threshold = Integer.MAX_VALUE;
			return oldTab;
		}
		// 扩充为原来的2倍
		else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
				 oldCap >= DEFAULT_INITIAL_CAPACITY)
			newThr = oldThr << 1; // double threshold
	}
	// 旧阈值大于0
	else if (oldThr > 0) // initial capacity was placed in threshold
		newCap = oldThr;
	else {               // zero initial threshold signifies using defaults
		newCap = DEFAULT_INITIAL_CAPACITY;
		// 负载因子0.75 * 数组长度16 = 12，新阈值为12
		newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
	}
	// 如果新阈值为0，根据负载因子设置新阈值
	if (newThr == 0) {
		float ft = (float)newCap * loadFactor;
		newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
				  (int)ft : Integer.MAX_VALUE);
	}
	threshold = newThr;
	Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
	table = newTab;
	// 旧数组有数据，复制到新数组
	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
					// jdk1.8中，旧链表迁移新链表，链表元素相对位置没有变化，实际是对对象的内存地址进行操作 
					// jdk1.7中，旧链表迁移新链表，如果在新表的数组索引位置相同，则链表元素会倒置
					Node<K,V> loHead = null, loTail = null;
					Node<K,V> hiHead = null, hiTail = null;
					Node<K,V> next;
					do {
						next = e.next;
						/**
							hash值与旧的长度做与运算，判断元素在数组中的位置是否需要移动  
							
							数组的长度为 2^N，即高位为1，其余为0，计算 e.hash & oldCap 只需看oldCap最高位1所对应的hash位  
							因为 newCap 进行了双倍扩容，即将 oldCap 左移一位，那么 oldCap-1 相当于 newCap-1 右移一位，右移后高位补0，与运算只能得到0  
							如果 (e.hash & oldCap) == 0，hash值需要与运算的那一位为0，那么 oldCap - 1 与 newCap - 1 的高位都是0，其余位又是相同的  
							表明旧元素与新元素计算出的位置相同  
							同理，当其 == 1 时，oldCap-1 高位为0，newCap-1 高位为1，其余位相同，计算出的新元素的位置比旧元素位置多了 2^N  
							即得出【新元素的下标 = 旧下标 + oldCap】
						**/
						// 如果为0，元素位置在扩容后数组中的位置没有发生改变
						if ((e.hash & oldCap) == 0) {
							if (loTail == null)
								// 首位
								loHead = e;
							else
								loTail.next = e;
							loTail = e;
						}
						// 不为0，元素位置在扩容后数组中的位置发生了改变，新的下标位置是 原下标位置 + 原数组长度
						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;
}

static class Entry<K,V> extends HashMap.Node<K,V> {
	Entry<K,V> before, after;
	Entry(int hash, K key, V value, Node<K,V> next) {
		super(hash, key, value, next);
	}
}

static final class Entry<K,V> implements Map.Entry<K,V> {
	K key;
	V value;
	Entry<K,V> left;
	Entry<K,V> right;
	Entry<K,V> parent;
	boolean color = BLACK;
	// ...
}

public V put(K key, V value) {
	Entry<K,V> t = root;
	// 第一次就直接构建根节点
	if (t == null) {
		compare(key, key); // type (and possibly null) check

		root = new Entry<>(key, value, null);
		size = 1;
		modCount++;
		return null;
	}
	int cmp;
	// 找到插入元素的父节点
	Entry<K,V> parent;
	// split comparator and comparable paths
	Comparator<? super K> cpr = comparator;
	if (cpr != null) {
		do {
			parent = t;
			cmp = cpr.compare(key, t.key);
			if (cmp < 0)
				t = t.left;
			else if (cmp > 0)
				t = t.right;
			else
				return t.setValue(value);
		} while (t != null);
	} else {
		if (key == null)
			throw new NullPointerException();
		// 使用key自己的Comparable方法
		Comparable<? super K> k = (Comparable<? super K>) key;
		do {
			parent = t;
			cmp = k.compareTo(t.key);
			if (cmp < 0)
				t = t.left;
			else if (cmp > 0)
				t = t.right;
			else
				return t.setValue(value);
		} while (t != null);
	}
	Entry<K,V> e = new Entry<>(key, value, parent);
	if (cmp < 0)
		parent.left = e;
	else
		parent.right = e;
	// 修改红黑树，左旋或右旋保证弱平衡且符合红黑规则	
	fixAfterInsertion(e);
	size++;
	modCount++;
	return null;
}

leftNo   = parentNo * 2 + 1
rightNo  = parentNo * 2 + 2
parentNo = (nodeNo - 1) / 2

transient Object[] queue;

public boolean offer(E e) {
	if (e == null)
		throw new NullPointerException();
	modCount++;
	int i = size;
	if (i >= queue.length)
		grow(i + 1);	// 扩容
	size = i + 1;
	if (i == 0)	// 如果这是插入的第一个元素
		queue[0] = e;
	else
		siftUp(i, e);	// 调整
	return true;
}

private void siftUpComparable(int k, E x) {
	Comparable<? super E> key = (Comparable<? super E>) x;
	// 从指定位置k开始，将x逐层与当前点的parent进行比较并交换，直到满足 x >= queue[parent]为止
	while (k > 0) {
		// parentNo = (nodeNo-1)/2
		int parent = (k - 1) >>> 1;
		Object e = queue[parent];
		if (key.compareTo((E) e) >= 0)
			break;
		queue[k] = e;
		k = parent;
	}
	queue[k] = key;
}

public E poll() {
	if (size == 0)
		return null;
	int s = --size;
	modCount++;
	E result = (E) queue[0];	// 0下表即最小值，即队首
	E x = (E) queue[s];
	queue[s] = null;
	if (s != 0)
		siftDown(0, x);	// 调整
	return result;
}

private void siftDownUsingComparator(int k, E x) {
	int half = size >>> 1;
	// 从k开始，将x逐层向下与当前点孩子中较小的那个交换，直到x小于或等于孩子中的任何一个为止
	while (k < half) {
		// 首先找到左右孩子中较小的那个，记录到c里，并用child记录其下标
		int child = (k << 1) + 1;	// leftNo = parentNo * 2 + 1
		Object c = queue[child];
		int right = child + 1;
		if (right < size &&
			comparator.compare((E) c, (E) queue[right]) > 0)
			c = queue[child = right];
		if (comparator.compare(x, (E) c) <= 0)
			break;
		/ 然后用c取代原来的值	
		queue[k] = c;
		k = child;
	}
	queue[k] = x;
}

/** Main lock guarding all access */
final ReentrantLock lock;

/** Condition for waiting takes */
private final Condition notEmpty;

/** Condition for waiting puts */
private final Condition notFull;

public void put(E e) throws InterruptedException {
	checkNotNull(e);
	final ReentrantLock lock = this.lock;
	lock.lockInterruptibly();
	try {
		while (count == items.length)
			notFull.await();
		enqueue(e);
	} finally {
		lock.unlock();
	}
}

private void enqueue(E x) {
	// assert lock.getHoldCount() == 1;
	// assert items[putIndex] == null;
	final Object[] items = this.items;
	items[putIndex] = x;
	if (++putIndex == items.length)	// 循环队列
		putIndex = 0;
	count++;
	notEmpty.signal();
}

/** Current number of elements */
private final AtomicInteger count = new AtomicInteger();

/** Lock held by take, poll, etc */
private final ReentrantLock takeLock = new ReentrantLock();

/** Lock held by put, offer, etc */
private final ReentrantLock putLock = new ReentrantLock();

public synchronized E pop() {
	E       obj;
	int     len = size();

	obj = peek();
	// 数组倒着取即可
	removeElementAt(len - 1);

	return obj;
}

final transient ReentrantLock lock = new ReentrantLock();

/** The array, accessed only via getArray/setArray. */
private transient volatile Object[] array;

public boolean add(E e) {
	final ReentrantLock lock = this.lock;
	lock.lock();
	try {
		Object[] elements = getArray();
		int len = elements.length;
		Object[] newElements = Arrays.copyOf(elements, len + 1);
		newElements[len] = e;
		setArray(newElements);
		return true;
	} finally {
		lock.unlock();
	}
}

final V putVal(K key, V value, boolean onlyIfAbsent) {
	if (key == null || value == null) throw new NullPointerException();
	// 获取hash值
	int hash = spread(key.hashCode());
	int binCount = 0;
	for (Node<K,V>[] tab = table;;) {
		Node<K,V> f; int n, i, fh;
		// 如果tab为空，初始化node数组
		if (tab == null || (n = tab.length) == 0)
			tab = initTable();
		// f为空，说明第一次在这个位置插入元素，用CAS插入Node节点	
		else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
			if (casTabAt(tab, i, null,
						 new Node<K,V>(hash, key, value, null)))
				break;                   // no lock when adding to empty bin
		}
		// 如果f的哈希为-1，说明当前f是ForwardingNode节点，表示有其它线程正在扩容，则一起进行扩容操作
		else if ((fh = f.hash) == MOVED)
			tab = helpTransfer(tab, f);
		// 把新的Node节点按链表或红黑树的方式插入到合适的位置	
		else {
			V oldVal = null;
			// 加锁
			synchronized (f) {
				// 插入前再次判断，防止被其他线程修改
				if (tabAt(tab, i) == f) {
					if (fh >= 0) {
						binCount = 1;
						// 遍历链表，找到对应的节点则修改值，否则在队尾加入节点
						for (Node<K,V> e = f;; ++binCount) {
							K ek;
							if (e.hash == hash &&
								((ek = e.key) == key ||
								 (ek != null && key.equals(ek)))) {
								oldVal = e.val;
								if (!onlyIfAbsent)
									e.val = value;
								break;
							}
							Node<K,V> pred = e;
							if ((e = e.next) == null) {
								pred.next = new Node<K,V>(hash, key,
														  value, null);
								break;
							}
						}
					}
					//如果f是TreeBin，说明是红黑树节点，在树上操作
					else if (f instanceof TreeBin) {
						Node<K,V> p;
						binCount = 2;
						if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
													   value)) != null) {
							oldVal = p.val;
							if (!onlyIfAbsent)
								p.val = value;
						}
					}
				}
			}
			if (binCount != 0) {
				// 链条中节点数大于8，则将链表转换为红黑树
				if (binCount >= TREEIFY_THRESHOLD)
					treeifyBin(tab, i);
				if (oldVal != null)
					return oldVal;
				break;
			}
		}
	}
	// 最后进行扩容判断
	addCount(1L, binCount);
	return null;
}

public boolean offer(E e) {
	checkNotNull(e);
	final Node<E> newNode = new Node<E>(e);

	for (Node<E> t = tail, p = t;;) {
		Node<E> q = p.next;
		if (q == null) {
			// p is last node
			if (p.casNext(null, newNode)) {
				// Successful CAS is the linearization point
				// for e to become an element of this queue,
				// and for newNode to become "live".
				if (p != t) // hop two nodes at a time
					casTail(t, newNode);  // Failure is OK.
				return true;
			}
			// Lost CAS race to another thread; re-read next
		}
		else if (p == q)
			// We have fallen off list.  If tail is unchanged, it
			// will also be off-list, in which case we need to
			// jump to head, from which all live nodes are always
			// reachable.  Else the new tail is a better bet.
			p = (t != (t = tail)) ? t : head;
		else
			// Check for tail updates after two hops.
			p = (p != t && t != (t = tail)) ? t : q;
	}
}

public int size() {
	int count = 0;
	for (Node<E> p = first(); p != null; p = succ(p))
		if (p.item != null)
			// Collection.size() spec says to max out
			if (++count == Integer.MAX_VALUE)
				break;
	return count;
}

// src：要复制的数组	srcPos：要复制的数组中的起始位置
// dest：副本数组		destPos：副本数组中的起始位置
// length：要复制的数组元素的数量
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);


public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
	T[] copy = ((Object)newType == (Object)Object[].class)
		? (T[]) new Object[newLength]
		: (T[]) Array.newInstance(newType.getComponentType(), newLength);
	System.arraycopy(original, 0, copy, 0,
					 Math.min(original.length, newLength));
	return copy;
}