1、List接口

最重要的三种List接口实现：ArrayList、Vector、LinkedList。它们的类图如下：

可以看到，3种List均来自 AbstratList 的实现。而 AbstratList 直接实现了List接口，并扩展自 AbstratCollection。

ArrayList 和 Vector 使用了数组实现，可以认为，ArrayList 封装了对内部数组的操作。比如向数组中添加、删除、插入新的元素或数组的扩展和重定义。对ArrayList或者Vector的操作，等价于对内部对象数组的操作。

ArrayList 和 Vector 几乎使用了相同的算法，它们的唯一区别可以认为是对多线程的支持。ArrayList 没有对一个方法做线程同步，因此不是线程安全的。Vector 中绝大多数方法都做了线程同步，是一种线程安全的实现。因此ArrayList 和 Vector 的性能特性相差无几。

LinkedList 使用了循环双向链表数据结构。LinkedList 由一系列表项连接而成。一个表项总是包含3个部分：元素内容、前驱表项和后驱表项。如图所示：

LinkedList的表项源码：

    private static class Node<E> {         E item;         Node<E> next;         Node<E> prev;          Node(Node<E> prev, E element, Node<E> next) {             this.item = element;             this.next = next;             this.prev = prev;         }     }

无论LinkedList是否为空，链表都有一个header表项，它既是链表的开始，也表示链表的结尾。它的后驱表项便是链表的第一个元素，前驱表项便是链表的最后一个元素。如图所示：

下面比较下ArrayList 和 LinkedList的不同。

1.增加元素到列表尾端

对于ArrayList来说，只要当前容量足够大，add()操作的效率是非常高的。

只有当ArrayList对容量的需求超过当前数组的大小时，才需要进行扩容。扩容会进行大量的数组复制操作。而复制时最终调用的是System.arraycopy()方法，因此，add()效率还是相当高的。

LinkedList由于使用了链表的结构，因此不需要维护容量的大小。这点比ArrayList有优势，不过，由于每次元素增加都需要新建Node对象，并进行更多的赋值操作。在频繁的系统调用中，对性能会产生一定影响。

2.插入元素到列表任意位置

ArrayList是基于数组实现的，而数组是一块连续的内存空间，每次插入操作，都会进行一次数组赋值。大量的数组复制会导致系统性能低下。

LinkedList是基于链表实现的，在任意位置插入和在尾端增加是一样的。所以，如果系统应用需要对List对象在任意位置进行频繁的插入操作，可以考虑用LinkedList替代ArrayList。

3.删除任意位置元素

对ArrayList来说，每次remove()移除元素都需要进行数组重组。并且元素位置越靠前开销越大，要删除的元素越靠后，开销越小。

在LinkedList的实现中，首先需要通过循环找到要删除的元素。如果要删除的元素位置处于List的前半段，则从前往后找；若处于后半段，则从后往前找。如果要移除中间位置的元素，则需要遍历完半个List，效率很低。

4.容量参数

容量参数是ArrayList 和 Vector等基于数组的List的特有性能参数，它表示初始数组的大小。

合理的设置容量参数，可以减少数组扩容，提升系统性能。

默认ArrayList的数组初始大小为10。

private static final int DEFAULT_CAPACITY = 10;

5.遍历列表

常用的三种列表遍历方式：ForEach操作、迭代器 和 for循环。

对于ForEach操作，反编译可知实际上是将ForEach循环体作为迭代器处理。不过ForEach比自定义的迭代器多了一步赋值操作，性能不如直接使用迭代器的方式。

使用For循环通过随机访问遍历列表，ArrayList表现很好，速度最快；但是LinkedList的表现非常差，应避免使用，这是因为对LinkedList的随机访问时，总会进行一次列表的遍历操作。

2、Map接口

Map是一种非常常用的数据结构。围绕着Map接口，最主要的实现类有Hashtable, HashMap, LinkedHashMap 和 TreeMap，在Hashtable中，还有Properties 类的实现。

Hashtable和hashMap的区别在于Hashtable的大部分方法都做了线程同步，而HashMap没有，因此，Hashtable是线程安全的，HashMap不是。其次，Hashtable 不允许key 或 value使用null值，而HashMap可以。第三，它们在内部对key的hash算法和hash值到内存索引的映射算法不同。

由于HashMap使用广泛，本文以HashMap为例，阐述它的实现原理。

1.HashMap的实现原理

简单来说，HashMap就是将key做hash算法，然后将hash值映射到内存地址，直接取得key所对应的数据。在HashMap中，底层数据结构使用的是数组。所谓的内存地址，就是数组的下标索引。

用代码简单表示如下：

object[key_hash] = value;

2.Hash冲突

当需要存放的两个元素1和2经hash计算后，发现对应在内存中的同一个地址。此时HashMap又会如何处理以保证数据的完整存放？

在HashMap的底层使用数组，但数组内的元素不是简单的值，而是一个Entity类的对象。每一个Entity表项包括key，value，next，hash几项。注意这里的next部分，它指向另外一个Entity。当put()操作有冲突时，新的Entity会替换原有的值，为了保证旧值不丢失，会将next指向旧值。这便实现了在一个数组空间内存放多个值项。因此，HashMap实际上是一个链表的数组。而在进行get()操作时，如果定位到的数组元素不含链表（当前entry的next指向null），则直接返回；如果定位到的数组元素包含链表，则需要遍历链表，通过key对象的equals方法逐一比对查找。

关键字：