Java 提供的集合类都在 Java.utils 包下，其中包含了很多 List, Set, Map, Queue… 它们的关系如下面这张类图所示：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

可以看到，Java 集合主要分为两类：Collection 和 Map. 而 Collection 又继承了 Iterable< E > 接口，Iterable 接口内只有一个 iterator 方法，返回一个 Iterator 迭代器:

public interface Iterable<T> {

    /**
    * Returns an {@link Iterator} for the elements in this object.
    *
    * @return An {@code Iterator} instance.
    */
    Iterator<T> iterator();
}

本篇文章将介绍 Iterator 迭代器。在介绍 Iterator 之前不得不提一下被它替代的 Enumeration< E >:

Enumeration< E >

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

public interface Enumeration<E> {

/**
 * Returns whether this {@code Enumeration} has more elements.
 *
 * @return {@code true} if there are more elements, {@code false} otherwise.
 * @see #nextElement
 */
    public boolean hasMoreElements();

/**
 * Returns the next element in this {@code Enumeration}.
 *
 * @return the next element..
 * @throws NoSuchElementException
 * if there are no more elements.
 * @see #hasMoreElements
 */
    public E nextElement();
}

Enumeration 是一个很古老的迭代器，有两个方法：

hasMoreElements() //是否还有元素
nextElement() //返回下一个元素

Enumeration 的实现类会生成一系列子元素，比如 StringTokenizer；通过 Enumeration 的上述两个方法可以用来遍历它实现类的元素，比如这样：

    //StringTokenizer : 切割, Breaks a string into tokens; new code should probably use {@link String#split}.
    Enumeration enumeration = new StringTokenizer("A-B-C", "-");
    while (enumeration.hasMoreElements()){
        System.out.println(enumeration.nextElement());
    }

运行结果：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

Enumeration 接口早在 JDK 1.0 时就推出了，当时比较早的容器比如 Hashtable, Vector 都使用它作为遍历工具。

那 Enumeration 为什么会被废弃呢？

根据官方文档:

NOTE: The functionality of this interface is duplicated by the Iterator interface. In addition, Iterator adds an optional remove operation, and has shorter method names. New implementations should consider using Iterator in preference to Enumeration.

可以大胆猜一下，应该是当初设计没有考虑全，只有两个方法，而且名字还太长了 - -。后来在 JDK 1.2 推出了 Iterator 替代它的功能。虽然 Enumeration 在 JDK 1.5 后增加了泛型的应用，依旧大势已去。

Iterator

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

Iterator 是一个集合上的迭代器，用来替代 Enumeration 进行遍历、迭代。

它和 Enumeration 有什么不同呢？

根据官方文档:

Iterators differ from enumerations in two ways:

Iterators allow the caller to remove elements from the underlying collection during the iteration with well-defined semantics.

Method names have been improved.

哈哈首先是名字缩短了，看来大家都懒得输入那么长的方法名。其次是允许调用者在遍历过程中语法正确地删除元素。

注意这个 [语法正确]，事实上我们在使用 Iterator 对容器进行迭代时如果修改容器可能会报 ConcurrentModificationException 的错。官方称这种情况下的迭代器是 fail-fast 迭代器。

fail-fast 与 ConcurrentModificationException

以 ArrayList 为例，在调用迭代器的 next，remove 方法时：

    public E next() {
        if (expectedModCount == modCount) {
            try {
                E result = get(pos + 1);
                lastPosition = ++pos;
                return result;
            } catch (IndexOutOfBoundsException e) {
                throw new NoSuchElementException();
            }
        }
        throw new ConcurrentModificationException();
    }

    public void remove() {
        if (this.lastPosition == -1) {
            throw new IllegalStateException();
        }

        if (expectedModCount != modCount) {
            throw new ConcurrentModificationException();
        }

        try {
            AbstractList.this.remove(lastPosition);
        } catch (IndexOutOfBoundsException e) {
            throw new ConcurrentModificationException();
        }

        expectedModCount = modCount;
        if (pos == lastPosition) {
            pos--;
        }
        lastPosition = -1;
    }

可以看到在调用迭代器的 next，remove 方法时都会比较 expectedModCount 和 modCount 是否相等，如果不相等就会抛出 ConcurrentModificationException ，也就是成为了 fail-fast。

而 modCount 在 add, clear, remove 时都会被修改：

public boolean add(E object) {
    //...
    modCount++;
    return true;
}

public void clear() {
    if (size != 0) {
        //...
        modCount++;
    }
}

public boolean remove(Object object) {
    Object[] a = array;
    int s = size;
    if (object != null) {
        for (int i = 0; i < s; i++) {
            if (object.equals(a[i])) {
                //...
                modCount++;
                return true;
            }
        }
    } else {
        for (int i = 0; i < s; i++) {
            if (a[i] == null) {
                //...
                modCount++;
                return true;
            }
        }
    }
    return false;
}

因此我们知道了 fail-fast 即 ConcurrentModificationException 出现的原因，怎么解决呢？

方法一:

用 CopyOnWriteArrayList，ConcurrentHashMap 替换 ArrayList， HashMap，它们的功能和名字一样，在写入时会创建一个 copy，然后在这个 copy 版本上进行修改操作，这样就不会影响原来的迭代。不过坏处就是浪费内存。

方法二：

使用 Collections.synchronizedList 加同步锁，不过这样有点粗暴。

可能得方法三（待考究，目前我还没搞清楚）：

在学习 ListView 中的观察者模式时，我注意到 DataSetObservable 的 notifyChanged 方法中有如下注释：

public void notifyChanged() {
    synchronized(mObservers) {
        // since onChanged() is implemented by the app, it could do anything, including
        // removing itself from {@link mObservers} - and that could cause problems if
        // an iterator is used on the ArrayList {@link mObservers}.
        // to avoid such problems, just march thru the list in the reverse order.
        for (int i = mObservers.size() - 1; i >= 0; i--) {
            mObservers.get(i).onChanged();
        }
    }
}

to avoid such problems, just march thru the list in the reverse order

为了避免影响 ArrayList 迭代，倒序处理。待考究，目前我还没搞清楚。

不过意外的发现了，原来 for-each 的循环内部也是使用了 Iterator 来遍历Collection，它也调用了 Iterator.next()，所以在修改元素时会检查(元素的)变化并抛出 ConcurrentModificationException。

在从任何 Collection中删除对象时总要使用 Iterator 的remove 方法， for-each 循环只是标准 Iterator 代码标准用法之上的一种语法糖（syntactic sugar）而已。

差点忘了 Iterator 的使用

所有 Collection 的子类都有 iterator() 方法来获得 Iterator，通过 Iterator 的标准操作方法，可以让我们不必关心具体集合的类型，从而避免向客户端暴露出集合的内部结构。

不使用 Iterator 遍历集合是这样的：

    for(int i=0; i<集合的大小;i++){  
        // ... 
    }

使用 Iterator 遍历集合是这样的：

    Iterator iterator = list.iterator();
    while (iterator.hasNext()){
        System.out.println(iterator.next());
    }

对比而言，后者客户端代码与具体集合类型耦合性弱，复用性更强。缺点就是无法获取指定的元素，只能挨个遍历。

Thanks

https://docs.oracle.com/javase/8/docs/api/java/util/Enumeration.html

https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html

http://javahungry.blogspot.com/2014/04/fail-fast-iterator-vs-fail-safe-iterator-difference-with-example-in-java.html

http://www.cnblogs.com/dolphin0520/p/3933551.html

http://blog.csdn.net/chenssy/article/details/38151189

http://blog.csdn.net/mazhimazh/article/details/17730517

http://javarevisited.blogspot.jp/2014/04/for-each-loop-puzzle-in-java-example.html

今天心情和股票一样红，还是学学 ListIterator 吧！

ListIterator

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

根据官方文档介绍, ListIterator 有以下功能：

允许我们向前、向后两个方向遍历 List;
在遍历时修改 List 的元素；
遍历时获取迭代器当前游标所在位置。

注意，迭代器没有当前所在元素一说，它只有一个游标( cursor )的概念，这个游标总是在元素之间，比如这样:

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

初始时它在第 0 个元素之前，调用 next() 游标后移一位：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

调用 previous() 游标就会回到之前位置。当向后遍历完元素，游标就会在元素 N 的后面：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

也就是说长度为 N 的集合会有 N+1 个游标的位置。

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

ListIterator 继承自 Iterator 接口（关于 Iterator 的介绍请点这里），在 Iterator 的基础上增加了 6 个方法：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

介绍一下新来的几个方法：

void hasPrevious()
- 判断游标前面是否有元素;
Object previous()
- 返回游标前面的元素，同时游标前移一位。游标前没有元素就报 java.util.NoSuchElementException 的错，所以使用前最好判断一下;
int nextIndex()
- 返回游标后边元素的索引位置，初始为 0 ；遍历 N 个元素结束时为 N;
int previousIndex()
- 返回游标前面元素的位置，初始时为 -1，同时报 java.util.NoSuchElementException 错;
void add(E)
- 在游标前面插入一个元素
- 注意，是前面
void set(E)
- 更新迭代器最后一次操作的元素为 E，也就是更新最后一次调用 next() 或者 previous() 返回的元素。
- 注意，当没有迭代，也就是没有调用 next() 或者 previous() 直接调用 set 时会报 java.lang.IllegalStateException 错;
void remove()
- 删除迭代器最后一次操作的元素，注意事项和 set 一样。

ListIterator 有两种获取方式

List.listIterator()
List.listIterator(int location)

区别在于第二种可以指定游标的所在位置。

ListIterator 的具体实现？

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

AbstractList 作为 List 的直接子类，里面实现了 listIterator() 方法，并且有两个内部迭代器实现类：SimpleListIterator，FullListIterator：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

listIterator() 返回的是 FullListIterator()：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

FullListIterator 继承了 SimpleListIterator, SimpleListIterator 实现了 Iterator 接口：

private class SimpleListIterator implements Iterator<E> {
    //游标的位置，初始为 -1
    int pos = -1;
    //用来判断是否 fail-fast 的变量
    int expectedModCount;
    //记录上次迭代的位置
    int lastPosition = -1;

    SimpleListIterator() {
        expectedModCount = modCount;
    }

    //当游标没有跑到最后一个元素后面时 hasNext 返回 true
    public boolean hasNext() {
        return pos + 1 < size();
    }

    //获取下一个元素
    public E next() {
        if (expectedModCount == modCount) {
            try {
                //获取游标后面的元素，具体子类有具体实现
                E result = get(pos + 1);
                //更新
                lastPosition = ++pos;
                return result;
            } catch (IndexOutOfBoundsException e) {
                throw new NoSuchElementException();
            }
        }
        //当迭代时修改元素，就会报这个错，上篇文章介绍过解决办法~
        throw new ConcurrentModificationException();
    }

    //删除上次迭代操作的元素
    public void remove() {
        //还没进行迭代操作就会报这个错
        if (this.lastPosition == -1) {
            throw new IllegalStateException();
        }

        if (expectedModCount != modCount) {
            throw new ConcurrentModificationException();
        }

        try {
            //调用子类实现的删除操作
            AbstractList.this.remove(lastPosition);
        } catch (IndexOutOfBoundsException e) {
            throw new ConcurrentModificationException();
        }

        expectedModCount = modCount;
        if (pos == lastPosition) {
            pos--;
        }
        //每次删除后都会还原为 -1，也就是说我们迭代一次后只能 remove 一次，再 remove 就会报错
        lastPosition = -1;
    }
}

了解了 SimpleListIterator 后我们看下 FullListIterator 的具体实现：

private final class FullListIterator extends SimpleListIterator implements ListIterator<E> {
    //根据 start 指定游标位置
    FullListIterator(int start) {
        if (start >= 0 && start <= size()) {
            pos = start - 1;
        } else {
            throw new IndexOutOfBoundsException();
        }
    }

    //在游标前面添加元素
    public void add(E object) {
        if (expectedModCount == modCount) {
            try {
                //调用子类的添加操作，ArrayList, LinkedList,Vector 的添加操作实现有所不同
                AbstractList.this.add(pos + 1, object);
            } catch (IndexOutOfBoundsException e) {
                throw new NoSuchElementException();
            }
            //游标后移一位
            pos++;
            //!注意！ 添加后 上次迭代位置又变回 -1 了，说明 add 后调用 remove, set 会有问题！
            lastPosition = -1;
            if (modCount != expectedModCount) {
                expectedModCount = modCount;
            }
        } else {
            throw new ConcurrentModificationException();
        }
    }

    //当游标不在初始位置（-1）时返回true
    public boolean hasPrevious() {
        return pos >= 0;
    }

    //游标后面的元素索引，就是游标 +1
    public int nextIndex() {
        return pos + 1;
    }

    //游标前面一个元素
    public E previous() {
        if (expectedModCount == modCount) {
            try {
                E result = get(pos);
                lastPosition = pos;
                pos--;
                return result;
            } catch (IndexOutOfBoundsException e) {
                throw new NoSuchElementException();
            }
        }
        throw new ConcurrentModificationException();
    }

    //游标前面元素的索引，就是游标的位置,有点晕的看开头那几张图
    public int previousIndex() {
        return pos;
    }

    //更新之前迭代的元素为 object
    public void set(E object) {
        if (expectedModCount == modCount) {
            try {
                //调用子类的set
                AbstractList.this.set(lastPosition, object);
            } catch (IndexOutOfBoundsException e) {
                throw new IllegalStateException();
            }
        } else {
            throw new ConcurrentModificationException();
        }
    }
}

可以看到 SimpleListIterator 的主要操作最后都交给子类来实现，List 的子类 ArrayList, LinkedList, Vector 由于底层实现原理不同（数组，双向链表），具体操作类实现有所不同。

等接下来分析到具体子类再看相关实现吧。

什么是集合？

集合，或者叫容器，是一个包含多个元素的对象；
集合可以对数据进行存储，检索，操作；
它们可以把许多个体组织成一个整体：
- 比如一副扑克牌（许多牌组成的集合）;
- 比如一个电话本（许多姓名和号码的映射）。

什么是集合框架？

集合框架是一个代表、操作集合的统一架构。所有的集合框架都包含以下几点：

接口：表示集合的抽象数据类型。接口允许我们操作集合时不必关注具体实现，从而达到“多态”。在面向对象编程语言中，接口通常用来形成规范。
实现类：集合接口的具体实现，是重用性很高的数据结构。
算法：用来根据需要对实体类中的对象进行计算，比如查找，排序。
- 同一种算法可以对不同的集合实现类进行计算，这是利用了“多态”。
- 重用性很高。

不仅 Java，其他语言也有一些集合框架，比如 C艹的 STL（标准模板库），Smalltalk 的集合层次结构。不同于他们陡峭的学习曲线，Java 集合框架设计的更加合理，学习起来更加轻松。

使用集合框架有什么好处呢?

使用 Java 集合框架能有以下几点好处：

编码更轻松：Java 集合框架为我们提供了方便使用的数据结构和算法，让我们不用从头造*，直接操心上层业务就好了。
代码质量更上一层楼：Java 集合框架经过几次升级迭代，数据结构和算法的性能已经优化地很棒了。由于是针对接口编程，不同实现类可以轻易互相替换。这么优雅的设计，省下你自己磨练多少工夫，恩？！
减少学习新 API 的成本：过去每个集合 API 下还有子 API 来对 API 进行操作，你得学好几层才能知道怎么使用，而且还容易出错。现在好了!有了标准的 Java 集合框架，每个 API 都继承自己顶层 API，只负责具体实现，一口气学 5 个集合，不费劲！
照猫画虎也容易多了：由于顶层接口已经把基础方法都定义好了，你只要实现接口，把具体实现方法填好，再也不用操心架构设计。

Java 集合框架主要结构图

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

如上图所示，Java 的集合主要按两种接口分类：Collection, Map.

Collection 接口

Collection 作为集合的一个根接口，定义了一组对象和它的子类需要实现的 15 个方法：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

对集合的基础操作，比如 :

int size()
- 获取元素个数
- boolean isEmpty()
- 是否个数为 0
- boolean contains(Object element)
- 是否包含指定元素
- boolean add(E element)
- 添加元素，成功时返回 true
- boolean remove(Object element)
- 删除元素，成功时返回 true
- Iterator<E> iterator()
- 获取迭代器

还有一些操作整个集合的方法，比如 :

boolean containsAll(Collection<?> c)
- 是否包含指定集合 c 的全部元素
boolean addAll(Collection<? extends E> c)
- 添加集合 c 中所有的元素到本集合中，如果集合有改变就返回 true
boolean removeAll(Collection<?> c)
- 删除本集合中和 c 集合中一致的元素，如果集合有改变就返回 true
boolean retainAll(Collection<?> c)
- 保留本集合中 c 集合中两者共有的，如果集合有改变就返回 true
void clear()
- 删除所有元素

还有对数组操作的方法：

Object[] toArray()
- 返回一个包含集合中所有元素的数组
<T> T[] toArray(T[] a)
- 返回一个包含集合中所有元素的数组，运行时根据集合元素的类型指定数组的类型

在 JDK 8 以后，Collection 接口还提供了从集合获取连续的或者并行流：

Stream<E> stream()
Stream<E> parallelStream()

点击这里了解流 Stream.

遍历 Collection 的几种方式：

for-each语法

Collection<Person> persons = new ArrayList<Person>();
for (Person person : persons) { 
    System.out.println(person.name);  
}

使用 Iterator 迭代器

Collection<Person> persons = new ArrayList<Person>();
Iterator iterator = persons.iterator();
while (iterator.hasNext) { 
    System.out.println(iterator.next);  
}

使用 aggregate operations 聚合操作

Collection<Person> persons = new ArrayList<Person>();
persons
    .stream()
    .forEach(new Consumer<Person>() {  
        @Override  
        public void accept(Person person) {  
            System.out.println(person.name);  
        }  
});

Aggregate Operations 聚合操作

在 JDK 8 以后，推荐使用聚合操作对一个集合进行操作。聚合操作通常和 lambda 表达式结合使用，让代码看起来更简洁（因此可能更难理解）。下面举几个简单的栗子：

1.使用流来遍历一个 ShapesCollection，然后输出红色的元素：

myShapesCollection.stream()
    .filter(e -> e.getColor() == Color.RED)
    .forEach(e -> System.out.println(e.getName()));

2.你还可以获取一个并行流（parallelStream），当集合元素很多时使用并发可以提高效率：

myShapesCollection.parallelStream()
    .filter(e -> e.getColor() == Color.RED)
    .forEach(e -> System.out.println(e.getName()));

3.聚合操作还有很多操作集合的方法，比如说你想把 Collection 中的元素都转成 String 对象，然后把它们连起来：

String joined = elements.stream()
    .map(Object::toString)
    .collect(Collectors.joining(", "));

看起来是不是非常简洁呢！

聚合操作还有很多功能，这里仅做介绍，想要了解更多可以查看Aggregate Operations 官方指引。

Iterator 迭代器

在Java 集合解析：Iterator 和 Java 集合解析：ListIterator 我介绍了 Collection 的迭代器 Iterator 以及用于 List 的迭代器 ListIterator。

结合 Collection 和 Iterator 可以实现一些复用性很强的方法，比如这样：

public static void filter(Collection<?> c) {
    for (Iterator<?> it = c.iterator(); it.hasNext(); )
        if (!condition(it.next()))
            it.remove();
}

这个 filter 方法是多态的，可以用于所有 Collection 的子类、实现类。这个例子说明了使用 Java 集合框架我们可以很随便就写出 “优雅，可拓展，复用性强” 的代码~

总结

Collection 接口是类集框架的基础之一。

它创建所有类集都将拥有的 15 个核心方法。

因为几乎所有集合类集都实现了 Collection接口，所以熟悉它对于清楚地理解框架是必要的。

接下来将逐步了解集合框架的各个子接口及实现类。

感谢密哥提醒，parallel 应该是并行，而不是并发。

并发与并行的概念区别还是挺大的。

并行”是指无论从微观还是宏观，二者都是一起执行的，就好像两个人各拿一把铁锨在挖坑，一小时后，每人一个大坑。
而“并发”在微观上不是同时执行的，只是把时间分成若干段，使多个进程快速交替的执行，从宏观外来看，好像是这些进程都在执行，这就好像两个人用同一把铁锨，轮流挖坑，一小时后，两个人各挖一个小一点的坑，要想挖两个大一点得坑，一定会用两个小时。
从以上本质不难看出，“并发”执行，在多个进程存在资源冲突时，并没有从根本提高执行效率。
http://zhidao.baidu.com/link?url=1L6YSAULAhjLH4ZYfO0yCbKlvo8DJeQMtCmCLKYpENStbpxNDiFCwaJf4iZaNDr7cho37GctXOddek3LhrO3_K

这里看到的一幅生动形象图：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

Thanks

https://docs.oracle.com/javase/tutorial/collections/intro/index.html

https://docs.oracle.com/javase/tutorial/collections/interfaces/collection.html

http://joearms.github.io/2013/04/05/concurrent-and-parallel-programming.html

蓝瘦！香菇！连着加班几天，醉了。学学 List 放松下！

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

在 Java 集合深入理解：Collection 中我们熟悉了 Java 集合框架的基本概念和优点，也了解了根接口之一的 Collection，这篇文章来加深 Collection 的子接口之一 List 的熟悉。

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

List 接口

一个 List 是一个元素有序的、可以重复、可以为 null 的集合（有时候我们也叫它“序列”）。

Java 集合框架中最常使用的几种 List 实现类是 ArrayList，LinkedList 和 Vector。在各种 List 中，最好的做法是以 ArrayList 作为默认选择。当插入、删除频繁时，使用 LinkedList，Vector 总是比 ArrayList 慢，所以要尽量避免使用它，具体实现后续文章介绍。

为什么 List 中的元素 “有序”、“可以重复”呢?

首先，List 的数据结构就是一个序列，存储内容时直接在内存中开辟一块连续的空间，然后将空间地址与索引对应。

其次根据官方文档：

The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list.

可以看到，List 接口的实现类在实现插入元素时，都会根据索引进行排列。

比如 ArrayList，本质是一个数组：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

LinkedList, 双向链表：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

由于 List 的元素在存储时互不干扰，没有什么依赖关系，自然可以重复（这点与 Set 有很大区别）。

List 接口定义的方法

List 中除了继承 Collection 的一些方法，还提供以下操作：

位置相关：List 和数组一样，都是从 0 开始，我们可以根据元素在 list 中的位置进行操作，比如说 get, set, add, addAll, remove;
搜索：从 list 中查找某个对象的位置，比如 indexOf, lastIndexOf;
迭代：使用 Iterator 的拓展版迭代器 ListIterator 进行迭代操作;
范围性操作：使用 subList 方法对 list 进行任意范围的操作。

Collection 中提供的一些方法就不介绍了，不熟悉的可以去看一下。

集合的操作

remove(Object)
- 用于删除 list 中头回出现的指定对象；
add(E), addAll(Collection<? extends E>)
- 用于把新元素添加到 list 的尾部，下面这段语句使得 list3 等于 list1 与 list2 组合起来的内容：
  
  List list3 = new ArrayList(list1);
  list3.addAll(list2);
注意：上述使用了 ArrayList 的转换构造函数:

public ArrayList(Collection

`Object` 的 `equlas`() 方法默认和 `==` 一样，比较的是地址是否相等。

public boolean equals(Object o) {
    return this == o;
}

因此和 Set，Map 一样，List 中如果想要根据两个对象的内容而不是地址比较是否相等时，需要重写 equals() 和 hashCode() 方法。 remove(), contains(), indexOf() 等等方法都需要依赖它们：

@Override 
public boolean contains(Object object) {
    Object[] a = array;
    int s = size;
    if (object != null) {
        for (int i = 0; i < s; i++) {
            //需要重载 Object 默认的 equals 
            if (object.equals(a[i])) {
                return true;
            }
        }
    } else {
        for (int i = 0; i < s; i++) {
            if (a[i] == null) {
                return true;
            }
        }
    }
    return false;
}

@Override
 public int indexOf(Object object) {
    Object[] a = array;
    int s = size;
    if (object != null) {
        for (int i = 0; i < s; i++) {
            if (object.equals(a[i])) {
                return i;
            }
        }
    } else {
        for (int i = 0; i < s; i++) {
            if (a[i] == null) {
                return i;
            }
        }
    }
    return -1;
}

两个 List 对象的所有位置上元素都一样才能相等。

位置访问，搜索

基础的位置访问操作方法有：

get, set, add, remove
- set, remove 方法返回的是被覆盖或者被删除的元素；
indexOf, lastIndexOf
- 返回指定元素在 list 中的首次出现/最后一次出现的位置（获取 lastIndexOf 是通过倒序遍历查找）;
addAll(int,Collection)
- 在特定位置插入指定集合的所有元素。这些元素按照迭代器 Iterator 返回的先后顺序进行插入；

下面是一个简单的 List 中的元素交换方法：

public static <E> void swap(List<E> a, int i, int j) {
    E tmp = a.get(i);
    a.set(i, a.get(j));
    a.set(j, tmp);
}

不同的是它是多态的，允许任何 List 的子类使用。 Collections 中的 shuffle 就有用到和下面这种相似的交换方法：

public static void shuffle(List<?> list, Random rnd) {
    for (int i = list.size(); i > 1; i--)
        swap(list, i - 1, rnd.nextInt(i));
}

这种算法使用指定的随机算法，从后往前重复的进行交换。和一些其他底层 shuffle 算法不同，这个算法更加公平（随机方法够随机的话，所有元素的被抽到的概率一样），同时够快（只要 list.size() -1 ）次交换。

局部范围操作

List.subList(int fromIndex, int toIndex) 方法返回 List 在 fromIndex 与 toIndex 范围内的子集。注意是左闭右开，[fromIndex,toIndex)。

注意！ List.subList 方法并没有像我们想的那样：创建一个新的 List，然后把旧 List 的指定范围子元素拷贝进新 List，根！本！不！是！
subList 返回的扔是 List 原来的引用，只不过把开始位置 offset 和 size 改了下，见 List.subList() 在 AbstractList 抽象类中的实现：

public List<E> subList(int start, int end) {
    if (start >= 0 && end <= size()) {
        if (start <= end) {
            if (this instanceof RandomAccess) {
                return new SubAbstractListRandomAccess<E>(this, start, end);
            }
            return new SubAbstractList<E>(this, start, end);
        }
        throw new IllegalArgumentException();
    }
    throw new IndexOutOfBoundsException();
}

SubAbstractListRandomAccess 最终也是继承 SubAbstractList,直接看 SubAbstractList：

    SubAbstractList(AbstractList<E> list, int start, int end) {
        fullList = list;
        modCount = fullList.modCount;
        offset = start;
        size = end - start;
    }

可以看到，的确是保持原来的引用。

所以，重点来了！

由于 subList 持有 List 同一个引用，所以对 subList 进行的操作也会影响到原有 List，举个栗子：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

你猜运行结果是什么？

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

验证了上述重点。

所以，我们可以使用 subList 对 List 进行范围操作，比如下面的代码，一句话实现了删除 shixinList 部分元素的操作：

shixinList.subList(fromIndex, toIndex).clear();

还可以查找某元素在局部范围内的位置：

int i = list.subList(fromIndex, toIndex).indexOf(o);
int j = list.subList(fromIndex, toIndex).lastIndexOf(o);

List 与 Array 区别？

List 在很多方面跟 Array 数组感觉很相似，尤其是 ArrayList，那 List 和数组究竟哪个更好呢？

相似之处：
- 都可以表示一组同类型的对象
- 都使用下标进行索引
不同之处：
- 数组可以存任何类型元素
- List 不可以存基本数据类型，必须要包装
- 数组容量固定不可改变；List 容量可动态增长
- 数组效率高; List 由于要维护额外内容，效率相对低一些

容量固定时优先使用数组，容纳类型更多，更高效。

在容量不确定的情景下， List 更有优势，看下 ArrayList 和 LinkedList 如何实现容量动态增长：

ArrayList 的扩容机制:

public boolean add(E object) {
    Object[] a = array;
    int s = size;
    //当放满时，扩容
    if (s == a.length) {
        //MIN_CAPACITY_INCREMENT 为常量，12
        Object[] newArray = new Object[s +
                (s < (MIN_CAPACITY_INCREMENT / 2) ?
                 MIN_CAPACITY_INCREMENT : s >> 1)];
        System.arraycopy(a, 0, newArray, 0, s);
        array = a = newArray;
    }
    a[s] = object;
    size = s + 1;
    modCount++;
    return true;
}

可以看到：

当 ArrayList 的元素个数小于 6 时，容量达到最大时，元素容量会扩增 12；
反之，增加当前元素个数的一半。

LinkedList 的扩容机制：

public boolean add(E object) {
    return addLastImpl(object);
}

private boolean addLastImpl(E object) {
    Link<E> oldLast = voidLink.previous;
    Link<E> newLink = new Link<E>(object, oldLast, voidLink);
    voidLink.previous = newLink;
    oldLast.next = newLink;
    size++;
    modCount++;
    return true;
}

可以看到，没！有！扩容机制！

这是由于 LinedList 实际上是一个双向链表，不存在元素个数限制，使劲加就行了。

transient Link<E> voidLink;

private static final class Link<ET> {
    ET data;

    Link<ET> previous, next;

    Link(ET o, Link<ET> p, Link<ET> n) {
        data = o;
        previous = p;
        next = n;
    }
}

List 与 Array 之间的转换

在 List 中有两个转换成数组的方法：

Object[] toArray()
- 返回一个包含 List 中所有元素的数组；
T[] toArray(T[] array)
- 作用同上，不同的是当参数 array 的长度比 List 的元素大时，会使用参数 array 保存 List 中的元素；否则会创建一个新的数组存放 List 中的所有元素；

ArrayList 中的实现：

public Object[] toArray() {
    int s = size;
    Object[] result = new Object[s];
    //这里的 array 就是 ArrayList 的底层实现，直接拷贝
    //System.arraycopy 是底层方法，效率很高
    System.arraycopy(array, 0, result, 0, s);
    return result;
}

public <T> T[] toArray(T[] contents) {
    int s = size;
    //先判断参数能不能放下这么多元素
    if (contents.length < s) {
        //放不下就创建个新数组
        @SuppressWarnings("unchecked") T[] newArray
            = (T[]) Array.newInstance(contents.getClass().getComponentType(), s);
        contents = newArray;
    }
    System.arraycopy(this.array, 0, contents, 0, s);
    if (contents.length > s) {
        contents[s] = null;
    }
    return contents;
}

LinkedList 的实现：

public Object[] toArray() {
    int index = 0;
    Object[] contents = new Object[size];
    Link<E> link = voidLink.next;
    while (link != voidLink) {
        //挨个赋值，效率不如 ArrayList
        contents[index++] = link.data;
        link = link.next;
    }
    return contents;
}

@Override
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] contents) {
    int index = 0;
    if (size > contents.length) {
        Class<?> ct = contents.getClass().getComponentType();
        contents = (T[]) Array.newInstance(ct, size);
    }
    Link<E> link = voidLink.next;
    while (link != voidLink) {
        //还是比 ArrayList 慢
        contents[index++] = (T) link.data;
        link = link.next;
    }
    if (index < contents.length) {
        contents[index] = null;
    }
    return contents;
}

数组工具类 Arrays 提供了数组转成 List 的方法 `asList` :

@SafeVarargs
public static <T> List<T> asList(T... array) {
    return new ArrayList<T>(array);
}

使用的是 Arrays 内部创建的 ArrayList 的转换构造函数：

    private final E[] a;
    ArrayList(E[] storage) {
        if (storage == null) {
            throw new NullPointerException("storage == null");
        }
        //直接复制
        a = storage;
    }

迭代器 Iterator, ListIterator

List 继承了 Collection 的 iterator() 方法，可以获取 Iterator，使用它可以进行向后遍历。

在此基础上，List 还可以通过 listIterator(), listIterator(int location) 方法（后者指定了游标的位置）获取更强大的迭代器 ListIterator。

使用 ListIterator 可以对 List 进行向前、向后双向遍历，同时还允许进行 add, set, remove 等操作。

List 的实现类中许多方法都使用了 ListIterator，比如 List.indexOf() 方法的一种实现：

public int indexOf(E e) {
    for (ListIterator<E> it = listIterator(); it.hasNext(); )
        if (e == null ? it.next() == null : e.equals(it.next()))
            return it.previousIndex();
    // Element not found
    return -1;
}

ListIterator 提供了 add, set, remove 操作，他们都是对迭代器刚通过 next(), previous()方法迭代的元素进行操作。下面这个栗子中，List 通过结合 ListIterator 使用，可以实现一个多态的方法，对所有 List 的实现类都适用：

public static <E> void replace(List<E> list, E val, E newVal) {
    for (ListIterator<E> it = list.listIterator(); it.hasNext(); )
        if (val == null ? it.next() == null : val.equals(it.next()))
            it.set(newVal);
}

List 的相关算法：

集合的工具类 Collections 中包含很多 List 的相关操作算法：

sort ，归并排序
shuffle ，随机打乱
reverse ，反转元素顺序
swap ，交换
binarySearch ，二分查找
……

具体实现我们后续介绍，感谢关注！

关联：
Collection, ListIterator, Collections

Thanks:

http://docs.oracle.com/javase/1.5.0/docs/api/java/util/List.html

https://docs.oracle.com/javase/tutorial/collections/interfaces/list.html

http://blog.csdn.net/mazhimazh/article/details/17759579#comments

http://www.blogjava.net/flysky19/articles/92775.html

今天好累，来学学 AbstractCollection 吧！

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

什么是 AbstractCollection

AbstractCollection 是 Java 集合框架中 Collection 接口的一个直接实现类， Collection 下的大多数子类都继承 AbstractCollection ，比如 List 的实现类, Set的实现类。

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~
它实现了一些方法，也定义了几个抽象方法留给子类实现，因此它是一个抽象类。

抽象方法

public abstract Iterator<E> iterator();
public abstract int size();

子类必须以自己的方式实现这两个方法。除此外，AbstractCollection 中默认不支持添加单个元素，如果直接调用 add(E)方法，会报错：

public boolean add(E object) {
    throw new UnsupportedOperationException();
}

因此，如果子类是可添加的数据结构，需要自己实现 add(E) 方法。

实现的方法

1.addAll() 添加一个集合内的全部元素:

public boolean addAll(Collection<? extends E> collection) {
    boolean result = false;
    //获取待添加对象的迭代器
    Iterator<? extends E> it = collection.iterator();
    while (it.hasNext()) {
        //挨个遍历，调用 add() 方法添加，因此如果没有实现 add(E) 方法，addAll() 也不能用
        if (add(it.next())) {
            result = true;
        }
    }
    return result;
}

2.clear() 删除所有元素：

public void clear() {
    //获取子类实现的迭代器，挨个遍历，删除
    Iterator<E> it = iterator();
    while (it.hasNext()) {
        it.next();
        //单线程使用迭代器的 remove() 方法不会导致 fail-fast
        it.remove();
    }
}

3.contains() 是否包含某个元素：

public boolean contains(Object object) {
    //获取子类实现的迭代器，挨个遍历，比较
    Iterator<E> it = iterator();
    if (object != null) {
        while (it.hasNext()) {
            //这个元素的类 需要重写 equals() 方法，不然结果够呛
            if (object.equals(it.next())) {
                return true;
            }
        }
    } else {
        //目标元素是空也能查找，说明 AbstractCollection 默认是支持元素为 null 的
        while (it.hasNext()) {
            if (it.next() == null) {
                return true;
            }
        }
    }
    return false;
}

4.containsAll() 是否包含指定集合中的全部元素:

public boolean containsAll(Collection<?> collection) {
    Iterator<?> it = collection.iterator();
    //挨个遍历指定集合
    while (it.hasNext()) {
        //contails 里也是遍历，双重循环，O(n^2)
        if (!contains(it.next())) {
            return false;
        }
    }
    return true;
}

5.isEmpty() 是否为空:

public boolean isEmpty() {
    //调用子类实现的 size() 方法
    return size() == 0;
}

6.remove() 删除某个元素:

public boolean remove(Object object) {
    //获取子类实现的 迭代器
    Iterator<?> it = iterator();
    if (object != null) {
        while (it.hasNext()) {
            if (object.equals(it.next())) {
                it.remove();
                return true;
            }
        }
    } else {
        while (it.hasNext()) {
            if (it.next() == null) {
                it.remove();
                return true;
            }
        }
    }
    return false;
}

受不了了，又是 if-else，直接写成这样看着不是更舒服吗：

public boolean remove(Object object) {
    Iterator<?> it = iterator();
    while (it.hasNext()) {
       if (object != null ? object.equals(it.next()) : it.next() == null) {
           it.remove();
           return true;
        }
    }
    return false;
}

使用if-else只需要进行判断一次object是否为null，而使用问号冒号表达式，每个元素进行比较时都需要一次判断。虽然看起来舒服了，但是效率下降了。

7.removeAll() 删除指定集合中包含在本集合的元素：

public boolean removeAll(Collection<?> collection) {
    boolean result = false;
    Iterator<?> it = iterator();
    while (it.hasNext()) {
        //双重循环
        if (collection.contains(it.next())) {
            it.remove();
            result = true;
        }
    }
    return result;
}

8.retainAll() 保留共有的，删除指定集合中不共有的：

public boolean retainAll(Collection<?> collection) {
    boolean result = false;
    Iterator<?> it = iterator();
    while (it.hasNext()) {
        //排除异己，不在我集合中的统统 886
        if (!collection.contains(it.next())) {
            it.remove();
            result = true;
        }
    }
    return result;
}

9.toArray(), toArray(T[] contents) 转换成数组：

public Object[] toArray() {
//把集合转换成 ArrayList，然后再调用 ArrayList.toArray() 
    return toArrayList().toArray();
}

public <T> T[] toArray(T[] contents) {
    return toArrayList().toArray(contents);
}

@SuppressWarnings("unchecked")
private ArrayList<Object> toArrayList() {
    ArrayList<Object> result = new ArrayList<Object>(size());
    for (E entry : this) {
        result.add(entry);
    }
    return result;
}

ArrayList, 集合与数组的桥梁。

10.toString() 把内容转换成一个 String 进行展示:

public String toString() {
    if (isEmpty()) {
        return "[]";
    }
    //注意默认容量是 size() 的 16 倍，为什么是 16 呢?
    StringBuilder buffer = new StringBuilder(size() * 16);
    buffer.append('[');
    //仍旧用到了迭代器
    Iterator<?> it = iterator();
    while (it.hasNext()) {
        Object next = it.next();
        if (next != this) {
            //这个 Object 也得重写 toString() 方法，不然不能输出内容
            buffer.append(next);
        } else {
            buffer.append("(this Collection)");
        }
        if (it.hasNext()) {
            buffer.append(", ");
        }
    }
    buffer.append(']');
    return buffer.toString();
}

我们之所以可以使用 System.out.print() 直接输出集合的全部内容，而不用挨个遍历输出，全都是 AbstractCollection 的功劳！

    List list = new LinkedList();
    System.out.println(list);

其他

1.AbstractCollection 默认的构造函数是 protected:

/**
 * Sole constructor.  (For invocation by subclass constructors, typically
 * implicit.)
 */
protected AbstractCollection() {
}

因此，官方推荐子类自己创建一个无参构造函数：

The programmer should generally provide a void (no argument) and Collection constructor, as per the recommendation in the Collection interface specification.

2.AbstractCollection 的 add(E) 方法默认是抛出异常，这样会不会容易导致问题？为什么不定义为抽象方法？

答案译自 * :

如果你想修改一个不可变的集合时，抛出 UnsupportedOperationException 是标准的行为，比如当你用 Collections.unmodifiableXXX() 方法对某个集合进行处理后，再调用这个集合的修改方法（add,remove,set…），都会报这个错；
因此 AbstractCollection.add(E) 抛出这个错误是准从标准；

那为什么会有这个标准呢？

在 Java 集合总，很多方法都提供了有用的默认行为，比如：

Iterator.remove()
AbstractList.add(int, E)
AbstractList.set(int, E)
AbstractList.remove(int)
AbstractMap.put(K, V)
AbstractMap.SimpleImmutableEntry.setValue(V)

而之所以没有定义为抽象方法，是因为可能有很多地方用不到这个方法，用不到还必须实现，这岂不是让人很困惑么。

个人觉得原因跟和设计模式中的接口隔离原则有些相似：

不要给客户端暴露不需要的方法。

今天心情比天蓝，来学学 AbstractList 吧！

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

什么是 AbstractList

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

AbstractList 继承自 AbstractCollection 抽象类，实现了 List 接口，是 ArrayList 和 AbstractSequentiaList 的父类。

它实现了 List 的一些位置相关操作(比如 get,set,add,remove)，是第一个实现随机访问方法的集合类，但不支持添加和替换。

在 AbstractCollection 抽象类中我们知道，AbstractCollection 要求子类必须实现两个方法： iterator() 和 size()。 AbstractList 实现了 iterator()方法：

public Iterator<E> iterator() {
    return new Itr();
}

但没有实现 size() 方法，此外还提供了一个抽象方法 get()：

public abstract E get(int location);

因此子类必须要实现 get(), size() 方法。

另外，如果子类想要能够修改元素，还需要重写 add(), set(), remove() 方法，否则会报 UnsupportedOperationException错。

实现的方法

1.默认不支持的 add(), set(),remove():

public boolean add(E e) {
    add(size(), e);
    return true;
}

public void add(int index, E element) {
    throw new UnsupportedOperationException();
}

public E set(int index, E element) {
    throw new UnsupportedOperationException();
}

public E remove(int index) {
    throw new UnsupportedOperationException();
}

2.indexOf(Object) 获取指定对象首次出现的索引：

public int indexOf(Object o) {
    //获取 ListIterator，此时游标位置为 0 
    ListIterator<E> it = listIterator();
    if (o==null) {
        //向后遍历
        while (it.hasNext())
            if (it.next()==null)
                //返回游标的前面元素索引
                return it.previousIndex();
    } else {
        while (it.hasNext())
            if (o.equals(it.next()))
                return it.previousIndex();
    }
    return -1;
}

在 ListIterator 中我们介绍了游标的概念，每次调用 listIterator.next() 方法游标都会后移一位，当 listIterator.next() == o 时（即找到我们需要的的元素），游标已经在 o 的后面，所以需要返回游标的 previousIndex().

3.lastIndexOf(Object) 获取指定对象最后一次出现的位置:

public int lastIndexOf(Object o) {
    //获取 ListIterator，此时游标在最后一位
    ListIterator<E> it = listIterator(size());
    if (o==null) {
        //向前遍历
        while (it.hasPrevious())
            if (it.previous()==null)
                //返回 it.nextIndex() 原因类似 2
                return it.nextIndex();
    } else {
        while (it.hasPrevious())
            if (o.equals(it.previous()))
                return it.nextIndex();
    }
    return -1;
}

4.clear(), removeRange(int, int), 全部/范围删除元素：

public void clear() {
    //传入由子类实现的 size()
    removeRange(0, size());
}

protected void removeRange(int fromIndex, int toIndex) {
    //获取 ListIterator 来进行迭代删除
    ListIterator<E> it = listIterator(fromIndex);
    for (int i=0, n=toIndex-fromIndex; i<n; i++) {
        it.next();
        it.remove();
    }
}

5.addAll(int,Collection

两种内部迭代器

与其他集合实现类不同，AbstractList 内部已经提供了 Iterator, ListIterator 迭代器的实现类，分别为 Itr, ListItr, 不需要我们去帮他实现。

Itr 代码分析：

private class Itr implements Iterator<E> {
    //游标
    int cursor = 0;

    //上一次迭代到的元素的位置，每次使用完就会置为 -1
    int lastRet = -1;

    //用来判断是否发生并发操作的标示，如果这两个值不一致，就会报错
    int expectedModCount = modCount;

    public boolean hasNext() {
        return cursor != size();
    }

    public E next() {
        //时刻检查是否有并发修改操作
        checkForComodification();
        try {
            int i = cursor;
            //调用 子类实现的 get() 方法获取元素
            E next = get(i);
            //有迭代操作后就会记录上次迭代的位置
            lastRet = i;
            cursor = i + 1;
            return next;
        } catch (IndexOutOfBoundsException e) {
            checkForComodification();
            throw new NoSuchElementException();
        }
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            //调用需要子类实现的 remove()方法
            AbstractList.this.remove(lastRet);
            if (lastRet < cursor)
                cursor--;
            //删除后 上次迭代的记录就会置为 -1
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException e) {
            throw new ConcurrentModificationException();
        }
    }

    //检查是否有并发修改
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

可以看到 Itr 只是简单实现了 Iterator 的 next, remove 方法。

ListItr 代码分析:

//ListItr 是 Itr 的增强版
private class ListItr extends Itr implements ListIterator<E> {
    //多了个指定游标位置的构造参数，怎么都不检查是否越界！
    ListItr(int index) {
        cursor = index;
    }

    //除了一开始都有前面元素
    public boolean hasPrevious() {
        return cursor != 0;
    }

    public E previous() {
        checkForComodification();
        try {
            //获取游标前面一位元素
            int i = cursor - 1;
            E previous = get(i);
            //为什么上次操作的位置是 游标当前位置呢？哦，看错了，游标也前移了
            lastRet = cursor = i;
            return previous;
        } catch (IndexOutOfBoundsException e) {
            checkForComodification();
            throw new NoSuchElementException();
        }
    }

    //下一个元素的位置就是当前游标所在位置
    public int nextIndex() {
        return cursor;
    }

    public int previousIndex() {
        return cursor-1;
    }

    public void set(E e) {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            //子类得检查 lasRet 是否为 -1
            AbstractList.this.set(lastRet, e);
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    public void add(E e) {
        checkForComodification();

        try {
            int i = cursor;
            AbstractList.this.add(i, e);
            //又置为 -1 了
            lastRet = -1;
            cursor = i + 1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}

ListItr 在 Itr 基础上多了向前和 set 操作。

两种内部类

在 subList 方法中我们发现在切分子序列时会分为两类，RandomAccess or not：

public List<E> subList(int fromIndex, int toIndex) {
    return (this instanceof RandomAccess ?
            new RandomAccessSubList<>(this, fromIndex, toIndex) :
            new SubList<>(this, fromIndex, toIndex));
}

RandomAccess

public interface RandomAccess {
}

RandomAccess 是一个空的接口，它用来标识某个类是否支持随机访问（随机访问，相对比“按顺序访问”）。一个支持随机访问的类明显可以使用更加高效的算法。

List 中支持随机访问最佳的例子就是 ArrayList, 它的数据结构使得 get(), set(), add()等方法的时间复杂度都是 O(1);

反例就是 LinkedList, 链表结构使得它不支持随机访问，只能按序访问，因此在一些操作上性能略逊一筹。

通常在操作一个 List 对象时，通常会判断是否支持随机访问，也就是* 是否为 RandomAccess 的实例*，从而使用不同的算法。

比如遍历，实现了 RandomAccess 的集合使用 get():

for (int i=0, n=list.size(); i &lt; n; i++)
          list.get(i);

比用迭代器更快：

  for (Iterator i=list.iterator(); i.hasNext(); )
      i.next();

实现了 RandomAccess 接口的类有：
ArrayList, AttributeList, CopyOnWriteArrayList, Vector, Stack 等。

SubList 源码：

// AbstractList 的子类，表示父 List 的一部分
class SubList<E> extends AbstractList<E> {
    private final AbstractList<E> l;
    private final int offset;
    private int size;

//构造参数:
//list ：父 List
//fromIndex : 从父 List 中开始的位置
//toIndex : 在父 List 中哪里结束
SubList(AbstractList<E> list, int fromIndex, int toIndex) {
    if (fromIndex < 0)
        throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
    if (toIndex > list.size())
        throw new IndexOutOfBoundsException("toIndex = " + toIndex);
    if (fromIndex > toIndex)
        throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                           ") > toIndex(" + toIndex + ")");
    l = list;
    offset = fromIndex;
    size = toIndex - fromIndex;
    //和父类使用同一个 modCount
    this.modCount = l.modCount;
}

//使用父类的 set()
public E set(int index, E element) {
    rangeCheck(index);
    checkForComodification();
    return l.set(index+offset, element);
}

//使用父类的 get()
public E get(int index) {
    rangeCheck(index);
    checkForComodification();
    return l.get(index+offset);
}

//子 List 的大小
public int size() {
    checkForComodification();
    return size;
}

public void add(int index, E element) {
    rangeCheckForAdd(index);
    checkForComodification();
    //根据子 List 开始的位置，加上偏移量，直接在父 List 上进行添加
    l.add(index+offset, element);
    this.modCount = l.modCount;
    size++;
}

public E remove(int index) {
    rangeCheck(index);
    checkForComodification();
    //根据子 List 开始的位置，加上偏移量，直接在父 List 上进行删除
    E result = l.remove(index+offset);
    this.modCount = l.modCount;
    size--;
    return result;
}

protected void removeRange(int fromIndex, int toIndex) {
    checkForComodification();
    //调用父类的 局部删除
    l.removeRange(fromIndex+offset, toIndex+offset);
    this.modCount = l.modCount;
    size -= (toIndex-fromIndex);
}

public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);
    int cSize = c.size();
    if (cSize==0)
        return false;

    checkForComodification();
    //还是使用的父类 addAll()
    l.addAll(offset+index, c);
    this.modCount = l.modCount;
    size += cSize;
    return true;
}

public Iterator<E> iterator() {
    return listIterator();
}

public ListIterator<E> listIterator(final int index) {
    checkForComodification();
    rangeCheckForAdd(index);

    //创建一个 匿名内部 ListIterator，指向的还是 父类的 listIterator
    return new ListIterator<E>() {
        private final ListIterator<E> i = l.listIterator(index+offset);

        public boolean hasNext() {
            return nextIndex() < size;
        }

        public E next() {
            if (hasNext())
                return i.next();
            else
                throw new NoSuchElementException();
        }

        public boolean hasPrevious() {
            return previousIndex() >= 0;
        }

        public E previous() {
            if (hasPrevious())
                return i.previous();
            else
                throw new NoSuchElementException();
        }

        public int nextIndex() {
            return i.nextIndex() - offset;
        }

        public int previousIndex() {
            return i.previousIndex() - offset;
        }

        public void remove() {
            i.remove();
            SubList.this.modCount = l.modCount;
            size--;
        }

        public void set(E e) {
            i.set(e);
        }

        public void add(E e) {
            i.add(e);
            SubList.this.modCount = l.modCount;
            size++;
        }
    };
}

public List<E> subList(int fromIndex, int toIndex) {
    return new SubList<>(this, fromIndex, toIndex);
}

private void rangeCheck(int index) {
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private void rangeCheckForAdd(int index) {
    if (index < 0 || index > size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private String outOfBoundsMsg(int index) {
    return "Index: "+index+", Size: "+size;
}

private void checkForComodification() {
    if (this.modCount != l.modCount)
        throw new ConcurrentModificationException();
}
}

总结：SubList 就是吭老族，虽然自立门户，等到要干活时，使用的都是父类的方法，父类的数据。

所以可以通过它来间接操作父 List。

RandomAccessSubList 源码：

class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
    RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
        super(list, fromIndex, toIndex);
    }

    public List<E> subList(int fromIndex, int toIndex) {
        return new RandomAccessSubList<>(this, fromIndex, toIndex);
    }
}

RandomAccessSubList 只不过是在 SubList 之外加了个 RandomAccess 的标识，表明他可以支持随机访问而已，别无他尔。

总结：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

AbstractList 作为 List 家族的中坚力量

既实现了 List 的期望
也继承了 AbstractCollection 的传统
还创建了内部的迭代器 Itr, ListItr
还有两个内部子类 SubList 和 RandomAccessSublist；

百废俱兴，AbstractList 博采众长，制定了 List 家族的家规，List 家族基础已经搭建的差不多了。

List 家族在 AbstractList 的指导下出了几个英豪，成为了 Java 世界的栋梁之才，具体细节，我们下回再续。

今天心情有点美丽，学学 ArrayList 放松下吧！

什么是 ArrayList

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

ArrayList 是 Java 集合框架中 List接口的一个实现类。

可以说 ArrayList 是我们使用最多的 List 集合，它有以下特点：

容量不固定，想放多少放多少（当然有最大阈值，但一般达不到）
有序的（元素输出顺序与输入顺序一致）
元素可以为 null
效率高
- size(), isEmpty(), get(), set() iterator(), ListIterator() 方法的时间复杂度都是 O(1)
- add() 添加操作的时间复杂度平均为 O(n)
- 其他所有操作的时间复杂度几乎都是 O(n)
占用空间更小
- 对比 LinkedList，不用占用额外空间维护链表结构

那 ArrayList 为什么有这些优点呢？我们通过源码一一解析。

ArrayList 的成员变量

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

1.底层数据结构，数组：

transient Object[] elementData

由于数组类型为 Object，所以允许添加 null 。
transient 说明这个数组无法序列化。
初始时为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 。

2.默认的空数组：

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

private static final Object[] EMPTY_ELEMENTDATA = {};

不清楚它俩啥区别。

3.数组初始容量为 10：

private static final int DEFAULT_CAPACITY = 10;

4.数组中当前元素个数：

private int size;

size <= capacity

5.数组最大容量：

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

Integer.MAX_VALUE = 0x7fffffff

换算成二进制： 2^31 - 1，1111111111111111111111111111111

十进制就是：2147483647，二十一亿多。

一些虚拟器需要在数组前加个头标签，所以减去 8 。
当想要分配比 MAX_ARRAY_SIZE 大的个数就会报 OutOfMemoryError。

ArrayList 的关键方法

1.构造函数

ArrayList 有三种构造函数：

//初始为空数组
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//根据指定容量，创建个对象数组
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

//直接创建和指定集合一样内容的 ArrayList
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray 有可能不返回一个 Object 数组
        if (elementData.getClass() != Object[].class)
            //使用 Arrays.copy 方法拷创建一个 Object 数组
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

2.添加元素：

public boolean add(E e) {
    //对数组的容量进行调整
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

//在指定位置添加一个元素
public void add(int index, E element) {
    rangeCheckForAdd(index);

    //对数组的容量进行调整
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //整体后移一位，效率不太好啊
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}


//添加一个集合
public boolean addAll(Collection<? extends E> c) {
    //把该集合转为对象数组
    Object[] a = c.toArray();
    int numNew = a.length;
    //增加容量
    ensureCapacityInternal(size + numNew);  // Increments modCount
    //挨个向后迁移
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    //新数组有元素，就返回 true
    return numNew != 0;
}

//在指定位置，添加一个集合
public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount

    int numMoved = size - index;
    //原来的数组挨个向后迁移
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);
    //把新的集合数组 添加到指定位置
    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

虽说 System.arraycopy 是底层方法，但每次添加都后移一位还是不太好。

3.对数组的容量进行调整：

public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        // 不是默认的数组，说明已经添加了元素
        ? 0
        // 默认的容量
        : DEFAULT_CAPACITY;

    if (minCapacity > minExpand) {
        //当前元素个数比默认容量大
        ensureExplicitCapacity(minCapacity);
    }
}

private void ensureCapacityInternal(int minCapacity) {
    //还没有添加元素
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //最小容量取默认容量和 当前元素个数 最大值
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // 容量不够了，需要扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

我们可以主动调用 ensureCapcity 来增加 ArrayList 对象的容量，这样就避免添加元素满了时扩容、挨个复制后移等消耗。

4.扩容：

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 1.5 倍 原来容量
    int newCapacity = oldCapacity + (oldCapacity >> 1);

    //如果当前容量还没达到 1.5 倍旧容量，就使用当前容量，省的站那么多地方
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;

    //新的容量居然超出了 MAX_ARRAY_SIZE
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        //最大容量可以是 Integer.MAX_VALUE
        newCapacity = hugeCapacity(minCapacity);

    // minCapacity 一般跟元素个数 size 很接近，所以新建的数组容量为 newCapacity 更宽松些
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

5.查询，修改等操作，直接根据角标对数组操作，都很快：

E elementData(int index) {
    return (E) elementData[index];
}

//获取
public E get(int index) {
    rangeCheck(index);
    //直接根据数组角标返回元素，快的一比
    return elementData(index);
}

//修改
public E set(int index, E element) {
    rangeCheck(index);
    E oldValue = elementData(index);

    //直接对数组操作
    elementData[index] = element;
    //返回原来的值
    return oldValue;
}

6.删除，还是有点慢：

//根据位置删除
public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    //挨个往前移一位
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    //原数组中最后一个元素删掉
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

//删除某个元素
public boolean remove(Object o) {
    if (o == null) {
        //挨个遍历找到目标
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                //快速删除
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

//内部方法，“快速删除”，就是把重复的代码移到一个方法里
//没看出来比其他 remove 哪儿快了 - -
private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

//保留公共的
public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}

//删除或者保留指定集合中的元素
private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    //使用两个变量，一个负责向后扫描，一个从 0 开始，等待覆盖操作
    int r = 0, w = 0;
    boolean modified = false;
    try {
        //遍历 ArrayList 集合
        for (; r < size; r++)
            //如果指定集合中是否有这个元素，根据 complement 判断是否往前覆盖删除
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        //发生了异常，直接把 r 后面的复制到 w 后面
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            // 清除多余的元素，clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

//清楚全部
public void clear() {
    modCount++;
    //并没有直接使数组指向 null,而是逐个把元素置为空
    //下次使用时就不用重新 new 了
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

7.判断状态：

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

//遍历，第一次找到就返回
public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

//倒着遍历
public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

8.转换成数组：

public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

public <T> T[] toArray(T[] a) {
    //如果只是要把一部分转换成数组
    if (a.length < size)
        // Make a new array of a's runtime type, but my contents:
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    //全部元素拷贝到 数组 a
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}

看下 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);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

如果 newType 是一个对象对组，就直接把 original 的元素拷贝到对象数组中；
否则新建一个 newType 类型的数组。

ArrayList 的内部实现

1.迭代器 Iterator, ListIterator 没什么特别，直接使用角标访问数组的元素，:

private class ListItr extends Itr implements ListIterator<E> {
    ListItr(int index) {
        super();
        cursor = index;
    }

    public boolean hasPrevious() {
        return cursor != 0;
    }

    public int nextIndex() {
        return cursor;
    }

    public int previousIndex() {
        return cursor - 1;
    }

    @SuppressWarnings("unchecked")
    public E previous() {
        checkForComodification();
        int i = cursor - 1;
        if (i < 0)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i;
        return (E) elementData[lastRet = i];
    }

    public void set(E e) {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.set(lastRet, e);
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    public void add(E e) {
        checkForComodification();

        try {
            int i = cursor;
            ArrayList.this.add(i, e);
            cursor = i + 1;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}

在 Java 集合深入理解：AbstractList 中我们介绍了 RandomAccess，里面提到，支持 RandomAccess 的对象，遍历时使用 get 比迭代器更快。

由于 ArrayList 继承自 RandomAccess，而且它的迭代器都是基于 ArrayList 的方法和数组直接操作，所以遍历时 get 的效率要 >= 迭代器。

int i=0, n=list.size(); i &lt; n; i++)
      list.get(i);

比用迭代器更快：

for (Iterator i=list.iterator(); i.hasNext(); )
     i.next();

另外，由于 ArrayList 不是同步的，所以在并发访问时，如果在迭代的同时有其他线程修改了 ArrayList, fail-fast 的迭代器 Iterator/ListIterator 会报 ConcurrentModificationException 错。

因此我们在并发环境下需要外部给 ArrayList 加个同步锁，或者直接在初始化时用 Collections.synchronizedList 方法进行包装：

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

Thanks

http://www.trinea.cn/android/arraylist-linkedlist-loop-performance/s

http://blog.csdn.net/u011518120/article/details/52026076

http://blog.csdn.net/wl_ldy/article/details/5938390

http://blog.csdn.net/zhangerqing/article/details/8122075

今天有点无聊，来学学 AbstractSequentialList 解解闷吧！

AbstractSequentialList 没有什么特别的，这里介绍是为了理解 LinkedList 更容易。

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

什么是 AbstractSequentialList

（ Sequential 相继的，按次序的）

AbstractSequentialList 继承自 AbstractList，是 LinkedList 的父类，是 List 接口的简化版实现。

简化在哪儿呢？简化在 AbstractSequentialList 只支持按次序访问，而不像 AbstractList 那样支持随机访问。

想要实现一个支持按次序访问的 List的话，只需要继承这个抽象类，然后把指定的抽象方法实现就好了。需要实现的方法：

size()
listIterator()，返回一个 ListIterator

你需要实现一个 ListIterator, 实现它的 hasNext(), hasPrevious(), next(), previous(), 还有那几个获取位置的方法，这样你就得到一个不可变的 ListIterator 了。如果你想让它可修改，还需要实现 add(), remove(), set() 方法。

正如在每个 Collection 接口中提倡的那样，AbstractSequentialList 的子类需要提供两个构造函数，一个无参，一个以 Collection 为参数。

成员函数

AbstractSequentialList 在 AbstractList 的基础上实现了以下方法：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

1.获取迭代器：

public Iterator<E> iterator() {
    //调用继承自
    return listIterator();
}

//继承 AbstractList 的 listIterator()
public ListIterator<E> listIterator() {
    return listIterator(0);
}

//需要实现类实现的方法
public abstract ListIterator<E> listIterator(int index);

2.add(int, E) 添加元素到指定位置，将当前处于该位置（如果有的话）和任何后续元素的元素移到右边（添加一个到它们的索引）：

public void add(int index, E element) {
    try {
        //调用 ListIterator.add()
        listIterator(index).add(element);
    } catch (NoSuchElementException exc) {
        throw new IndexOutOfBoundsException("Index: "+index);
    }
}

如果 Listerator 的实现类实现 add() 方法，会报 `UnsupportedOperationException` 错。

3.addAll(int index, Collection

用获取到的 listIterator 逐个添加集合中的元素,这就要考验 ListIterator.add 方法的实现效率了，总不能每次都后移一位吧

的确在目前集合框架中 AbstractSequentialList 的唯一实现类 LinkedList 实现的 ListIterator 中，由于 LinkedList 的双休链表特性，每次 add 只需要调整指针指向就可以了。

4.get(int index) 获取指定位置的元素：

public E get(int index) {
    try {
        return listIterator(index).next();
    } catch (NoSuchElementException exc) {
        throw new IndexOutOfBoundsException("Index: "+index);
    }
}

5.set(int index, E element) 修改指定位置的元素为新的：

public E set(int index, E element) {
    try {
        ListIterator<E> e = listIterator(index);
        E oldVal = e.next();
        e.set(element);
        return oldVal;
    } catch (NoSuchElementException exc) {
        throw new IndexOutOfBoundsException("Index: "+index);
    }
}

6.remove(int index) 删除指定位置的元素：

public E remove(int index) {
    try {
        ListIterator<E> e = listIterator(index);
        E outCast = e.next();
        e.remove();
        return outCast;
    } catch (NoSuchElementException exc) {
        throw new IndexOutOfBoundsException("Index: "+index);
    }
}

总结

可以看到， AbstractSequentialList 把父类 AbstractList 中没有实现或者没有支持的操作都实现了，而且都是调用的 ListIterator 相关方法进行操作。

在 Java 集合深入理解：AbstractList 中我们介绍了 RandomAccess，里面提到，支持 RandomAccess 的对象，遍历时使用 get 比迭代器更快。

而 AbstractSequentialList 只支持迭代器按顺序访问，不支持 RandomAccess，所以遍历 AbstractSequentialList 的子类，使用 for 循环 get() 的效率要 <= 迭代器遍历：

int i=0, n=list.size(); i &lt; n; i++)
      list.get(i);

get()太慢，还不如用迭代器：

for (Iterator i=list.iterator(); i.hasNext(); )
     i.next();

Thanks

http://www.trinea.cn/android/arraylist-linkedlist-loop-performance/

今天心情不太好，来学一下 List 吧！

什么是队列

队列是数据结构中比较重要的一种类型，它支持 FIFO，尾部添加、头部删除（先进队列的元素先出队列），跟我们生活中的排队类似。

队列有两种：

单队列
循环队列

单队列就是常见的队列, 每次添加元素时，都是添加到队尾：

以数组实现的队列为例，初始时队列长度固定为 4，font 和 rear 均为 0：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

每添加一个元素，rear 后移一位。当添加四个元素后， rear 到了索引为 4 的位置：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

这时 a1,a2 出队，front 后移动到 2：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

这时想要再添加两个元素，但 rear 后移两位后就会越界：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

明明有三个空位，却只能再放入一个！这就是单队列的“假溢出”情况。

（上述参考借鉴自 http://www.nowamagic.net/librarys/veda/detail/2350）

针对这种情况，解决办法就是后面满了，就再从头开始，也就是头尾相接的循环。这就是 “循环队列” 的概念。

循环队列:

循环队列中，
rear = (rear - size) % size

接着上面的例子，当 rear 大于队列长度时，rear = ( 5 - 5) % 5 = 0 :

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

这样继续添加时，还可以添加几个元素：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

那如何判断队列是否装满元素了呢，单使用 front == rear 无法判断究竟是空的还是满了。

两种方法：

加个标志 flag ,初始为 false，添加满了置为 true；
不以 front = rear 为放满标志，改为 (rear - front) % size = 1。

法 2 的公式放满元素时空余了一个位置，这个公式是什么意思呢？

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

接着上面的情况，当 rear 从后面添加元素跑到前面 0 时，再添加一个元素 a6，rear 后移一位到 1，这时 front = 2, (1 - 2) % 5 = 1, 满足放满条件。

因此，当 rear > font 时，队列中元素个数 = rear - font;

当 rear < font 时，队列中元素分为两部分： size - font 和 rear ,也就是 rear + size - font。以上述图片为例，队列中元素个数 = 1 + 5 - 2 = 4.

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

接着我们介绍 Java 集合框架中的队列 Queue

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

Java 集合中的 Queue 继承自 Collection 接口，Deque, LinkedList, PriorityQueue, BlockingQueue 等类都实现了它。

Queue 用来存放等待处理元素的集合，这种场景一般用于缓冲、并发访问。

除了继承 Collection 接口的一些方法，Queue 还添加了额外的添加、删除、查询操作。

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

添加、删除、查询这些个操作都提供了两种形式，其中一种在操作失败时直接抛出异常，而另一种则返回一个特殊的值：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

Queue 方法介绍：

1.add(E), offer(E) 在尾部添加:

boolean add(E e);

boolean offer(E e);

他们的共同之处是建议实现类禁止添加 null 元素，否则会报空指针 NullPointerException；

不同之处在于 add() 方法在添加失败（比如队列已满）时会报一些运行时错误错；而 offer() 方法即使在添加失败时也不会奔溃，只会返回 false。

2016.11.21 添加

注意

Queue 是个接口，它提供的 add, offer 方法初衷是希望子类能够禁止添加元素为 null，这样可以避免在查询时返回 null 究竟是正确还是错误。

事实上大多数 Queue 的实现类的确响应了 Queue 接口的规定，比如 ArrayBlockingQueue，PriorityBlockingQueue 等等。

但还是有一些实现类没有这样要求，比如 LinkedList。

感谢 sumsear 指出。

2.remove(), poll() 删除并返回头部：

E remove();

E poll();

当队列为空时 remove() 方法会报 NoSuchElementException 错; 而 poll() 不会奔溃，只会返回 null。

3.element(), peek() 获取但不删除：

E element();

E peek();

当队列为空时 element() 抛出异常；peek() 不会奔溃，只会返回 null。

其他

1.虽然 LinkedList 没有禁止添加 null，但是一般情况下 Queue 的实现类都不允许添加 null 元素，为啥呢？因为 poll(), peek() 方法在异常的时候会返回 null，你添加了 null　以后，当获取时不好分辨究竟是否正确返回。

2.Queue 一般都是 FIFO 的，但是也有例外，比如优先队列 priority queue（它的顺序是根据自然排序或者自定义 comparator 的）；再比如 LIFO 的队列（跟栈一样，后来进去的先出去）。

不论进入、出去的先后顺序是怎样的，使用 remove()，poll() 方法操作的都是头部的元素；而插入的位置则不一定是在队尾了，不同的 queue 会有不同的插入逻辑。

Thanks

https://docs.oracle.com/javase/tutorial/collections/interfaces/queue.html

https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html

http://www.nowamagic.net/librarys/veda/detail/2350

http://www.nowamagic.net/librarys/veda/detail/2351

什么是 Deque

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

Deque 是 Double ended queue (双端队列) 的缩写,读音和 deck 一样，蛋壳。

Deque 继承自 Queue,直接实现了它的有 LinkedList, ArayDeque, ConcurrentLinkedDeque 等。

Deque 支持容量受限的双端队列，也支持大小不固定的。一般双端队列大小不确定。

Deque 接口定义了一些从头部和尾部访问元素的方法。比如分别在头部、尾部进行插入、删除、获取元素。和 Queue

类似，每个操作都有两种方法，一种在异常情况下直接抛出异常奔溃，另一种则不会抛异常，而是返回特殊的值，比如 false, null …

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

插入（Insert）方法的第二种是针对固定大小的双端队列设计的。大多数情况下插入都不会失败。

Deque 继承了 Queue 接口的方法。当 Deque 当做队列使用时（FIFO），添加元素是添加到队尾，删除时删除的是头部元素。从 Queue 接口继承的方法对应容器的方法如图所示：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

Deque 也能当栈用（后进先出）。这时入栈、出栈元素都是在双端队列的头部进行。Deque 中和栈对应的方法如图所示：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

Deque 包含的方法如下图所示：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

根据名字就能看到功能，具体实现我们下篇看 LinkedList 源码时介绍。

Deque 的实现类

Deque 的实现类主要分为两种场景：

一般场景
- LinkedList 大小可变的链表双端队列，允许元素为 null
- ArrayDeque 大下可变的数组双端队列，不允许 null
并发场景
- LinkedBlockingDeque 如果队列为空时，获取操作将会阻塞，知道有元素添加

Deque 与工作密取

在并发编程中，双端队列 Deque 还用于 “工作密取” 模式。

什么是工作密取呢？

在生产者-消费者模式中，所有消费者都从一个工作队列中取元素，一般使用阻塞队列实现；

而在工作密取模式中，每个消费者有其单独的工作队列，如果它完成了自己双端队列中的全部工作，那么它就可以从其他消费者的双端队列末尾秘密地获取工作。

工作密取模式对比传统的生产者-消费者模式，更为灵活，因为多个线程不会因为在同一个工作队列中抢占内容发生竞争。在大多数时候，它们只是访问自己的双端队列。即使需要访问另一个队列时，也是从队列的尾部获取工作，降低了队列上的竞争程度。

Thanks

https://docs.oracle.com/javase/tutorial/collections/interfaces/deque.html
https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html
http://www.nowamagic.net/librarys/veda/detail/2296
《Java 并发编程实战》

今天心情鱼肚白，来学学 LinkedList 吧！

日常开发中，保存一组数据使用的最多的就是 ArrayList，其次就是 LinkedList 了。

我们知道 ArrayList 是以数组实现的，遍历时很快，但是插入、删除时都需要移动后面的元素，效率略差些。

而LinkedList 是以链表实现的，插入、删除时只需要改变前后两个节点指针指向即可，省事不少。

今天来看下 LinkedList 源码。

#

LinkedList 继承结构

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

LinkedList 继承自 AbstractSequentialList 接口，同时了还实现了 Deque, Queue 接口。

LinkedList 双向链表实现

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

可以看到， LinkedList 的成员变量只有三个：

头节点 first
尾节点 last
容量 size

节点是一个双向节点：
点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

用一副图表示节点：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

LinkedList 的方法

1.关键的几个内部方法（头部添加删除，尾部添加删除，获取指定节点，指定节点的添加删除）

//插入到头部
private void linkFirst(E e) {
    //获取头节点
    final Node<E> f = first;
    //新建一个节点，尾部指向之前的 头元素 first
    final Node<E> newNode = new Node<>(null, e, f);
    //first 指向新建的节点
    first = newNode;
    //如果之前是空链表，新建的节点 也是最后一个节点
    if (f == null)
        last = newNode;
    else
        //原来的第一个节点（现在的第二个）头部指向新建的头结点
        f.prev = newNode;
    size++;
    modCount++;
}

//插入到尾部
void linkLast(E e) {
    //获取尾部节点
    final Node<E> l = last;
    //新建一个节点，头部指向之前的 尾节点 last
    final Node<E> newNode = new Node<>(l, e, null);
    //last 指向新建的节点
    last = newNode;
    //如果之前是空链表， 新建的节点也是第一个节点
    if (l == null)
        first = newNode;
    else
        //原来的尾节点尾部指向新建的尾节点
        l.next = newNode;
    size++;
    modCount++;
}

//在 指定节点 前插入一个元素，这里假设 指定节点不为 null
void linkBefore(E e, Node<E> succ) {
    // 获取指定节点 succ 前面的一个节点
    final Node<E> pred = succ.prev;
    //新建一个节点，头部指向 succ 前面的节点，尾部指向 succ 节点，数据为 e
    final Node<E> newNode = new Node<>(pred, e, succ);
    //让 succ 节点头部指向 新建的节点
    succ.prev = newNode;
    //如果 succ 前面的节点为空，说明 succ 就是第一个节点，那现在新建的节点就变成第一个节点了
    if (pred == null)
        first = newNode;
    else
        //如果前面有节点，让前面的节点
        pred.next = newNode;
    size++;
    modCount++;
}

//删除头节点并返回该节点上的数据，假设不为 null
private E unlinkFirst(Node<E> f) {
    // 获取数据，一会儿返回
    final E element = f.item;
    //获取头节点后面一个节点
    final Node<E> next = f.next;
    //使头节点上数据为空，尾部指向空
    f.item = null;
    f.next = null; // help GC
    //现在头节点后边的节点变成第一个了
    first = next;
    //如果头节点后面的节点为 null，说明移除这个节点后，链表里没节点了
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

//删除尾部节点并返回，假设不为空
private E unlinkLast(Node<E> l) {

    final E element = l.item;
    //获取倒数第二个节点
    final Node<E> prev = l.prev;
    //尾节点数据、尾指针置为空
    l.item = null;
    l.prev = null; // help GC
    //现在倒数第二变成倒数第一了
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}

//删除某个指定节点
E unlink(Node<E> x) {
    // 假设 x 不为空
    final E element = x.item;
    //获取指定节点前面、后面的节点
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    //如果前面没有节点，说明 x 是第一个
    if (prev == null) {
        first = next;
    } else {
        //前面有节点，让前面节点跨过 x 直接指向 x 后面的节点
        prev.next = next;
        x.prev = null;
    }

    //如果后面没有节点，说 x 是最后一个节点
    if (next == null) {
        last = prev;
    } else {
        //后面有节点，让后面的节点指向 x 前面的
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

//获取指定位置的节点
Node<E> node(int index) {
    // 假设指定位置有元素

    //二分一下，如果小于 size 的一半，从头开始遍历
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        //大于 size 一半，从尾部倒着遍历
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

这些内部方法实现了对链表节点的基本修改操作，每次操作都只要修改前后节点的指针，时间复杂度为 O(1)。

很多公开方法都是通过调用它们实现的。

2.公开的添加方法：

//普通的在尾部添加元素
public boolean add(E e) {
    linkLast(e);
    return true;
}

//在指定位置添加元素
public void add(int index, E element) {
    checkPositionIndex(index);
    //指定位置也有可能是在尾部
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

//添加一个集合的元素
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);

    //把 要添加的集合转成一个 数组
    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;

    //创建两个节点，分别指向要插入位置前面和后面的节点
    Node<E> pred, succ;
    //要添加到尾部
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        //要添加到中间， succ 指向 index 位置的节点，pred 指向它前一个
        succ = node(index);
        pred = succ.prev;
    }

    //遍历要添加内容的数组
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        //创建新节点，头指针指向 pred
        Node<E> newNode = new Node<>(pred, e, null);
        //如果 pred 为空，说明新建的这个是头节点
        if (pred == null)
            first = newNode;
        else
            //pred 指向新建的节点
            pred.next = newNode;
        //pred 后移一位
        pred = newNode;
    }

    //添加完后需要修改尾指针 last
    if (succ == null) {
        //如果 succ 为空，说明要插入的位置就是尾部，现在 pred 已经到最后了
        last = pred;
    } else {
        //否则 pred 指向后面的元素
        pred.next = succ;
        succ.prev = pred;
    }

    //元素个数增加
    size += numNew;
    modCount++;
    return true;
}

//添加到头部，时间复杂度为 O(1)
public void addFirst(E e) {
    linkFirst(e);
}

//添加到尾部，时间复杂度为 O(1)
public void addLast(E e) {
    linkLast(e);
}

继承自双端队列的添加方法：

//入栈，其实就是在头部添加元素
public void push(E e) {
    addFirst(e);
}

//安全的添加操作，在尾部添加
public boolean offer(E e) {
    return add(e);
}

//在头部添加
public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

//尾部添加
public boolean offerLast(E e) {
    addLast(e);
    return true;
}

3.删除方法：

//删除头部节点
public E remove() {
    return removeFirst();
}

//删除指定位置节点
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

//删除包含指定元素的节点，这就得遍历了
public boolean remove(Object o) {
    if (o == null) {
        //遍历终止条件，不等于 null
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

//删除头部元素
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

//删除尾部元素
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

//删除首次出现的指定元素，从头遍历
public boolean removeFirstOccurrence(Object o) {
    return remove(o);
}

//删除最后一次出现的指定元素，倒过来遍历
public boolean removeLastOccurrence(Object o) {
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

继承自双端队列的删除方法：

public E pop() {
    return removeFirst();
}

public E pollFirst() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

public E pollLast() {
    final Node<E> l = last;
    return (l == null) ? null : unlinkLast(l);
}

清除全部元素其实只需要把首尾都置为 null, 这个链表就已经是空的，因为无法访问元素。
但是为了避免浪费空间，需要把中间节点都置为 null：

public void clear() {
    for (Node<E> x = first; x != null; ) {
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
}

3.公开的修改方法，只有一个 set :

//set 很简单，找到这个节点，替换数据就好了
public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

4.公开的查询方法：

//挨个遍历，获取第一次出现位置
public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

//倒着遍历，查询最后一次出现的位置
public int lastIndexOf(Object o) {
    int index = size;
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (x.item == null)
                return index;
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (o.equals(x.item))
                return index;
        }
    }
    return -1;
}

//是否包含指定元素
public boolean contains(Object o) {
    return indexOf(o) != -1;
}

//获取指定位置的元素，需要遍历
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

//获取第一个元素，很快
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

//获取第一个，同时删除它
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

//也是获取第一个，和 poll 不同的是不删除
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

//长得一样嘛
public E peekFirst() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
 }

//最后一个元素，也很快
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

public E peekLast() {
    final Node<E> l = last;
    return (l == null) ? null : l.item;
}

关键方法介绍完了，接下来是内部实现的迭代器，需要注意的是 LinkedList 实现了一个倒序迭代器 DescendingIterator；还实现了一个 ListIterator ，名叫 ListItr

迭代器

1.DescendingIterator 倒序迭代器

//很简单，就是游标直接在 迭代器尾部，然后颠倒黑白，说是向后遍历，实际是向前遍历
private class DescendingIterator implements Iterator<E> {
    private final ListItr itr = new ListItr(size());
    public boolean hasNext() {
        return itr.hasPrevious();
    }
    public E next() {
        return itr.previous();
    }
    public void remove() {
        itr.remove();
    }
}

2. ListItr 操作基本都是调用的内部关键方法，没什么特别的

private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;
    private int nextIndex;
    private int expectedModCount = modCount;

    ListItr(int index) {
        // 二分遍历，指定游标位置
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }

    public boolean hasNext() {
        return nextIndex < size;
    }

    public E next() {
        checkForComodification();
        if (!hasNext())
            throw new NoSuchElementException();
        //很简单，后移一位
        lastReturned = next;
        next = next.next;
        nextIndex++;
        return lastReturned.item;
    }

    public boolean hasPrevious() {
        return nextIndex > 0;
    }

    public E previous() {
        checkForComodification();
        if (!hasPrevious())
            throw new NoSuchElementException();

        lastReturned = next = (next == null) ? last : next.prev;
        nextIndex--;
        return lastReturned.item;
    }

    public int nextIndex() {
        return nextIndex;
    }

    public int previousIndex() {
        return nextIndex - 1;
    }

    public void remove() {
        checkForComodification();
        if (lastReturned == null)
            throw new IllegalStateException();

        Node<E> lastNext = lastReturned.next;
        unlink(lastReturned);
        if (next == lastReturned)
            next = lastNext;
        else
            nextIndex--;
        lastReturned = null;
        expectedModCount++;
    }

    public void set(E e) {
        if (lastReturned == null)
            throw new IllegalStateException();
        checkForComodification();
        lastReturned.item = e;
    }

    public void add(E e) {
        checkForComodification();
        lastReturned = null;
        if (next == null)
            linkLast(e);
        else
            linkBefore(e, next);
        nextIndex++;
        expectedModCount++;
    }

    public void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (modCount == expectedModCount && nextIndex < size) {
            action.accept(next.item);
            lastReturned = next;
            next = next.next;
            nextIndex++;
        }
        checkForComodification();
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

还有个 LLSpliterator 继承自 Spliterator， JDK 8 出来的新东东，这里暂不研究

Spliterator 是 Java 8 引入的新接口，顾名思义，Spliterator 可以理解为 Iterator 的 Split 版本（但用途要丰富很多）。

使用 Iterator 的时候，我们可以顺序地遍历容器中的元素，使用 Spliterator 的时候，我们可以将元素分割成多份，分别交于不于的线程去遍历，以提高效率。

使用 Spliterator 每次可以处理某个元素集合中的一个元素 — 不是从 Spliterator 中获取元素，而是使用 tryAdvance() 或 forEachRemaining() 方法对元素应用操作。

但 Spliterator 还可以用于估计其中保存的元素数量，而且还可以像细胞分裂一样变为一分为二。这些新增加的能力让流并行处理代码可以很方便地将工作分布到多个可用线程上完成。

转自 http://blog.sina.com.cn/s/blog_3fe961ae0102wxdb.html

总结

吐个槽，估计是很多人维护的，有些方法功能代码完全一样

比如：

private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}

private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

LinkedList 特点

双向链表实现
元素时有序的，输出顺序与输入顺序一致
允许元素为 null
所有指定位置的操作都是从头开始遍历进行的
和 ArrayList 一样，不是同步容器

并发访问注意事项

linkedList 和 ArrayList 一样，不是同步容器。所以需要外部做同步操作，或者直接用 Collections.synchronizedList 方法包一下，最好在创建时就报一下：

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

LinkedList 的迭代器都是 fail-fast 的: 如果在并发环境下，其他线程使用迭代器以外的方法修改数据，会导致 ConcurrentModificationException.

ArrayList VS LinkedList

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

ArrayList

基于数组，在数组中搜索和读取数据是很快的。因此 ArrayList 获取数据的时间复杂度是O(1);
但是添加、删除时该元素后面的所有元素都要移动，所以添加/删除数据效率不高；
另外其实还是有容量的，每次达到阈值需要扩容，这个操作比较影响效率。

LinkedList

基于双端链表，添加/删除元素只会影响周围的两个节点，开销很低；
只能顺序遍历，无法按照索引获得元素，因此查询效率不高；
没有固定容量，不需要扩容；
需要更多的内存，如文章开头图片所示 LinkedList 每个节点中需要多存储前后节点的信息，占用空间更多些。

拓展

两个队列实现一个栈？

http://www.cnblogs.com/kaituorensheng/archive/2013/03/02/2939690.html

Thanks

http://www.kutear.com/post/java/2016-08-16-think_in_java_11_and_17

https://segmentfault.com/a/1190000002516799

http://blog.csdn.net/mynameishuangshuai/article/category/6438276

http://blog.csdn.net/u011518120/article/details/51984405

http://blog.csdn.net/u010370082/article/details/45046755

http://www.lai18.com/content/1257052.html

今天刮台风，躲屋里看看 Vector ！

都说 Vector 是线程安全的 ArrayList，今天来根据源码看看是不是这么相似。

什么是 Vector

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

Vector 和 ArrayList 一样，都是继承自 AbstractList。它是 Stack 的父类。英文的意思是 “矢量”。

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

Vector 成员变量

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

1.底层也是个数组

protected Object[] elementData;

2.数组元素个数，为啥不就叫 size 呢？奇怪

protected int elementCount;

3.扩容时增长数量，允许用户自己设置。如果这个值是 0 或者负数，扩容时会扩大 2 倍，而不是 1.5

protected int capacityIncrement;

4.默认容量

private static final int DEFAULT_SIZE = 10;

Vector 的 4 种构造方法

//创建默认容量 10 的数组，同时增长量为 0 
public Vector() {
    this(DEFAULT_SIZE, 0);
}

//创建一个用户指定容量的数组，同时增长量为 0 
public Vector(int capacity) {
    this(capacity, 0);
}

//创建指定容量大小的数组，设置增长量。如果增长量为 非正数，扩容时会扩大两倍
public Vector(int capacity, int capacityIncrement) {
    if (capacity < 0) {
        throw new IllegalArgumentException("capacity < 0: " + capacity);
    }
    elementData = newElementArray(capacity);
    elementCount = 0;
    this.capacityIncrement = capacityIncrement;
}

//创建一个包含指定集合的数组
public Vector(Collection<? extends E> c) {
    //转成数组，赋值
    elementData = c.toArray();
    elementCount = elementData.length;

    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    //可能有这个神奇的 bug，用 Arrays.copyOf 重新创建、复制
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}

一个内部方法，返回一个新数组：

private E[] newElementArray(int size) {
    return (E[]) new Object[size];
}

Vector 的成员方法

1.先来看 JDK 7 中 Vector 的 3 种扩容方式：

//根据指定的容量进行扩容   
private void grow(int newCapacity) {
    //创建个指定容量的新数组，这里假设指定的容量比当前数组元素个数多
    E[] newData = newElementArray(newCapacity);
    //把当前数组复制到新创建的数组
    System.arraycopy(elementData, 0, newData, 0, elementCount);
    //当前数组指向新数组
    elementData = newData;
}

//默认增长一倍的扩容
private void growByOne() {
    int adding = 0;
    //扩容量 capacityIncrement 不大于 0，就增长一倍
    if (capacityIncrement <= 0) {
        if ((adding = elementData.length) == 0) {
            adding = 1;
        }
    } else {
        //否则按扩容量走
        adding = capacityIncrement;
    }

    //创建个新数组，大小为当前容量加上 adding
    E[] newData = newElementArray(elementData.length + adding);
    //复制，赋值
    System.arraycopy(elementData, 0, newData, 0, elementCount);
    elementData = newData;
}

//指定默认扩容数量的扩容
private void growBy(int required) {
    int adding = 0;
    //扩容量 capacityIncrement 不大于 0
    if (capacityIncrement <= 0) {
        //如果当前数组内没有元素，就按指定的数量扩容
        if ((adding = elementData.length) == 0) {
            adding = required;
        }
        //增加扩容数量到 指定的以上
        while (adding < required) {
            adding += adding;
        }
    } else {
        //扩容量大于 0 ，还是按指定的扩容数量走啊
        adding = (required / capacityIncrement) * capacityIncrement;
        //不过也可能出现偏差，因为是 int 做除法，所以扩容值至少是 指定扩容量的一倍以上
        if (adding < required) {
            adding += capacityIncrement;
        }
    }
    //创建，复制，赋值一条龙
    E[] newData = newElementArray(elementData.length + adding);
    System.arraycopy(elementData, 0, newData, 0, elementCount);
    elementData = newData;
}

2.（我能说一开始看错了，看成 JDK7 的了吗 - -）再来看JDK 8 中的扩容机制，变成一种了：

//扩容，传入最小容量，跟 ArrayList.grow(int) 很相似，只是扩大量不同 
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    //如果增长量 capacityIncrement 不大于 0 ，就扩容 2 倍
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

3.Vector中的 5 种添加元素的方法

//扩容前兆，检查数量
private void ensureCapacityHelper(int minCapacity) {
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

//在指定位置插入一个元素，同步的
public synchronized void insertElementAt(E obj, int index) {
    modCount++;
    if (index > elementCount) {
        throw new ArrayIndexOutOfBoundsException(index
                                                 + " > " + elementCount);
    }
    ensureCapacityHelper(elementCount + 1);
    //扩容后就把插入点后面的元素统一后移一位
    System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
    //赋值
    elementData[index] = obj;
    elementCount++;
}

//尾部插入元素，同步的
public synchronized void addElement(E obj) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = obj;
}

public void add(int index, E element) {
    insertElementAt(element, index);
}

//添加一个集合到尾部，同步的
public synchronized boolean addAll(Collection<? extends E> c) {
    modCount++;
    //转成数组
    Object[] a = c.toArray();
    int numNew = a.length;
    //扩容，复制到数组后面
    ensureCapacityHelper(elementCount + numNew);
    System.arraycopy(a, 0, elementData, elementCount, numNew);
    elementCount += numNew;
    return numNew != 0;
}

//添加一个结合到指定位置，同步的
public synchronized boolean addAll(int index, Collection<? extends E> c) {
    modCount++;
    if (index < 0 || index > elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityHelper(elementCount + numNew);

    //要移动多少个元素
    int numMoved = elementCount - index;
    if (numMoved > 0)
        //把插入位置后面的元素后移这么多位
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);
    //复制元素到数组中
    System.arraycopy(a, 0, elementData, index, numNew);
    elementCount += numNew;
    return numNew != 0;
}

最后还有个 ListIterator 的添加方法

    public void add(E e) {
        int i = cursor;
        synchronized (Vector.this) {
            checkForComodification();
            Vector.this.add(i, e);
            expectedModCount = modCount;
        }
        cursor = i + 1;
        lastRet = -1;
    }

4.Vector 中的 9 种删除方法

//删除指定位置的元素，同步的
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--;
    //最后多余的一位置为 null
    elementData[elementCount] = null; /* to let gc do its work */
}

//删除指定元素，同步的
public synchronized boolean removeElement(Object obj) {
    modCount++;
    int i = indexOf(obj);
    if (i >= 0) {
        removeElementAt(i);
        return true;
    }
    return false;
}

E elementData(int index) {
    return (E) elementData[index];
}

//删除指定位置的元素
public synchronized E remove(int index) {
    modCount++;
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    E oldValue = elementData(index);

    //找到删除该元素后，后面有多少位元素需要前移一位
    int numMoved = elementCount - index - 1;
    if (numMoved > 0)
        //迁移一位
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    //最后一位置为 null，不浪费空间
    elementData[--elementCount] = null; // Let gc do its work

    return oldValue;
}

public boolean remove(Object o) {
    return removeElement(o);
}

//删除指定集合的所有元素，同步的
public synchronized boolean removeAll(Collection<?> c) {
    //直接调用 AbstractCollection 的 removeAll 方法，用迭代器挨个删除
    return super.removeAll(c);
}

//删除所有元素，同步的
public synchronized void removeAllElements() {
    modCount++;
    // 挨个置为空，Let gc do its work
    for (int i = 0; i < elementCount; i++)
        elementData[i] = null;

    elementCount = 0;
}

//删除指定范围的元素,同步的
protected synchronized void removeRange(int fromIndex, int toIndex) {
    modCount++;
    //把结束位置以后的元素向前移动 指定数量个位置，覆盖
    int numMoved = elementCount - toIndex;
    System.arraycopy(elementData, toIndex, elementData, fromIndex,
                     numMoved);

    // 把多余的位置置为 null
    int newElementCount = elementCount - (toIndex-fromIndex);
    while (elementCount != newElementCount)
        elementData[--elementCount] = null;
}

//排除异己，同步的
public synchronized boolean retainAll(Collection<?> c) {
    return super.retainAll(c);
}

//JDK 1.8 新增的
public synchronized boolean removeIf(Predicate<? super E> filter) {
    Objects.requireNonNull(filter);
    // 将要删除的内容加入 removeSet
    int removeCount = 0;
    final int size = elementCount;
    final BitSet removeSet = new BitSet(size);
    final int expectedModCount = modCount;
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        @SuppressWarnings("unchecked")
        final E element = (E) elementData[i];
        if (filter.test(element)) {
            removeSet.set(i);
            removeCount++;
        }
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }

    // 遍历，删除
    final boolean anyToRemove = removeCount > 0;
    if (anyToRemove) {
        final int newSize = size - removeCount;
        for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
            i = removeSet.nextClearBit(i);
            elementData[j] = elementData[i];
        }
        for (int k=newSize; k < size; k++) {
            elementData[k] = null;  // Let gc do its work
        }
        elementCount = newSize;
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

    return anyToRemove;
}

写“同步的”写的手抽筋，还是统计不是同步的方法吧 - -。

5. Vector 中的修改方法

//修改指定位置为指定元素
public synchronized E set(int index, E element) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    //找到这个元素，直接设置新值
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

//修改指定位置为指定元素
public synchronized void setElementAt(E obj, int index) {
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                 elementCount);
    }
    //数组就是方便，直接更新就好了
    elementData[index] = obj;
}

//修改数组容量
public synchronized void setSize(int newSize) {
    modCount++;
    //元素个数超出容量就要扩容
    if (newSize > elementCount) {
        ensureCapacityHelper(newSize);
    } else {
        //新增 elementCount - newSize 个元素
        for (int i = newSize ; i < elementCount ; i++) {
            elementData[i] = null;
        }
    }
    elementCount = newSize;
}

//排序，修改顺序
public synchronized void sort(Comparator<? super E> c) {
    final int expectedModCount = modCount;
    //用的是 Arrays.sort 
    Arrays.sort((E[]) elementData, 0, elementCount, c);
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    modCount++;
}

//缩小数组容量，减少占用资源
public synchronized void trimToSize() {
    modCount++;
    int oldCapacity = elementData.length;
    if (elementCount < oldCapacity) {
        //新建个小点的数组，赋值
        elementData = Arrays.copyOf(elementData, elementCount);
    }
}

6. Vector 中的查询

//查找 o 从指定位置 index 开始第一次出现的位置
public synchronized int indexOf(Object o, int index) {
    if (o == null) {
        for (int i = index ; i < elementCount ; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = index ; i < elementCount ; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

//查找 o 在数组中首次出现的位置
public int indexOf(Object o) {
    return indexOf(o, 0);
}

//是否包含 O 
public boolean contains(Object o) {
    return indexOf(o, 0) >= 0;
}

//是否包含整个集合
public synchronized boolean containsAll(Collection<?> c) {
    //调用 AbstractCollection 的方法，使用迭代器挨个遍历查找，两重循环
    return super.containsAll(c);
}

//第一个元素，其实提供了 get() 方法就够了
public synchronized E firstElement() {
    if (elementCount == 0) {
        throw new NoSuchElementException();
    }
    return elementData(0);
}

//最后一个元素，其实提供了 get() 方法就够了
public synchronized E lastElement() {
    if (elementCount == 0) {
        throw new NoSuchElementException();
    }
    return elementData(elementCount - 1);
}

public synchronized boolean isEmpty() {
    return elementCount == 0;
}

//实际包含元素个数
public synchronized int size() {
    return elementCount;
}

//数组大小，>= 元素个数
public synchronized int capacity() {
    return elementData.length;
}

7. Vector 也可以转成数组

public synchronized Object[] toArray() {
    return Arrays.copyOf(elementData, elementCount);
}

//跟 ArrayList 简直一样
public synchronized <T> T[] toArray(T[] a) {
    if (a.length < elementCount)
        return (T[]) Arrays.copyOf(elementData, elementCount, a.getClass());

    System.arraycopy(elementData, 0, a, 0, elementCount);

    if (a.length > elementCount)
        a[elementCount] = null;

    return a;
}

8. Vector 中的迭代器

普通迭代器　Iterator:

public synchronized Iterator<E> iterator() {
    return new Itr();
}

private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    public boolean hasNext() {
        // 调用 next() 前的检查
        return cursor != elementCount;
    }

    public E next() {
        //注意了，Vector 连迭代器的方法也加了同步
        synchronized (Vector.this) {
            checkForComodification();
            int i = cursor;
            if (i >= elementCount)
                throw new NoSuchElementException();
            cursor = i + 1;
            return elementData(lastRet = i);
        }
    }

    public void remove() {
        if (lastRet == -1)
            throw new IllegalStateException();
        //注意了，Vector 连迭代器的方法也加了同步
        synchronized (Vector.this) {
            checkForComodification();
            Vector.this.remove(lastRet);
            expectedModCount = modCount;
        }
        cursor = lastRet;
        lastRet = -1;
    }

    //大概看下这个 1.8 的方法
    @Override
    public void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        synchronized (Vector.this) {
            final int size = elementCount;
            int i = cursor;
            if (i >= size) {
                return;
            }
    @SuppressWarnings("unchecked")
            final E[] elementData = (E[]) Vector.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                action.accept(elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

ListIterator:

public synchronized ListIterator<E> listIterator(int index) {
    if (index < 0 || index > elementCount)
        throw new IndexOutOfBoundsException("Index: "+index);
    return new ListItr(index);
}

final class ListItr extends Itr implements ListIterator<E> {
    ListItr(int index) {
        super();
        cursor = index;
    }

    public boolean hasPrevious() {
        return cursor != 0;
    }

    public int nextIndex() {
        return cursor;
    }

    public int previousIndex() {
        return cursor - 1;
    }

    public E previous() {
        synchronized (Vector.this) {
            checkForComodification();
            int i = cursor - 1;
            if (i < 0)
                throw new NoSuchElementException();
            cursor = i;
            return elementData(lastRet = i);
        }
    }

    public void set(E e) {
        if (lastRet == -1)
            throw new IllegalStateException();
        synchronized (Vector.this) {
            checkForComodification();
            Vector.this.set(lastRet, e);
        }
    }

    public void add(E e) {
        int i = cursor;
        synchronized (Vector.this) {
            checkForComodification();
            Vector.this.add(i, e);
            expectedModCount = modCount;
        }
        cursor = i + 1;
        lastRet = -1;
    }
}

//1.8 新增的略过。。。

//还多了个 sort 方法，自己传入的集合需要实现比较器
@SuppressWarnings("unchecked")
@Override
public synchronized void sort(Comparator<? super E> c) {
    final int expectedModCount = modCount;
    Arrays.sort((E[]) elementData, 0, elementCount, c);
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    modCount++;
}

Vector 还支持 Enumeration　迭代：

public Enumeration<E> elements() {
    return new Enumeration<E>() {
        int count = 0;

        public boolean hasMoreElements() {
            return count < elementCount;
        }

        public E nextElement() {
            synchronized (Vector.this) {
                if (count < elementCount) {
                    return elementData(count++);
                }
            }
            throw new NoSuchElementException("Vector Enumeration");
        }
    };
}

总结

Vector 特点

底层由一个可以增长的数组组成
Vector 通过 capacity (容量) 和 capacityIncrement (增长数量) 来尽量少的占用空间
扩容时默认扩大两倍
最好在插入大量元素前增加 vector 容量，那样可以减少重新申请内存的次数
通过 iterator 和 lastIterator 获得的迭代器是 fail-fast 的
通过 elements 获得的老版迭代器 Enumeration 不是 fail-fast 的
同步类，每个方法前都有同步锁 synchronized
在 JDK 2.0 以后，经过优化，Vector 也加入了 Java 集合框架大家族

Vector VS ArrayList

共同点：

都是基于数组
都支持随机访问
默认容量都是 10
都有扩容机制

区别：

Vector 出生的比较早，JDK 1.0 就出生了，ArrayList JDK 1.2 才出来
Vector 比 ArrayList 多一种迭代器 Enumeration
Vector 是线程安全的，ArrayList 不是
Vector 默认扩容 2 倍，ArrayList 是 1.5

如果没有线程安全的需求，一般推荐使用 ArrayList，而不是 Vector，因为每次都要获取锁，效率太低。

Thanks

https://docs.oracle.com/javase/8/docs/api/java/util/Vector.html

http://blog.csdn.net/u011518120/article/details/52192680

今天心情不错，再来一篇 Stack ！

数据结构中的栈

数据结构中，栈是一种线性数据结构，遵从 LIFO（后进先出）的操作顺序，所有操作都是在顶部进行

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

有点像羽毛球筒：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

栈通常有三种操作：

push 入栈
pop 栈顶元素出栈，并返回
peek 获取栈顶元素，并不删除

我们自定义一个栈时只要实现上述三个主要操作即可，本文中将使用 Java 中的 LinkedList　实现一个栈。

栈的使用场景：

栈最主要的意义就在于：入栈和出栈的对称性。

在 Android 开发中，我们经常需要开启、回退一个 Activity，其实这里就有栈的应用，每次开启Activity，如果不是特殊的启动模式，就会在栈顶加入一个 Activity，点击返回后，之前的 Activity 出栈。

其他场景比如递归（斐波那契数列，汉诺塔）。

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

Java 集合框架中的栈 Stack

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

Java 集合框架中的 Stack 继承自 Vector：

由于 Vector 有 4 个构造函数，加上 Stack 本身的一种，也就是说有 5 中创建 Stack 的方法
跟 Vector 一样，它是数组实现的栈。

Stack 的方法

Stack 中新建的方法比较少：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

1.构造函数

//构建一个空栈
public Stack() {
}

2.入栈

//调用的 Vector.addElement()
public E push(E item) {
    addElement(item);

    return item;
}

Vector 的 addElement() 方法，就是在数组尾部添加元素：

public synchronized void addElement(E obj) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = obj;
}

3.获取顶端元素，但不删除

public synchronized E peek() {
    //调用 Vector.size() 返回元素个数
    int     len = size();

    if (len == 0)
        throw new EmptyStackException();
    //调用 Vector.elementAt 得到栈顶元素
    return elementAt(len - 1);
}

Vector.elementAt(int):

public synchronized E elementAt(int index) {
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
    }

    return elementData(index);
}

Vector.elementData(int):

E elementData(int index) {
    return (E) elementData[index];
}

4.出栈

public synchronized E pop() {
    E       obj;
    int     len = size();

    //调用 peek() 获取顶端元素，一会儿返回
    obj = peek();
    //调用 Vector.removeElementAt 删除顶端元素
    removeElementAt(len - 1);

    return obj;
}

Vector.removeElementAt(int):

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--;
    elementData[elementCount] = null; /* to let gc do its work */
}

5.查找元素是否在栈中

public synchronized int search(Object o) {
    int i = lastIndexOf(o);

    //返回的是栈顶到该元素出现的位置的距离
    if (i >= 0) {
        return size() - i;
    }
    return -1;
}

6.是否为空

public boolean empty() {
    return size() == 0;
}

Vector.size():

public synchronized int size() {
    return elementCount;
}

总结

Java 集合框架中的 Stack 具有以下特点：

继承自 Vector
有 5 种创建 Stack 的方法
采用数组实现
除了 push()，剩下的方法都是同步的

用链表实现一个栈？

由于 Stack　是用数组实现的，我们用链表实现一下吧，这里就选择　LinkedList 来实现：

/**
 * description:LinkedList 模拟 Stack
 * <br/>
 * author: shixinzhang
 * <br/>
 * data: 10/23/2016
 */
public class LinkedListStack extends LinkedList{
    public LinkedListStack(){
        super();
    }

    @Override
    public void push(Object o) {
        super.push(o);
    }

    @Override
    public Object pop() {
        return super.pop();
    }

    @Override
    public Object peek() {
        return super.peek();
    }

    @Override
    public boolean isEmpty() {
        return super.isEmpty();
    }

    public int search(Object o){
        return indexOf(o);
    }
}

调用：

@Test
public void testPush() throws Exception {
    LinkedListStack stack = new LinkedListStack();
    System.out.println("栈是否为空: " + stack.isEmpty());

    stack.push("shixin");
    stack.push("好帅");
    stack.push("技巧一流");
    stack.push("haha");

    System.out.println("栈中元素: " + stack);

    System.out.println("获取顶端元素 peek :" + stack.peek());

    System.out.println("顶端元素出栈 pop :" + stack.pop());

    System.out.println("出栈后栈内元素:" + stack);

    System.out.println("search(好帅) 的位置:" + stack.search("好帅"));
}
}

结果：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

可以看到，我其实都没做什么哈哈，都是 LinkedList 内部提供的方法，操作的都是在链表头部的元素，而不是尾部。

其实 LinkedList 这个栈的特性也是继承自双端队列 Deque，官方也推荐在使用栈时优先使用 Deque，而不是 Stack,有兴趣的可以去了解下。

Thanks

https://docs.oracle.com/javase/8/docs/api/java/util/Stack.html

http://www.cnblogs.com/kaituorensheng/archive/2013/03/02/2939690.html

http://www.nowamagic.net/librarys/veda/detail/2298

终于把 List 常用的几种容器介绍完了，接下来开始 Map 的相关介绍。

什么是 Map

Java 中的 Map 接口是和 Collection 接口同一等级的集合根接口，它表示一个键值对 (key-value) 的映射。类似数学中函数的概念。

数学中的函数：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

一个 Map 中，任意一个 key 都有唯一确定的 value 与其对应，这个 key-value 的映射就是 map。

Map 中元素的顺序取决于迭代器迭代时的顺序，有的实现类保证了元素输入输出时的顺序，比如说 TreeMap；有的实现类则是无序的，比如 HashMap。

Map 的三个 collection 视图：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

Map 接口提供了三种角度来分析 Map:

KeySet
Values
Entry

1.KeySet

KeySet 是一个 Map 中键（key）的集合，以 Set 的形式保存，不允许重复，因此键存储的对象需要重写 equals() 和 hashCode() 方法。

在上图就是保存 AA, BB, CC, DD… 等键的集合。

可以通过 Map.keySet() 方法获得。

2.Values

Values 是一个 Map 中值 (value) 的集合，以 Collection 的形式保存，因此可以重复。

在上图就是保存 90,90,56,78… 等值的集合。

通过 Map.values() 方法获得。

3.Entry

Entry 是 Map 接口中的静态内部接口，表示一个键值对的映射，例如上图中 AA-90 这一组映射关系。

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

Entry 具有上图中的方法：

getKey() , 获取这组映射中的键 key
getValue() , 获取这组映射中的值 value
setValue() , 修改这组映射中的值
hashCode() , 返回这个 Entry 的哈希值
equals() , 对比 key-value 是否相等

通过 Map.entrySet() 方法获得的是一组 Entry 的集合，保存在 Set 中，所以 Map 中的 Entry 也不能重复。

public Set<Map.Entry<K,V>> entrySet();

Map 的三种遍历方式

根据 Map 提供的三种视图，可以有三种 map 遍历方式 :

1.使用 keySet 遍历：

    Set set = map.keySet();
    for (Object key : set) {
        System.out.println(map.get(key));
    }

2.使用 values 遍历：

    Collection values = map.values();
    Iterator iterator = values.iterator();
    while (iterator.hasNext()){
        System.out.println("value " + iterator.next());
    }

3.使用 Entry 遍历

    Set entrySet = map.entrySet();
    for (Object o : entrySet) {
        Map.Entry entry = (Map.Entry) o;
        System.out.println(entry);      //key=value
        System.out.println(entry.getKey() + " / " + entry.getValue());
    }

Map 的实现类

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

Map 的实现类主要有 4 种：

Hashtable
- 古老，线程安全
HashMap
- 速度很快，但没有顺序
TreeMap
- 有序的，效率比 HashMap 低
LinkedHashMap
- 结合 HashMap 和 TreeMap 的有点，有序的同时效率也不错，仅比 HashMap 慢一点

其中后三个的区别很类似 Set 的实现类：

HashSet
TreeSet
LinkedHashSet

Map 的每个实现类都应该实现 2 个构造方法：

无参构造方法，用于创建一个空的 map
参数是 Map 的构造方法，用于创建一个包含参数内容的新 map

第二种构造方法允许我们复制一个 map。

虽然没有强制要求，但自定义 Map 实现类时最好都这样来。

总结

Map 有以下特点：

没有重复的 key
每个 key 只能对应一个 value, 多个 key 可以对应一个 value
key,value 都可以是任何引用类型的数据，包括 null
Map 取代了古老的 Dictionary 抽象类

注意：
可以使用 Map 作为 Map 的值，但禁止使用 Map 作为 Map 的键。因为在这么复杂的 Map 中，equals() 方法和 hashCode() 比较难定义。

另一方面，你应该尽量避免使用“可变”的类作为 Map 的键。如果你将一个对象作为键值并保存在 Map 中，之后又改变了其状态，那么 Map 就会产生混乱，你所保存的值可能丢失。

Thanks

https://docs.oracle.com/javase/8/docs/api/java/util/Map.html
https://docs.oracle.com/javase/tutorial/collections/interfaces/map.html
https://docs.oracle.com/javase/tutorial/collections/implementations/map.html
http://www.cnblogs.com/skywang12345/p/3308931.html
http://www.nowamagic.net/librarys/veda/detail/1202

在学习 HashMap 前，我们先来温习下 Hash(哈希) 的概念。

什么是 Hash

Hash（哈希），又称“散列”。

散列（hash）英文原意是“混杂”、“拼凑”、“重新表述”的意思。

在某种程度上，散列是与排序相反的一种操作，排序是将集合中的元素按照某种方式比如字典顺序排列在一起，而散列通过计算哈希值，打破元素之间原有的关系，使集合中的元素按照散列函数的分类进行排列。

在介绍一些集合时，我们总强调需要重写某个类的 equlas() 方法和 hashCode() 方法，确保唯一性。这里的 hashCode() 表示的是对当前对象的唯一标示。计算 hashCode 的过程就称作哈希。

为什么要有 Hash

我们通常使用数组或者链表来存储元素，一旦存储的内容数量特别多，需要占用很大的空间，而且在查找某个元素是否存在的过程中，数组和链表都需要挨个循环比较，而通过哈希计算，可以大大减少比较次数。

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

举个栗子：

现在有 4 个数 {2,5,9,13}，需要查找 13 是否存在。

1.使用数组存储，需要新建个数组 new int[]{2,5,9,13}，然后需要写个循环遍历查找：

    int[] numbers = new int[]{2,5,9,13};
    for (int i = 0; i < numbers.length; i++) {
        if (numbers[i] == 13){
            System.out.println("find it!");
            return;
        }
    }

这样需要遍历 4 次才能找到，时间复杂度为 O(n)。

2.而假如存储时先使用哈希函数进行计算，这里我随便用个函数：

 H[key] = key % 3;

四个数 {2,5,9,13} 对应的哈希值为：

 H[2] = 2 % 3 = 2;
 H[5] = 5 % 3 = 2;
 H[9] = 9 % 3 = 0;
 H[13] = 13 % 3 = 1;

然后把它们存储到对应的位置。

当要查找 13 时，只要先使用哈希函数计算它的位置，然后去那个位置查看是否存在就好了，本例中只需查找一次，时间复杂度为 O(1)。

因此可以发现，哈希其实是随机存储的一种优化，先进行分类，然后查找时按照这个对象的分类去找。

哈希通过一次计算大幅度缩小查找范围，自然比从全部数据里查找速度要快。

比如你和我一样是个剁手族买书狂，家里书一大堆，如果书存放时不分类直接摆到书架上（数组存储），找某本书时可能需要脑袋从左往右从上往下转好几圈才能发现；如果存放时按照类别分开放，技术书、小说、文学等等分开（按照某种哈希函数计算），找书时只要从它对应的分类里找，自然省事多了。

哈希函数

哈希的过程中需要使用哈希函数进行计算。

哈希函数是一种映射关系，根据数据的关键词 key ，通过一定的函数关系，计算出该元素存储位置的函数。

表示为：

address = H [key]

几种常见的哈希函数（散列函数）构造方法

直接定址法
- 取关键字或关键字的某个线性函数值为散列地址。
- 即 H(key) = key 或 H(key) = a*key + b，其中a和b为常数。
- 比如
除留余数法
- 取关键字被某个不大于散列表长度 m 的数 p 求余，得到的作为散列地址。
- 即 H(key) = key % p, p < m。
- 比如
数字分析法
- 当关键字的位数大于地址的位数，对关键字的各位分布进行分析，选出分布均匀的任意几位作为散列地址。
- 仅适用于所有关键字都已知的情况下，根据实际应用确定要选取的部分，尽量避免发生冲突。
- 比如
平方取中法
- 先计算出关键字值的平方，然后取平方值中间几位作为散列地址。
- 随机分布的关键字，得到的散列地址也是随机分布的。
- 比如
折叠法（叠加法）
- 将关键字分为位数相同的几部分，然后取这几部分的叠加和（舍去进位）作为散列地址。
- 用于关键字位数较多，并且关键字中每一位上数字分布大致均匀。
- 比如
随机数法
- 选择一个随机函数，把关键字的随机函数值作为它的哈希值。
- 通常当关键字的长度不等时用这种方法。

构造哈希函数的方法很多，实际工作中要根据不同的情况选择合适的方法，总的原则是尽可能少的产生冲突。

通常考虑的因素有关键字的长度和分布情况、哈希值的范围等。

如：当关键字是整数类型时就可以用除留余数法；如果关键字是小数类型，选择随机数法会比较好。

哈希冲突的解决

选用哈希函数计算哈希值时，可能不同的 key 会得到相同的结果，一个地址怎么存放多个数据呢？这就是冲突。

常用的主要有两种方法解决冲突：

1.链接法（拉链法）

拉链法解决冲突的做法是：
将所有关键字为同义词的结点链接在同一个单链表中。

若选定的散列表长度为 m，则可将散列表定义为一个由 m 个头指针组成的指针数组 T[0..m-1] 。

凡是散列地址为 i 的结点，均插入到以 T[i] 为头指针的单链表中。
T 中各分量的初值均应为空指针。

在拉链法中，装填因子 α 可以大于 1，但一般均取 α ≤ 1。

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

2.开放定址法

用开放定址法解决冲突的做法是：

用开放定址法解决冲突的做法是：当冲突发生时，使用某种探测技术在散列表中形成一个探测序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址（即该地址单元为空）为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探测到开放的地址则表明表中无待查的关键字，即查找失败。

简单的说：当冲突发生时，使用某种探查(亦称探测)技术在散列表中寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到。

按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、二次探查法、双重散列法等。

a.线性探查法

hi=(h(key)+i) ％ m ，0 ≤ i ≤ m-1

基本思想是：
探查时从地址 d 开始，首先探查 T[d]，然后依次探查 T[d+1]，…，直到 T[m-1]，此后又循环到 T[0]，T[1]，…，直到探查到有空余地址或者到 T[d-1]为止。

b.二次探查法

hi=(h(key)+i*i) ％ m，0 ≤ i ≤ m-1

基本思想是：
探查时从地址 d 开始，首先探查 T[d]，然后依次探查 T[d+1^2]，T[d+2^2]，T[d+3^2],…，等，直到探查到有空余地址或者到 T[d-1]为止。

缺点是无法探查到整个散列空间。

c.双重散列法

hi=(h(key)+i*h1(key)) ％ m，0 ≤ i ≤ m-1

基本思想是：
探查时从地址 d 开始，首先探查 T[d]，然后依次探查 T[d+h1(d)], T[d + 2*h1(d)]，…，等。

该方法使用了两个散列函数 h(key) 和 h1(key)，故也称为双散列函数探查法。

定义 h1(key) 的方法较多，但无论采用什么方法定义，都必须使 h1(key) 的值和 m 互素，才能使发生冲突的同义词地址均匀地分布在整个表中，否则可能造成同义词地址的循环计算。

该方法是开放定址法中最好的方法之一。

哈希的应用

哈希表
分布式缓存

哈希表（散列表）

哈希表（hash table）是哈希函数最主要的应用。

哈希表是实现关联数组（associative array）的一种数据结构，广泛应用于实现数据的快速查找。

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

用哈希函数计算关键字的哈希值（hash value）,通过哈希值这个索引就可以找到关键字的存储位置，即桶（bucket）。哈希表不同于二叉树、栈、序列的数据结构一般情况下，在哈希表上的插入、查找、删除等操作的时间复杂度是 O(1)。

查找过程中，关键字的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。
影响产生冲突多少有以下三个因素：

哈希函数是否均匀；
处理冲突的方法；
哈希表的加载因子。

哈希表的加载因子和容量决定了在什么时候桶数（存储位置）不够，需要重新哈希。

加载因子太大的话桶太多，遍历时效率变低；太大的话频繁 rehash，导致性能降低。所以加载因子的大小需要结合时间和空间效率考虑。

在 HashMap 中的加载因子为 0.75，即四分之三。

分布式缓存

网络环境下的分布式缓存系统一般基于一致性哈希（Consistent hashing）。简单的说，一致性哈希将哈希值取值空间组织成一个虚拟的环，各个服务器与数据关键字K使用相同的哈希函数映射到这个环上，数据会存储在它顺时针“游走”遇到的第一个服务器。可以使每个服务器节点的负载相对均衡，很大程度上避免资源的浪费。

在动态分布式缓存系统中，哈希算法的设计是关键点。使用分布更合理的算法可以使得多个服务节点间的负载相对均衡，可以很大程度上避免资源的浪费以及部分服务器过载。使用带虚拟节点的一致性哈希算法，可以有效地降低服务硬件环境变化带来的数据迁移代价和风险，从而使分布式缓存系统更加高效稳定。

Thanks

http://www.nowamagic.net/librarys/veda/detail/1273

http://blog.csdn.net/cywosp/article/details/23397179/

http://www.cnblogs.com/qiaoshanzi/p/5295554.html

http://baike.baidu.com/view/549615.htm

https://books.google.co.jp/books?id=wCWmdhdX1AYC&pg=PA214&lpg=PA214&dq=%E6%95%B0%E5%AD%97%E5%88%86%E6%9E%90%E6%B3%95&source=bl&ots=5ieOT99Dob&sig=UcYbua2lwYocCQr32HF0XDF34h4&hl=zh-CN&sa=X&ved=0ahUKEwj104zw__fPAhUDw7wKHf3cAhIQ6AEISzAJ#v=onepage&q=%E6%95%B0%E5%AD%97%E5%88%86%E6%9E%90%E6%B3%95&f=false

http://sjjp.tjuci.edu.cn/sjjg/DataStructure/DS/web/chazhao/chazhao9.4.3.3.htm

http://www.cnblogs.com/qiaoshanzi/p/5295554.html

今天来了解下 AbstractMap。

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

什么是 AbstractMap

AbstractMap 是 Map 接口的的实现类之一，也是 HashMap, TreeMap, ConcurrentHashMap 等类的父类。

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

AbstractMap 提供了 Map 的基本实现，使得我们以后要实现一个 Map 不用从头开始，只需要继承 AbstractMap, 然后按需求实现/重写对应方法即可。

AbstarctMap 中唯一的抽象方法：

public abstract Set<Entry<K,V>> entrySet();

当我们要实现一个不可变的 Map 时，只需要继承这个类，然后实现 entrySet() 方法，这个方法返回一个保存所有 key-value 映射的 set。通常这个 Set 不支持 add(), remove() 方法，Set 对应的迭代器也不支持 remove() 方法。

如果想要实现一个可变的 Map,我们需要在上述操作外，重写 put() 方法，因为默认不支持 put 操作：

public V put(K key, V value) {
    throw new UnsupportedOperationException();
}

而且 entrySet() 返回的 Set 的迭代器，也得实现 remove() 方法，因为 AbstractMap 中的删除相关操作都需要调用该迭代器的 remove() 方法。

正如其他集合推荐的那样，比如 AbstractCollection 接口，实现类最好提供两种构造方法：

一种是不含参数的，返回一个空 map
一种是以一个 map 为参数，返回一个和参数内容一样的 map

AbstractMap 的成员变量

transient volatile Set<K>        keySet;
transient volatile Collection<V> values;

有两个成员变量：

keySet, 保存 map 中所有键的 Set
values, 保存 map 中所有值的集合

他们都是 transient, volatile, 分别表示不可序列化、并发环境下变量的修改能够保证线程可见性。

需要注意的是 volatile 只能保证可见性，不能保证原子性，需要保证操作是原子性操作，才能保证使用 volatile 关键字的程序在并发时能够正确执行。

AbstractMap 的成员方法

AbstractMap 中实现了许多方法，实现类会根据自己不同的要求选择性的覆盖一些。

接下来根据看看 AbstractMap 中的方法。

1.添加

public V put(K key, V value) {
    throw new UnsupportedOperationException();
}

public void putAll(Map<? extends K, ? extends V> m) {
    for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
        put(e.getKey(), e.getValue());
}

可以看到默认是不支持添加操作的，实现类需要重写 put() 方法。

2.删除

public V remove(Object key) {
    //获取保存 Map.Entry 集合的迭代器
    Iterator<Entry<K,V>> i = entrySet().iterator();
    Entry<K,V> correctEntry = null;
    //遍历查找，当某个 Entry 的 key 和 指定 key 一致时结束
    if (key==null) {
        while (correctEntry==null && i.hasNext()) {
            Entry<K,V> e = i.next();
            if (e.getKey()==null)
                correctEntry = e;
        }
    } else {
        while (correctEntry==null && i.hasNext()) {
            Entry<K,V> e = i.next();
            if (key.equals(e.getKey()))
                correctEntry = e;
        }
    }

    //找到了，返回要删除的值
    V oldValue = null;
    if (correctEntry !=null) {
        oldValue = correctEntry.getValue();
        //调用迭代器的 remove 方法
        i.remove();
    }
    return oldValue;
}

//调用 Set.clear() 方法清除
public void clear() {
    entrySet().clear();
}

3.获取

//时间复杂度为 O(n)
//许多实现类都重写了这个方法
public V get(Object key) {
    //使用 Set 迭代器进行遍历，根据 key 查找
    Iterator<Entry<K,V>> i = entrySet().iterator();
    if (key==null) {
        while (i.hasNext()) {
            Entry<K,V> e = i.next();
            if (e.getKey()==null)
                return e.getValue();
        }
    } else {
        while (i.hasNext()) {
            Entry<K,V> e = i.next();
            if (key.equals(e.getKey()))
                return e.getValue();
        }
    }
    return null;
}

4.查询状态

//是否存在指定的 key
//时间复杂度为 O(n)
//许多实现类都重写了这个方法
public boolean containsKey(Object key) {
    //还是迭代器遍历，查找 key，跟 get() 很像啊
    Iterator<Map.Entry<K,V>> i = entrySet().iterator();
    if (key==null) {
        while (i.hasNext()) {
            Entry<K,V> e = i.next();
            //getKey()
            if (e.getKey()==null)
                return true;
        }
    } else {
        while (i.hasNext()) {
            Entry<K,V> e = i.next();
            if (key.equals(e.getKey()))
                return true;
        }
    }
    return false;
}


//查询是否存在指定的值
public boolean containsValue(Object value) {
    Iterator<Entry<K,V>> i = entrySet().iterator();
    if (value==null) {
        while (i.hasNext()) {
            Entry<K,V> e = i.next();
            //getValue()
            if (e.getValue()==null)
                return true;
        }
    } else {
        while (i.hasNext()) {
            Entry<K,V> e = i.next();
            if (value.equals(e.getValue()))
                return true;
        }
    }
    return false;
}


public int size() {
    //使用 Set.size() 获取元素个数
    return entrySet().size();
}

public boolean isEmpty() {
    return size() == 0;
}

5.用于比较的 equals(), hashCode()

//内部用来测试 SimpleEntry, SimpleImmutableEntry 是否相等的方法
private static boolean eq(Object o1, Object o2) {
    return o1 == null ? o2 == null : o1.equals(o2);
}

//判断指定的对象是否和当前 Map 一致
//为什么参数不是泛型而是 对象呢
//据说是创建这个方法时还没有泛型 - -
public boolean equals(Object o) {
    //引用指向同一个对象
    if (o == this)
        return true;

    //必须是 Map 的实现类
    if (!(o instanceof Map))
        return false;
    //强转为 Map
    Map<?,?> m = (Map<?,?>) o;
    //元素个数必须一致
    if (m.size() != size())
        return false;

    try {
        //还是需要一个个遍历，对比
        Iterator<Entry<K,V>> i = entrySet().iterator();
        while (i.hasNext()) {
            //对比每个 Entry 的 key 和 value
            Entry<K,V> e = i.next();
            K key = e.getKey();
            V value = e.getValue();
            if (value == null) {
                //对比 key, value
                if (!(m.get(key)==null && m.containsKey(key)))
                    return false;
            } else {
                if (!value.equals(m.get(key)))
                    return false;
            }
        }
    } catch (ClassCastException unused) {
        return false;
    } catch (NullPointerException unused) {
        return false;
    }

    return true;
}

//整个 map 的 hashCode() 
public int hashCode() {
    int h = 0;
    //是所有 Entry 哈希值的和
    Iterator<Entry<K,V>> i = entrySet().iterator();
    while (i.hasNext())
        h += i.next().hashCode();
    return h;
}

6.获取三个主要的视图

获取所有的键:

public Set<K> keySet() {
    //如果成员变量 keySet 为 null,创建个空的 AbstractSet
    if (keySet == null) {
        keySet = new AbstractSet<K>() {
            public Iterator<K> iterator() {
                return new Iterator<K>() {
                    private Iterator<Entry<K,V>> i = entrySet().iterator();

                    public boolean hasNext() {
                        return i.hasNext();
                    }

                    public K next() {
                        return i.next().getKey();
                    }

                    public void remove() {
                        i.remove();
                    }
                };
            }

            public int size() {
                return AbstractMap.this.size();
            }

            public boolean isEmpty() {
                return AbstractMap.this.isEmpty();
            }

            public void clear() {
                AbstractMap.this.clear();
            }

            public boolean contains(Object k) {
                return AbstractMap.this.containsKey(k);
            }
        };
    }
    return keySet;
}

获取所有的值:

public Collection<V> values() {
    if (values == null) {
        //没有就创建个空的 AbstractCollection 返回
        values = new AbstractCollection<V>() {
            public Iterator<V> iterator() {
                return new Iterator<V>() {
                    private Iterator<Entry<K,V>> i = entrySet().iterator();

                    public boolean hasNext() {
                        return i.hasNext();
                    }

                    public V next() {
                        return i.next().getValue();
                    }

                    public void remove() {
                        i.remove();
                    }
                };
            }

            public int size() {
                return AbstractMap.this.size();
            }

            public boolean isEmpty() {
                return AbstractMap.this.isEmpty();
            }

            public void clear() {
                AbstractMap.this.clear();
            }

            public boolean contains(Object v) {
                return AbstractMap.this.containsValue(v);
            }
        };
    }
    return values;
}

获取所有键值对，需要子类实现：

public abstract Set<Entry<K,V>> entrySet();

AbstractMap 中的内部类

正如 Map 接口中有内部类 Map.Entry 一样， AbstractMap 也有两个内部类：

SimpleImmutableEntry, 表示一个不可变的键值对
SimpleEntry, 表示可变的键值对

SimpleImmutableEntry，不可变的键值对,实现了 Map.Entry < K,V> 接口：

public static class SimpleImmutableEntry<K,V>
    implements Entry<K,V>, java.io.Serializable
{
    private static final long serialVersionUID = 7138329143949025153L;
    //key-value
    private final K key;
    private final V value;

    //构造函数，传入 key 和 value
    public SimpleImmutableEntry(K key, V value) {
        this.key   = key;
        this.value = value;
    }

    //构造函数2，传入一个 Entry，赋值给本地的 key 和 value
    public SimpleImmutableEntry(Entry<? extends K, ? extends V> entry) {
        this.key   = entry.getKey();
        this.value = entry.getValue();
    }

    //返回 键
    public K getKey() {
        return key;
    }

    //返回 值
    public V getValue() {
        return value;
    }

    //修改值，不可修改的 Entry 默认不支持这个操作
    public V setValue(V value) {
        throw new UnsupportedOperationException();
    }

    //比较指定 Entry 和本地是否相等
    //要求顺序，key-value 必须全相等
    //只要是 Map 的实现类即可，不同实现也可以相等
    public boolean equals(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<?,?> e = (Map.Entry<?,?>)o;
        return eq(key, e.getKey()) && eq(value, e.getValue());
    }

    //哈希值
    //是键的哈希与值的哈希的 异或
    public int hashCode() {
        return (key   == null ? 0 :   key.hashCode()) ^
               (value == null ? 0 : value.hashCode());
    }

    //返回一个 String
    public String toString() {
        return key + "=" + value;
    }

}

SimpleEntry, 可变的键值对:

public static class SimpleEntry<K,V>
    implements Entry<K,V>, java.io.Serializable
{
    private static final long serialVersionUID = -8499721149061103585L;

    private final K key;
    private V value;

    public SimpleEntry(K key, V value) {
        this.key   = key;
        this.value = value;
    }

    public SimpleEntry(Entry<? extends K, ? extends V> entry) {
        this.key   = entry.getKey();
        this.value = entry.getValue();
    }

    public K getKey() {
        return key;
    }

    public V getValue() {
        return value;
    }

    //支持 修改值
    public V setValue(V value) {
        V oldValue = this.value;
        this.value = value;
        return oldValue;
    }

    public boolean equals(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<?,?> e = (Map.Entry<?,?>)o;
        return eq(key, e.getKey()) && eq(value, e.getValue());
    }

    public int hashCode() {
        return (key   == null ? 0 :   key.hashCode()) ^
               (value == null ? 0 : value.hashCode());
    }

    public String toString() {
        return key + "=" + value;
    }

}

SimpleEntry 与 SimpleImmutableEntry 唯一的区别就是支持 setValue() 操作。

总结

和 AbstractCollection 接口，AbstractList 接口作用相似， AbstractMap 是一个基础实现类，实现了 Map 的主要方法，默认不支持修改。

常用的几种 Map, 比如 HashMap, TreeMap, LinkedHashMap 都继承自它。

Thanks

https://docs.oracle.com/javase/8/docs/api/java/util/AbstractMap.html

还有肉肉做的紫菜包饭，让我今天能量十足！

前面我们介绍了哈希相关概念：哈希哈希函数冲突解决哈希表，这篇文章我们来根据 JDK 1.8 源码，深入了解下使用频率很高的 HashMap 。

读完本文你将了解到：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

什么是 HashMap

HashMap 是一个采用哈希表实现的键值对集合，继承自 AbstractMap，实现了 Map 接口。
HashMap 的特殊存储结构使得在获取指定元素前需要经过哈希运算，得到目标元素在哈希表中的位置，然后再进行少量比较即可得到元素，这使得 HashMap 的查找效率贼高。

当发生哈希冲突（碰撞）的时候，HashMap 采用拉链法进行解决（不熟悉 “哈希冲突” 和 “拉链法” 这 2 个概念的同学可以点这里了解），因此 HashMap 的底层实现是数组+链表，如下图所示：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

HashMap 的特点

结合平时使用，可以了解到 HashMap 大概具有以下特点：

底层实现是链表数组，JDK 8 后又加了红黑树
实现了 Map 全部的方法
key 用 Set 存放，所以想做到 key 不允许重复，key 对应的类需要重写 hashCode 和 equals 方法
允许空键和空值（但空键只有一个，且放在第一位，下面会介绍）
元素是无序的，而且顺序会不定时改变
插入、获取的时间复杂度基本是 O(1)（前提是有适当的哈希函数，让元素分布在均匀的位置）
遍历整个 Map 需要的时间与桶(数组) 的长度成正比（因此初始化时 HashMap 的容量不宜太大）
两个关键因子：初始容量、加载因子

除了不允许 null 并且同步，Hashtable 几乎和他一样。

下面结合源码进行验证这些特点。

HashMap 的 13 个成员变量

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

1.默认初始容量：16，必须是 2 的整数次方

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

2.默认加载因子的大小：0.75，可不是随便的，结合时间和空间效率考虑得到的

static final float DEFAULT_LOAD_FACTOR = 0.75f;

3.最大容量： 2^ 30 次方

static final int MAXIMUM_CAPACITY = 1 << 30;

4.当前 HashMap 修改的次数，这个变量用来保证 fail-fast 机制

transient int modCount;

5.阈值，下次需要扩容时的值，等于容量*加载因子

int threshold;

6.树形阈值：JDK 1.8 新增的，当使用树而不是列表来作为桶时使用。必须必 2 大

static final int TREEIFY_THRESHOLD = 8;

7.非树形阈值：也是 1.8 新增的，扩容时分裂一个树形桶的阈值（？不是很懂 - -），要比 TREEIFY_THRESHOLD 小

static final int UNTREEIFY_THRESHOLD = 6;

8.树形最小容量：桶可能是树的哈希表的最小容量。至少是 TREEIFY_THRESHOLD 的 4 倍，这样能避免扩容时的冲突

static final int MIN_TREEIFY_CAPACITY = 64;

9.缓存的键值对集合（另外两个视图：keySet 和 values 是在 AbstractMap 中声明的）

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

10.哈希表中的链表数组

transient Node<K,V>[] table;

11.键值对的数量

transient int size;

12.哈希表的加载因子

final float loadFactor;

HashMap 的初始容量和加载因子

由于 HashMap 扩容开销很大（需要创建新数组、重新哈希、分配等等），因此与扩容相关的两个因素：

容量：数组的数量
加载因子：决定了 HashMap 中的元素占有多少比例时扩容

成为了 HashMap 最重要的部分之一，它们决定了 HashMap 什么时候扩容。

HashMap 的默认加载因子为 0.75，这是在时间、空间两方面均衡考虑下的结果：

加载因子太大的话发生冲突的可能就会大，查找的效率反而变低
太小的话频繁 rehash，导致性能降低

当设置初始容量时，需要提前考虑 Map 中可能有多少对键值对，设计合理的加载因子，尽可能避免进行扩容。

如果存储的键值对很多，干脆设置个大点的容量，这样可以少扩容几次。

HashMap 的关键方法

1. HashMap 的 4 个构造方法

//创建一个空的哈希表，初始容量为 16，加载因子为 0.75
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

//创建一个空的哈希表，指定容量，使用默认的加载因子
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

//创建一个空的哈希表，指定容量和加载因子
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    //根据指定容量设置阈值
    this.threshold = tableSizeFor(initialCapacity);
}

//创建一个内容为参数 m 的内容的哈希表
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

其中第三种构造方法调用了 tableSizeFor(int) 来根据指定的容量设置阈值，这个方法经过若干次无符号右移、求异运算，得出最接近指定参数 cap 的 2 的 N 次方容量。假如你传入的是 5，返回的初始容量为 8 。

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;
}

第四种构造方法调用了 putMapEntries()，这个方法用于向哈希表中添加整个集合：

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        //数组还是空，初始化参数
        if (table == null) { 
            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();
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            //先经过 hash() 计算位置，然后复制指定 map 的内容
            putVal(hash(key), key, value, false, evict);
        }
    }
}

2.HashMap 中的链表节点

前面提到，HashMap 的底层数据结构之一（JDK 1.8 前单纯是）就是链表数组：

transient Node<K,V>[] table;

每一个链表节点如下：

//实现了 Map.Entry 接口
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;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            //Map.Entry 相等的条件：键相等、值相等、个数相等、顺序相等
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

3.HashMap 中的添加操作 **

下文用“桶”来指代要数组，每个桶都对应着一条链表：

//添加指定的键值对到 Map 中，如果已经存在，就替换
public V put(K key, V value) {
    //先调用 hash() 方法计算位置
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //如果当前 哈希表内容为空，新建，n 指向最后一个桶的位置，tab 为哈希表另一个引用
    //resize() 后续介绍
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //如果要插入的位置没有元素，新建个节点并放进去
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        //如果要插入的桶已经有元素，替换
        // e 指向被替换的元素
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
        //p 指向要插入的桶第一个 元素的位置，如果 p 的哈希值、键、值和要添加的一样，就停止找，e 指向 p
            e = p;
        else if (p instanceof TreeNode)
        //如果不一样，而且当前采用的还是 JDK 8 以后的树形节点，调用 putTreeVal 插入
            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);
                    //当这个桶内链表个数大于等于 8，就要树形化
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //如果找到要替换的节点，就停止，此时 e 已经指向要被替换的节点
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //存在要替换的节点
        if (e != null) {
            V oldValue = e.value;
            //替换，返回
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //如果超出阈值，就得扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

根据代码可以总结插入逻辑如下:

先调用 hash() 方法计算哈希值
然后调用 putVal() 方法中根据哈希值进行相关操作
如果当前哈希表内容为空，新建一个哈希表
如果要插入的桶中没有元素，新建个节点并放进去
否则从桶中第一个元素开始查找哈希值对应位置
1. 如果桶中第一个元素的哈希值和要添加的一样，替换，结束查找
2. 如果第一个元素不一样，而且当前采用的还是 JDK 8 以后的树形节点，调用 putTreeVal() 进行插入
3. 否则还是从传统的链表数组中查找、替换，结束查找
4. 当这个桶内链表个数大于等于 8，就要调用 treeifyBin() 方法进行树形化
最后检查是否需要扩容

插入过程中涉及到几个其他关键的方法：

hash():计算对应的位置
resize():扩容
putTreeVal():树形节点的插入
treeifyBin():树形化容器

HashMap 在 JDK1.8 新增树形化相关的内容比较多，下一篇介绍，接下来先介绍传统的 HashMap 相关内容。

4.HashMap 中的哈希函数 hash() **

HashMap 中通过将传入键的 hashCode 进行无符号右移 16 位，然后进行按位异或，得到这个键的哈希值。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

看看源码里的注释怎么说的：

Computes key.hashCode() and spreads (XORs) higher bits of hash to lower. Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide. (Among known examples are sets of Float keys holding consecutive whole numbers in small tables.) So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed, utility, and quality of bit-spreading. Because many common sets of hashes are already reasonably distributed (so don’t benefit from spreading), and because we use trees to handle large sets of collisions in bins, we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds.

大概意思就是：

由于哈希表的容量都是 2 的 N 次方，在当前，元素的 hashCode() 在很多时候下低位是相同的，这将导致冲突（碰撞），因此 1.8 以后做了个移位操作：将元素的 hashCode() 和自己右移 16 位后的结果求异或。

由于 int 只有 32 位，无符号右移 16 位相当于把高位的一半移到低位：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

举个栗子：

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~
（图片来自 http://yikun.github.io/2015/04/01/Java-HashMap%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/）

这样可以避免只靠低位数据来计算哈希时导致的冲突，计算结果由高低位结合决定，可以避免哈希值分布不均匀。

而且，采用位运算效率更高。

5.HashMap 中的初始化/扩容方法 resize() **

每次添加时会比较当前元素个数和阈值：

    //如果超出阈值，就得扩容
    if (++size > threshold)
        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) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //新的容量为旧的两倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            //如果旧容量小于等于 16，新的阈值就是旧阈值的两倍
            newThr = oldThr << 1; // double threshold
    }
    //如果旧容量为 0 ，并且旧阈值>0，说明之前创建了哈希表但没有添加元素，初始化容量等于阈值
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        //旧容量、旧阈值都是0，说明还没创建哈希表，容量为默认容量，阈值为 容量*加载因子
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //如果新的阈值为 0 ，就得用 新容量*加载因子 重计算一次
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    //更新阈值
    threshold = newThr;
    //创建新链表数组，容量是原来的两倍
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    //接下来就得遍历复制了
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                //旧的桶置为空
                oldTab[j] = null;
                //当前 桶只有一个元素，直接赋值给对应位置
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    //如果旧哈希表中这个位置的桶是树形结构，就要把新哈希表里当前桶也变成树形结构
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { //保留旧哈希表桶中链表的顺序
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    //do-while 循环赋值给新哈希表
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

扩容过程中几个关键的点：

新初始化哈希表时，容量为默认容量，阈值为容量*加载因子
已有哈希表扩容时，容量、阈值均翻倍
如果之前这个桶的节点类型是树，需要把新哈希表里当前桶也变成树形结构
复制给新哈希表中需要重新索引（rehash），这里采用的计算方法是
- e.hash & (newCap - 1)，等价于 e.hash % newCap

结合扩容源码可以发现扩容的确开销很大，需要迭代所有的元素，rehash、赋值，还得保留原来的数据结构。

所以在使用的时候，最好在初始化的时候就指定好 HashMap 的长度，尽量避免频繁 resize()。

6.HashMap 的获取方法 get() **

HashMap 另外一个经常使用的方法就是 get(key)，返回键对应的值:

如果 HashMap 中包含一个键值对 k-v 满足：

(key == null ? k == null : key.equals(k))

就返回值 v，否则返回 null;

public V get(Object key) {
    Node<K,V> e;
    //还是先计算 哈希值
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //tab 指向哈希表，n 为哈希表的长度，first 为 (n - 1) & hash 位置处的桶中的头一个节点
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        //如果桶里第一个元素就相等，直接返回
        if (first.hash == hash &&
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        //否则就得慢慢遍历找
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                //如果是树形节点，就调用树形节点的 get 方法
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                //do-while 遍历链表的所有节点
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

查找方法比较简单:

先计算哈希值;
然后再用 (n - 1) & hash 计算出桶的位置;
在桶里的链表进行遍历查找。

时间复杂度一般跟链表长度有关，因此哈希算法越好，元素分布越均匀，get() 方法就越快，不然遍历一条长链表，太慢了。

不过在 JDK 1.8 以后 HashMap 新增了红黑树节点，优化这种极端情况下的性能问题。

总结

1.HashMap 有那么多优点（见文首），也有个缺点：不是同步的。

当多线程并发访问一个哈希表时，需要在外部进行同步操作，否则会引发数据不同步问题。

你可以选择加锁，也可以考虑用 Collections.synchronizedMap 包一层，变成个线程安全的 Map：

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

最好在初始化时就这么做。

2.HashMap 三个视图返回的迭代器都是 fail-fast 的：如果在迭代时使用非迭代器方法修改了 map 的内容、结构，迭代器就会报 ConcurrentModificationException 的错。

3.当 HashMap 中有大量的元素都存放到同一个桶中时，这时候哈希表里只有一个桶，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。

针对这种情况，JDK 1.8 中引用了红黑树（时间复杂度为 O(logn)）优化这个问题。

4.为什么哈希表的容量一定要是 2的整数次幂?

首先，capacity 为 2的整数次幂的话，计算桶的位置 h&(length-1) 就相当于对 length 取模，提升了计算效率；

其次，capacity 为 2 的整数次幂的话，为偶数，这样 capacity-1 为奇数，奇数的最后一位是 1，这样便保证了 h&(capacity-1) 的最后一位可能为 0，也可能为 1（这取决于h的值），即与后的结果可能为偶数，也可能为奇数，这样便可以保证散列的均匀性；

而如果 capacity 为奇数的话，很明显 capacity-1 为偶数，它的最后一位是 0，这样 h&(capacity-1) 的最后一位肯定为 0，即只能为偶数，这样任何 hash 值都只会被散列到数组的偶数下标位置上，这便浪费了近一半的空间。

摘自： https://github.com/GeniusVJR/LearningNotes/blob/master/Part2/JavaSE/HashMap%E6%BA%90%E7%A0%81%E5%89%96%E6%9E%90.md

因此，哈希表容量取 2 的整数次幂，有以下 2 点好处：

使用减法替代取模，提升计算效率；
为了使不同 hash 值发生碰撞的概率更小，尽可能促使元素在哈希表中均匀地散列。

5.HashMap 允许 key, value 为 null，同时他们都保存在第一个桶中。

看代码，添加时先调用 hash()：

public V put(K key, V value) {
    //先调用 hash() 方法计算位置
    return putVal(hash(key), key, value, false, true);
}

而在计算哈希值时，如果为 null 就直接返回 0 ，说明了这一点：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

6.HashMap 中 equals() 和 hashCode() 有什么作用？

HashMap 的添加、获取时需要通过 key 的 hashCode() 进行 hash()，然后计算下标 ( n-1 & hash)，从而获得要找的同的位置。

当发生冲突（碰撞）时，利用 key.equals() 方法去链表或树中去查找对应的节点。

7.你知道 hash 的实现吗？为什么要这样实现？

在 JDK 1.8 的实现中，是通过 hashCode() 的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)。

主要是从速度、功效、质量来考虑的，这么做可以在桶的 n 比较小的时候，保证高低 bit 都参与到 hash 的计算中，同时位运算不会有太大的开销。

摘自：http://yikun.github.io/2015/04/01/Java-HashMap%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/

下篇文章介绍 HashMap 在 JDK 1.8 新增的红黑树结构，点击查看

Thanks

https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html

http://blog.csdn.net/eson_15/article/details/51158865

http://blog.csdn.net/q291611265/article/details/46763053

http://yikun.github.io/2015/04/01/Java-HashMap%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/

https://github.com/GeniusVJR/LearningNotes/blob/master/Part2/JavaSE/HashMap%E6%BA%90%E7%A0%81%E5%89%96%E6%9E%90.md

http://www.nowamagic.net/librarys/veda/detail/1273

上篇文章我们介绍了 HashMap 的主要特点和关键方法源码解读，这篇文章我们介绍 HashMap 在 JDK1.8 新增树形化相关的内容。

读完本文你将了解到：

传统 HashMap 的缺点

JDK 1.8 以前 HashMap 的实现是数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。

当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。

针对这种情况，JDK 1.8 中引入了红黑树（查找时间复杂度为 O(logn)）来优化这个问题。

HashMap 在 JDK 1.8 中新增的数据结构 – 红黑树

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

JDK 1.8 中 HashMap 中除了链表节点：

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

还有另外一种节点：TreeNode，它是 1.8 新增的，属于数据结构中的红黑树（不了解红黑树的同学可以点击这里了解红黑树）：

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

可以看到就是个红黑树节点，有父亲、左右孩子、前一个元素的节点，还有个颜色值。

另外由于它继承自 LinkedHashMap.Entry ，而 LinkedHashMap.Entry 继承自 HashMap.Node ，因此还有额外的 6 个属性：

//继承 LinkedHashMap.Entry 的
Entry<K,V> before, after;

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

HashMap 中关于红黑树的三个关键参数

HashMap 中有三个关于红黑树的关键参数:

TREEIFY_THRESHOLD
UNTREEIFY_THRESHOLD
MIN_TREEIFY_CAPACITY

值及作用如下：

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

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

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

HashMap 在 JDK 1.8 中新增的操作：桶的树形化 treeifyBin()

在Java 8 中，如果一个桶中的元素个数超过 TREEIFY_THRESHOLD(默认是 8 )，就使用红黑树来替换链表，从而提高速度。

这个替换的方法叫 treeifyBin() 即树形化。

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


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

上述操作做了这些事:

根据哈希表中元素个数确定是扩容还是树形化
如果是树形化
- 遍历桶中的元素，创建相同个数的树形节点，复制内容，建立起联系
- 然后让桶第一个元素指向新建的树头结点，替换桶的链表内容为树形内容

但是我们发现，之前的操作并没有设置红黑树的颜色值，现在得到的只能算是个二叉树。在最后调用树形节点 hd.treeify(tab) 方法进行塑造红黑树，来看看代码：

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

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

可以看到，将二叉树变为红黑树时，需要保证有序。这里有个双重循环，拿树中的所有节点和当前节点的哈希值进行对比(如果哈希值相等，就对比键，这里不用完全有序），然后根据比较结果确定在树种的位置。

HashMap 在 JDK 1.8 中新增的操作：红黑树中添加元素 putTreeVal()

上面介绍了如何把一个桶中的链表结构变成红黑树结构。

在添加时，如果一个桶中已经是红黑树结构，就要调用红黑树的添加元素方法 putTreeVal()。

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

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

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

通过上面的代码可以知道，HashMap 中往红黑树中添加一个新节点 n 时，有以下操作：

从根节点开始遍历当前红黑树中的元素 p，对比 n 和 p 的哈希值；
如果哈希值相等并且键也相等，就判断为已经有这个元素（这里不清楚为什么不对比值）；
如果哈希值就通过其他信息，比如引用地址来给个大概比较结果，这里可以看到红黑树的比较并不是很准确，注释里也说了，只是保证个相对平衡即可；
最后得到哈希值比较结果后，如果当前节点 p 还没有左孩子或者右孩子时才能插入，否则就进入下一轮循环;
插入元素后还需要进行红黑树例行的平衡调整，还有确保根节点的领先地位。

HashMap 在 JDK 1.8 中新增的操作：红黑树中查找元素 getTreeNode()

HashMap 的查找方法是 get():

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

它通过计算指定 key 的哈希值后，调用内部方法 getNode()；

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) {
        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() 方法就是根据哈希表元素个数与哈希值求模（使用的公式是 (n - 1) &hash）得到 key 所在的桶的头结点，如果头节点恰好是红黑树节点，就调用红黑树节点的 getTreeNode() 方法，否则就遍历链表节点。

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

getTreeNode 方法使通过调用树形节点的 find() 方法进行查找：

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

由于之前添加时已经保证这个树是有序的，因此查找时基本就是折半查找，效率很高。

这里和插入时一样，如果对比节点的哈希值和要查找的哈希值相等，就会判断 key 是否相等，相等就直接返回（也没有判断值哎）；不相等就从子树中递归查找。

HashMap 在 JDK 1.8 中新增的操作：树形结构修剪 split()

HashMap 中， resize() 方法的作用就是初始化或者扩容哈希表。当扩容时，如果当前桶中元素结构是红黑树，并且元素个数小于链表还原阈值 UNTREEIFY_THRESHOLD （默认为 6），就会把桶中的树形结构缩小或者直接还原（切分）为链表结构，调用的就是 split():

    //参数介绍
    //tab 表示保存桶头结点的哈希表
    //index 表示从哪个位置开始修剪
    //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;
            //如果当前节点哈希值的最后一位等于要修剪的 bit 值
            if ((e.hash & bit) == 0) {
                    //就把当前节点放到 lXXX 树中
                if ((e.prev = loTail) == null)
                    loHead = e;
                else
                    loTail.next = e;
                //然后 loTail 记录 e
                loTail = e;
                //记录 lXXX 树的节点数量
                ++lc;
            }
            else {  //如果当前节点哈希值最后一位不是要修剪的
                    //就把当前节点放到 hXXX 树中
                if ((e.prev = hiTail) == null)
                    hiHead = e;
                else
                    hiTail.next = e;
                hiTail = e;
                //记录 hXXX 树的节点数量
                ++hc;
            }
        }


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

从上述代码可以看到，HashMap 扩容时对红黑树节点的修剪主要分两部分，先分类、再根据元素个数决定是还原成链表还是精简一下元素仍保留红黑树结构。

1.分类

指定位置、指定范围，让指定位置中的元素 （hash & bit) == 0 的，放到 lXXX 树中，不相等的放到 hXXX 树中。

2.根据元素个数决定处理情况

符合要求的元素（即 lXXX 树），在元素个数小于 6 时还原成链表，最后让哈希表中修剪的痛 tab[index] 指向 lXXX 树；在元素个数大于 6 时，还是用红黑树，只不过是修剪了下枝叶；

不符合要求的元素（即 hXXX 树）也是一样的操作，只不过最后它是放在了修剪范围外 tab[index + bit]。

总结

JDK 1.8 以后哈希表的添加、删除、查找、扩容方法都增加了一种节点为 TreeNode 的情况：

添加时，当桶中链表个数超过 8 时会转换成红黑树；
删除、扩容时，如果桶中结构为红黑树，并且树中元素个数太少的话，会进行修剪或者直接还原成链表结构；
查找时即使哈希函数不优，大量元素集中在一个桶中，由于有红黑树结构，性能也不会差。

(图片来自：http://tech.meituan.com/java-hashmap.html)

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

这篇文章根据源码分析了 HashMap 在 JDK 1.8 里新增的 TreeNode 的一些关键方法，可以看到，1.8 以后的 HashMap 结合了哈希表和红黑树的优点，不仅快速，而且在极端情况也能保证性能，设计者苦心孤诣可见一斑，写到这里不禁仰天长叹：什么时候我才能写出这么 NB 的代码啊！！！

Thanks

http://openjdk.java.net/jeps/180

http://yikun.github.io/2015/04/01/Java-HashMap%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/

http://www.importnew.com/14417.html

http://tech.meituan.com/java-hashmap.html

点击查看 Java 集合框架深入理解 系列， - ( ゜- ゜)つロ 乾杯~

Java 提供的 集合类都在 Java.utils 包下，其中包含了很多 List, Set, Map, Queue… 它们的关系如下面这张类图所示：

可以看到，Java 集合主要分为两类：Collection 和 Map. 而 Collection 又继承了 Iterable< E > 接口，Iterable 接口内只有一个 iterator 方法，返回一个 Iterator 迭代器:

本篇文章将介绍 Iterator 迭代器。 在介绍 Iterator 之前不得不提一下被它替代的 Enumeration< E >:

Enumeration< E >

Enumeration 是一个很古老的迭代器，有两个方法：

Enumeration 的实现类会生成一系列子元素，比如 StringTokenizer；通过 Enumeration 的上述两个方法可以用来遍历它实现类的元素，比如这样：

Enumeration 接口早在 JDK 1.0 时就推出了，当时比较早的容器比如 Hashtable, Vector 都使用它作为遍历工具。

那 Enumeration 为什么会被废弃呢？

根据官方文档:

可以大胆猜一下，应该是当初设计没有考虑全，只有两个方法，而且名字还太长了 - -。 后来在 JDK 1.2 推出了 Iterator 替代它的功能。虽然 Enumeration 在 JDK 1.5 后增加了泛型的应用，依旧大势已去。

Iterator

Iterator 是一个集合上的迭代器，用来替代 Enumeration 进行遍历、迭代。

它 和 Enumeration 有什么不同呢？

根据官方文档:

哈哈首先是名字缩短了，看来大家都懒得输入那么长的方法名。 其次是 允许调用者在遍历过程中语法正确地删除元素。

注意这个 [语法正确]，事实上我们在使用 Iterator 对容器进行迭代时如果修改容器 可能会报 ConcurrentModificationException 的错。官方称这种情况下的迭代器是 fail-fast 迭代器。

fail-fast 与 ConcurrentModificationException

以 ArrayList 为例，在调用迭代器的 next，remove 方法时：

可以看到在调用迭代器的 next，remove 方法时都会比较 expectedModCount 和 modCount 是否相等，如果不相等就会抛出 ConcurrentModificationException ，也就是成为了 fail-fast。

而 modCount 在 add, clear, remove 时都会被修改：

因此我们知道了 fail-fast 即 ConcurrentModificationException 出现的原因，怎么解决呢？

方法一:

用 CopyOnWriteArrayList，ConcurrentHashMap 替换 ArrayList， HashMap，它们的功能和名字一样，在写入时会创建一个 copy，然后在这个 copy 版本上进行修改操作，这样就不会影响原来的迭代。不过坏处就是浪费内存。

方法二：

使用 Collections.synchronizedList 加 同步锁，不过这样有点粗暴。

可能得方法三（待考究，目前我还没搞清楚）：

在学习 ListView 中的观察者模式 时，我注意到 DataSetObservable 的 notifyChanged 方法中有如下注释：

为了避免影响 ArrayList 迭代，倒序处理。 待考究，目前我还没搞清楚。

不过意外的发现了，原来 for-each 的循环内部也是使用了 Iterator 来遍历Collection，它也调用了 Iterator.next()，所以在修改元素时会检查(元素的)变化并抛出 ConcurrentModificationException。

在从任何 Collection中删除对象时总要使用 Iterator 的remove 方法， for-each 循环只是标准 Iterator 代码标准用法之上的一种语法糖（syntactic sugar）而已。

差点忘了 Iterator 的使用

所有 Collection 的子类都有 iterator() 方法来获得 Iterator，通过 Iterator 的标准操作方法，可以让我们不必关心具体集合的类型，从而避免向客户端暴露出集合的内部结构。

不使用 Iterator 遍历集合是这样的：

使用 Iterator 遍历集合是这样的：

对比而言，后者客户端代码与具体集合类型耦合性弱，复用性更强。缺点就是无法获取指定的元素，只能挨个遍历。

Thanks

ListIterator

根据官方文档介绍, ListIterator 有以下功能：

注意，迭代器 没有当前所在元素一说，它只有一个游标( cursor )的概念，这个游标总是在元素之间，比如这样:

初始时它在第 0 个元素之前，调用 next() 游标后移一位：

调用 previous() 游标就会回到之前位置。当向后遍历完元素，游标就会在元素 N 的后面：

也就是说长度为 N 的集合会有 N+1 个游标的位置。

ListIterator 继承自 Iterator 接口（关于 Iterator 的介绍 请点这里），在 Iterator 的基础上增加了 6 个方法：

介绍一下新来的几个方法：

ListIterator 有两种获取方式

区别在于第二种可以指定 游标的所在位置。

ListIterator 的具体实现？

AbstractList 作为 List 的直接子类，里面实现了 listIterator() 方法，并且有两个内部迭代器实现类：SimpleListIterator，FullListIterator：

listIterator() 返回的是 FullListIterator()：

FullListIterator 继承了 SimpleListIterator, SimpleListIterator 实现了 Iterator 接口：

了解了 SimpleListIterator 后我们看下 FullListIterator 的具体实现：

可以看到 SimpleListIterator 的主要操作最后都交给子类来实现，List 的子类 ArrayList, LinkedList, Vector 由于底层实现原理不同（数组，双向链表），具体操作类实现有所不同。

等接下来分析到具体子类再看相关实现吧。

什么是集合？

什么是集合框架？

集合框架是一个代表、操作集合的统一架构。所有的集合框架都包含以下几点：

不仅 Java，其他语言也有一些集合框架，比如 C艹 的 STL（标准模板库），Smalltalk 的集合层次结构。不同于他们陡峭的学习曲线，Java 集合框架设计的更加合理，学习起来更加轻松。

使用集合框架有什么好处呢?

使用 Java 集合框架能有以下几点好处：

Java 集合框架主要结构图

如上图所示，Java 的集合主要按两种接口分类：Collection, Map.

Collection 接口

Collection 作为集合的一个根接口，定义了一组对象和它的子类需要实现的 15 个方法：

对集合的基础操作，比如 :

还有一些操作整个集合的方法，比如 :

还有对数组操作的方法：

在 JDK 8 以后，Collection 接口还提供了从集合获取连续的或者并行流：

点击这里了解流 Stream.

遍历 Collection 的几种方式：

Aggregate Operations 聚合操作

在 JDK 8 以后，推荐使用聚合操作对一个集合进行操作。聚合操作通常和 lambda 表达式结合使用，让代码看起来更简洁（因此可能更难理解）。下面举几个简单的栗子：

聚合操作还有很多功能，这里仅做介绍，想要了解更多可以查看Aggregate Operations 官方指引。

Iterator 迭代器

在Java 集合解析：Iterator 和 Java 集合解析：ListIterator 我介绍了 Collection 的迭代器 Iterator 以及用于 List 的迭代器 ListIterator。

结合 Collection 和 Iterator 可以实现一些复用性很强的方法，比如这样：

这个 filter 方法是多态的，可以用于所有 Collection 的子类、实现类。 这个例子说明了使用 Java 集合框架我们可以很随便就写出 “优雅，可拓展，复用性强” 的代码~

总结

Collection 接口是类集框架的基础之一。

它创建所有类集都将拥有的 15 个核心方法。

点击查看 Java 集合框架深入理解系列， - ( ゜- ゜)つロ乾杯~

Java 提供的集合类都在 Java.utils 包下，其中包含了很多 List, Set, Map, Queue… 它们的关系如下面这张类图所示：

本篇文章将介绍 Iterator 迭代器。在介绍 Iterator 之前不得不提一下被它替代的 Enumeration< E >:

可以大胆猜一下，应该是当初设计没有考虑全，只有两个方法，而且名字还太长了 - -。后来在 JDK 1.2 推出了 Iterator 替代它的功能。虽然 Enumeration 在 JDK 1.5 后增加了泛型的应用，依旧大势已去。

它和 Enumeration 有什么不同呢？

哈哈首先是名字缩短了，看来大家都懒得输入那么长的方法名。其次是允许调用者在遍历过程中语法正确地删除元素。

注意这个 [语法正确]，事实上我们在使用 Iterator 对容器进行迭代时如果修改容器可能会报 ConcurrentModificationException 的错。官方称这种情况下的迭代器是 fail-fast 迭代器。

使用 Collections.synchronizedList 加同步锁，不过这样有点粗暴。

在学习 ListView 中的观察者模式时，我注意到 DataSetObservable 的 notifyChanged 方法中有如下注释：

为了避免影响 ArrayList 迭代，倒序处理。待考究，目前我还没搞清楚。

注意，迭代器没有当前所在元素一说，它只有一个游标( cursor )的概念，这个游标总是在元素之间，比如这样:

ListIterator 继承自 Iterator 接口（关于 Iterator 的介绍请点这里），在 Iterator 的基础上增加了 6 个方法：

区别在于第二种可以指定游标的所在位置。

不仅 Java，其他语言也有一些集合框架，比如 C艹的 STL（标准模板库），Smalltalk 的集合层次结构。不同于他们陡峭的学习曲线，Java 集合框架设计的更加合理，学习起来更加轻松。

这个 filter 方法是多态的，可以用于所有 Collection 的子类、实现类。这个例子说明了使用 Java 集合框架我们可以很随便就写出 “优雅，可拓展，复用性强” 的代码~

感谢密哥提醒，parallel 应该是并行，而不是并发。

这里看到的一幅生动形象图：

其次根据官方文档：

Collection 中提供的一些方法就不介绍了，不熟悉的可以去看一下。

`Object` 的 `equlas`() 方法默认和 `==` 一样，比较的是地址是否相等。

在 List 中有两个转换成数组的方法：

数组工具类 Arrays 提供了数组转成 List 的方法 `asList` :