邱永臣叫西门追雪

JUnit4整合Spring出现的包不兼容问题

Posted on 2016-05-29

Symbols count in article: 3.3k | Reading time ≈ 6 mins.

在创建“物业报修系统”项目时，我第一次尝试使用了Maven来创建（基于InteliJ IDEA），在配置Spring的依赖时，手动逐个import各个包，结果在启动JUnit4单元测试时出现以下错误：

java.lang.NoSuchMethodError: org.springframework.core.annotation.AnnotationUtils.isInJavaLangAnnotationPackage(Ljava/lang/annotation/Annotation;)Z

    at org.springframework.test.util.MetaAnnotationUtils.findAnnotationDescriptor(MetaAnnotationUtils.java:117)
    at org.springframework.test.util.MetaAnnotationUtils.findAnnotationDescriptor(MetaAnnotationUtils.java:88)
    at org.springframework.test.context.support.ActiveProfilesUtils.resolveActiveProfiles(ActiveProfilesUtils.java:80)
    at org.springframework.test.context.support.AbstractTestContextBootstrapper.buildMergedContextConfiguration(AbstractTestContextBootstrapper.java:367)
    at org.springframework.test.context.support.AbstractTestContextBootstrapper.buildMergedContextConfiguration(AbstractTestContextBootstrapper.java:305)
    at org.springframework.test.context.DefaultTestContext.<init>(DefaultTestContext.java:67)
    at org.springframework.test.context.TestContextManager.<init>(TestContextManager.java:103)
    at org.springframework.test.context.junit4.SpringJUnit4ClassRunner.createTestContextManager(SpringJUnit4ClassRunner.java:124)
    at org.springframework.test.context.junit4.SpringJUnit4ClassRunner.<init>(SpringJUnit4ClassRunner.java:115)
    at sun.reflect.NativeConstructorAccessorImpl.newInstance0(Native Method)
    at sun.reflect.NativeConstructorAccessorImpl.newInstance(NativeConstructorAccessorImpl.java:62)
    at sun.reflect.DelegatingConstructorAccessorImpl.newInstance(DelegatingConstructorAccessorImpl.java:45)
    at java.lang.reflect.Constructor.newInstance(Constructor.java:408)
    at org.junit.internal.builders.AnnotatedBuilder.buildRunner(AnnotatedBuilder.java:29)
    at org.junit.internal.builders.AnnotatedBuilder.runnerForClass(AnnotatedBuilder.java:21)
    at org.junit.runners.model.RunnerBuilder.safeRunnerForClass(RunnerBuilder.java:59)
    at org.junit.internal.builders.AllDefaultPossibilitiesBuilder.runnerForClass(AllDefaultPossibilitiesBuilder.java:26)
    at org.junit.runners.model.RunnerBuilder.safeRunnerForClass(RunnerBuilder.java:59)
    at org.junit.internal.requests.ClassRequest.getRunner(ClassRequest.java:26)
    at org.junit.internal.requests.FilterRequest.getRunner(FilterRequest.java:31)
    at com.intellij.junit4.JUnit4IdeaTestRunner.startRunnerWithArgs(JUnit4IdeaTestRunner.java:98)
    at com.intellij.junit4.JUnit4IdeaTestRunner.startRunnerWithArgs(JUnit4IdeaTestRunner.java:42)
    at com.intellij.rt.execution.junit.JUnitStarter.prepareStreamsAndStart(JUnitStarter.java:234)
    at com.intellij.rt.execution.junit.JUnitStarter.main(JUnitStarter.java:74)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
    at java.lang.reflect.Method.invoke(Method.java:483)
    at com.intellij.rt.execution.application.AppMain.main(AppMain.java:144)


Process finished with exit code -1

我调试了半天，没发现代码里有错误，于是谷歌一下，有人说是包不兼容云云，我心里真是狗粮咧（那么多包都认识我，但我不认识它们，要在几十个包里解决包不兼容问题，这也太难了吧-_-）。

于是乎，我重新创建了一个项目，一次性编写完Spring的依赖，让InteliJ IDEA用Maven的方式帮我引入各个包，再次启动JUnit4的单元测试，得到了测试通过的提示…

适配器（设计模式）

Posted on 2016-05-27

Symbols count in article: 964 | Reading time ≈ 2 mins.

适配器模式之所以存在，和不同手机充电线的接头互不相同是一样的。

比如说，假设现在只有一个带标准USB插口的充电器，怎么样才既能给Android手机充电，又能给iPhone充电呢？答案当然是使用不同的充电线，一条有micro接口，一条有雷电接口。也就是说，我们使用充电线后，虽然仍旧是使用标准USB接口充电，但实际上负责传电的已经变成了micro usb接口和雷电接口，充电线其实就是个另类的适配器。

再举个例子：

假设我们现在有个类son，实现了Eat接口，Eat接口里有EatFood方法，同时还有一个外部类mother（内部聚合了一个son版Eat接口），mother会调用Eat接口的EatFood方法，让son去吃饭。现在mother让son去吃饭时再带上一个女孩一起吃(绝对是亲生的的有木有)，但不允许修改son和Eat接口，这时怎么办？（要求是不改变原有接口的同时，还能使用新功能）

这时我们可以创建一个撩妹版son（handSomeSon），他也实现了Eat接口，他在实现EatFood方法时，偷偷地在调用了另一个新接口EatWithGirl的EatFoodWithGril方法，这样一来，mother（内部聚合了一个handSomeSon版Eat接口）还是调用Eat接口的EatFood方法，撩妹版son就和妹子去吃饭去了。也就是说，我们不改变原有接口Eat，却使用到了新接口EatWithGirl的功能。

至于适配器模式的优缺点，可以总结如下。

优点

将目标类(mother)与适配者类(EatWithGirl接口）解耦，并不直接连通。
代码灵活性和扩展性都非常好，符合开闭原则。
类适配器模式（handSomeSon继承自实现了EatWithGirl接口的类）有个优点，可以在适配器handSomeSon中修改实现了EatWithGirl接口的类的方法，适配器更加灵活。
对象适配器模式（handSomeSon内部有实现了EatWithGirl接口的类的对象实例）有个优点，可以同时适配实现了EatWithGirl接口的类和该类的子类。

缺点

类适配器模式的缺点正好和对象适配器的优点相反，而对象适配器模式的缺点正好和类适配器的优点相反。
适配器可能会有许多子类（对象适配器）或许多适配器类（类适配器）

JDK源代码之Vector

Posted on 2016-05-27

Symbols count in article: 2.2k | Reading time ≈ 4 mins.

Vector是和HashTable一个时代的容器，拥有支持同步的特点（各个方法前一律加上synchronized关键字）。后来不支持同步的ArrayList替代了Vector，日渐流行，也正是因为这个原因，Vector和ArrayList的内部实现都差不多。

具体的源码我就不一一注释，只放出让我觉得有意思的方法。

Vector默认的容量是10，扩容时加上一个capacityIncrement或直接翻倍。

System.arraycopy与Arrays.copyOf

我在研究源码时，发现Vector里间替地使用以上2个方法，它们究竟有什么差别呢？
翻出Arrays.copyOf的代码：

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")

    // 利用反射机制创建一个新的数组
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);

    // copyOf依旧调用System.arraycopy
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

可见，copyOf也会调用arraycopy，而且会创建一个新的数组。
而arraycopy会调用系统底层的复制方法，不同系统的arraycop是不同滴。

removeElementAt(int index)与insertElementAt(E obj, int index)

以上2个方法都会调用系统底层的数组复制函数，复杂度都是O(n)。

// 删除元素
public synchronized void removeElementAt(int index) {
    modCount++;
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                 elementCount);
    }
    else if (index < 0) {
        throw new ArrayIndexOutOfBoundsException(index);
    }
    int j = elementCount - index - 1;
    if (j > 0) {
        System.arraycopy(elementData, index + 1, elementData, index, j);
    }
    elementCount--;

    // GC优化
    elementData[elementCount] = null; /* to let gc do its work */
}

// 增加元素
public synchronized void insertElementAt(E obj, int index) {
    modCount++;
    if (index > elementCount) {
        throw new ArrayIndexOutOfBoundsException(index
                                                 + " > " + elementCount);
    }
    ensureCapacityHelper(elementCount + 1);
    // 调用系统底层的arraycopy
    System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
    elementData[index] = obj;
    elementCount++;
}

synchronized

Vector之所以与ArrayList不同，支持同步，完成是多亏了synchronized这个关键字。
Vector和HashTable一样，虽然支持同步，但却被抛弃了。

JKD源代码之HashTable

Posted on 2016-05-26 | Edited on 2016-05-27

Symbols count in article: 4.8k | Reading time ≈ 8 mins.

HashTable是个比较古老的实现，现在已经不推荐使用，虽然它比HashMap多了支持同步，但在同步并发方面ConcurrentHashMap更强，而不考虑同步的话，HashMap效率比它高了不少，正如官方注释一样：“If a thread-safe implementation is not needed, it is recommended to use HashMap in place of Hashtable. If a thread-safe highly-concurrent implementation is desired, then it is recommended to use java.util.concurrent.ConcurrentHashMap in place of Hashtable.”

在get()/put()/remove()等方法上，HashTable都加上了synchronized关键字，以此来实现同步，但熟悉JVM的童鞋都知道，synchronized关键字的代价很高，涉及到内核态和用户态的切换，所有HashTable的效率比较低。

在计算数组下标时，HashTable用了相对比较简单的求模运算，而不像HashMap那样做了移位优化：

1	int index = (hash & 0x7FFFFFFF) % tab.length;

获取：public synchronized V get(Object key)

public synchronized V get(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    // 计算出数组下标
    int index = (hash & 0x7FFFFFFF) % tab.length;
    // 遍历该链，找到哈希码和key都相同的元素
    for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return (V)e.value;
        }
    }
    return null;
}

可见，HashTable内部在处理冲突时，只是单纯地用链来实现，而不像HashMap一样，在冲突过多时，使用红黑树来优化。

添加：public synchronized V put(K key, V value)

public synchronized V put(K key, V value) {
    // Make sure the value is not null
	// 不允许value为空
    if (value == null) {
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    // 遍历现有元素，如果有相同的key，就替换
    for(; entry != null ; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }

    // 如果不存在相同的key，就往里边插入一个新的key
    addEntry(hash, key, value, index);
    return null;
}

HashTable不允许空的key，也不允许空的value。

添加一个新的键值对：private void addEntry(int hash, K key, V value, int index)

private void addEntry(int hash, K key, V value, int index) {
    modCount++;

    Entry<?,?> tab[] = table;
    if (count >= threshold) {
        // Rehash the table if the threshold is exceeded
        rehash();

        tab = table;
        hash = key.hashCode();
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    // Creates the new entry.
    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>) tab[index];
    // 将新的键值对插到链头
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
}

在这里可以看出，当有新的冲突出现时，新的冲突会插在链头（也许是用了程序局部性原理）

删除：public synchronized V remove(Object key)

public synchronized V remove(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    // 找到数组下标
    Entry<K,V> e = (Entry<K,V>)tab[index];
    for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
    	       // 寻找待删除的键值对
        if ((e.hash == hash) && e.key.equals(key)) {
            modCount++;
            // 如果不是链头
            if (prev != null) {
                prev.next = e.next;
            // 处在链头
            } else {
                tab[index] = e.next;
            }
            count--;
            V oldValue = e.value;
            e.value = null;
            return oldValue;
        }
    }
    return null;
}

重散列算法：protected void rehash()

protected void rehash() {
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;

    // 同样，容量扩大一倍（默认容量是11）
    // overflow-conscious code
    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            // Keep running with MAX_ARRAY_SIZE buckets
            return;
        newCapacity = MAX_ARRAY_SIZE;
    }
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

    modCount++;
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;

    // 从后往前遍历旧数组
    for (int i = oldCapacity ; i-- > 0 ;) {
        // 遍历该下标处的冲突链
        for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
            Entry<K,V> e = old;
            old = old.next;

            // 计算新下标
            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = (Entry<K,V>)newMap[index];
            // 插入新数组
            newMap[index] = e;
        }
    }
}

JDK源代码之HashMap

Posted on 2016-05-26

Symbols count in article: 15k | Reading time ≈ 26 mins.

HashMap首先是一种Map结构，将一个key映射到一个value，有点特殊的是，HashMap不仅允许value为空，也允许key为空。

其次，HashMap继承自抽象map，而不是像HashTable那样继承自Dictionary（虽然都实现了Map接口）；另外，HashTable是同步的，而HashMap并不支持同步。

HashMap内部使用了Hash机制，该机制可以有效地将add与get的平均复杂度降低为O(1)（以前get在最坏的情况下会是O(n)，现在当哈希码相同的同一条链上元素数目超过8时，该链会转为平衡树，所以最坏的情况下是O(logN)）

重要字段

默认容量：DEFAULT_INITIAL_CAPACITY

HashMap的默认容量，初始值设为16。初始值的设置是有讲究的，必须是2的N次方形式，为什么？在为key计算下标时，我们需要让key的哈希码和数组容量做与运算，2的冥可以使得数据更加分散。

最大容纳因子：loadFactor

HashMap的饱和比例，默认为0.75，当HashMap中的数据量达到75%时，HashMap会启用resize()方法扩大容量，扩大为之前的2倍，也就是newCap = oldCap << 1。

节点数组：Node<K,V>[] table

可见HashMap内部其实使用了数组，节点数组，每个Node节点是一个键值对，各个键值对之间通过next指针相连在一起。

Node的源代码如下：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    // 每个键值对的哈希码也是独一无二的
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    // 更换该键值对的值
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    // 判断两个键值对是否equals，不仅key要相同，而且value也要相同
    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

Set<Map.Entry<K,V>> entrySet

存储键值对的一个set集合，它和上面的table有什么区别？似乎被抛弃了，因为已经有了entrySet()方法。

size

HashMap内部数据的大小。

threshold

size的数值超过它时，HashMap必须扩容。

重要方法

计算哈希码：static final int hash(Object key)：

static final int hash(Object key) {
    int h;

    // 如果对象为空则返回0
    // 如果不为空，就求得key.hashCode()的结果h，将h与其左移16位后的结果做异或。
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这里为什么要和左移16位的结果呢？官方是这样解释的：“Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide.”。
原来，这是为了减小冲突，把高位的数据扩散到低位。举个例子，假设HashMap的数组大小是16，那么计算出来的哈希码必须和16（二进制是4个1）做与的运算，这样一来，哈希码只有低4位才起作用，如果有大量的key的哈希码的低4位都相同而更高位不同，它们最终依旧会放在同一个下标，哪怕它们之间因为高位不同而差别巨大。

扩容并重散列：final Node<K,V>[] resize()

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {

       // HashMap原先的容量已经达到极限，无法扩容，直接返回旧的table
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }

        // 将容量直接翻倍，“可用容量”也翻倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }

    // 在HashMap为空的情况下进行扩容，初始化各项参数
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;

    // 得到新的table数组，大小是原先的两倍
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {

       // 逐项扫描旧table数组
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;

            // 如果旧tabel数组的某一下标处不为空
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;

                // 如果该下标处只有一个元素，而没有因哈希码相同而处在同一条链上元素
                if (e.next == null)
                   // 直接放入新的table数组。因为数组容量扩大一倍，有可能下标是之前的两倍，也有可能不变
                    newTab[e.hash & (newCap - 1)] = e;

                // 如果该下标处的元素是一个树节点。（哈希码冲突的key都放在同一棵树上，树根放在该哈希码对应的数组下标处）
                else if (e instanceof TreeNode)
                	 // 将旧的树分裂，放到新的数组中去
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

                // 如果同一链中数据不到8个（仍未分裂为树），则将旧链分为2条新链
                else { // preserve order

                	 // 下标较小的新链(low)
                    Node<K,V> loHead = null, loTail = null;
                	// 下标较大的新链(high)
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 之前都是与oldCap-1（假设二进制有4位）做与运算，结果是4位二进制，如今与oldCap
                        // （有5位，且最高位为1其余为0）做运算，第5位是0的到下标低的新链，第5位是1的到下标大的新链
                        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);

                    // 将两条新链加入新table数组
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

该方法处理的数组下标处元素有以下3种情况：

该下标处不存在冲突的数据
该下标处存在冲突的数据，冲突的数据不够多，用一条链来存储（新的冲突的数据不再放在链头部，而是放在链尾部）
该下标处存在冲突的数据，冲突的数据特别多，用一棵平衡树来存储

该方法是HashMap中极为重要的方法，处理HashMap扩大容量时的各种情况。

关于该方法的性能：

如果是第一种情况，复杂度当然是O(1)
如果是第二种情况，复杂度是该链的长度，最差情况下会达到O(n)
如果是第三种情况，那么复杂度和红黑树的遍历有关，在下面分析到树的分裂时再具体分析。搜索插入删除的复杂度都能做到O(logN)。

插入：final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)：将一个键值对插入HashMap

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;

    // 如果旧table数组为空，就需要调用resize方法来扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    // 哈希码与数组大小做与运算，寻找合适的下标。
    // 如果该下标处为空，就新建一个Node节点.
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);

    // 该下标已经有元素存在
    else {
        Node<K,V> e; K k;
        // 该下标的元素的key就是要插入的key
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 该下标的元素是个树节点（说明哈希码冲突的key过多，已经被逼用红黑树结构来存储）
        else if (p instanceof TreeNode)
        	 // 插入到该哈希码对应的红黑树中
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 该下标的元素是条链的链头
        else {
        	 // 遍历该链，力图插入到链尾
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 如果该链的长度达到一定长度，就转为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 该链中已经有该key
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 插入后，考虑是否要扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

该方法会将一个键值对插入到HashMap，哈希码由hash()方法计算得到。

和resize()方法类似，在插入键值对时也要分情况考虑：

如果数组下标处为空，则直接插入一个Node节点
如果数组下标处不为空，且是一个树节点，则插入键值对到该下标对应的红黑树中去
如果数组下标处不为空，且是一条链的链头，则尝试插入到链尾
在这过程中，如果key已经存在则返回

在插入后还要考虑是否要扩容。

获取value：final Node<K,V> getNode(int hash, Object key)

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;

    // 确保数组不为空，且根据该哈希码计算得到的下标处不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 该下标处就是我们要找的key
        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<K,V>)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;
}

getNode方法根据key的哈希码和key来查找相应的value。
同样的，该方法也会分情况讨论。

删除：final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable)

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }

        // 分情况，将该节点删除
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

想要删除一个节点，首先要查找到该节点，事实上，该方法中的搜索过程和getNode一模一样。
找到后，也是根据数组下标处元素的不同来分情况，这里不再赘述。

static final int tableSizeFor(int cap)：对一个整数，求出大于它且最接近它的2的冥

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

该方法非常巧妙，将最高位的1不断地置换到所有地位上去（结果类似于000011111111），最终加1，记得到2的冥次(也就是000111111111)。

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict)：将一堆数据插入HashMap

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {

       // 如果HashMap数组为空，没有元素
        if (table == null) { // pre-size
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);

            // 当前设置的“可用容量”不够，扩大“可用容量”。
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        else if (s > threshold)
            resize();

        // 将m中的键值对都插入HashMap
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit)：将旧数组上的树分裂到新数组上去

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // Relink into lo and hi lists, preserving order
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        if ((e.hash & bit) == 0) {
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }

    if (loHead != null) {
       // 如果新的低链数量不够，就只形成一条链
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);

        // 如果数量很多，就将链转为红黑树
        else {
            tab[index] = loHead;
            if (hiHead != null) // (else is already treeified)
                loHead.treeify(tab);
        }
    }
    if (hiHead != null) {
       // 如果新的高链数量不够，就只形成一条链
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
     // 如果数量很多，就将链转为红黑树
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}

树的分裂，其复杂度似乎也是O(n)？将链转为树时涉及到红黑树的插入平衡等调整，尚未接触红黑树，待日后补充。

总结：不同于以前HashMap单纯用链来处理冲突，现在的HashMap引入了红黑树来应付大量的冲突，HashMap的效率提高了不少，当n是一百万时也可以接受，至少在最坏情况下复杂度不再是O(n)。

Object源码（JAVA）

Posted on 2016-05-25

Symbols count in article: 1.2k | Reading time ≈ 2 mins.

我们都知道，JAVA是门面向对象语言，也就是说，JAVA中对象的地位是极高的。

遍观JDK源码，所有的类都继承自始祖级别的类：Object类。

Object类内部的方法有如下这些：

方法	说明
getClass()	获得该对象的Class类对象
clone()	克隆一份新对象，两个对象不==，但equals
toString()	以字符串形式，输出对象信息
hashCode()	获得该对象的哈希码
equals()	判断两个对象内容是否相等
finalize()	用于GC，当算法将该对象放入待清除队列后会尝试调用该方法一次
wait()	使得当前线程释放该对象的锁，让该对象恢复自由
notify()	唤醒一个等待该对象的线程，使得该对象被线程拥有
notify()	给所有等待的线程发去唤醒消息

源码

toString()：该函数仅仅打印出对象所属的类+‘@’+对象哈希码

1
2
3

public String toString() {
    return getClass().getName() + "@" + Integer.toHexString(hashCode());
}

equals()：平时我们说==与equals是不同的两种东西，但这里的equals内部就是用了==来作比较。
1
2
3
public boolean equals(Object obj) {
return (this == obj);
}

hashCode()：这里Object的hashCode方法没有实现，可以看一下String的hashCode是怎么实现的。

// 以下是String的hashCode()
public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

可见String在计算哈希码前会尝试返回上一次已经计算出来的结果，为什么要乘以31再加上字符的ANSC码呢？

第一，乘上一个数是为了分权重（越在前面的字符在哈希码中权值越大，这使得前缀相同长度相同的字符串的哈希码差不多大，可以存放在相邻的地方）。
第二，乘上31是因为31是素数，可以增大结果的唯一性。

从0到1理解JVM垃圾回收机制

Posted on 2016-05-22

Symbols count in article: 2.1k | Reading time ≈ 4 mins.

从C++转到JAVA，首先要知道的一条是，JAVA拥有相对比较完善的内存垃圾回收机制（回想以前在中大的作业平台上写C++代码，在new之后总会忘记free，导致我每次都不能开开心心地AC，巨汗-_-!）

JAVA是一门半编译半解释的语言，在编译阶段无法确定回收垃圾的具体位置（虽然有部分是可以确定的），所以回收垃圾的任务主要交由JVM来处理，我们经常听到高手们谈到的所谓GC指的就是垃圾回收。

垃圾回收主要有两步：

识别哪些是垃圾
使用回收的算法将垃圾‘扫入’垃圾桶

谁是垃圾

在之前的博文里，我们知道JAVA运行时主要分程序计数器、虚拟机栈、本地方法栈、堆、方法区。前3者随着线程同生共死，当线程结束时，它们的内存就被回收了，只有剩下的堆和方法区需要我们竭尽全力地进行垃圾回收。

那么，在堆和方法区里，我们怎么知道谁是垃圾呢？

寻找垃圾算法之引用计数法

熟悉操作系统的童鞋都知道，引用计数算法的主要思想是：当有个地方引用了某个对象时，该对象的计数器增加1，当那个地方不再引用该对象时，该对象的计数器减1；直到计数器的值为0，系统就认为该对象不再有用，把它标记为垃圾。

一个论文引用的例子可以解释该算法：假设你是个德高望重的学者，你写了篇影响巨大的论文，那么你的论文理所当然会被许多人引用和参考，因为你的论文特别有价值；相反，如果你是个三流的研究人员，你写的东西无人问津，就会被视为“垃圾”。

这个算法最大的缺点是：它无法处理相互循环引用的情况。什么意思呢？

还是论文引用的例子：假设现在有3个三流的研究人员A、B和C，他们分别写出了3篇质量极其低下的论文，按理来说，他们的论文是“垃圾”，不会被人引用，但数据显示，3篇论文的被引用数都为1。相关部门调查后发现，A引用了B的论文，B引用了C的论文，而C又引用了A的论文，所以虽然3篇全都是“垃圾”，但却存在着彼此的引用，形成了一个环，使得人们认为3篇论文不是“垃圾”，逃过了被“回收”的危险。

因为这个缺点，引用计数法基本只作为反例，只存在于教科书上。

寻找垃圾算法之可达性分析算法

可达性分析的原理是：一个对象引用了另一个对象时，两个对象之间就存在连线，理清了所有的对象的引用关系之后，它们基本都会处在同一颗树上，此时，将不在树上的对象视为垃圾。也就是说，那些无人知晓的对象都是垃圾。

这个算法的关键点是：从谁开始找呢？

（如果从垃圾开始找，那么那些不是垃圾的反倒视为垃圾，这是极为严重的噩梦！）

有种对象，它的价值比较大，不会被轻易抛弃，相对稳定，存在的时间较长，被称为GC Roots，是可达性分析算法的起始点。GC Roots一般只存在于栈和方法区中（具体是虚拟机栈中局部变量表内引用的对象、本地方法栈中Native方法引用的对象和方法区中静态变量和常量引用的对象），堆中不会有。

清除垃圾的强有力手段

知道谁是垃圾，下一步是启用算法将其清除。也许有人会笑，清除内存中的垃圾有什么难的，直接将它标记为废弃不就得了嘛，还在那边唧唧歪歪的整啥呀？

标记清除算法

这个算法和上面说的“直接标记为废弃”一模一样，先扫描一遍，利用可达性分析算法，将垃圾标记出来，再扫描一遍，将垃圾清除。

这个算法太简单了，简单到不是计算机专业的人也能秒懂，但它的简单也导致了极为复杂的后果：在一整段内存上，将其中的几个地方标记为废弃，会使得这条内存看起来‘坑坑洼洼’的，也就是内存碎片。碎片一多，分配内存时就不能顺利地拿到一块大内存（毕竟内存条上只有细小的碎片）。

为了解决这个碎片的问题，人们又想到了一个方法。

标记复制算法

这个算法的标记阶段和标记清除算法一样，差别在于，它不再清除无用的内存，而是将有用的内存复制到另一片空间，剩下的这片空间称为未拆封全新区域。

举个例子，对于一块1G的内存，我们将它划分为2块512M的小内存，每次我们只使用其中一块；在垃圾回收时先找出垃圾，然后将不是垃圾的对象移动到另一块内存上，并将这一块内存清空；下一次进行回收时也是同样的原理。

但这个算法也有一个缺点：任何时候都有一块内存不会被用到，也就是说，内存被浪费了。

幸好，这个缺点可以减弱到能被接受的程度。（既然每次都会浪费掉一块内存，那么，我们每次都只浪费一块非常小的内存不就行了吗？）

标记整理算法

标记出垃圾后，既不直接将其清除，也不将有效对象复制到另一块内存上，而是将有效对象复制到内存的开头，如此一来，既不会导致过多碎片，也不会浪费另一块内存。

分代收集算法

上面三个算法都仅考虑对现有垃圾的回收，未曾考虑到时间这个不可避免的因素在垃圾回收中的影响，所以现代的虚拟机都使用一种被称为“分代收集”的算法来进行实际的垃圾回收。分代收集的原理是：根据对象的已存活时长，将其划分到不同区域，在不同区域里采取不同的回收算法。

一般来说，虚拟机会将堆分为2个年代：

新生代
老年代

在新生代里使用了标记复制算法，所以新生代又分为3个区域：

一个eden亚当区（占80%空间）：这个区里存放着大量鲜活的年轻对象，它们中只有少数会存活下来。
两个survivor幸存者区（各占10%空间）：这个区里存放的对象已经有了一定年纪，它们的部分人可能有机会迁往老年代进行养老。

从0到1理解JVM内存分配机制

Posted on 2016-05-22

Symbols count in article: 945 | Reading time ≈ 2 mins.

在JAVA中，除了在即时编译器优化后部分对象会在栈上分得足够空间，其余的对象都会在堆上“求分配空间”，所以之前我们才说，堆里存在着大大小小密密麻麻的对象。

那么在堆里，对象究竟会分到哪部分的内存，新生代还是老年代？

普通对象

答案是：对象一般会分配到新生代中Eden区的内存。

一个普通对象的极端经历

有新对象到来，而Eden又没有足够的空间时，新生代尝试进行新生代的垃圾回收（也就是Minor GC）。在尝试之前，它需要知道，如果情况特别糟糕，这次Minor GC是否安全，也就是新生代所有对象都必须移到老年代以便腾出空间存放新对象，换句话说，新生代会问老年代：“你还有连续空间可以存放我现在的崽崽们吗”，如果老年代给他个肯定，新生代就可以无忧无虑地进行Minor GC了。

如果老年代没有给出肯定答案，新生代就会再问一句：“在以往迁往你那边的对象大小里，取个平均值，你现在还有那么大的连续空间吗？”如果老年代回答yes，新生代就认为接下来的Minor GC的对象有极大的可能小于历史平均值，可以冒些风险进行MinorGC（风险是接下来的对象确实超过了历史平均值，老年代没有连续空间存放新生代来的对象，老年代需要进行老年代的回收也就是Full GC，因为新生代的冒险进行了一次失败的Minor GC，老年代需付出Full GC的代价，而后新生代再重头尝试Minor GC）。当然了，如果老年代说了不，那么新生代就得先等老年代执行了Full GC再执行新生代专属的Minor GC。

那些超大的对象

如果对象十分非常极其以及特别的巨大，那么新生代会直接请求老年代的帮助，将对象分配在老年代（老年代人太好了，新生代装不下的对象它负责装。）

一群长寿的对象

如果对象太老，也就是说在Eden区呆了一代，又在Survivor存活期呆了15代（默认是15代），那么该对象会迁往老年代，可见，JVM的世界里，一个对象的退休年龄是16。

一群稳定的幸存者

Survivor区中的对象不必等15代才能迁往老年代。如果某一年纪的对象的所占空间超过Survivor区大小的一半，它们会被赶走，赶到老年代。那种年纪的对象有这么多一起存活了这么长时间，JVM默认它们这一代的稳定性都比较好，可以提前去老年区过稳定的生活。

从0到1理解JVM运行时数据区

Posted on 2016-05-18

Symbols count in article: 1.9k | Reading time ≈ 3 mins.

与操作系统类似，JVM（JAVA虚拟机）拥有自己的运行时数据区。在操作系统中，通常有代码区、数据区、堆、栈和静态区等，而JVM中的数据区则有所不同（虽然JVM号称虚拟机，是机器，但它和现实机器始终还是有差别的）。

JVM的运行时数据区类型有下面5种：

类型	属于	抛出异常类型
程序计数器	线程私有	无
虚拟机栈	线程私有	SOF、OOM
本地方法栈	线程私有	SOF、OOM
堆	公有	OOM
方法区	公有	OOM

程序计数器

程序计数器和CPU中的PC寄存器起着同样的作用：保存下一条指令的地址。不同的是，CPU中的PC寄存器是共有的，JVM中的程序计数器是线程私有的，每个线程都需要一个程序计数器来记住自己已经执行到哪儿了，线程之间轮流执行一段时间，轮到自己时，就可以借助程序计数器从正确的地方往下执行。

虚拟机栈

顾名思义，该栈属于JVM，用来保存一些必要的数据。熟悉操作系统的人都知道，在执行一个方法时，系统会将返回地址和形参等压入栈，执行过程中会从栈里获得形参，执行完方法的全部指令后再从栈中获得返回地址以便跳出方法。

虚拟机栈的原理也是一样的，在准备执行一个方法时，JVM会为该方法生成一个栈帧，将栈帧压入栈；在执行方法的过程中，JVM借用该栈帧搞一些动作；执行完方法后将该栈帧出栈。也就是说，虚拟机栈主要是服务于方法们的执行过程的，一个方法的诞生需要虚拟机栈，一个方法的死亡也需要虚拟机栈，虚拟机栈是多么的有爱和有担当。

虚拟机栈的栈帧中都有些什么玩意呢？

局部变量表：这玩意可不得了，它保存了一个方法执行过程中所需要的所有局部变量！比如说，我们在一个save()方法里定义了一个int类型的temp变量，每次执行save()时，temp都会出现在局部变量表中。更不得了的是，局部变量表的大小在编译时就固定了！不过值得注意的是，该表中只存放变量，不存放对象。
返回地址：也就是俗话中的“return到哪儿去”。
操作数栈：熟悉计算机组成原理或编译原理的童鞋都知道，虽然现代计算机很多都是基于寄存器，但在很早以前曾有一种基于栈的机器，后来因效率问题基于栈的设计被弃用。而JVM，恰恰就是一种基于栈的设计。写过基于栈的四则计算器的同志都知道操作数栈是什么玩意。
动态链接：我还不是特别明白动态链接，以后再回来补充。

因为该区基于栈结构，所以不可避免在极端情况下会出现栈溢出（SOF）；另外呢，该区的大小是可以动态扩展的，有时候机器没有多余供其扩展，供其挥霍，也就不可避免地出现内存不足（OOM）。

本地方法栈

随着时代的进步，JAVA的执行效率在逐渐地提升，JAVA已经能够做到在合适的时候“调用操作系统的本地方法，以一种C或C++的速度去执行”。那么在执行系统本地方法时，本地方法也需要栈呀，这些栈在哪里呢？不太可能复用虚拟机栈吧（虚拟机栈专门服务于JAVA语言）。应该在哪里设置个栈呢？为了解决这个问题，聪明的人类推出了本地方法栈，它是属于本地方法的栈。

堆

堆是什么呢？熟悉C语言的同学都知道，在C中动态申请一块空间需要使用malloc函数，该函数将在堆里获得空间，这里的堆和JVM中的堆其实也是差不多的。
JVM中的堆，主要用于内存的动态分配。一个对象需要内存时，主要从堆中申请到（注意我用了‘主要’，现如今有栈上分配等技术可以给对象分配内存）。简单地说，堆中充满了大大小小密密麻麻的对象。

由于对象主要都在堆里，当一个对象不再有用时，我们可以将它从堆里抹除，这种做法叫做垃圾回收，英文名叫GC。

出于现代垃圾回收器的需要，堆通常被分为新生代（内含一个EDEN区和两个Survivor区）和老生代。垃圾回收器不断地监视着堆里的众多对象，看谁不爽就把谁KO，将之扼杀于堆中。

堆存放了所有线程的对象，它顺理成章地成为公共区域。

方法区

方法区是运行时数据区中的最后一个，它存放的主要是运行时的代码。当一个类被加载时，它会从class文件里被加载到方法区中，它的类版本、字段信息、方法信息、接口信息和常量池都会被加载到方法区中。除了存放类的信息，方法区还存放常量、静态变量和代码。也就是说，方法区中的内容大部分都是不变的，除了一个叫做常量池的奇葩。

常量池里边主要是符号引用和直接引用（不明白这两个概念的可以将它们看作一条条的字符串，如“hi”，“hello”等），之所以说常量池会变化，是因为运行时产生的常量也可以加入常量池。

将JVM的运行时数据区和操作系统的运行时数据区做比较，结果如下

JVM	操作系统
程序计数器	PC寄存器
虚拟机栈、本地方法栈	栈
GC堆	ｍalloc堆
方法区	代码区

JDK源代码之LinkedList

Posted on 2016-05-18

Symbols count in article: 9.7k | Reading time ≈ 16 mins.

LinkedList特性

底层数据结构

LinkedList不同于ArrayList的数组，它基于链表。

效率

LinkedList的插入删除快，遍历慢（ArrayList正好相反）

实现的接口

1
2
3

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList实现了List接口、Deque双向队列接口（既可以当作FILO队列也可以当作FIFO栈）、Cloneable接口、序列化接口。
值得注意的是，LinkedList继承自AbstractSequentialList（AbstractSequentialList和ArrayList一样继承自AbstractList），也就是说，LinkedList比ArrayList更细化了一层。

细化的那层AbstractSequentialList实现了“链表”版的get/set/add/remove方法，这使得LinkedList和ArrayList有了质的差别（毕竟彼此的基因遗传都不同）。

同步机制

与ArrayList一样，LinkedList也是不同步的，可以用包装器来创造一个支持同步的List:

1	List list = Collections.synchronizedList(new LinkedList(...));

LinkedList字段

transient int size = 0;

transient Node<E> first;

transient Node<E> last;

很明显，LinkedList用了first节点和last节点来保存整个链表（ArrayList用的是数组）。
注：transient关键字的作用是防止该字段被序列化（一些敏感的信息不能序列化然后在网络上传输）。

LinkedList方法分析

linkFirst(E e) （将一个元素插入链表头部）

private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

先建立一个以first为后继的新节点，令first为该新节点；然后再修改第二个节点的prev变量使其指向新头部（如果没有第二个节点就修改last）

linkLast(E e)（将一个元素插入链表尾部）

机制与linkFirst(E e)相似，只需将first替换为last

linkBefore(E e, Node succ) （将一个元素插到一个节点之前）

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

该方法会判断另一个节点之前是否有节点存在，没有就修改first。

unlinkFirst(Node f)（将链表头部节点剔除）

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

该方法中有条垃圾回收优化的语句：

1	f.next = null; // help GC

强行令变量为null，不再引用该对象，该对象便会在下一轮的GC中被回收。
此外，该方法会判断第二个元素是否存在，没有就修改last。

unlinkLast(Node l)（将链表尾部节点剔除）

与unlinkFirst(Node<E> f)类似

unlink(Node x)（剔除某个特定的节点）
Read more »

JDK源代码之ArrayList

Posted on 2016-05-17 | Edited on 2016-05-18

Symbols count in article: 75k | Reading time ≈ 2:05

ArrayList的特性

实现的接口

ArrayList的类声明如下：

1 2	public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

轻轻一撇，我们便是可以看出，ArrayList继承自抽象泛型类AbstractList<>，它实现了List接口（Collection集合的List），也拥有RandomAccess/Cloneable/Serializable三个“标注”接口。

同步机制

与Vector相比，ArrayList放弃了同步机制。如果我想要一个支持同步的ArrayList，可以使用Collections工具类中的synchronizedList方法构建一个List：

1	List list = Collections.synchronizedList(new ArrayList(...));

时间空间复杂度

ArrayList的get/size/isEmpty等方法的复杂度均为常数，add方法的复杂度为O(n)，其余的都是线性复杂度。

ArrayList字段

private static final long serialVersionUID = 8683452581122892189L;

/**
 * Default initial capacity.
 * ArrayList的默认容量。插满会自动扩充。
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * Shared empty array instance used for empty instances.
 * 保存ArrayList元素的空数组
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to
 * DEFAULT_CAPACITY when the first element is added.
 */
transient Object[] elementData; // non-private to simplify nested class access

/**
 * The size of the ArrayList (the number of elements it contains).
 * ArrayList的实际大小（已经插入了多少数据）
 *
 * @serial
 */
private int size;

ArrayList方法分析

从上往下分析

使用Eclipse阅读JDK源码

Posted on 2016-05-17 | Edited on 2016-05-27

Symbols count in article: 165 | Reading time ≈ 1 mins.

研究JDK源代码，是从JAVA新手走向高手的必经之路。阅读JDK源码的方法如下：

在eclipse中新建一个JAVA工程

将JDK安装根目录里的src.zip解压到JAVA工程目录下

回到eclipse，右键点击工程，选择refresh

此时，除了一堆编译错误外，你应该可以开始阅读JDK所有源码

从无到有写一个后台注册模块（基于SSH2）

Posted on 2016-05-17

Symbols count in article: 22k | Reading time ≈ 37 mins.

此次项目基于SSH2框架（物业报修系统），为了避免忘记框架使用的步骤，我稍微记录一下注册模块的编写过程。

框架分层

核心是Spring框架，它有IOC容器，可以方便地管理Struts2和Hibernate；Struts2因其MVC的架构，因而负责显示；Hibernate则是持久层，实现DAO。

步骤

下面是详细的步骤，根据时间先后一步一步来。

Tomcat容器的配置（WebRoot/WEB-INF/web.xml）

该文件告诉Tomcat，主页是哪个、Action交给谁处理、网站的编码格式、过滤拦截哪些URL、托管给Spring等。

<?xml version="1.0" encoding="UTF-8"?>
<web-app version="2.5" xmlns="http://java.sun.com/xml/ns/javaee"
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://java.sun.com/xml/ns/javaee
    http://java.sun.com/xml/ns/javaee/web-app_2_5.xsd">

    <!-- 所有请求都通过FilterDispatcher查找actionMapper的设置来决定请求对应的是哪个Action -->

    <display-name>邱永臣配置</display-name>

    <!-- 过滤器的配置 -->
    <filter>
        <!-- 名字 -->
        <filter-name>filterDispatcher</filter-name>
        <!-- 过滤器对应的名字 -->
        <filter-class>org.apache.struts2.dispatcher.FilterDispatcher</filter-class>
    </filter>

    <filter-mapping>
        <filter-name>filterDispatcher</filter-name>
        <!-- 过滤匹配的URL -->
        <url-pattern>/*</url-pattern>
    </filter-mapping>

    <!-- 解决中文乱码问题 -->
    <filter>
        <filter-name>struts-clean</filter-name>
        <filter-class>org.apache.struts2.dispatcher.ActionContextCleanUp</filter-class>
    </filter>
    <filter-mapping>
        <filter-name>struts-clean</filter-name>
        <url-pattern>/*</url-pattern>
    </filter-mapping>

    <!-- 进入WEB应用访问的默认文件 -->
    <welcome-file-list>
        <welcome-file>lookRemindRepairOrder.jsp</welcome-file>
    </welcome-file-list>

    <context-param>
        <param-name>contextConfigLocation</param-name>
        <!-- 如果将该xml文件放在WEB-INF下面的话，就需要下面配置 <param-value>WEB-INF/applicationContext.xml</param-value> -->
        <param-value>WEB-INF/applicationContext.xml</param-value>
        <!-- 下面是默认配置 -->
        <!-- <param-value>classpath:com/lzq/config/applicationContext-*.xml</param-value> -->
    </context-param>

    <!-- 采用Listener来初始化Spring容器 -->
    <listener>
        <listener-class>org.springframework.web.context.ContextLoaderListener</listener-class>
    </listener>
</web-app>

编写用户实体（model层）

所谓用户实体，其实是java bean，它内部有用户数据：

/**
 *
 */
package com.ilovecl.myproperty.model;

/**
 * 学生实体
 *
 * @author 邱永臣
 *
 *         对应的数据库建表命令为 create table `Student` ( `userId` int not null primary
 *         key auto_increment, `userName` varchar(20) not null, `password`
 *         varchar(20) not null, `phoneNumber` long, `email` varchar(100),
 *         `sexual` varchar(10)) ENGINE=InnoDB DEFAULT CHARSET=utf8;
 */

public class Student {
    private int userId;
    private String userName;
    private String password;
    private long phoneNumber;
    private String email;
    private String sexual;

    public Student() {
        super();
        // TODO Auto-generated constructor stub
    }

    public Student(String userName2, String password2, long phoneNumber2,
            String email2, String sexual2) {
        this.userName = userName2;
        this.password = password2;
        this.phoneNumber = phoneNumber2;
        this.email = email2;
        this.sexual = sexual2;
    }

    /**
     * @return the userId
     */
    public int getUserId() {
        return userId;
    }

    /**
     * @param userId
     *            the userId to set
     */
    public void setUserId(int userId) {
        this.userId = userId;
    }

    /**
     * @return the userName
     */
    public String getUserName() {
        return userName;
    }

    /**
     * @param userName
     *            the userName to set
     */
    public void setUserName(String userName) {
        this.userName = userName;
    }

    /**
     * @return the password
     */
    public String getPassword() {
        return password;
    }

    /**
     * @param password
     *            the password to set
     */
    public void setPassword(String password) {
        this.password = password;
    }

    /**
     * @return the phoneNumber
     */
    public long getPhoneNumber() {
        return phoneNumber;
    }

    /**
     * @param phoneNumber
     *            the phoneNumber to set
     */
    public void setPhoneNumber(long phoneNumber) {
        this.phoneNumber = phoneNumber;
    }

    /**
     * @return the email
     */
    public String getEmail() {
        return email;
    }

    /**
     * @param email
     *            the email to set
     */
    public void setEmail(String email) {
        this.email = email;
    }

    /**
     * @return the sexual
     */
    public String getSexual() {
        return sexual;
    }

    /**
     * @param sexual
     *            the sexual to set
     */
    public void setSexual(String sexual) {
        this.sexual = sexual;
    }

}

编写Hibernate的映射文件(Student.hbm.xml)

Hibernate正是凭借它，才能将对象映射到数据库中去：

<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE hibernate-mapping PUBLIC "-//Hibernate/Hibernate Mapping DTD 3.0//EN"
"http://hibernate.sourceforge.net/hibernate-mapping-3.0.dtd">

<hibernate-mapping>
    <class name="com.ilovecl.myproperty.model.Student" table="Student">
        <id name="userId" type="java.lang.Integer">
            <column name="userId" />
            <generator class="increment" />
        </id>
        <property name="userName" type="java.lang.String">
            <column name="userName" length="20" />
        </property>
        <property name="password" type="java.lang.String">
            <column name="password" length="20" />
        </property>
        <property name="phoneNumber" type="java.lang.Long">
            <column name="phoneNumber" />
        </property>
        <property name="email" type="java.lang.String">
            <column name="email" length="100" />
        </property>
        <property name="sexual" type="java.lang.String">
            <column name="sexual" length="10" />
        </property>
    </class>
</hibernate-mapping>

将Hibernate托管给Spring

在WebRoot/WEB-INF/applicationContext.xml中增加下面的代码代码，告诉Hibernate数据库的信息，映射文件的位置，将Hibernate的sessionFactory托管给Spring：

<bean id="dataSource" class="org.apache.commons.dbcp.BasicDataSource">
        <property name="driverClassName">
            <value>com.mysql.jdbc.Driver</value>
        </property>
        <property name="url">
            <!-- 设置字符集，防止插入到数据库里时出现乱码 -->
            <value>jdbc:mysql://139.129.118.90:3306/myproperty?useUnicode=true&amp;characterEncoding=UTF-8</value>
        </property>
        <property name="username">
            <value>root</value>
        </property>
        <property name="password">
            <value>test</value>
        </property>
    </bean>
    <bean id="sessionFactory"
        class="org.springframework.orm.hibernate3.LocalSessionFactoryBean">
        <property name="dataSource">
            <ref bean="dataSource" />
        </property>
        <property name="hibernateProperties">
            <props>
                <prop key="hibernate.dialect">
                    org.hibernate.dialect.MySQLDialect
                </prop>
            </props>
        </property>
        <property name="mappingResources">
            <list>
                <value>com/ilovecl/myproperty/model/Student.hbm.xml</value>
            </list>
        </property>
    </bean>

    <bean id="baseTransactionProxy"
        class="org.springframework.transaction.interceptor.TransactionProxyFactoryBean"
        abstract="true">
        <property name="transactionManager">
            <ref bean="transactionManager" />
        </property>
        <property name="transactionAttributes">
            <props>
                <prop key="save*">PROPAGATION_REQUIRED</prop>
                <prop key="update*">PROPAGATION_REQUIRED</prop>
                <prop key="delete*">PROPAGATION_REQUIRED</prop>
            </props>
        </property>
    </bean>

编写DAO层代码（接口和实现）

DAO层专门操作实体，比如增删改查一个学生等。
接口代码：

/**
 *
 */
package com.ilovecl.myproperty.DAO;

import java.util.List;

import com.ilovecl.myproperty.model.Student;

/**
 * DAO层：学生DAO的接口
 *
 * @author 邱永臣
 *
 */
public interface IStudentDAO {
    public abstract void save(Student transientInstance);

    public abstract void delete(Student persistentInstance);

    public abstract Student findById(java.lang.Integer id);

    public abstract List<Student> findByUserName(java.lang.String userName);

    boolean isStudentExits(String userName);

}

实现的代码：

/**
 *
 */
package com.ilovecl.myproperty.DAO.impl;

import java.util.List;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
import org.springframework.orm.hibernate3.support.HibernateDaoSupport;

import com.ilovecl.myproperty.DAO.IStudentDAO;
import com.ilovecl.myproperty.model.Student;

/**
 * @author 邱永臣
 *
 */
public class StudentDAO extends HibernateDaoSupport implements IStudentDAO {

    private static final Log log = LogFactory.getLog(StudentDAO.class);

    /*
     * (non-Javadoc)
     *
     * @see
     * com.ilovecl.myproperty.DAO.IStudentDAO#save(com.ilovecl.myproperty.model
     * .Student)
     */
    @Override
    public void save(Student transientInstance) {
        log.debug("save(Student transientInstance) in StudentDAO");
        try {
            this.getHibernateTemplate().saveOrUpdate(transientInstance);
            log.debug("save(Student transientInstance) in StudentDAO successful");
        } catch (RuntimeException re) {
            log.error("save(Student transientInstance) in StudentDAO failed",
                    re);
            throw re;
        }

    }

    /*
     * (non-Javadoc)
     *
     * @see
     * com.ilovecl.myproperty.DAO.IStudentDAO#delete(com.ilovecl.myproperty.
     * model.Student)
     */
    @Override
    public void delete(Student persistentInstance) {
        log.debug("delete(Student persistentInstance)");
        try {
            getHibernateTemplate().delete(persistentInstance);
            log.debug("delete(Student persistentInstance) successful");
        } catch (RuntimeException re) {
            log.error("delete(Student persistentInstance) failed", re);
            throw re;
        }

    }

    /*
     * (non-Javadoc)
     *
     * @see com.ilovecl.myproperty.DAO.IStudentDAO#findById(java.lang.Integer)
     */
    @Override
    public Student findById(Integer id) {
        log.debug("findById(Integer id) : " + id);
        try {
            Student instance = (Student) getHibernateTemplate().get(
                    "com.ilovecl.myproperty.model.Student", id);
            return instance;
        } catch (RuntimeException re) {
            log.error("findById(Integer id) failed", re);
            throw re;
        }
    }

    /*
     * (non-Javadoc)
     *
     * @see
     * com.ilovecl.myproperty.DAO.IStudentDAO#findByUsername(java.lang.Object)
     */
    @SuppressWarnings("unchecked")
    @Override
    public List<Student> findByUserName(String userName) {
        List<Student> students;
        try {
            String queryString = "from Student as model where model."
                    + "userName" + "= ?";
            students = getHibernateTemplate().find(queryString, userName);
        } catch (RuntimeException re) {
            log.error("findByUserName failed", re);
            throw re;
        }

        return students;
    }

    @Override
    public boolean isStudentExits(String userName) {
        return findByUserName(userName).size() == 1;
    }
}

将DAO托管给Spring

在WebRoot/WEB-INF/applicationContext.xml中增加下面的代码代码：

<!-- 将学生DAO托给Spring -->
<bean id="studentDAO" class="com.ilovecl.myproperty.DAO.impl.StudentDAO">
    <property name="sessionFactory">
        <ref bean="sessionFactory" />
    </property>
</bean>

编写逻辑层代码（接口与实现）

逻辑层原先放在Struts2控制层的Action中，但随着Action的日渐庞大，许多负责的逻辑代码需要分离出来单独作为逻辑层。

接口的代码：

/**
 *
 */
package com.ilovecl.myproperty.service;

import com.ilovecl.myproperty.DAO.IStudentDAO;
import com.ilovecl.myproperty.model.Student;

/**
 * @author 邱永臣
 *
 */
public interface IRegisterService {

    public IStudentDAO getStudentDAO();

    public void setStudentDAO(IStudentDAO studentDAO);

    public boolean register(Student student);

    boolean isStudentExits(String userName);
}

实现的代码：

/**
 *
 */
package com.ilovecl.myproperty.service.impl;

import com.ilovecl.myproperty.DAO.IStudentDAO;
import com.ilovecl.myproperty.model.Student;
import com.ilovecl.myproperty.service.IRegisterService;

/**
 * @author 邱永臣
 *
 */
public class RegisterService implements IRegisterService {

    private IStudentDAO studentDAO;

    /**
     * @return the studentDAO
     */
    public IStudentDAO getStudentDAO() {
        return studentDAO;
    }

    /**
     * @param studentDAO
     *            the studentDAO to set
     */
    public void setStudentDAO(IStudentDAO studentDAO) {
        this.studentDAO = studentDAO;
    }

    /*
     * (non-Javadoc)
     *
     * @see
     * com.ilovecl.myproperty.service.IRegisterService#isStudentExits(java.lang
     * .String)
     */
    @Override
    public boolean isStudentExits(String userName) {
        return studentDAO.findByUserName(userName).size() == 1;
    }

    /*
     * (non-Javadoc)
     *
     * @see
     * com.ilovecl.myproperty.service.IRegisterService#register(java.lang.String
     * , java.lang.String)
     */
    @Override
    public boolean register(Student student) {
        if (isStudentExits(student.getUserName())) {
            return false;
        }

        studentDAO.save(student);

        return true;
    }

}

将逻辑层托管给Spring

在WebRoot/WEB-INF/applicationContext.xml中增加下面的代码代码：

<!-- 注册业务逻辑 -->
<bean id="registerService" parent="baseTransactionProxy">
    <property name="target">
        <bean class="com.ilovecl.myproperty.service.impl.RegisterService">
            <property name="studentDAO" ref="studentDAO" />
        </bean>
    </property>
</bean>

编写Struts2的Action

到这里，我们就进入了Struts2的MVC世界。

控制层：Action属于MVC中的C；

模型层：Struts1中用java bean作为模型层，也就是MVC中的M，但该方案在Struts2中被废除，模型层的内容直接放入Action;

视图层：jsp的内容即是视图层；

Action最主要的方法是execute，在用户点击注册按钮时，会执行该方法：

/**
 *
 */
package com.ilovecl.myproperty.struts.action;

import com.ilovecl.myproperty.model.Student;
import com.ilovecl.myproperty.service.IRegisterService;
import com.opensymphony.xwork2.ActionSupport;

/**
 * 用户注册功能的Action类
 *
 * @author 邱永臣
 *
 */
@SuppressWarnings("serial")
public class StudentRegisterAction extends ActionSupport {
    private int userId;
    private String userName;
    private String password;
    private String passwordConfirm;
    private long phoneNumber;
    private String email;
    private String sexual;

    String message;

    private IRegisterService iRegisterService;

    /**
     *
     */
    public StudentRegisterAction() {
        phoneNumber = 0;
        email = "";
        sexual = "";
    }

    /*
     * (non-Javadoc)
     *
     * @see com.opensymphony.xwork2.ActionSupport#execute()
     */
    @Override
    public String execute() throws Exception {
        this.message = "";

        if (this.userName.equals("")) {
            this.message += "用户名为空！\n";
            return INPUT;
        } else if (this.password.equals("") || this.passwordConfirm.equals("")) {
            this.message += "密码为空！\n";
            return INPUT;
        } else if (!this.password.equals(this.passwordConfirm)) {
            this.message += "两次密码不相同！\n";
            return INPUT;
        }

        if (iRegisterService.isStudentExits(userName)) {
            this.message += "账户已存在！";
            return INPUT;
        }
        if (iRegisterService.register(new Student(userName, password,
                phoneNumber, email, sexual))) {
            this.message = "注册成功";
            return SUCCESS;
        } else {
            this.message = "注册失败";
            return INPUT;
        }
    }

    /**
     * @return the userId
     */
    public int getUserId() {
        return userId;
    }

    /**
     * @param userId
     *            the userId to set
     */
    public void setUserId(int userId) {
        this.userId = userId;
    }

    /**
     * @return the userName
     */
    public String getUserName() {
        return userName;
    }

    /**
     * @param userName
     *            the userName to set
     */
    public void setUserName(String userName) {
        this.userName = userName;
    }

    /**
     * @return the password
     */
    public String getPassword() {
        return password;
    }

    /**
     * @param password
     *            the password to set
     */
    public void setPassword(String password) {
        this.password = password;
    }

    /**
     * @return the passwordConfirm
     */
    public String getPasswordConfirm() {
        return passwordConfirm;
    }

    /**
     * @param passwordConfirm
     *            the passwordConfirm to set
     */
    public void setPasswordConfirm(String passwordConfirm) {
        this.passwordConfirm = passwordConfirm;
    }

    /**
     * @return the phoneNumber
     */
    public long getPhoneNumber() {
        return phoneNumber;
    }

    /**
     * @param phoneNumber
     *            the phoneNumber to set
     */
    public void setPhoneNumber(long phoneNumber) {
        this.phoneNumber = phoneNumber;
    }

    /**
     * @return the email
     */
    public String getEmail() {
        return email;
    }

    /**
     * @param email
     *            the email to set
     */
    public void setEmail(String email) {
        this.email = email;
    }

    /**
     * @return the sexual
     */
    public String getSexual() {
        return sexual;
    }

    /**
     * @param sexual
     *            the sexual to set
     */
    public void setSexual(String sexual) {
        this.sexual = sexual;
    }

    /**
     * @return the iRegisterService
     */
    public IRegisterService getiRegisterService() {
        return iRegisterService;
    }

    /**
     * @param iRegisterService
     *            the iRegisterService to set
     */
    public void setiRegisterService(IRegisterService iRegisterService) {
        this.iRegisterService = iRegisterService;
    }

    /**
     * @return the message
     */
    public String getMessage() {
        return message;
    }

    /**
     * @param message
     *            the message to set
     */
    public void setMessage(String message) {
        this.message = message;
    }

}

将Action托管给Spring

在WebRoot/WEB-INF/applicationContext.xml中增加下面的代码代码：

<!-- 学生注册界面的Action -->
<bean id="studentRegisterAction"
    class="com.ilovecl.myproperty.struts.action.StudentRegisterAction">
    <property name="iRegisterService" ref="registerService" />
</bean>

让Struts2找到从Spring那里找到Action

由于Spring管理着Action，Struts2需要Action的时候，只能找Spring要。

在struts.xml中增加下面的代码代码：

<action name="register" class="studentRegisterAction">
    <result name="success">/register.jsp</result>
    <result name="input">/register.jsp</result>
</action>

编写视图层页面（jsp）

<%@ page contentType="text/html;charset=utf-8"%>
<%@ taglib prefix="s" uri="/struts-tags"%>

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>

<title>用户注册</title>

</head>

<body><br><br><br><br>
    <div align="center">
        ${requestScope.message}
        <s:form action="register" method="POST">
            <s:textfield name="userName" label="user name" />
            <s:password name="password" size="21" label="password" />
            <s:password name="passwordConfirm" size="21" label="passwordConfirm" />
            <s:textfield name="phoneNumber" label="phoneNumber" />
            <s:textfield name="email" label="email" />
            <s:textfield name="sexual" label="sexual" />
            <s:submit value="OK" />
        </s:form>
    </div>
</body>
</html>

其它

上面是就是一个完整的SSH2实现的注册模块，在运行之前必须先建立数据库，数据库的信息和建表命令都在上面。

JAVA值传递

Posted on 2016-05-15

Symbols count in article: 2.4k | Reading time ≈ 4 mins.

问题的来源

写项目时，有一个方法需要返回两种类型的对象，所以我将两个空白的对象作为参数传给方法，在方法里修改。修改时，我没有一条条地填上空白对象的属性，而是贪图方便，将一个新对象赋值给空白对象，结果原来的那个空白对象仍旧是空白的。

问题详情

java不同于C++，在参数传递中只有值传递，没有引用传递。在下面的方法声明里，repairOrder是一个RepairOrder对象的引用，student是一个Student对象的引用：

public boolean getDetailOfRepairOrder(int repairOrderId,
        RepairOrder repairOrder, Student student) {
    repairOrder.setName("test");
    student.setPhone(18819473231);

    RepairOrder newR = new RepairOrder();
    newR.setName("newR test");

    repairOrder = newR;
}

我将一个r和一个s传给上面的函数：

1
2
3

RepairOrder r = new RepairOrder();
Student s = new Student();
getDetailOfRepairOrder(3234234, r, s)

程序的结果是，r的name属性是test而不是newR test，为什么？

邱永臣

一个吃瓜群众，有时跑龙套,有时码字.

GitHub E-Mail

优点

缺点

System.arraycopy与Arrays.copyOf

removeElementAt(int index)与insertElementAt(E obj, int index)

synchronized

获取：public synchronized V get(Object key)

添加：public synchronized V put(K key, V value)

添加一个新的键值对：private void addEntry(int hash, K key, V value, int index)

删除：public synchronized V remove(Object key)

重散列算法：protected void rehash()

重要字段

默认容量：DEFAULT_INITIAL_CAPACITY

最大容纳因子：loadFactor

节点数组：Node<K,V>[] table

Set<Map.Entry<K,V>> entrySet

size

threshold

重要方法

计算哈希码：static final int hash(Object key)：

扩容并重散列：final Node<K,V>[] resize()

插入：final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)：将一个键值对插入HashMap

获取value：final Node<K,V> getNode(int hash, Object key)

删除：final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable)

static final int tableSizeFor(int cap)：对一个整数，求出大于它且最接近它的2的冥

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict)：将一堆数据插入HashMap

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit)：将旧数组上的树分裂到新数组上去

源码

谁是垃圾

寻找垃圾算法之引用计数法

寻找垃圾算法之可达性分析算法

清除垃圾的强有力手段

标记清除算法

标记复制算法

标记整理算法

分代收集算法

普通对象

一个普通对象的极端经历

那些超大的对象

一群长寿的对象

一群稳定的幸存者

程序计数器

虚拟机栈

本地方法栈

堆

方法区

LinkedList特性

底层数据结构

效率

实现的接口

同步机制

LinkedList字段

LinkedList方法分析

linkFirst(E e) （将一个元素插入链表头部）

linkLast(E e)（将一个元素插入链表尾部）

linkBefore(E e, Node succ) （将一个元素插到一个节点之前）

unlinkFirst(Node f)（将链表头部节点剔除）

unlinkLast(Node l)（将链表尾部节点剔除）

unlink(Node x)（剔除某个特定的节点） Read more »

ArrayList的特性

实现的接口

同步机制

时间空间复杂度

ArrayList字段

ArrayList方法分析

框架分层

步骤

Tomcat容器的配置（WebRoot/WEB-INF/web.xml）

编写用户实体（model层）

编写Hibernate的映射文件(Student.hbm.xml)

将Hibernate托管给Spring

编写DAO层代码（接口和实现）

将DAO托管给Spring

编写逻辑层代码（接口与实现）

将逻辑层托管给Spring

编写Struts2的Action

将Action托管给Spring

让Struts2找到从Spring那里找到Action

编写视图层页面（jsp）

其它

问题的来源

unlink(Node x)（剔除某个特定的节点）
Read more »