转载

图学java基础篇之集合

（本文部分图片引用自其他博客，最后有链接，侵删。由于笔记使用markdown记录，格式可能不是太好看，见谅。另今天先完成一部分占坑，明天补全）

图学java基础篇之集合红字为java.util包下的，绿字为concurrent包下扩展的与并发相关的类

ArrayList

功能：有序非线程安全列表要点：

LinkedList

功能：有序非线程安全列表要点：

Vector

功能：有序线程安全列表要点：

Stack

功能：基于Vector实现的堆栈要点：

CopyOnWriteArrayList

功能：快照版本的ArrayList，修改操作通过复制一份数组操作要点：

实现线程安全List的方法

使用synchronized：对List操作是进行同步，需要自己控制
使用Vector：效率低，已经较少使用了
使用CopyOnWriteArrayList，前边已经介绍了，这个只能在量小读多写少的场景下用，且性能很差，一般不要用
使用Collections.synchronizedList()：工具类提供的一个比较简便的方法，可以直接创建一个线程安全的list，建议使用。其原理是对ArrayList进行包装，通过一个对象锁来控制并发，需要注意的是要弄清楚对象锁锁的是哪个对象。

HashMap

功能：要点：key-value的map,存储位置根据key的hash值确定

HashTable

功能：key-value的map,存储位置根据key的hash值确定，与Hash的算法不同之处是，其位置直接通过hash(key)%table.length计算（HashMap使用h&(length – 1)计算，效率更高，才外还有一些细节不同，可自行参看源码）要点：

TreeMap

功能：基于红黑树实现的有序集合

要点：

ConcurrentHashMap

功能：线程安全的HashMap，属于java.util.concurrent下的拓展类要点：

线程安全
底层实现是一个Segment 数组，Segment内部通过一个HashEntry
数组存储元素数据，同时Segment继承了ReentrantLock，直接通过本身的锁对改段数据操作同步
从底层结构可以发现，其修改时不会对整个集合加锁，而是对段加锁，因此允许同时修改多个段，效率更高
继承NavigableMap,主要实现了SortMap，因此是有序的
Segment的划分是通过key的hashCode计算

ConcurrentSkipListMap

功能：线程安全的有序Map，是通过一个叫做跳表的数据结构实现

要点：

线程安全
底层实现是一个多层链表，每层元素都有序，每低一层都包含上一层的元素，最底层包含所有元素。这样设计的巧妙之处是从上层逐层查找时，能够快速定位元素区间。思想上有点像折半查找，不过是把每次折半的中间值分层存了起来。同时链表结构是修改操作同样高效
key是有序的
空间换时间，效率很高，但是空间占用也很厉害