Java中各种数据结构如何实现和扩容？
摘要：能沉淀下来的东西，往往都很基础，整理了下JAVA中遇到的数据结构 目录大纲： 到目前接触到的 有几个说明： 可扩容数组 ArrayList 扩容数组的实现, 满了后扩容，扩容在1.5倍，通过copy过来，无扩容因子
能沉淀下来的东西，往往都很基础，整理了下JAVA中遇到的数据结构
目录大纲：
到目前接触到的
有几个说明：
可扩容数组
ArrayList扩容数组的实现, 满了后扩容，扩容在1.5倍，通过copy过来，无扩容因子
int newCapacity = oldCapacity + (oldCapacity >> 1);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
可扩容的数组链表
数组链表的扩容实现：
以HashMap为例子， 当链表深度过长，或生产个新的数组链表进行copy
注意：
扩容过程中容易出现死链，下面是死链的个演示：
扩容前
[ 1 ] [ 2 ] [ 3 ] [ 空]
5 10
第一个线程扩容后，数组链表如下
[ 1 ] [ 10 ] [3] [] [] [] []
2
第二个线程又把从头把2指向10，然后2和10形成了个死循环
扩容代码
//对HashMap死链理解的注解 . 2017.02.17 by 何锦彬 JDK,1.7.51
void transfer(Entry[] newTable, boolean rehash) {
//获取新table的容量
int newCapacity = newTable.length;
//迭代以前的数组
for (Entry<K,V> e : table) {
//如果数组上有元素
while(null != e) {
// 赋值next
Entry<K,V> next = e.next;
//获取e在新的table里的位置
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
//把e指向当前的新数组里的第一个元素，这里会并发了，如果在这断点等待下个线程过来，就会死循环，尝试下
e.next = newTable[i];
//替代新数组的位置
newTable[i] = e;
e = next;
}
}
}
栈
stack栈的实现 ，基于数组继承自Vector(故线程安全)：
获取peek()：get(len-1)
出栈 pop()： 从数组最大坐标开始取出，peek(len-1) , 然后remove
入栈 push(o) : add(o)
阻塞队列
阻塞队列的实现：
基于数组和单向链表
获取：peek()，
实现：重入锁保证线程安全，peek()，从顶部获取
阻塞入队：put(o)，
实现： 重入锁保证线程安全，通过Condition阻塞，无超时，支持Interrupt
带超时阻塞入队： offer(o,timeout, tmeUnit),
实现： 重入锁保证线程安全，通过Condition阻塞，condition方法，awaitNanos(纳秒)，支持Interrupt
其它注意点：
当前数组的大小: AtomicInteger计算，用CAS保证同步，记得ReentrantLock必须是全局变量，局部的话，每次锁的对象是this.
红黑树：
红黑树的实现，TreeMap举例，加入自己的注释的理解：
//对treeMap的红黑树理解注解. 2017.02.16 by 何锦彬 JDK,1.7.51<br> <br>/** From CLR */
private void fixAfterInsertion(Entry<K, V> x) {
//新加入红黑