能沉淀下来的东西，往往都很基础，整理了下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举例，加入自己的注释的理解：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 //对treeMap的红黑树理解注解. 2017.02.16 by 何锦彬 JDK,1.7.51<br> <br>/** From CLR */ private void fixAfterInsertion(Entry<K, V> x) { //新加入红黑树的默认节点就是红色 x.color = RED; /** * 1. 如为根节点直接跳出 */ while (x != null && x != root && x.parent.color == RED) { if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { //如果X的父节点（P）是其父节点的父节点（G）的左节点 //即 下面这种情况 /** * G * P(RED) U */ //获取其叔(U)节点 Entry<K, V> y = rightOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { // 这种情况，对应下面 图：情况一 /** * G * P(RED) U(RED) * X */ //如果叔节点是红色的（父节点有判断是红色）. 即是双红色，比较好办，通过改变颜色就行. 把P和U都设置成黑色然后,X加到P节点。 G节点当作新加入节点继续迭代 setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else { //处理红父，黑叔的情况 if (x == rightOf(parentOf(x))) { // 这种情况，对应下面 图：情况二 /** * G * P(RED) U(BLACK) * X */ //如果X是右边节点 x = parentOf(x); // 进行左旋 rotateLeft(x); } //左旋后，是这种情况了，对应下面 图：情况三 /** * G * P(RED) U(BLACK) * X */ // 到这，X只能是左节点了，而且P是红色，U是黑色的情况 //把P改成黑色，G改成红色，以G为节点进行右旋 setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateRight(parentOf(parentOf(x))); } } else { //父节点在右边的 /** * G * U P(RED) */ //获取U Entry<K, V> y = leftOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { //红父红叔的情况 /** * G * U(RED) P(RED) */ setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); //把G当作新插入的节点继续进行迭代 x = parentOf(parentOf(x)); } else { //红父黑叔，并且是右父的情况 /** * G * U(RED) P(RED) */ if (x == leftOf(parentOf(x))) { //如果插入的X是左节点 /** * G * U(BLACK) P(RED) * X */ x = parentOf(x); //以P为节点进行右旋 rotateRight(x); } //右旋后 /** * G * U(BLACK) P(RED) * X */ setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); //以G为节点进行左旋 rotateLeft(parentOf(parentOf(x))); } } } //红黑树的根节点始终是黑色 root.color = BLACK; }
其实就是一颗2-3-4树变种，红黑树详情可以看我上一篇
而且JDK8的hashMap链表后，链表的深度超过8也是转换成红黑树的存储，个人是认为转换成红黑树后，hashMap的扩容条件是有问题了，应该加入是否有红黑树的判断
