常用集合框架结构图

list

• ArrayList
  基于数组实现的，是一个动态数组，其容量能自动增长，可以允许重复元素，有序
  不是线程安全的，只能用在单线程环境下，多线程环境下可以考虑用Collections.synchronizedList(List l)函数返回一个线程安全的ArrayList类，也可以使用concurrent并发包下的CopyOnWriteArrayList类

底层逻辑

使用数组存储数据（默认初始容量为10），每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容（将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张）

特点
继承了数组的特性，可以通过下标索引直接查找到指定位置的元素，因此查找效率高O(1)，但每次插入或删除元素，就要大量地移动元素，插入删除元素的效率低（增删效率低）

• Vector
  Vector底层实现和ArrayList相似，区别在于方法采用synchronized。实现项目中几乎不用
  ArrayList和Vector区别

ArrayList在内存不够时默认是扩展50% + 1个，Vector是默认扩展1倍
Vector提供indexOf(obj, start)接口，ArrayList没有
Vector线程安全级别,但是大多数情况下不使用Vector，因为线程安全需要更大的系统开销

• LinkedList
  由双链表实现，增删由于不需要移动底层数组数据，其底层是链表实现的，只需要修改链表节点指针，对元素的插入和删除效率较高，但是遍历效率较低O(n/2)
  不是线程安全的

底层逻辑

使用双向链表实现，每个节点都有一个前驱（之前前面节点的指针）和一个后继（指向后面节点的指针）。LinkedList没有长度的概念，所以不存在容量不足的问题

双向链表

Set

• HashSet
  用来存储没有重复元素的集合类，并且它是无序的。内部实现是基于 HashMap实现（利用了 HashMap 的 key 不能重复这个原理来实现 HashSet ）

底层逻辑

HashSet内部维护一个HashMap，实际存储的元素都存放在HashMap的key上面，而value中的值都是统一的一个固定对象private static final Object PRESENT = new Object();

Map

• HashMap
  HashMap是一个键值对的集合，数据结构为 数组+(链表或红黑树)
  HashMap允许key和value为null，非线程安全。多线程建议使用ConcurrentHashMap，虽然HashTable也是线程安全的，但是性能较差

  
  数据结构图

为什么采用这种结构来存储元素呢？

数组的特点：查询效率高，插入，删除效率低。
链表的特点：查询效率低，插入删除效率高。
在HashMap底层使用数组加（链表或红黑树）的结构完美的解决了数组和链表的问题，使得查询和插入，删除的效率都很高。

使用HashMap注意事项：
因为HashMap的内部扩容机制，每次扩容都是一笔大的开销。所以应尽量规避，例如实现定义HashMap的长度

• ConcurrentHashMap
  主要就是为了应对hashmap在并发环境下不安全而诞生的，ConcurrentHashMap的设计与实现非常精巧，大量的利用了volatile，final，CAS等lock-free技术来减少锁竞争对于性能的影响

JDK1.7版本的ConcurrentHashMap
采用Segment数组（分段锁）+HashEntry+红黑树的实现方式。Segment类似于HashMap的结构。

内部结构图

从上面的结构我们可以了解到，ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作。
第一次Hash定位到Segment，第二次Hash定位到元素所在的链表的头部。所以缺点便是查找数据需要进行两次hash

JDK1.8版本的ConcurrentHashMap
采用synchronized+CAS+HashEntry+红黑树的实现方式。
Java8 ConcurrentHashMap结构基本上和Java8的HashMap一样，区别在于采用CAS+Synchronized保证线程安全

CAS是一种乐观锁，包含三个操作数 —— 内存位置（V）、预期原值（A）和新值(B)。如果内存地址里面的值和A的值是一样的，那么就将内存里面的值更新成B