语源科技BlogJava-CarpenterLee

Java Stream API入门篇

CarpenterLee — Wed, 29 Mar 2017 13:38:00 GMT

本文github地址
你可能没意识到Java对函数式编程的重视程度，看看Java 8加入函数式编程扩充多少功能就清楚了。Java 8之所以费这么大功夫引入函数式编程，原因有二：

代码简洁，函数式编程写出的代码简洁且意图明确，使用stream接口让你从此告别for循环。
多核友好，Java函数式编程使得编写并行程序从未如此简单，你需要的全部就是调用一下parallel()方法。

这一节我们学习stream，也就是Java函数式编程的主角。对于Java 7来说stream完全是个陌生东西，stream并不是某种数据结构，它只是数据源的一种视图。这里的数据源可以是一个数组，Java容器或I/O channel等。正因如此要得到一个stream通常不会手动创建，而是调用对应的工具方法，比如：

调用Collection.stream()或者Collection.parallelStream()方法
调用Arrays.stream(T[] array)方法

常见的stream接口继承关系如图：

图中4种stream接口继承自BaseStream，其中IntStream, LongStream, DoubleStream对应三种基本类型（int, long, double，注意不是包装类型），Stream对应所有剩余类型的stream视图。为不同数据类型设置不同stream接口，可以1.提高性能，2.增加特定接口函数。

你可能会奇怪为什么不把IntStream等设计成Stream的子接口？毕竟这接口中的方法名大部分是一样的。答案是这些方法的名字虽然相同，但是返回类型不同，如果设计成父子接口关系，这些方法将不能共存，因为Java不允许只有返回类型不同的方法重载。

虽然大部分情况下stream是容器调用Collection.stream()方法得到的，但stream和collections有以下不同：

无存储。stream不是一种数据结构，它只是某种数据源的一个视图，数据源可以是一个数组，Java容器或I/O channel等。
为函数式编程而生。对stream的任何修改都不会修改背后的数据源，比如对stream执行过滤操作并不会删除被过滤的元素，而是会产生一个不包含被过滤元素的新stream。
惰式执行。stream上的操作并不会立即执行，只有等到用户真正需要结果的时候才会执行。
可消费性。stream只能被“消费”一次，一旦遍历过就会失效，就像容器的迭代器那样，想要再次遍历必须重新生成。

对stream的操作分为为两类，中间操作(intermediate operations)和结束操作(terminal operations)，二者特点是：

中间操作总是会惰式执行，调用中间操作只会生成一个标记了该操作的新stream，仅此而已。
结束操作会触发实际计算，计算发生时会把所有中间操作积攒的操作以pipeline的方式执行，这样可以减少迭代次数。计算完成之后stream就会失效。

如果你熟悉Apache Spark RDD，对stream的这个特点应该不陌生。

下表汇总了Stream接口的部分常见方法：

操作类型	接口方法
中间操作	concat() distinct() filter() flatMap() limit() map() peek() skip() sorted() parallel() sequential() unordered()
结束操作	allMatch() anyMatch() collect() count() findAny() findFirst() forEach() forEachOrdered() max() min() noneMatch() reduce() toArray()

区分中间操作和结束操作最简单的方法，就是看方法的返回值，返回值为stream的大都是中间操作，否则是结束操作。

stream方法使用

stream跟函数接口关系非常紧密，没有函数接口stream就无法工作。回顾一下：函数接口是指内部只有一个抽象方法的接口。通常函数接口出现的地方都可以使用Lambda表达式，所以不必记忆函数接口的名字。

forEach()

我们对forEach()方法并不陌生，在Collection中我们已经见过。方法签名为void forEach(Consumer action)，作用是对容器中的每个元素执行action指定的动作，也就是对元素进行遍历。

// 使用Stream.forEach()迭代
Stream stream = Stream.of("I", "love", "you", "too");
stream.forEach(str -> System.out.println(str));

由于forEach()是结束方法，上述代码会立即执行，输出所有字符串。

filter()

函数原型为Stream filter(Predicate predicate)，作用是返回一个只包含满足predicate条件元素的Stream。

// 保留长度等于3的字符串
Stream stream= Stream.of("I", "love", "you", "too");
stream.filter(str -> str.length()==3)
.forEach(str -> System.out.println(str));

上述代码将输出为长度等于3的字符串you和too。注意，由于filter()是个中间操作，如果只调用filter()不会有实际计算，因此也不会输出任何信息。

distinct()

函数原型为Stream distinct()，作用是返回一个去除重复元素之后的Stream。

Stream stream= Stream.of("I", "love", "you", "too", "too");
stream.distinct()
    .forEach(str -> System.out.println(str));

上述代码会输出去掉一个too之后的其余字符串。

sorted()

排序函数有两个，一个是用自然顺序排序，一个是使用自定义比较器排序，函数原型分别为Stream　sorted()和Stream　sorted(Comparator comparator)。

Stream stream= Stream.of("I", "love", "you", "too");
stream.sorted((str1, str2) -> str1.length()-str2.length())
    .forEach(str -> System.out.println(str));

上述代码将输出按照长度升序排序后的字符串，结果完全在预料之中。

map()

函数原型为 Stream map(Function mapper)，作用是返回一个对当前所有元素执行执行mapper之后的结果组成的Stream。直观的说，就是对每个元素按照某种操作进行转换，转换前后Stream中元素的个数不会改变，但元素的类型取决于转换之后的类型。

Stream stream　= Stream.of("I", "love", "you", "too");
stream.map(str -> str.toUpperCase())
    .forEach(str -> System.out.println(str));

上述代码将输出原字符串的大写形式。

flatMap()

函数原型为 Stream flatMap(Function> mapper)，作用是对每个元素执行mapper指定的操作，并用所有mapper返回的Stream中的元素组成一个新的Stream作为最终返回结果。说起来太拗口，通俗的讲flatMap()的作用就相当于把原stream中的所有元素都"摊平"之后组成的Stream，转换前后元素的个数和类型都可能会改变。

Stream> stream = Stream.of(Arrays.asList(1,2), Arrays.asList(3, 4, 5));
stream.flatMap(list -> list.stream())
    .forEach(i -> System.out.println(i));

上述代码中，原来的stream中有两个元素，分别是两个List，执行flatMap()之后，将每个List都“摊平”成了一个个的数字，所以会新产生一个由5个数字组成的Stream。所以最终将输出1~5这5个数字。

结语

截止到目前我们感觉良好，已介绍StreamAPI理解起来并不费劲儿。如果你就此以为函数式编程不过如此，恐怕是高兴地太早了。下一节对Stream规约操作的介绍将刷新你现在的认识。

本文github地址，欢迎关注。

CarpenterLee 2017-03-29 21:38 发表评论

《深入理解Java集合框架》系列文章

CarpenterLee — Tue, 31 May 2016 07:28:00 GMT

Introduction

关于C++标准模板库(Standard Template Library, STL)的书籍和资料有很多，关于Java集合框架(Java Collections Framework, JCF)的资料却很少，甚至很难找到一本专门介绍它的书籍，这给Java学习者们带来不小的麻烦。我深深的不解其中的原因。虽然JCF设计参考了STL，但其定位不是Java版的STL，而是要实现一个精简紧凑的容器框架，对STL的介绍自然不能替代对JCF的介绍。

本系列文章主要从数据结构和算法层面分析JCF中List, Set, Map, Stack, Queue等典型容器，结合生动图解和源代码，帮助读者对Java集合框架建立清晰而深入的理解。本文并不特意介绍Java的语言特性，但会在需要的时候做出简洁的解释。

具体内容安排如下：

Java Collections Framework概览对Java Collections Framework，以及Java语言特性做出基本介绍。
Java ArrayList源码剖析结合源码对ArrayList进行讲解。
Java LinkedList源码剖析结合源码对LinkedList进行讲解。
Java ArrayDeque源码剖析以AarryDeque为例讲解Stack和Queue。
史上最清晰的红黑树讲解（上）和史上最清晰的红黑树讲解（下）结合源码对TreeSet和TreeMap进行讲解。
Java HashSet和HashMap源码剖析结合源码对HashSet和HashMap进行讲解。
Java集合框架源码剖析：LinkedHashSet 和 LinkedHashMap 结合源码对LinkedHashSet和LinkedHashMap进行讲解。
深入理解Java PriorityQueue 结合源码对PriorityQueue进行讲解。
浅谈WeakHashMap 对WeakHashMap做出基本介绍。

Authors

Name	Weibo Id	GitHub	Mail
李豪	@计算所的小鼠标	CarpenterLee	hooleeucas@163.com

以上所有博文均在博主GitHub上有副本，并且能保证最新版本。欢迎各位博友关注。

CarpenterLee 2016-05-31 15:28 发表评论

浅谈WeakHashMap

CarpenterLee — Mon, 30 May 2016 23:27:00 GMT

Java WeakHashMap 到底Weak在哪里，它真的很弱吗？WeakHashMap 的适用场景是什么，使用时需要注意些什么？弱引用和强引用对Java GC有什么不同影响？本文将给出清晰而简洁的介绍。

总体介绍

在Java集合框架系列文章的最后，笔者打算介绍一个特殊的成员：WeakHashMap，从名字可以看出它是某种 Map。它的特殊之处在于 WeakHashMap 里的entry可能会被GC自动删除，即使程序员没有调用remove()或者clear()方法。

更直观的说，当使用 WeakHashMap 时，即使没有显示的添加或删除任何元素，也可能发生如下情况：

调用两次size()方法返回不同的值；
两次调用isEmpty()方法，第一次返回false，第二次返回true；
两次调用containsKey()方法，第一次返回true，第二次返回false，尽管两次使用的是同一个key；
两次调用get()方法，第一次返回一个value，第二次返回null，尽管两次使用的是同一个对象。

遇到这么奇葩的现象，你是不是觉得使用者一定会疯掉？其实不然，WeekHashMap 的这个特点特别适用于需要缓存的场景。在缓存场景下，由于内存是有限的，不能缓存所有对象；对象缓存命中可以提高系统效率，但缓存MISS也不会造成错误，因为可以通过计算重新得到。

要明白 WeekHashMap 的工作原理，还需要引入一个概念：弱引用（WeakReference）。我们都知道Java中内存是通过GC自动管理的，GC会在程序运行过程中自动判断哪些对象是可以被回收的，并在合适的时机进行内存释放。GC判断某个对象是否可被回收的依据是，是否有有效的引用指向该对象。如果没有有效引用指向该对象（基本意味着不存在访问该对象的方式），那么该对象就是可回收的。这里的“有效引用”并不包括弱引用。也就是说，虽然弱引用可以用来访问对象，但进行垃圾回收时弱引用并不会被考虑在内，仅有弱引用指向的对象仍然会被GC回收。

WeakHashMap 内部是通过弱引用来管理entry的，弱引用的特性对应到 WeakHashMap 上意味着什么呢？将一对key, value放入到 WeakHashMap 里并不能避免该key值被GC回收，除非在 WeakHashMap 之外还有对该key的强引用。

关于强引用，弱引用等概念以后再具体讲解，这里只需要知道Java中引用也是分种类的，并且不同种类的引用对GC的影响不同就够了。

具体实现

WeakHashMap的存储结构类似于HashMap，读者可自行参考前文，这里不再赘述。

关于强弱引用的管理方式，博主将会另开专题单独讲解。

Weak HashSet?

如果你看过前几篇关于 Map 和 Set 的讲解，一定会问：既然有 WeekHashMap，是否有 WeekHashSet 呢？答案是没有:( 。不过Java Collections工具类给出了解决方案，Collections.newSetFromMap(Map map)方法可以将任何 Map包装成一个Set。通过如下方式可以快速得到一个 Weak HashSet：

// 将WeakHashMap包装成一个Set
Set weakHashSet = Collections.newSetFromMap(
new WeakHashMap());

不出你所料，newSetFromMap()方法只是对传入的 Map做了简单包装：

// Collections.newSetFromMap()用于将任何Map包装成一个Set
public static  Set newSetFromMap(Map map) {
    return new SetFromMap<>(map);
}

private static class SetFromMap extends AbstractSet
    implements Set, Serializable
{
    private final Map m;  // The backing map
    private transient Set s;       // Its keySet
    SetFromMap(Map map) {
        if (!map.isEmpty())
            throw new IllegalArgumentException("Map is non-empty");
        m = map;
        s = map.keySet();
    }
    public void clear()               {        m.clear(); }
    public int size()                 { return m.size(); }
    public boolean isEmpty()          { return m.isEmpty(); }
    public boolean contains(Object o) { return m.containsKey(o); }
    public boolean remove(Object o)   { return m.remove(o) != null; }
    public boolean add(E e) { return m.put(e, Boolean.TRUE) == null; }
    public Iterator iterator()     { return s.iterator(); }
    public Object[] toArray()         { return s.toArray(); }
    public  T[] toArray(T[] a)     { return s.toArray(a); }
    public String toString()          { return s.toString(); }
    public int hashCode()             { return s.hashCode(); }
    public boolean equals(Object o)   { return o == this || s.equals(o); }
    public boolean containsAll(Collection c) {return s.containsAll(c);}
    public boolean removeAll(Collection c)   {return s.removeAll(c);}
    public boolean retainAll(Collection c)   {return s.retainAll(c);}
    // addAll is the only inherited implementation

}

结语

至此深入Java集合框架(Java Collections Framework Internals)系列已经全部讲解完毕，希望这几篇简短的博文能够帮助各位读者对Java容器框架建立基本的理解。通过这里可以返回本系列文章目录。

如果对各位有哪怕些微的帮助，博主将感到非常高兴！如果博文中有任何的纰漏和谬误，欢迎各位博友指正。

本文GitHub地址

CarpenterLee 2016-05-31 07:27 发表评论

Java集合框架源码剖析：LinkedHashSet 和 LinkedHashMap

CarpenterLee — Mon, 30 May 2016 01:19:00 GMT

Java LinkedHashMap和HashMap有什么区别和联系？为什么LinkedHashMap会有着更快的迭代速度？LinkedHashSet跟LinkedHashMap有着怎样的内在联系？本文从数据结构和算法层面，结合生动图解为读者一一解答。

本文github地址

总体介绍

如果你已看过前面关于HashSet和HashMap，以及TreeSet和TreeMap的讲解，一定能够想到本文将要讲解的LinkedHashSet和LinkedHashMap其实也是一回事。LinkedHashSet和LinkedHashMap在Java里也有着相同的实现，前者仅仅是对后者做了一层包装，也就是说LinkedHashSet里面有一个LinkedHashMap（适配器模式）。因此本文将重点分析LinkedHashMap。

LinkedHashMap实现了Map接口，即允许放入key为null的元素，也允许插入value为null的元素。从名字上可以看出该容器是linked list和HashMap的混合体，也就是说它同时满足HashMap和linked list的某些特性。可将LinkedHashMap看作采用linked list增强的HashMap。

事实上LinkedHashMap是HashMap的直接子类，二者唯一的区别是LinkedHashMap在HashMap的基础上，采用双向链表（doubly-linked list）的形式将所有entry连接起来，这样是为保证元素的迭代顺序跟插入顺序相同。上图给出了LinkedHashMap的结构图，主体部分跟HashMap完全一样，多了header指向双向链表的头部（是一个哑元），该双向链表的迭代顺序就是entry的插入顺序。

除了可以保迭代历顺序，这种结构还有一个好处：迭代LinkedHashMap时不需要像HashMap那样遍历整个table，而只需要直接遍历header指向的双向链表即可，也就是说LinkedHashMap的迭代时间就只跟entry的个数相关，而跟table的大小无关。

有两个参数可以影响LinkedHashMap的性能：初始容量（inital capacity）和负载系数（load factor）。初始容量指定了初始table的大小，负载系数用来指定自动扩容的临界值。当entry的数量超过capacity*load_factor时，容器将自动扩容并重新哈希。对于插入元素较多的场景，将初始容量设大可以减少重新哈希的次数。

将对象放入到LinkedHashMap或LinkedHashSet中时，有两个方法需要特别关心：hashCode()和equals()。hashCode()方法决定了对象会被放到哪个bucket里，当多个对象的哈希值冲突时，equals()方法决定了这些对象是否是“同一个对象”。所以，如果要将自定义的对象放入到LinkedHashMap或LinkedHashSet中，需要*@Override*hashCode()和equals()方法。

通过如下方式可以得到一个跟源Map迭代顺序一样的LinkedHashMap：

void foo(Map m) {
Map copy = new LinkedHashMap(m);

}

出于性能原因，LinkedHashMap是非同步的（not synchronized），如果需要在多线程环境使用，需要程序员手动同步；或者通过如下方式将LinkedHashMap包装成（wrapped）同步的：

Map m = Collections.synchronizedMap(new LinkedHashMap(...));

方法剖析

get()

get(Object key)方法根据指定的key值返回对应的value。该方法跟HashMap.get()方法的流程几乎完全一样，读者可自行参考前文，这里不再赘述。

put()

put(K key, V value)方法是将指定的key, value对添加到map里。该方法首先会对map做一次查找，看是否包含该元组，如果已经包含则直接返回，查找过程类似于get()方法；如果没有找到，则会通过addEntry(int hash, K key, V value, int bucketIndex)方法插入新的entry。

注意，这里的插入有两重含义：

从table的角度看，新的entry需要插入到对应的bucket里，当有哈希冲突时，采用头插法将新的entry插入到冲突链表的头部。
从header的角度看，新的entry需要插入到双向链表的尾部。

addEntry()代码如下：

// LinkedHashMap.addEntry()
void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);// 自动扩容，并重新哈希
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = hash & (table.length-1);// hash%table.length
    }
    // 1.在冲突链表头部插入新的entry
    HashMap.Entry old = table[bucketIndex];
    Entry e = new Entry<>(hash, key, value, old);
    table[bucketIndex] = e;
    // 2.在双向链表的尾部插入新的entry
    e.addBefore(header);
    size++;
}

上述代码中用到了addBefore()方法将新entry e插入到双向链表头引用header的前面，这样e就成为双向链表中的最后一个元素。addBefore()的代码如下：

// LinkedHashMap.Entry.addBefor()，将this插入到existingEntry的前面
private void addBefore(Entry existingEntry) {
    after  = existingEntry;
    before = existingEntry.before;
    before.after = this;
    after.before = this;
}

上述代码只是简单修改相关entry的引用而已。

remove()

remove(Object key)的作用是删除key值对应的entry，该方法的具体逻辑是在removeEntryForKey(Object key)里实现的。removeEntryForKey()方法会首先找到key值对应的entry，然后删除该entry（修改链表的相应引用）。查找过程跟get()方法类似。

注意，这里的删除也有两重含义：

从table的角度看，需要将该entry从对应的bucket里删除，如果对应的冲突链表不空，需要修改冲突链表的相应引用。
从header的角度来看，需要将该entry从双向链表中删除，同时修改链表中前面以及后面元素的相应引用。

removeEntryForKey()对应的代码如下：

// LinkedHashMap.removeEntryForKey()，删除key值对应的entry
final Entry removeEntryForKey(Object key) {

    int hash = (key == null) ? 0 : hash(key);
    int i = indexFor(hash, table.length);// hash&(table.length-1)
    Entry prev = table[i];// 得到冲突链表
    Entry e = prev;
    while (e != null) {// 遍历冲突链表
        Entry next = e.next;
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {// 找到要删除的entry
            modCount++; size--;
            // 1. 将e从对应bucket的冲突链表中删除
            if (prev == e) table[i] = next;
            else prev.next = next;
            // 2. 将e从双向链表中删除
            e.before.after = e.after;
            e.after.before = e.before;
            return e;
        }
        prev = e; e = next;
    }
    return e;
}

LinkedHashSet

前面已经说过LinkedHashSet是对LinkedHashMap的简单包装，对LinkedHashSet的函数调用都会转换成合适的LinkedHashMap方法，因此LinkedHashSet的实现非常简单，这里不再赘述。

public class LinkedHashSet
    extends HashSet
    implements Set, Cloneable, java.io.Serializable {

    // LinkedHashSet里面有一个LinkedHashMap
    public LinkedHashSet(int initialCapacity, float loadFactor) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

    public boolean add(E e) {//简单的方法转换
        return map.put(e, PRESENT)==null;
    }

}

CarpenterLee 2016-05-30 09:19 发表评论

史上最清晰的红黑树讲解（下）

CarpenterLee — Wed, 25 May 2016 08:48:00 GMT

本文github地址

上一篇文章史上最清晰的红黑树讲解（上）对Java TreeMap的插入以及插入之后的调整过程给出了详述。本文接着以Java TreeMap为例，从源码层面讲解红黑树的删除，以及删除之后的调整过程。如果还没有看过上一篇文章，请在阅读本文之前大致浏览一下前文，以方便理解。

寻找节点后继

对于一棵二叉查找树，给定节点t，其后继（树种比大于t的最小的那个元素）可以通过如下方式找到：

t的右子树不空，则t的后继是其右子树中最小的那个元素。
t的右孩子为空，则t的后继是其第一个向左走的祖先。

后继节点在红黑树的删除操作中将会用到。

TreeMap中寻找节点后继的代码如下：

// 寻找节点后继函数successor()
static  TreeMap.Entry successor(Entry t) {
    if (t == null)
        return null;
    else if (t.right != null) {// 1. t的右子树不空，则t的后继是其右子树中最小的那个元素
        Entry p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {// 2. t的右孩子为空，则t的后继是其第一个向左走的祖先
        Entry p = t.parent;
        Entry ch = t;
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

remove()

remove(Object key)的作用是删除key值对应的entry，该方法首先通过上文中提到的getEntry(Object key)方法找到key值对应的entry，然后调用deleteEntry(Entry entry)删除对应的entry。由于删除操作会改变红黑树的结构，有可能破坏红黑树的约束条件，因此有可能要进行调整。

getEntry()函数前面已经讲解过，这里重点放deleteEntry()上，该函数删除指定的entry并在红黑树的约束被破坏时进行调用fixAfterDeletion(Entry x)进行调整。

由于红黑树是一棵增强版的二叉查找树，红黑树的删除操作跟普通二叉查找树的删除操作也就非常相似，唯一的区别是红黑树在节点删除之后可能需要进行调整。现在考虑一棵普通二叉查找树的删除过程，可以简单分为两种情况：

删除点p的左右子树都为空，或者只有一棵子树非空。
删除点p的左右子树都非空。

对于上述情况1，处理起来比较简单，直接将p删除（左右子树都为空时），或者用非空子树替代p（只有一棵子树非空时）；对于情况2，可以用p的后继s（树中大于x的最小的那个元素）代替p，然后使用情况1删除s（此时s一定满足情况1，可以画画看）。

基于以上逻辑，红黑树的节点删除函数deleteEntry()代码如下：

// 红黑树entry删除函数deleteEntry()
private void deleteEntry(Entry p) {
    modCount++;
    size--;
    if (p.left != null && p.right != null) {// 2. 删除点p的左右子树都非空。
        Entry s = successor(p);// 后继
        p.key = s.key;
        p.value = s.value;
        p = s;
    }
    Entry replacement = (p.left != null ? p.left : p.right);
    if (replacement != null) {// 1. 删除点p只有一棵子树非空。
        replacement.parent = p.parent;
        if (p.parent == null)
            root = replacement;
        else if (p == p.parent.left)
            p.parent.left  = replacement;
        else
            p.parent.right = replacement;
        p.left = p.right = p.parent = null;
        if (p.color == BLACK)
            fixAfterDeletion(replacement);// 调整
    } else if (p.parent == null) {
        root = null;
    } else { // 1. 删除点p的左右子树都为空
        if (p.color == BLACK)
            fixAfterDeletion(p);// 调整
        if (p.parent != null) {
            if (p == p.parent.left)
                p.parent.left = null;
            else if (p == p.parent.right)
                p.parent.right = null;
            p.parent = null;
        }
    }
}

上述代码中占据大量代码行的，是用来修改父子节点间引用关系的代码，其逻辑并不难理解。下面着重讲解删除后调整函数fixAfterDeletion()。首先请思考一下，删除了哪些点才会导致调整？只有删除点是BLACK的时候，才会触发调整函数，因为删除RED节点不会破坏红黑树的任何约束，而删除BLACK节点会破坏规则4。

跟上文中讲过的fixAfterInsertion()函数一样，这里也要分成若干种情况。记住，无论有多少情况，具体的调整操作只有两种：1.改变某些节点的颜色，2.对某些节点进行旋转。

上述图解的总体思想是：将情况1首先转换成情况2，或者转换成情况3和情况4。当然，该图解并不意味着调整过程一定是从情况1开始。通过后续代码我们还会发现几个有趣的规则：a).如果是由情况1之后紧接着进入的情况2，那么情况2之后一定会退出循环（因为x为红色）；b).一旦进入情况3和情况4，一定会退出循环（因为x为root）。

删除后调整函数fixAfterDeletion()的具体代码如下，其中用到了上文中提到的rotateLeft()和rotateRight()函数。通过代码我们能够看到，情况3其实是落在情况4内的。情况5～情况8跟前四种情况是对称的，因此图解中并没有画出后四种情况，读者可以参考代码自行理解。

private void fixAfterDeletion(Entry x) {
    while (x != root && colorOf(x) == BLACK) {
        if (x == leftOf(parentOf(x))) {
            Entry sib = rightOf(parentOf(x));
            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);                   // 情况1
                setColor(parentOf(x), RED);             // 情况1
                rotateLeft(parentOf(x));                // 情况1
                sib = rightOf(parentOf(x));             // 情况1
            }
            if (colorOf(leftOf(sib))  == BLACK &&
                colorOf(rightOf(sib)) == BLACK) {
                setColor(sib, RED);                     // 情况2
                x = parentOf(x);                        // 情况2
            } else {
                if (colorOf(rightOf(sib)) == BLACK) {
                    setColor(leftOf(sib), BLACK);       // 情况3
                    setColor(sib, RED);                 // 情况3
                    rotateRight(sib);                   // 情况3
                    sib = rightOf(parentOf(x));         // 情况3
                }
                setColor(sib, colorOf(parentOf(x)));    // 情况4
                setColor(parentOf(x), BLACK);           // 情况4
                setColor(rightOf(sib), BLACK);          // 情况4
                rotateLeft(parentOf(x));                // 情况4
                x = root;                               // 情况4
            }
        } else { // 跟前四种情况对称
            Entry sib = leftOf(parentOf(x));
            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);                   // 情况5
                setColor(parentOf(x), RED);             // 情况5
                rotateRight(parentOf(x));               // 情况5
                sib = leftOf(parentOf(x));              // 情况5
            }
            if (colorOf(rightOf(sib)) == BLACK &&
                colorOf(leftOf(sib)) == BLACK) {
                setColor(sib, RED);                     // 情况6
                x = parentOf(x);                        // 情况6
            } else {
                if (colorOf(leftOf(sib)) == BLACK) {
                    setColor(rightOf(sib), BLACK);      // 情况7
                    setColor(sib, RED);                 // 情况7
                    rotateLeft(sib);                    // 情况7
                    sib = leftOf(parentOf(x));          // 情况7
                }
                setColor(sib, colorOf(parentOf(x)));    // 情况8
                setColor(parentOf(x), BLACK);           // 情况8
                setColor(leftOf(sib), BLACK);           // 情况8
                rotateRight(parentOf(x));               // 情况8
                x = root;                               // 情况8
            }
        }
    }
    setColor(x, BLACK);
}

TreeSet

前面已经说过TreeSet是对TeeMap的简单包装，对TreeSet的函数调用都会转换成合适的TeeMap方法，因此TreeSet的实现非常简单。这里不再赘述。

// TreeSet是对TreeMap的简单包装
public class TreeSet extends AbstractSet
    implements NavigableSet, Cloneable, java.io.Serializable
{

    private transient NavigableMap m;
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
    public TreeSet() {
        this.m = new TreeMap();// TreeSet里面有一个TreeMap
    }

    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }

}

CarpenterLee 2016-05-25 16:48 发表评论

史上最清晰的红黑树讲解（上）

CarpenterLee — Tue, 17 May 2016 23:57:00 GMT

本文github地址

本文以Java TreeMap为例，从源代码层面，结合详细的图解，剥茧抽丝地讲解红黑树（Red-Black tree）的插入，删除以及由此产生的调整过程。

总体介绍

Java TreeMap实现了SortedMap接口，也就是说会按照key的大小顺序对Map中的元素进行排序，key大小的评判可以通过其本身的自然顺序（natural ordering），也可以通过构造时传入的比较器（Comparator）。

TreeMap底层通过红黑树（Red-Black tree）实现，也就意味着containsKey(), get(), put(), remove()都有着log(n)的时间复杂度。其具体算法实现参照了《算法导论》。

出于性能原因，TreeMap是非同步的（not synchronized），如果需要在多线程环境使用，需要程序员手动同步；或者通过如下方式将TreeMap包装成（wrapped）同步的：

SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

红黑树是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一陪。具体来说，红黑树是满足如下条件的二叉查找树（binary search tree）：

每个节点要么是红色，要么是黑色。
根节点必须是黑色
红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）。
对于每个节点，从该点至null（树尾端）的任何路径，都含有相同个数的黑色节点。

在树的结构发生改变时（插入或者删除操作），往往会破坏上述条件3或条件4，需要通过调整使得查找树重新满足红黑树的条件。

预备知识

前文说到当查找树的结构发生改变时，红黑树的条件可能被破坏，需要通过调整使得查找树重新满足红黑树的条件。调整可以分为两类：一类是颜色调整，即改变某个节点的颜色；另一类是结构调整，集改变检索树的结构关系。结构调整过程包含两个基本操作：左旋（Rotate Left），右旋（RotateRight）。

左旋

左旋的过程是将x的右子树绕x逆时针旋转，使得x的右子树成为x的父亲，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。

TreeMap中左旋代码如下：

//Rotate Left
private void rotateLeft(Entry p) {
    if (p != null) {
        Entry r = p.right;
        p.right = r.left;
        if (r.left != null)
            r.left.parent = p;
        r.parent = p.parent;
        if (p.parent == null)
            root = r;
        else if (p.parent.left == p)
            p.parent.left = r;
        else
            p.parent.right = r;
        r.left = p;
        p.parent = r;
    }
}

右旋

右旋的过程是将x的左子树绕x顺时针旋转，使得x的左子树成为x的父亲，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。

TreeMap中右旋代码如下：

//Rotate Right
private void rotateRight(Entry p) {
    if (p != null) {
        Entry l = p.left;
        p.left = l.right;
        if (l.right != null) l.right.parent = p;
        l.parent = p.parent;
        if (p.parent == null)
            root = l;
        else if (p.parent.right == p)
            p.parent.right = l;
        else p.parent.left = l;
        l.right = p;
        p.parent = l;
    }
}

方法剖析

get()

get(Object key)方法根据指定的key值返回对应的value，该方法调用了getEntry(Object key)得到相应的entry，然后返回entry.value。因此getEntry()是算法的核心。算法思想是根据key的自然顺序（或者比较器顺序）对二叉查找树进行查找，直到找到满足k.compareTo(p.key) == 0的entry。

具体代码如下：

//getEntry()方法
final Entry getEntry(Object key) {

    if (key == null)//不允许key值为null
        throw new NullPointerException();
    Comparablesuper K> k = (Comparablesuper K>) key;//使用元素的自然顺序
    Entry p = root;
    while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0)//向左找
            p = p.left;
        else if (cmp > 0)//向右找
            p = p.right;
        else
            return p;
    }
    return null;
}

put()

put(K key, V value)方法是将指定的key, value对添加到map里。该方法首先会对map做一次查找，看是否包含该元组，如果已经包含则直接返回，查找过程类似于getEntry()方法；如果没有找到则会在红黑树中插入新的entry，如果插入之后破坏了红黑树的约束，还需要进行调整（旋转，改变某些节点的颜色）。

public V put(K key, V value) {

    int cmp;
    Entry parent;
    if (key == null)
        throw new NullPointerException();
    Comparablesuper K> k = (Comparablesuper K>) key;//使用元素的自然顺序
    do {
        parent = t;
        cmp = k.compareTo(t.key);
        if (cmp < 0) t = t.left;//向左找
        else if (cmp > 0) t = t.right;//向右找
        else return t.setValue(value);
    } while (t != null);
    Entry e = new Entry<>(key, value, parent);//创建并插入新的entry
    if (cmp < 0) parent.left = e;
    else parent.right = e;
    fixAfterInsertion(e);//调整
    size++;
    return null;
}

上述代码的插入部分并不难理解：首先在红黑树上找到合适的位置，然后创建新的entry并插入（当然，新插入的节点一定是树的叶子）。难点是调整函数fixAfterInsertion()，前面已经说过，调整往往需要1.改变某些节点的颜色，2.对某些节点进行旋转。

调整函数fixAfterInsertion()的具体代码如下，其中用到了上文中提到的rotateLeft()和rotateRight()函数。通过代码我们能够看到，情况2其实是落在情况3内的。情况4～情况6跟前三种情况是对称的，因此图解中并没有画出后三种情况，读者可以参考代码自行理解。

//红黑树调整函数fixAfterInsertion()
private void fixAfterInsertion(Entry x) {
    x.color = RED;
    while (x != null && x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Entry y = rightOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {//如果y为null，则视为BLACK
setColor(parentOf(x), BLACK);   // 情况1
                setColor(y, BLACK); // 情况1
                setColor(parentOf(parentOf(x)), RED);   // 情况1
                x = parentOf(parentOf(x)); // 情况1
            } else {
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);   // 情况2
                    rotateLeft(x); // 情况2
                }
                setColor(parentOf(x), BLACK); // 情况3
                setColor(parentOf(parentOf(x)), RED); // 情况3
                rotateRight(parentOf(parentOf(x))); // 情况3
            }
        } else {
            Entry y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK); // 情况4
                setColor(y, BLACK);   // 情况4
                setColor(parentOf(parentOf(x)), RED); // 情况4
                x = parentOf(parentOf(x)); // 情况4
            } else {
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);   // 情况5
                    rotateRight(x); // 情况5
                }
                setColor(parentOf(x), BLACK);   // 情况6
                setColor(parentOf(parentOf(x)), RED); // 情况6
                rotateLeft(parentOf(parentOf(x)));   // 情况6
            }
        }
    }
    root.color = BLACK;
}

remove()

有关remove()的具体讲解将放到下一篇博文当中，敬请期待！

CarpenterLee 2016-05-18 07:57 发表评论

Java PriorityQueue源码剖析

CarpenterLee — Thu, 12 May 2016 13:22:00 GMT

摘要: Java中PriorityQueue通过二叉小顶堆实现，可以用一棵完全二叉树表示。本文从Queue接口函数出发，结合生动的图解，深入浅出地分析PriorityQueue每个操作的具体过程和开销，将有助于您对该容器建立清晰明了的认识。阅读全文

CarpenterLee 2016-05-12 21:22 发表评论

为什么你的博客不够火？

CarpenterLee — Wed, 11 May 2016 01:02:00 GMT

CNBlog首页博客热度分析

本文github地址

前言

每个博客园的园友或许都会有这种经历：自己辛辛苦苦，认认真真的写了篇博客，然后满心欢喜的发到了博客园首页，当你以为大功告成坐等点击量暴表的时候，却发现自己的博文根本无人问津。那将是何等的痛苦:(

不要再自我怀疑，不要再自怨自艾，博客不火，不一定是博文内容不够严谨深入，也不一定是你能力不足，而可能仅仅是因为你选择了错误的发表时机。

本文基于博客园近3个月4000篇首页博文，运用大数据分析，机器学习，文本挖掘等先进技术，深入而细致的剖析决定博客热度的若干因素，让您从此也能写出精湛的技术博客，成为博客园的技术达人（做梦到此结束...）。

技术实现

经分析，博客园首页网页结构比较简洁，通过爬虫抓取http://www.cnblogs.com/sitehome/p/your_page_num 连接下的内容，即可获取所有首页博文。本文采用的是jsoup这个Java HTML Parser进行的网页抓取。博客园页码只支持到200，每页20篇，也就是最多能够抓取4000篇首页博客。对数据进行清洗后存储到文件，供下一步分析。

由于数据量并不大，分析数据采用的是excel表格。不要觉得low，用表格来处理小规模数据，效果不亚于数据库。

分析结果

博友们一天之内喜欢什么时候发博客？

哪个时间段发的博客更容易火？

我们对一天中不同时间段发表的博客进行统计，然后计算每个小时内的博客发表量，以及当前这个小时每篇博客的平均热度。这里的热度是用来衡量一篇博文受欢迎程度的综合指标，计算公式为：

hot=(recommend*10+comment*5+view)

为避免离群点，当hot值超过1600时则按1600处理。上图中标注的热度（红色线）为对文章热度求平均之后，然后做归一化(avg_hot/800*100%)之后的结果。

从上图可以明显看出，一天之内有三个时间段大家比较爱发博客，分别是10:00左右，16:00左右和22:00左右，这分别对应的是上午上班时间，下午上班时间，和晚上加班时间。一天内也有三个时间段大家不怎么爱发博客，分别是1:00~7:00，12:00左右，19:00左右，分别对应大家的睡觉时间，午饭时间和下班时间。

什么时候发的博客更容易火呢？抛开凌晨那段时间不提（因为博客量太少），上图可以看出，早上8:00左右发的博客热度最高，中午12:00左右和晚上22:00左右也是个热度小高峰。

对比上图中的蓝线和红线，我们发现博客发表高峰和访问高峰（热度评估主要基于访问量，所以热度表示了访问量的趋势）并不总是成比例。具体表现如下：

早上8:00是一天中访问量最高的时候，但博客发表并不是很多（上班路上大家刷刷博客？）

上午10:00左右是博客发表的高峰，但访问量却呈下降趋势（忙着写自己的博客而忘记看别人的博客）

中午12:00左右访问量很高，但博客发表量却出奇的低（吃饭的时候不写博客，倒是可以手机刷刷博客）

大家一周之内喜欢在哪一天发博客？

一周之内哪一天发的博客更容易火？

我们对一周中不同天发表的博客进行统计，然后计算每天的博客发表量，以及当天每篇博客的平均热度。

通过上图可以看出：

星期一和星期二是博客发表的热潮（上班前两天不但工作积极，写博客也很积极）

之后一直下降，到周六达到最低谷（终于盼来周末，谁还写博客！）。

博客热度跟发表量基本吻合，可见工作日大家不但工作热情高，写博客和读博客的热情都不低。

到了周末，写博客的人少，看博客的人更少！

周四博客阅读量出现了回升，你可以帮忙想想是为什么。

上图意味着，周末还是老老实实的出去玩吧，即使写了博客也不会有人看的。特别是周六，千万不要在周六发表技术博客，切记切记！

总结

经过以上分析，我们得出结论：为了避免吃力不讨好的情况，发表博客一定要认准时机。

博客想要火，就不能睡懒觉，因为你要在8:00钟左右发表博客。
更不能吃午饭，因为你还要在12:00左右发表博客。
当然，为了犒劳以下忙碌一周的你，周末切记不要苦逼的写博客，因为即使写得再认真也不会有人看。
周一，周二以及周四，才是您发表博客的黄道吉日。

以上四项基本原则，一定要牢记于心，切记不要轻易违背。否则没有点击量，你的博客还不如写道日记本里。

未来的工作

博客热度不仅跟发表时间有关，当然也跟博客内容，以及博主的个人影响力等诸多因素相关。希望各位博友能够加入更多分析。

本文用到的所有代码和数据，都已经放到了博主github上，欢迎各位博友切磋。

CarpenterLee 2016-05-11 09:02 发表评论

Java ArrayDeque源码剖析

CarpenterLee — Sat, 07 May 2016 10:30:00 GMT

ArrayDeque

本文github地址

前言

Java里有一个叫做Stack的类，却没有叫做Queue的类（它是个接口名字）。当需要使用栈时，Java已不推荐使用Stack，而是推荐使用更高效的ArrayDeque；既然Queue只是一个接口，当需要使用队列时也就首选ArrayDeque了（次选是LinkedList）。

总体介绍

要讲栈和队列，首先要讲Deque接口。Deque的含义是“double ended queue”，即双端队列，它既可以当作栈使用，也可以当作队列使用。下表列出了Deque与Queue相对应的接口：

Queue Method	Equivalent Deque Method	说明
`add(e)`	`addLast(e)`	向队尾插入元素，失败则抛出异常
`offer(e)`	`offerLast(e)`	向队尾插入元素，失败则返回`false`
`remove()`	`removeFirst()`	获取并删除队首元素，失败则抛出异常
`poll()`	`pollFirst()`	获取并删除队首元素，失败则返回`null`
`element()`	`getFirst()`	获取但不删除队首元素，失败则抛出异常
`peek()`	`peekFirst()`	获取但不删除队首元素，失败则返回`null`

下表列出了Deque与Stack对应的接口：

Stack Method	Equivalent Deque Method	说明
`push(e)`	`addFirst(e)`	向栈顶插入元素，失败则抛出异常
无	`offerFirst(e)`	向栈顶插入元素，失败则返回`false`
`pop()`	`removeFirst()`	获取并删除栈顶元素，失败则抛出异常
无	`pollFirst()`	获取并删除栈顶元素，失败则返回`null`
`peek()`	`peekFirst()`	获取但不删除栈顶元素，失败则抛出异常
无	`peekFirst()`	获取但不删除栈顶元素，失败则返回`null`

上面两个表共定义了Deque的12个接口。添加，删除，取值都有两套接口，它们功能相同，区别是对失败情况的处理不同。一套接口遇到失败就会抛出异常，另一套遇到失败会返回特殊值（false或null）。除非某种实现对容量有限制，大多数情况下，添加操作是不会失败的。虽然Deque的接口有12个之多，但无非就是对容器的两端进行操作，或添加，或删除，或查看。明白了这一点讲解起来就会非常简单。

ArrayDeque和LinkedList是Deque的两个通用实现，由于官方更推荐使用AarryDeque用作栈和队列，加之上一篇已经讲解过LinkedList，本文将着重讲解ArrayDeque的具体实现。

从名字可以看出ArrayDeque底层通过数组实现，为了满足可以同时在数组两端插入或删除元素的需求，该数组还必须是循环的，即循环数组（circular array），也就是说数组的任何一点都可能被看作起点或者终点。ArrayDeque是非线程安全的（not thread-safe），当多个线程同时使用的时候，需要程序员手动同步；另外，该容器不允许放入null元素。

上图中我们看到，head指向首端第一个有效元素，tail指向尾端第一个可以插入元素的空位。因为是循环数组，所以head不一定总等于0，tail也不一定总是比head大。

方法剖析

addFirst()

addFirst(E e)的作用是在Deque的首端插入元素，也就是在head的前面插入元素，在空间足够且下标没有越界的情况下，只需要将elements[--head] = e即可。

实际需要考虑：1.空间是否够用，以及2.下标是否越界的问题。上图中，如果head为0之后接着调用addFirst()，虽然空余空间还够用，但head为-1，下标越界了。下列代码很好的解决了这两个问题。

//addFirst(E e)
public void addFirst(E e) {
    if (e == null)//不允许放入null
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;//2.下标是否越界
    if (head == tail)//1.空间是否够用
        doubleCapacity();//扩容
}

上述代码我们看到，空间问题是在插入之后解决的，因为tail总是指向下一个可插入的空位，也就意味着elements数组至少有一个空位，所以插入元素的时候不用考虑空间问题。

下标越界的处理解决起来非常简单，head = (head - 1) & (elements.length - 1)就可以了，这段代码相当于取余，同时解决了head为负值的情况。因为elements.length必需是2的指数倍，elements - 1就是二进制低位全1，跟head - 1相与之后就起到了取模的作用，如果head - 1为负数（其实只可能是-1），则相当于对其取相对于elements.length的补码。

下面再说说扩容函数doubleCapacity()，其逻辑是申请一个更大的数组（原数组的两倍），然后将原数组复制过去。过程如下图所示：

图中我们看到，复制分两次进行，第一次复制head右边的元素，第二次复制head左边的元素。

//doubleCapacity()
private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // head右边元素的个数
    int newCapacity = n << 1;//原空间的2倍
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    Object[] a = new Object[newCapacity];
    System.arraycopy(elements, p, a, 0, r);//复制右半部分，对应上图中绿色部分
    System.arraycopy(elements, 0, a, r, p);//复制左半部分，对应上图中灰色部分
    elements = (E[])a;
    head = 0;
    tail = n;
}

addLast()

addLast(E e)的作用是在Deque的尾端插入元素，也就是在tail的位置插入元素，由于tail总是指向下一个可以插入的空位，因此只需要elements[tail] = e;即可。插入完成后再检查空间，如果空间已经用光，则调用doubleCapacity()进行扩容。

public void addLast(E e) {
    if (e == null)//不允许放入null
        throw new NullPointerException();
    elements[tail] = e;//赋值
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)//下标越界处理
        doubleCapacity();//扩容
}

下标越界处理方式addFirt()中已经讲过，不再赘述。

pollFirst()

pollFirst()的作用是删除并返回Deque首端元素，也即是head位置处的元素。如果容器不空，只需要直接返回elements[head]即可，当然还需要处理下标的问题。由于ArrayDeque中不允许放入null，当elements[head] == null时，意味着容器为空。

public E pollFirst() {
    E result = elements[head];
    if (result == null)//null值意味着deque为空
        return null;
    elements[h] = null;//let GC work
    head = (head + 1) & (elements.length - 1);//下标越界处理
    return result;
}

pollLast()

pollLast()的作用是删除并返回Deque尾端元素，也即是tail位置前面的那个元素。

public E pollLast() {
    int t = (tail - 1) & (elements.length - 1);//tail的上一个位置是最后一个元素
    E result = elements[t];
    if (result == null)//null值意味着deque为空
        return null;
    elements[t] = null;//let GC work
    tail = t;
    return result;
}

peekFirst()

peekFirst()的作用是返回但不删除Deque首端元素，也即是head位置处的元素，直接返回elements[head]即可。

public E peekFirst() {
return elements[head]; // elements[head] is null if deque empty
}

peekLast()

peekLast()的作用是返回但不删除Deque尾端元素，也即是tail位置前面的那个元素。

public E peekLast() {
return elements[(tail - 1) & (elements.length - 1)];
}

CarpenterLee 2016-05-07 18:30 发表评论

Java LinkedList源码剖析

CarpenterLee — Wed, 04 May 2016 00:35:00 GMT

LinkedList

本文github地址

总体介绍

LinkedList同时实现了List接口和Deque接口，也就是说它既可以看作一个顺序容器，又可以看作一个队列（Queue），同时又可以看作一个栈（Stack）。这样看来，LinkedList简直就是个全能冠军。当你需要使用栈或者队列时，可以考虑使用LinkedList，一方面是因为Java官方已经声明不建议使用Stack类，更遗憾的是，Java里根本没有一个叫做Queue的类（它是个接口名字）。关于栈或队列，现在的首选是ArrayDeque，它有着比LinkedList（当作栈或队列使用时）有着更好的性能。

LinkedList底层通过双向链表实现，本节将着重讲解插入和删除元素时双向链表的维护过程，也即是之间解跟List接口相关的函数，而将Queue和Stack以及Deque相关的知识放在下一节讲。双向链表的每个节点用内部类Node表示。LinkedList通过first和last引用分别指向链表的第一个和最后一个元素。注意这里没有所谓的哑元，当链表为空的时候first和last都指向null。

//Node内部类
private static class Node {
    E item;
    Node next;
    Node prev;
    Node(Node prev, E element, Node next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

LinkedList的实现方式决定了所有跟下标相关的操作都是线性时间，而在首段或者末尾删除元素只需要常数时间。为追求效率LinkedList没有实现同步（synchronized），如果需要多个线程并发访问，可以先采用Collections.synchronizedList()方法对其进行包装。

方法剖析

add()

add()方法有两个版本，一个是add(E e)，该方法在LinkedList的末尾插入元素，因为有last指向链表末尾，在末尾插入元素的花费是常数时间。只需要简单修改几个相关引用即可；另一个是add(int index, E element)，该方法是在指定下表处插入元素，需要先通过线性查找找到具体位置，然后修改相关引用完成插入操作。

结合上图，可以看出add(E e)的逻辑非常简单。

//add(E e)
public boolean add(E e) {
    final Node l = last;
    final Node newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;//原来链表为空，这是插入的第一个元素
    else
        l.next = newNode;
    size++;
    return true;
}

add(int index, E element)的逻辑稍显复杂，可以分成两部，1.先根据index找到要插入的位置；2.修改引用，完成插入操作。

//add(int index, E element)
public void add(int index, E element) {
    checkPositionIndex(index);//index >= 0 && index <= size;
    if (index == size)//插入位置是末尾，包括列表为空的情况
        add(element);
    else{
        Node succ = node(index);//1.先根据index找到要插入的位置
        //2.修改引用，完成插入操作。
        final Node pred = succ.prev;
        final Node newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)//插入位置为0
            first = newNode;
        else
            pred.next = newNode;
        size++;
    }
}

上面代码中的node(int index)函数有一点小小的trick，因为链表双向的，可以从开始往后找，也可以从结尾往前找，具体朝那个方向找取决于条件index < (size >> 1)，也即是index是靠近前端还是后端。

remove()

remove()方法也有两个版本，一个是删除跟指定元素相等的第一个元素remove(Object o)，另一个是删除指定下标处的元素remove(int index)。

两个删除操作都要1.先找到要删除元素的引用，2.修改相关引用，完成删除操作。在寻找被删元素引用的时候remove(Object o)调用的是元素的equals方法，而remove(int index)使用的是下标计数，两种方式都是线性时间复杂度。在步骤2中，两个revome()方法都是通过unlink(Node x)方法完成的。这里需要考虑删除元素是第一个或者最后一个时的边界情况。

//unlink(Node x)，删除一个Node
E unlink(Node x) {
    final E element = x.item;
    final Node next = x.next;
    final Node prev = x.prev;
    if (prev == null) {//删除的是第一个元素
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }
    if (next == null) {//删除的是最后一个元素
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }
    x.item = null;//let GC work
    size--;
    return element;
}

get()

get(int index)得到指定下标处元素的引用，通过调用上文中提到的node(int index)方法实现。

public E get(int index) {
checkElementIndex(index);//index >= 0 && index < size;
return node(index).item;
}

set()

set(int index, E element)方法将指定下标处的元素修改成指定值，也是先通过node(int index)找到对应下表元素的引用，然后修改Node中item的值。

public E set(int index, E element) {
    checkElementIndex(index);
    Node x = node(index);
    E oldVal = x.item;
    x.item = element;//替换新值
    return oldVal;
}

CarpenterLee 2016-05-04 08:35 发表评论

语源科技BlogJava-CarpenterLee

Java Stream API入门篇

stream方法使用

forEach()

filter()

distinct()

sorted()

map()

flatMap()

结语

《深入理解Java集合框架》系列文章

Introduction

Contents

Authors

浅谈WeakHashMap

总体介绍

具体实现

Weak HashSet?

结语

Java集合框架源码剖析：LinkedHashSet 和 LinkedHashMap

总体介绍

方法剖析

get()

put()

remove()

LinkedHashSet

史上最清晰的红黑树讲解（下）

寻找节点后继

remove()

TreeSet

史上最清晰的红黑树讲解（上）

总体介绍

预备知识

左旋

右旋

方法剖析

get()

put()

remove()

Java PriorityQueue源码剖析

为什么你的博客不够火？

CNBlog首页博客热度分析

前言

技术实现

分析结果

博友们一天之内喜欢什么时候发博客？

哪个时间段发的博客更容易火？

大家一周之内喜欢在哪一天发博客？

一周之内哪一天发的博客更容易火？

总结

未来的工作

Java ArrayDeque源码剖析

ArrayDeque

前言

总体介绍

方法剖析

addFirst()

addLast()

pollFirst()

pollLast()

peekFirst()

peekLast()

Java LinkedList源码剖析

LinkedList

总体介绍

方法剖析

add()

remove()

get()

set()