1、ArrayList<E>

先看其源码：

private static final int DEFAULT_CAPACITY = 10; //初始内存大小

transient Object[] elementData; //真实数据存放地， 被 transient 修饰的属性变量不会被序列化(不被网络传输、持久化)

实现是基于动态数组的数据结构，每个元素在内存中存储地址是连续的。每次扩容会固定为1.5倍，所以当你ArrayList达到一定量之后会是一种很大的浪费，并且每次扩容的过程是内部复制数组到新数组；对于每个元素的检索，ArrayList要优于LinkedList。非线程安全

ArrayList默认容量是10，如果初始化时一开始指定了容量，或者通过集合作为元素，则容量为指定的大小或参数集合的大小。每次扩容时新容量按老容量1.5倍计算，如果新容量数大于所需最小容量则为新增后所需的最小容量。如果计算后的新容量数超过限制的容量数 MAX_ARRAY_SIZE ( Integer.MAX_VALUE - 8 )，则用所需的最小容量与 MAX_ARRAY_SIZE 进行判断，超过则指定为 Integer 的最大值，否则指定为限制容量大小。然后通过数组的复制将原数据复制到一个更大(新的容量大小)的数组。

Vector与其大致相同，都是基于数组的数据结构，但是线程安全（扩容等方法加了synchronized），vector每次扩容容量是翻倍，即为原来的2倍

2、LinkedList

transient int size = 0;

LinkedList是采用链表的方式来实现List接口的,它本身有自己特定的方法，如: addFirst(),addLast(),getFirst(),removeFirst()等. 由于是采用链表实现的,因此在进行 新增 和 删除 动作时在效率上要比ArrayList要好得多 ! 适合用来实现Stack(堆栈)与Queue(队列),前者先进后出，后者是先进先出。非线程安全

理论上效率好，实际得看新增、删除位置或者说实际中数据量小，效率差异忽略不计。

3、HashSet

内部也是基于 Hashmap 实现，不允许有重复元素。无序。初始容量16，扩容因子0.75 。在HashSet中，元素都存到HashMap键值对的Key上面，而Value时有一个统一的值private static final Object PRESENT = new Object();定义一个虚拟的Object对象作为HashMap的value，将此对象定义为static final。

4、LinkedHashSet

集成 HashSet ，但内部也是基于 LinkedHashMap ，与HashSet 相比无新方法，但元素是有序的。

5、TreeSet

内部基于TreeMap，TreeSet中存放的元素是有序的（不是插入时的顺序，是有按关键字大小排序的），且元素不能重复。存放自定义对象，需自定义对象实现Comparable 接口，并重写接口中的compareTo方法，当 compareTo方法

返回 0 时 只会存一个元素，认为是相同的元素，这时就不再向TreeSet中插入相同的新元素。返回负数会倒序存储，认为新插入的元素比上一个元素小，于是二叉树存储时，会存在根的左侧，读取时就是倒序序排列的。返回自然数时 认为新插入的元素比上一个元素大，于是二叉树存储时，会存在根的右侧，读取时就是正序排列的。6、HashMap

无序，非线程安全，无重复key，允许key和value空值 ，key为空值时其hashCode值定为了0，从而将其存放在哈希表的第0个bucket中。默认的初始化大小为16，之后每次扩充为原来的2倍。

a. JDK7中HashMap采用的是 数组（位桶）+链表的方式，即我们常说的散列链表的方式，

transient Entry<K,V>[] table;

HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。

HashMap的resize（rehash）

当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，这是一个常用的操作，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。

那么HashMap什么时候进行扩容呢？当HashMap中的元素个数超过数组大小loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过160.75=12的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。

HashMap的性能参数

HashMap 包含如下几个构造器：

HashMap()：构建一个初始容量为 16，负载因子为 0.75 的 HashMap。ashMap(int initialCapacity)：构建一个初始容量为 initialCapacity，负载因子为 0.75 的 HashMap。HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的负载因子创建一个 HashMap。

HashMap的基础构造器HashMap(int initialCapacity, float loadFactor)带有两个参数，它们是初始容量initialCapacity和负载因子loadFactor。

负载因子loadFactor衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。

HashMap的实现中，通过threshold字段来判断HashMap的最大容量：

threshold = (int)(capacity * loadFactor);

结合负载因子的定义公式可知，threshold就是在此loadFactor和capacity对应下允许的最大元素数目，超过这个数目就重新resize，以降低实际的负载因子。默认的的负载因子0.75是对空间和时间效率的一个平衡选择。当容量超出此最大容量时， resize后的HashMap容量是容量的两倍。

b、JDK8中采用的是数组（位桶）+链表/红黑树（有关红黑树请查看红黑树）的方式，也是非线程安全的。当某个位桶的链表的长度达到某个阀值的时候，这个链表就将转换成红黑树。当同一个hash值的节点数不小于8时，将不再以单链表的形式存储了，会被调整成一颗红黑树。这就是JDK7与JDK8中HashMap实现的最大区别。

transient Node<K,V>[] table;

R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。

7、HashTable

无序，线程安全，无重复key，不允许key和value空值，HashTable默认的初始大小为11，之后每次扩充为原来的2n+1。内部是采用synchronized来保证线程安全的，但在线程竞争激烈的情况下HashTable的效率下降得很快因为synchronized关键字会造成代码块或方法成为为临界区(对同一个对象加互斥锁)，当一个线程访问临界区的代码时，其他线程也访问同一临界区时，会进入阻塞或轮询状态。究其原因，实际上是有获取锁意向的线程的数目增加，但是锁还是只有单个，导致大量的线程处于轮询或阻塞，导致同一时间段有效执行的线程的增量远不及线程总体增量。

8、LinkedHashMap

有序，非线程安全，Key和Value都允许空，继承了HashMap。维护一个额外的双向链表保证了迭代顺序。

源码内部有Entry<K,V> before, after;next 。next是用于维护HashMap指定table位置上连接的Entry的顺序的，before、After是用于维护Entry插入的先后顺序的。

9、CocurrentHashMap

不允许key、value为null，

利用锁分段技术增加了锁的数目，从而使争夺同一把锁的线程的数目得到控制。 锁分段技术就是对数据集进行分段，每段竞争一把锁，不同数据段的数据不存在锁竞争，从而有效提高 高并发访问效率。CocurrentHashMap在get方法是无需加锁的，因为用到的共享变量都采用volatile关键字修饰，保证共享变量在线程之间的可见性(每次读取都先同步缓存和内存，直接从内存中获取值，虽然不是原子操作，但根据JAVA内存模型的happen before原则，对volatile字段的写入操作先于读操作，能够保证不会脏读),volatile为了让变量提供线程之间的内存可见性，会禁止程序执行结果的重排序（导致缓存优化的效果降低）。

实际使用中 Map<String, Integer> count = new ConcurrentHashMap<>();

比较

JDK6,7中的ConcurrentHashmap主要使用Segment来实现减小锁（ReentrantLock）粒度，把HashMap分割成若干个Segment（分段），在put的时候需要锁住Segment，get时候不加锁，使用volatile来保证可见性，当要统计全局时（比如size），首先会尝试多次计算modcount 来确定，这几次尝试中，是否有其他线程进行了修改操作，如果没有，则直接返回size。如果有，则需要依次锁住所有的Segment来计算；jdk7中ConcurrentHashmap中，当长度过长碰撞会很频繁，链表的增改删查操作都会消耗很长的时间，影响性能,所以jdk8 中完全重写了concurrentHashmap, 主要设计上的变化有以下几点:不采用segment而采用node，锁住node来实现减小锁粒度。设计了MOVED状态 当resize的中过程中 线程2还在put数据，线程2会帮助resize。使用3个CAS操作来确保node的一些操作的原子性，这种方式代替了锁。sizeCtl的不同值来代表不同含义，起到了控制的作用。

JDK8中使用synchronized而不是ReentrantLock，

10.TreeMap 有序的key-value集合，它是通过红黑树实现的。该映射根据其键的自然顺序进行排序，默认是升序的，如果我们需要改变排序方式，则需要使用比较器：Comparator ，该方法主要是根据第一个参数o1,小于、等于或者大于o2分别返回负整数、0或者正整数。TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fastl的。

11 cas原理

CAS:Compare and Swap, 翻译成比较并交换。 CAS有3个操作数，内存值V，旧的预期值A，要修改的新值B。当且仅当预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做。

CAS通过调用JNI的代码实现的。JNI:Java Native Interface为JAVA本地调用，允许java调用其他语言。

而compareAndSwapInt就是借助C来调用CPU底层指令实现的。