简栈文化

public class Subject {
 
   private String name; 
   public Subject(String s) { 
      name = s; 
   } 

   public String getName() { 
      return name; 
   } 

   public void setName(String s) { 
      name = s; 
   } 
}

public class Student implements Cloneable { 
 
   // 对象引用 
   private Subject subj; 
   private String name; 
 
   public Student(String s, String sub) { 
      name = s; 
      subj = new Subject(sub); 
   } 
 
   public Subject getSubj() { 
      return subj; 
   } 
 
   public String getName() { 
      return name; 
   } 
 
   public void setName(String s) { 
      name = s; 
   } 
 
   /** 
    *  重写clone()方法 
    * @return 
    */ 
   public Object clone() { 
      //浅拷贝 
      try { 
         // 直接调用父类的clone()方法
         return super.clone(); 
      } catch (CloneNotSupportedException e) { 
         return null; 
      } 
   } 
}

public class CopyDemoMain {
    public static void main(String[] args) {
        // 原始对象
        Student stud = new Student("杨充", "潇湘剑雨");
        System.out.println("原始对象: " + stud.getName() + " - " + stud.getSubj().getName());

        // 拷贝对象
        Student clonedStud = (Student) stud.clone();
        System.out.println("拷贝对象: " + clonedStud.getName() + " - " + clonedStud.getSubj().getName());

        // 原始对象和拷贝对象是否一样：
        System.out.println("原始对象和拷贝对象是否一样: " + (stud == clonedStud));
        // 原始对象和拷贝对象的name属性是否一样
        System.out.println("原始对象和拷贝对象的name属性是否一样: " + (stud.getName() == clonedStud.getName()));
        // 原始对象和拷贝对象的subj属性是否一样
        System.out.println("原始对象和拷贝对象的subj属性是否一样: " + (stud.getSubj() == clonedStud.getSubj()));

        stud.setName("小杨逗比");
        stud.getSubj().setName("潇湘剑雨大侠");
        System.out.println("更新后的原始对象: " + stud.getName() + " - " + stud.getSubj().getName());
        System.out.println("更新原始对象后的克隆对象: " + clonedStud.getName() + " - " + clonedStud.getSubj().getName());
    }
}

public class DeepStudent implements Cloneable {
    // 对象引用 
    private Subject subj;
    private String  name;

    public DeepStudent(String s, String sub) {
        name = s;
        subj = new Subject(sub);
    }

    public Subject getSubj() {
        return subj;
    }

    public String getName() {
        return name;
    }

    public void setName(String s) {
        name = s;
    }

    /**
     * 重写clone()方法
     *
     * @return
     */
    public Object clone() {
        // 深拷贝，创建拷贝类的一个新对象，这样就和原始对象相互独立
        DeepStudent s = new DeepStudent(name, subj.getName());
        return s;
    }
}

public class ColoredCircle implements Serializable { 
 
   private int x; 
   private int y; 
 
   public ColoredCircle(int x, int y) { 
      this.x = x; 
      this.y = y; 
   } 
 
   public int getX() { 
      return x; 
   } 
 
   public void setX(int x) { 
      this.x = x; 
   } 
 
   public int getY() { 
      return y; 
   } 
 
   public void setY(int y) { 
      this.y = y; 
   } 
 
   @Override 
   public String toString() { 
      return "x=" + x + ", y=" + y; 
   } 
}

public class DouBi implements Serializable {

    private static final long serialVersionUID = -8752043194511106066L;

    private int x;
    private int y;

    public DouBi(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public void setX(int x) {
        this.x = x;
    }

    public int getY() {
        return y;
    }

    public void setY(int y) {
        this.y = y;
    }
}

public class CopyDemoMain3 {
    public static void main(String[] args) {
        ObjectOutputStream oos = null;
        ObjectInputStream ois = null;
        try {
            // 创建原始的可序列化对象
            DouBi c1 = new DouBi(100, 100);
            System.out.println("原始的对象 = " + c1);
            DouBi c2 = null;
            // 通过序列化实现深拷贝
            ByteArrayOutputStream bos = new ByteArrayOutputStream();
            oos = new ObjectOutputStream(bos);
            // 序列化以及传递这个对象
            oos.writeObject(c1);
            oos.flush();
            ByteArrayInputStream bin = new ByteArrayInputStream(bos.toByteArray());
            ois = new ObjectInputStream(bin);
            // 返回新的对象
            c2 = (DouBi) ois.readObject();
            // 校验内容是否相同
            System.out.println("复制后的对象   = " + c2);
            // 改变原始对象的内容
            c1.setX(200);
            c1.setY(200);
            // 查看每一个现在的内容
            System.out.println("查看原始的对象 = " + c1);
            System.out.println("查看复制的对象 = " + c2);
        } catch (IOException e) {
            System.out.println("Exception in main = " + e);
        } catch (ClassNotFoundException e) {
            e.printStackTrace();
        } finally {
            if (oos != null) {
                try {
                    oos.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            if (ois != null) {
                try {
                    ois.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
    }
}

public void test4() {
    int[] lNumbers1 = new int[5];
    int[] rNumbers1 = Arrays.copyOf(lNumbers1, lNumbers1.length);
    rNumbers1[0] = 1;
    boolean first = lNumbers1[0] == rNumbers1[0];
    Log.d("小杨逗比", "lNumbers2[0]=" + lNumbers1[0] + ",rNumbers2[0]=" + rNumbers1[0]+"---"+first);

    int[] lNumbers3 = new int[5];
    int[] rNumbers3 = lNumbers3.clone();
    rNumbers3[0] = 1;
    boolean second = lNumbers3[0] == rNumbers3[0];
    Log.d("小杨逗比", "lNumbers3[0]=" + lNumbers3[0] + ",rNumbers3[0]=" + rNumbers3[0]+"---"+second);
}

2019-03-25 14:28:09.907 30316-30316/org.yczbj.ycrefreshview D/小杨逗比: lNumbers2[0]=0,rNumbers2[0]=1---false
2019-03-25 14:28:09.907 30316-30316/org.yczbj.ycrefreshview D/小杨逗比: lNumbers3[0]=0,rNumbers3[0]=1---false

public static void test5() {
    People[] lNumbers1 = new People[5];
    lNumbers1[0] = new People();
    People[] rNumbers1 = lNumbers1;
    boolean first = lNumbers1[0].equals(rNumbers1[0]);
    Log.d("小杨逗比", "lNumbers1[0]=" + lNumbers1[0] + ",rNumbers1[0]=" + rNumbers1[0]+"--"+first);

    People[] lNumbers2 = new People[5];
    lNumbers2[0] = new People();
    People[] rNumbers2 = Arrays.copyOf(lNumbers2, lNumbers2.length);
    boolean second = lNumbers2[0].equals(rNumbers2[0]);
    Log.d("小杨逗比", "lNumbers2[0]=" + lNumbers2[0] + ",rNumbers2[0]=" + rNumbers2[0]+"--"+second);

    People[] lNumbers3 = new People[5];
    lNumbers3[0] = new People();
    People[] rNumbers3 = lNumbers3.clone();
    boolean third = lNumbers3[0].equals(rNumbers3[0]);
    Log.d("小杨逗比", "lNumbers3[0]=" + lNumbers3[0] + ",rNumbers3[0]=" + rNumbers3[0]+"--"+third);
}

public static class People implements Cloneable {

    int age;
    Holder holder;

    @Override
    protected Object clone() {
        try {
            return super.clone();
        } catch (CloneNotSupportedException e) {
            e.printStackTrace();
        }
        return null;
    }

    public static class Holder {
        int holderValue;
    }
}

2019-03-25 14:53:17.054 31093-31093/org.yczbj.ycrefreshview D/小杨逗比: lNumbers1[0]=org.yczbj.ycrefreshview.MainActivity$People@46a2c18,rNumbers1[0]=org.yczbj.ycrefreshview.MainActivity$People@46a2c18--true
2019-03-25 14:53:17.054 31093-31093/org.yczbj.ycrefreshview D/小杨逗比: lNumbers2[0]=org.yczbj.ycrefreshview.MainActivity$People@d344671,rNumbers2[0]=org.yczbj.ycrefreshview.MainActivity$People@d344671--true
2019-03-25 14:53:17.054 31093-31093/org.yczbj.ycrefreshview D/小杨逗比: lNumbers3[0]=org.yczbj.ycrefreshview.MainActivity$People@91e9c56,rNumbers3[0]=org.yczbj.ycrefreshview.MainActivity$People@91e9c56--true

public static void test6() {
    ArrayList<People> lPeoples = new ArrayList<>();
    People people1 = new People();
    lPeoples.add(people1);
    Log.d("小杨逗比", "lPeoples[0]=" + lPeoples.get(0));
    ArrayList<People> rPeoples = (ArrayList<People>) lPeoples.clone();
    Log.d("小杨逗比", "rPeoples[0]=" + rPeoples.get(0));
    boolean b = lPeoples.get(0).equals(rPeoples.get(0));
    Log.d("小杨逗比", "比较两个对象" + b);
}

public static class People implements Cloneable {

    int age;
    Holder holder;

    @Override
    protected Object clone() {
        try {
            People people = (People) super.clone();
            people.holder = (People.Holder) this.holder.clone();
            return people;
        } catch (CloneNotSupportedException e) {
            e.printStackTrace();
        }
        return null;
    }

    public static class Holder implements Cloneable {

        int holderValue;

        @Override
        protected Object clone() {
            try {
                return super.clone();
            } catch (CloneNotSupportedException e) {
                e.printStackTrace();
            }
            return null;
        }
    }
}

public static void test7() {
    ArrayList<People> lPeoples = new ArrayList<>();
    People people1 = new People();
    people1.holder = new People.Holder();
    lPeoples.add(people1);
    Log.d("小杨逗比", "lPeoples[0]=" + lPeoples.get(0));
    ArrayList<People> rPeoples = new ArrayList<>();
    for (People people : lPeoples) {
        rPeoples.add((People) people.clone());
    }
    Log.d("小杨逗比", "rPeoples[0]=" + rPeoples.get(0));
    boolean b = lPeoples.get(0).equals(rPeoples.get(0));
    Log.d("小杨逗比", "比较两个对象" + b);
}

public static class People implements Cloneable {

    int age;
    Holder holder;

    @Override
    protected Object clone() {
        try {
            People people = (People) super.clone();
            people.holder = (People.Holder) this.holder.clone();
            return people;
        } catch (CloneNotSupportedException e) {
            e.printStackTrace();
        }
        return null;
    }

    public static class Holder implements Cloneable {

        int holderValue;

        @Override
        protected Object clone() {
            try {
                return super.clone();
            } catch (CloneNotSupportedException e) {
                e.printStackTrace();
            }
            return null;
        }
    }
}

public static Unsafe getUnsafe() {
    Class cc = sun.reflect.Reflection.getCallerClass(2);
    if (cc.getClassLoader() != null)
        throw new SecurityException("Unsafe");
    return theUnsafe;
}

java -Xbootclasspath:/usr/jdk1.7.0/jre/lib/rt.jar:. com.mishadoff.magic.UnsafeClient

Field f = Unsafe.class.getDeclaredField("theUnsafe");
f.setAccessible(true);
Unsafe unsafe = (Unsafe) f.get(null);

Preferences -> Java -> Compiler -> Errors/Warnings ->
Deprecated and restricted API -> Forbidden reference -> Warning           

class A {
    private long a; // not initialized value

    public A() {
        this.a = 1; // initialization
    }

    public long a() { return this.a; }
}

A o1 = new A(); // constructor
o1.a(); // prints 1

A o2 = A.class.newInstance(); // reflection
o2.a(); // prints 1

A o3 = (A) unsafe.allocateInstance(A.class); // unsafe
o3.a(); // prints 0

class Guard {
    private int ACCESS_ALLOWED = 1;

    public boolean giveAccess() {
        return 42 == ACCESS_ALLOWED;
    }
}

Guard guard = new Guard();
guard.giveAccess();   // false, no access

// bypass
Unsafe unsafe = getUnsafe();
Field f = guard.getClass().getDeclaredField("ACCESS_ALLOWED");
unsafe.putInt(guard, unsafe.objectFieldOffset(f), 42); // memory corruption

guard.giveAccess(); // true, access granted

unsafe.putInt(guard, 16 + unsafe.objectFieldOffset(f), 42); // memory corruption

public static long sizeOf(Object o) {
    Unsafe u = getUnsafe();
    HashSet<Field> fields = new HashSet<Field>();
    Class c = o.getClass();
    while (c != Object.class) {
        for (Field f : c.getDeclaredFields()) {
            if ((f.getModifiers() & Modifier.STATIC) == 0) {
                fields.add(f);
            }
        }
        c = c.getSuperclass();
    }

    // get offset
    long maxSize = 0;
    for (Field f : fields) {
        long offset = u.objectFieldOffset(f);
        if (offset > maxSize) {
            maxSize = offset;
        }
    }

    return ((maxSize/8) + 1) * 8;   // padding
}

public static long sizeOf(Object object){
    return getUnsafe().getAddress(
        normalize(getUnsafe().getInt(object, 4L)) + 12L);
}

private static long normalize(int value) {
    if(value >= 0) return value;
    return (~0L >>> 32) & value;
}

static Object shallowCopy(Object obj) {
    long size = sizeOf(obj);
    long start = toAddress(obj);
    long address = getUnsafe().allocateMemory(size);
    getUnsafe().copyMemory(start, address, size);
    return fromAddress(address);
}

static long toAddress(Object obj) {
    Object[] array = new Object[] {obj};
    long baseOffset = getUnsafe().arrayBaseOffset(Object[].class);
    return normalize(getUnsafe().getInt(array, baseOffset));
}

static Object fromAddress(long address) {
    Object[] array = new Object[] {null};
    long baseOffset = getUnsafe().arrayBaseOffset(Object[].class);
    getUnsafe().putLong(array, baseOffset, address);
    return array[0];
}

String password = new String("l00k@myHor$e");
String fake = new String(password.replaceAll(".", "?"));
System.out.println(password); // l00k@myHor$e
System.out.println(fake); // ????????????

getUnsafe().copyMemory(
          fake, 0L, null, toAddress(password), sizeOf(password));

System.out.println(password); // ????????????
System.out.println(fake); // ????????????

Field stringValue = String.class.getDeclaredField("value");
stringValue.setAccessible(true);
char[] mem = (char[]) stringValue.get(password);
for (int i=0; i < mem.length; i++) {
  mem[i] = '?';
}

long intClassAddress = normalize(getUnsafe().getInt(new Integer(0), 4L));
long strClassAddress = normalize(getUnsafe().getInt("", 4L));
getUnsafe().putAddress(intClassAddress + 36, strClassAddress);

(String) (Object) (new Integer(666))

byte[] classContents = getClassContent();
Class c = getUnsafe().defineClass(
              null, classContents, 0, classContents.length);
    c.getMethod("a").invoke(c.newInstance(), null); // 1

private static byte[] getClassContent() throws Exception {
    File f = new File("/home/mishadoff/tmp/A.class");
    FileInputStream input = new FileInputStream(f);
    byte[] content = new byte[(int)f.length()];
    input.read(content);
    input.close();
    return content;
}

getUnsafe().throwException(new IOException());

class SuperArray {
    private final static int BYTE = 1;

    private long size;
    private long address;

    public SuperArray(long size) {
        this.size = size;
        address = getUnsafe().allocateMemory(size * BYTE);
    }

    public void set(long i, byte value) {
        getUnsafe().putByte(address + i * BYTE, value);
    }

    public int get(long idx) {
        return getUnsafe().getByte(address + idx * BYTE);
    }

    public long size() {
        return size;
    }
}

long SUPER_SIZE = (long)Integer.MAX_VALUE * 2;
SuperArray array = new SuperArray(SUPER_SIZE);
System.out.println("Array size:" + array.size()); // 4294967294
for (int i = 0; i < 100; i++) {
    array.set((long)Integer.MAX_VALUE + i, (byte)3);
    sum += array.get((long)Integer.MAX_VALUE + i);
}
System.out.println("Sum of 100 elements:" + sum);  // 300

interface Counter {
    void increment();
    long getCounter();
}

class CounterClient implements Runnable {
    private Counter c;
    private int num;

    public CounterClient(Counter c, int num) {
        this.c = c;
        this.num = num;
    }

    @Override
    public void run() {
        for (int i = 0; i < num; i++) {
            c.increment();
        }
    }
}

int NUM_OF_THREADS = 1000;
int NUM_OF_INCREMENTS = 100000;
ExecutorService service = Executors.newFixedThreadPool(NUM_OF_THREADS);
Counter counter = ... // creating instance of specific counter
long before = System.currentTimeMillis();
for (int i = 0; i < NUM_OF_THREADS; i++) {
    service.submit(new CounterClient(counter, NUM_OF_INCREMENTS));
}
service.shutdown();
service.awaitTermination(1, TimeUnit.MINUTES);
long after = System.currentTimeMillis();
System.out.println("Counter result: " + c.getCounter());
System.out.println("Time passed in ms:" + (after - before));

class StupidCounter implements Counter {
    private long counter = 0;

    @Override
    public void increment() {
        counter++;
    }

    @Override
    public long getCounter() {
        return counter;
    }
}

Counter result: 99542945
Time passed in ms: 679

class SyncCounter implements Counter {
    private long counter = 0;

    @Override
    public synchronized void increment() {
        counter++;
    }

    @Override
    public long getCounter() {
        return counter;
    }
}

Counter result: 100000000
Time passed in ms: 10136

class LockCounter implements Counter {
    private long counter = 0;
    private WriteLock lock = new ReentrantReadWriteLock().writeLock();

    @Override
    public void increment() {
        lock.lock();
        counter++;
        lock.unlock();
    }

    @Override
    public long getCounter() {
        return counter;
    }
}

Counter result: 100000000
Time passed in ms: 8065

class AtomicCounter implements Counter {
    AtomicLong counter = new AtomicLong(0);

    @Override
    public void increment() {
        counter.incrementAndGet();
    }

    @Override
    public long getCounter() {
        return counter.get();
    }
}

Counter result: 100000000
Time passed in ms: 6552

class CASCounter implements Counter {
    private volatile long counter = 0;
    private Unsafe unsafe;
    private long offset;

    public CASCounter() throws Exception {
        unsafe = getUnsafe();
        offset = unsafe.objectFieldOffset(CASCounter.class.getDeclaredField("counter"));
    }

    @Override
    public void increment() {
        long before = counter;
        while (!unsafe.compareAndSwapLong(this, offset, before, before + 1)) {
            before = counter;
        }
    }

    @Override
    public long getCounter() {
        return counter;
    }
}

Counter result: 100000000
Time passed in ms: 6454

//线程1
boolean stop = false;
while (!stop) {
    do();
} 

//线程2
stop = true;

//线程1
volatile boolean stop = false;
while (!stop) {
    do();
} 

//线程2
stop = true;

double pi = 3.14;  //A
double r = 1;     //B
double s = pi * r * r; //C

double pi = 3.14;
double r = 0;
double s = 0;
boolean start = false;
//线程1
r = 10; //A
start = true; //B

//线程2
if (start) {  //C
    s = pi * r * r;  //D
}

double pi = 3.14;
double r = 0;
double s = 0;
volatile boolean start = false;
//线程1
r = 10; //A
start = true; //B

//线程2
if (start) {  //C
    s = pi * r * r;  //D
}

public class Test {
    public volatile int inc = 0;
     
    public void increase() {
        inc++;
    }
     
    public static void main(String[] args) {
        final Test test = new Test();
        for(int i=0;i<10;i++){
            new Thread(){
                public void run() {
                    for(int j=0;j<1000;j++)
                        test.increase();
                };
            }.start();
        }
         
        while(Thread.activeCount()>1)  //保证前面的线程都执行完
            Thread.yield();
        System.out.println(test.inc);
    }
}

  Node<K,V> loHead = null, loTail = null;
  Node<K,V> hiHead = null, hiTail = null;
  Node<K,V> next;
  do {
      next = e.next;
      if ((e.hash & oldCap) == 0) {
          if (loTail == null)
              loHead = e;
          else
              loTail.next = e;
          loTail = e;
      }
      else {
          if (hiTail == null)
              hiHead = e;
          else
              hiTail.next = e;
          hiTail = e;
      }
  } while ((e = next) != null);
  if (loTail != null) {
      loTail.next = null;
      newTab[j] = loHead;
  }
  if (hiTail != null) {
      hiTail.next = null;
      newTab[j + oldCap] = hiHead;
}

static class Node implements Map.Entry {
    //哈希值，就是位置
    final int hash;
    //键
    final K key;
    //值
    V value;
    //指向下一个几点的指针
    Node next;
    //...
}

static final class TreeNode extends LinkedHashMap.Entry {
    TreeNode parent;  // red-black tree links
    TreeNode left;
    TreeNode right;
    TreeNode prev;    // needed to unlink next upon deletion
    boolean red;
}

//继承 LinkedHashMap.Entry 的
Entry before, after;

//HashMap.Node 的
final int hash;
final K key;
V value;
Node next;

//一个桶的树化阈值
//当桶中元素个数超过这个值时，需要使用红黑树节点替换链表节点
//这个值必须为 8，要不然频繁转换效率也不高
static final int TREEIFY_THRESHOLD = 8;

//一个树的链表还原阈值
//当扩容时，桶中元素个数小于这个值，就会把树形的桶元素 还原（切分）为链表结构
//这个值应该比上面那个小，至少为 6，避免频繁转换
static final int UNTREEIFY_THRESHOLD = 6;

//哈希表的最小树形化容量
//当哈希表中的容量大于这个值时，表中的桶才能进行树形化
//否则桶内元素太多时会扩容，而不是树形化
//为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;

//将桶内所有的 链表节点 替换成 红黑树节点
final void treeifyBin(Node[] tab, int hash) {
    int n, index; Node e;
    //如果当前哈希表为空，或者哈希表中元素的个数小于 进行树形化的阈值(默认为 64)，就去新建/扩容
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        //如果哈希表中的元素个数超过了 树形化阈值，进行树形化
        // e 是哈希表中指定位置桶里的链表节点，从第一个开始
        TreeNode hd = null, tl = null; //红黑树的头、尾节点
        do {
            //新建一个树形节点，内容和当前链表节点 e 一致
            TreeNode p = replacementTreeNode(e, null);
            if (tl == null) //确定树头节点
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);  
        //让桶的第一个元素指向新建的红黑树头结点，以后这个桶里的元素就是红黑树而不是链表了
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}


    TreeNode replacementTreeNode(Node p, Node next) {
    return new TreeNode<>(p.hash, p.key, p.value, next);
}

   final void treeify(Node[] tab) {
    TreeNode root = null;
    for (TreeNode x = this, next; x != null; x = next) {
        next = (TreeNode)x.next;
        x.left = x.right = null;
        if (root == null) { //头回进入循环，确定头结点，为黑色
            x.parent = null;
            x.red = false;
            root = x;
        }
        else {  //后面进入循环走的逻辑，x 指向树中的某个节点
            K k = x.key;
            int h = x.hash;
            Class kc = null;
            //又一个循环，从根节点开始，遍历所有节点跟当前节点 x 比较，调整位置，有点像冒泡排序
            for (TreeNode p = root;;) {
                int dir, ph;        //这个 dir 
                K pk = p.key;
                if ((ph = p.hash) > h)  //当比较节点的哈希值比 x 大时， dir 为 -1
                    dir = -1;
                else if (ph < h)  //哈希值比 x 小时 dir 为 1
                    dir = 1;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    // 如果比较节点的哈希值、 x 
                    dir = tieBreakOrder(k, pk);

                    //把 当前节点变成 x 的父亲
                    //如果当前比较节点的哈希值比 x 大，x 就是左孩子，否则 x 是右孩子 
                TreeNode xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    moveRootToFront(tab, root);
}

final TreeNode putTreeVal(HashMap map, Node[] tab,
                               int h, K k, V v) {
    Class kc = null;
    boolean searched = false;
    TreeNode root = (parent != null) ? root() : this;
    //每次添加元素时，从根节点遍历，对比哈希值
    for (TreeNode p = root;;) {
        int dir, ph; K pk;
        if ((ph = p.hash) > h)
            dir = -1;
        else if (ph < h)
            dir = 1;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))  
        //如果当前节点的哈希值、键和要添加的都一致，就返回当前节点（奇怪，不对比值吗？）
            return p;
        else if ((kc == null &&
                  (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            //如果当前节点和要添加的节点哈希值相等，但是两个节点的键不是一个类，只好去挨个对比左右孩子 
            if (!searched) {
                TreeNode q, ch;
                searched = true;
                if (((ch = p.left) != null &&
                     (q = ch.find(h, k, kc)) != null) ||
                    ((ch = p.right) != null &&
                     (q = ch.find(h, k, kc)) != null))
                    //如果从 ch 所在子树中可以找到要添加的节点，就直接返回
                    return q;
            }
            //哈希值相等，但键无法比较，只好通过特殊的方法给个结果
            dir = tieBreakOrder(k, pk);
        }

        //经过前面的计算，得到了当前节点和要插入节点的一个大小关系
        //要插入的节点比当前节点小就插到左子树，大就插到右子树
        TreeNode xp = p;
     //这里有个判断，如果当前节点还没有左孩子或者右孩子时才能插入，否则就进入下一轮循环 
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            Node xpn = xp.next;
            TreeNode x = map.newTreeNode(h, k, v, xpn);
            if (dir <= 0)
                xp.left = x;
            else
                xp.right = x;
            xp.next = x;
            x.parent = x.prev = xp;
            if (xpn != null)
                ((TreeNode)xpn).prev = x;
            //红黑树中，插入元素后必要的平衡调整操作
            moveRootToFront(tab, balanceInsertion(root, x));
            return null;
        }
    }
}

//这个方法用于 a 和 b 哈希值相同但是无法比较时，直接根据两个引用的地址进行比较
//这里源码注释也说了，这个树里不要求完全有序，只要插入时使用相同的规则保持平衡即可
 static int tieBreakOrder(Object a, Object b) {
    int d;
    if (a == null || b == null ||
        (d = a.getClass().getName().
         compareTo(b.getClass().getName())) == 0)
        d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
             -1 : 1);
    return d;
}

public V get(Object key) {
    Node e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node getNode(int hash, Object key) {
    Node[] tab; Node first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

final TreeNode getTreeNode(int h, Object k) {
    return ((parent != null) ? root() : this).find(h, k, null);
}

//从根节点根据 哈希值和 key 进行查找
final TreeNode find(int h, Object k, Class kc) {
    TreeNode p = this;
    do {
        int ph, dir; K pk;
        TreeNode pl = p.left, pr = p.right, q;
        if ((ph = p.hash) > h)
            p = pl;
        else if (ph < h)
            p = pr;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        else if (pl == null)
            p = pr;
        else if (pr == null)
            p = pl;
        else if ((kc != null ||
                  (kc = comparableClassFor(k)) != null) &&
                 (dir = compareComparables(kc, k, pk)) != 0)
            p = (dir < 0) ? pl : pr;
        else if ((q = pr.find(h, k, kc)) != null)
            return q;
        else
            p = pl;
    } while (p != null);
    return null;
}

//参数介绍
//tab 表示保存桶头结点的哈希表
//index 表示从哪个位置开始修剪
//bit 要修剪的位数（哈希值）
final void split(HashMap map, Node[] tab, int index, int bit) {
    TreeNode b = this;
    // Relink into lo and hi lists, preserving order
    TreeNode loHead = null, loTail = null;
    TreeNode hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    for (TreeNode e = b, next; e != null; e = next) {
        next = (TreeNode)e.next;
        e.next = null;
        //如果当前节点哈希值的最后一位等于要修剪的 bit 值
        if ((e.hash & bit) == 0) {
                //就把当前节点放到 lXXX 树中
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            //然后 loTail 记录 e
            loTail = e;
            //记录 lXXX 树的节点数量
            ++lc;
        }
        else {  //如果当前节点哈希值最后一位不是要修剪的
                //就把当前节点放到 hXXX 树中
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            //记录 hXXX 树的节点数量
            ++hc;
        }
    }


    if (loHead != null) {
        //如果 lXXX 树的数量小于 6，就把 lXXX 树的枝枝叶叶都置为空，变成一个单节点
        //然后让这个桶中，要还原索引位置开始往后的结点都变成还原成链表的 lXXX 节点
        //这一段元素以后就是一个链表结构
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
        else {
        //否则让索引位置的结点指向 lXXX 树，这个树被修剪过，元素少了
            tab[index] = loHead;
            if (hiHead != null) // (else is already treeified)
                loHead.treeify(tab);
        }
    }
    if (hiHead != null) {
        //同理，让 指定位置 index + bit 之后的元素
        //指向 hXXX 还原成链表或者修剪过的树
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}

com.alibaba.dubbo.rpc.cluster.LoadBalance 
接口提供了
<T> Invoker<T> select(List<Invoker<T>> invokers, URL url, Invocation invocation) throws RpcException; 
通过该方法，进行结点选择。

com.alibaba.dubbo.rpc.cluster.loadbalance.AbstractLoadBalance 
实现了一些公共方法，并定义抽象方法
protected abstract <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation); 
该方法由具体的负载均衡实现类去实现。