//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;
  //復(fù)制一個新的數(shù)組newElements
  Object[] newElements = Arrays.copyOf(elements, len + 1);
  newElements[len] = e;
  //修改后指向新的數(shù)組
  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;
 //循環(huán)插入元素，避免并發(fā)插入失敗
 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) {
   //如果當(dāng)前桶無元素，則通過cas操作插入新節(jié)點
   if (casTabAt(tab, i, null,
       new Node<K,V>(hash, key, value, null)))
    break;     
  }
  //如果當(dāng)前桶正在擴容，則協(xié)助擴容
  else if ((fh = f.hash) == MOVED)
   tab = helpTransfer(tab, f);
  else {
   V oldVal = null;
   //hash沖突時鎖住當(dāng)前需要添加節(jié)點的頭元素，可能是鏈表頭節(jié)點或者紅黑樹的根節(jié)點
   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;;) { //查找前繼節(jié)點
   if (n != null) { //查找到前繼節(jié)點
    Object v; int c;
    Node<K,V> f = n.next; //獲取后繼節(jié)點的后繼節(jié)點
    if (n != b.next) //發(fā)生競爭，兩次節(jié)點獲取不一致，并發(fā)導(dǎo)致
     break;
    if ((v = n.value) == null) { // 節(jié)點已經(jīng)被刪除
     n.helpDelete(b, f);
     break;
    }
    if (b.value == null || v == n) 
     break;
    if ((c = cpr(cmp, key, n.key)) > 0) { //進行下一輪查找，比當(dāng)前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(); //獲取隨機數(shù)
 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)) { //如果獲取的調(diào)表層級小于等于當(dāng)前最大層級，則直接添加，并將它們組成一個上下的鏈表
   for (int i = 1; i <= level; ++i)
    idx = new Index<K,V>(z, idx, null);
  }
  else { // try to grow by one level //否則增加一層level，在這里體現(xiàn)為Index<K,V>數(shù)組
   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層的具體數(shù)據(jù)
     newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j);
    if (casHead(h, newh)) {
     h = newh;
     idx = idxs[level = oldLevel];
     break;
    }
   }
  }
  // 逐層插入數(shù)據(jù)過程
  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;
}