[Java] 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<k,v>[] tab = table;;) {
  node<k,v> 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<k,v>(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<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;
     }
    }
   }
   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) {
  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<k,v> z;  // added node
 if (key == null)
  throw new nullpointerexception();
 comparator<? super k> cmp = comparator;
 outer: for (;;) {
  for (node<k,v> b = findpredecessor(key, cmp), n = b.next;;) { //查找前继节点
   if (n != null) { //查找到前继节点
  object v; int c;
  node<k,v> 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<k,v>(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<k,v> idx = null;
  headindex<k,v> h = head;
  if (level <= (max = h.level)) { //如果获取的调表层级小于等于当前最大层级，则直接添加，并将它们组成一个上下的链表
   for (int i = 1; i <= level; ++i)
  idx = new index<k,v>(z, idx, null);
  }
  else { // try to grow by one level //否则增加一层level，在这里体现为index<k,v>数组
   level = max + 1; // hold in array and later pick the one to use
   @suppresswarnings("unchecked")index<k,v>[] idxs =
  (index<k,v>[])new index<?,?>[level+1];
   for (int i = 1; i <= level; ++i)
  idxs[i] = idx = new index<k,v>(z, idx, null);
   for (;;) {
  h = head;
  int oldlevel = h.level;
  if (level <= oldlevel) // lost race to add level
   break;
  headindex<k,v> newh = h;
  node<k,v> oldbase = h.node;
  for (int j = oldlevel+1; j <= level; ++j) //新添加的level层的具体数据
   newh = new headindex<k,v>(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<k,v> q = h, r = q.right, t = idx;;) {
  if (q == null || t == null)
   break splice;
  if (r != null) {
   node<k,v> 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;
}