Java从同步容器到并发容器的操作过程

//Vector
public synchronized int size() {};
public synchronized E get(int index) {};
//HashTable 
public synchronized V put(K key, V value) {};
public synchronized V remove(Object key) {};

public static void deleteVector(){
 int index = vectors.size() - 1;
 vectors.remove(index);
}

public static void deleteVector(){
 synchronized (vectors) {
  int index = vectors.size() - 1;
  vectors.remove(index);
 }
}

public static void foreachVector(){
 synchronized (vectors) {
  for (int i = 0; i < vectors.size(); i++) {
   System.out.println(vectors.get(i).toString());
  }
 }
}

//添加元素
public boolean add(E e) {
 //独占锁
 final ReentrantLock lock = this.lock;
 lock.lock();
 try {
  Object[] elements = getArray();
  int len = elements.length;
  //复制一个新的数组newElements
  Object[] newElements = Arrays.copyOf(elements, len + 1);
  newElements[len] = e;
  //修改后指向新的数组
  setArray(newElements);
  return true;
 } finally {
  lock.unlock();
 }
}
public E get(int index) {
 //未加锁，直接获取
 return get(getArray(), index);
}

final V putVal(K key, V value, boolean onlyIfAbsent) {
 if (key == null || value == null) throw new NullPointerException();
 int hash = spread(key.hashCode()); //计算桶的hash值
 int binCount = 0;
 //循环插入元素，避免并发插入失败
 for (Node[] tab = table;;) {
  Node f; int n, i, fh;
  if (tab == null || (n = tab.length) == 0)
   tab = initTable();
  else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
   //如果当前桶无元素，则通过cas操作插入新节点
   if (casTabAt(tab, i, null,
       new Node(hash, key, value, null)))
    break;     
  }
  //如果当前桶正在扩容，则协助扩容
  else if ((fh = f.hash) == MOVED)
   tab = helpTransfer(tab, f);
  else {
   V oldVal = null;
   //hash冲突时锁住当前需要添加节点的头元素，可能是链表头节点或者红黑树的根节点
   synchronized (f) { 
    if (tabAt(tab, i) == f) {
     if (fh >= 0) {
      binCount = 1;
      for (Node 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 pred = e;
       if ((e = e.next) == null) {
        pred.next = new Node(hash, key,
               value, null);
        break;
       }
      }
     }
     else if (f instanceof TreeBin) {
      Node p;
      binCount = 2;
      if ((p = ((TreeBin)f).putTreeVal(hash, key,
              value)) != null) {
       oldVal = p.val;
       if (!onlyIfAbsent)
        p.val = value;
      }
     }
    }
   }
   if (binCount != 0) {
    if (binCount >= TREEIFY_THRESHOLD)
     treeifyBin(tab, i);
    if (oldVal != null)
     return oldVal;
    break;
   }
  }
 }
 addCount(1L, binCount);
 return null;
}

int random_level() { 
 K = 1; 
 while (random(0,1)) 
  K++; 
 
 return K; 
} 

private V doPut(K key, V value, boolean onlyIfAbsent) {
 Node z;    // added node
 if (key == null)
  throw new NullPointerException();
 Comparator<? super K> cmp = comparator;
 outer: for (;;) {
  for (Node b = findPredecessor(key, cmp), n = b.next;;) { //查找前继节点
   if (n != null) { //查找到前继节点
    Object v; int c;
    Node f = n.next; //获取后继节点的后继节点
    if (n != b.next) //发生竞争，两次节点获取不一致，并发导致
     break;
    if ((v = n.value) == null) { // 节点已经被删除
     n.helpDelete(b, f);
     break;
    }
    if (b.value == null || v == n) 
     break;
    if ((c = cpr(cmp, key, n.key)) > 0) { //进行下一轮查找，比当前key大
     b = n;
     n = f;
     continue;
    }
    if (c == 0) { //相等时直接cas修改值
     if (onlyIfAbsent || n.casValue(v, value)) {
      @SuppressWarnings("unchecked") V vv = (V)v;
      return vv;
     }
     break; // restart if lost race to replace value
    }
    // else c < 0; fall through
   }
   z = new Node(key, value, n); //9. n.key > key > b.key
   if (!b.casNext(n, z)) //cas修改值 
    break;   // restart if lost race to append to b
   break outer;
  }
 }
 int rnd = ThreadLocalRandom.nextSecondarySeed(); //获取随机数
 if ((rnd & 0x80000001) == 0) { // test highest and lowest bits
  int level = 1, max;
  while (((rnd >>>= 1) & 1) != 0) // 获取跳表层级
   ++level;
  Index idx = null;
  HeadIndex h = head;
  if (level <= (max = h.level)) { //如果获取的调表层级小于等于当前最大层级，则直接添加，并将它们组成一个上下的链表
   for (int i = 1; i <= level; ++i)
    idx = new Index(z, idx, null);
  }
  else { // try to grow by one level //否则增加一层level，在这里体现为Index数组
   level = max + 1; // hold in array and later pick the one to use
   @SuppressWarnings("unchecked")Index[] idxs =
    (Index[])new Index<?,?>[level+1];
   for (int i = 1; i <= level; ++i)
    idxs[i] = idx = new Index(z, idx, null);
   for (;;) {
    h = head;
    int oldLevel = h.level;
    if (level <= oldLevel) // lost race to add level
     break;
    HeadIndex newh = h;
    Node oldbase = h.node;
    for (int j = oldLevel+1; j <= level; ++j) //新添加的level层的具体数据
     newh = new HeadIndex(oldbase, newh, idxs[j], j);
    if (casHead(h, newh)) {
     h = newh;
     idx = idxs[level = oldLevel];
     break;
    }
   }
  }
  // 逐层插入数据过程
  splice: for (int insertionLevel = level;;) {
   int j = h.level;
   for (Index q = h, r = q.right, t = idx;;) {
    if (q == null || t == null)
     break splice;
    if (r != null) {
     Node n = r.node;
     // compare before deletion check avoids needing recheck
     int c = cpr(cmp, key, n.key);
     if (n.value == null) {
      if (!q.unlink(r))
       break;
      r = q.right;
      continue;
     }
     if (c > 0) {
      q = r;
      r = r.right;
      continue;
     }
    }
    if (j == insertionLevel) {
     if (!q.link(r, t))
      break; // restart
     if (t.node.value == null) {
      findNode(key);
      break splice;
     }
     if (--insertionLevel == 0)
      break splice;
    }
    if (--j >= insertionLevel && j < level)
     t = t.down;
    q = q.down;
    r = q.right;
   }
  }
 }
 return null;
}