从最基础的数据结构 数组|链表|树 开始，基于这些基础数据结构通过各种设计组合成具备特定功能的数据结构，这些结构是编码的基础和核心。比如C++的vector，jdk自带了大量这些数据结构，统称为集合。

1、基本知识

I、接口

集合主要是俩类三种结构，一类是线性表，只存储数据本身，有List和Set两种，区别是Set不可重复；另一类是Key-Value键值对，有索引功能.

II、迭代接口 - Iterator

老的框架还有Enumeration 接口，Iterator接口也是23种设计模式中的经典模式；在List和Set的接口中都有iterator接口，而map本质上是一个Set和Map接口的联合实现，也有iterator访问方法。

为何使用Iterator？

封装了对象的内部实现，通过iterator接口提供其内部数据的访问，而无需知道内部的数据结构。还有一个非常重要的用途，集合提供了一个快速失败的功能 fast failture，当多个同时操作集合时，能够迅速感知到 modCount(修改次数)的变化

III、常用集合 - 基本实现

HashSet/TreeSet

ArrayList/LinkedList

HashMap/HashTable/TreeMap

IV、历史集合

Vector/HashTable/Stack/Dictionary/Properties ... 很多集合开始使用，后来被抛弃，最后又重写了

V、特殊集合 - Collections封装接口

a、只读集合 unmodifiableList | unmodifiableMap | unmodifiableSet

b、线程安全 synchronizedList | synchronizedMap | synchronizedSet

c、副本集合 单例 singleton | 多个重复填充值 | nCopies

VI、算法集合 - Collections封装接口

a、排序 sort

b、检索 binarySearch

c、求值 max/min

d、操作 fill-填充/shuffle-打乱/reverse-反转

...

下面开始一些具体数据结构的精讲，源码阅读。jdk的集合中，所有采用数组这种原始结构的，都大量采用了底层实现，以实现数组元素间的快速拷贝和数据转移，比如， System.arraycopy 是 native 函数，jdk 类库底层 C++ 实现直接实现 内存的拷贝，比如Arrays.copyOf 只是在 System.arraycopy 做了封装，以支持泛型等等。这是理解很多集合实现的一个重要点，不然大规模频繁的转移数据，实现上肯定是低效的。jdk通过折中达到  内存占用，使用效率，灵活性的一个平衡。

2、List精讲

I、ArrayList - 数组实现

既然是数组实现，最重要的就是容量的设定和回收，设计的太小，放不下;设计的太大，内存浪费

a、容量管理

i、初始容量：默认 容量是 10，可以初始化指定

ii、扩容：ensureCapacity 扩容并没有完全按照用户设置的值 minCapacity 扩容，而是用 用户扩充的容量 和 原始数据容量的 1.5 倍比，取其大值

目的是，不用频繁去扩容

iii、回收容量 trimToSize 压缩空余的数组内存空间

-- 正如上所说，扩容和回收都需要移动数据位置，采用了系统函数提高效率

b、寻址/索引

指定位置 index - 因为数组下表本身就带有地址索引信息，所以指定位置直接指向即可

寻找对象的位置 indexOf/lastIndexOf，因为是无序数组，所以，只能循环查找;需要注意的是，寻找的原则是equals函数，所以如果不是以对象引用查找，而是以对象的内容作为查找的话，一定需要覆盖equals方法

c、存取操作

顺序增加 add(Element)| 指定位置增加 add(index,Element) | 批量增加 addAll(Collection)

指定位置修改 set(index,Element)

指定位置删除 remove(index) | 删除对象 remove(Element) | 另外，提供了快速删除，即不需要取删除的数据，直接移位

指定位置获取 get(index)

-- 指定位置的操作都依赖于寻址;除了修改和顺序增加外，所有操作都涉及数组对象的移位操作；增加操作前，都调用扩容方法检查是否真的需要扩容

d、其他操作

转换数组 toArray

序列化 readObject | writeObject

支持 null 对象

II、LinkedList - 双向环形链表实现

链表实现，就没有容量的概念，为了维持链表结构，就需要保留一个前向、后向的引用

a、寻址/索引

指定位置 entry(index) - 因为链表没有位置索引，为了优化寻找，根据index大小判断从头部正向寻找，还是从尾部逆向寻找

寻找对象的位置, 这点和ArrayList一样

b、存取操作

顺序增加 addBefore(Element) addLast offer | 指定位置增加 add(index,Element) | 批量增加 addAll(Collection)

指定位置修改 set(index,Element)

指定位置删除 remove(index) removeFirst removeLast | 删除对象 remove(Element)

指定位置获取 get(index) getFirst getLast peek

c、其他操作

同ArrayList

III、ArrayList VS LinkedList

a、首先从内存空间使用上看 ArrayList 有两难境界，规划空间小频繁扩容，规划空间多，浪费比较多。特别是多次操作后，需要及时回收，否则内存就会浪费泄漏；LinkedList存储只有本身节点（需要另外存储 引用，每个元素需要多8个字节）

b、从寻址上看，指定位置操作 ArrayList只需要 O(1) 常量时间, 而LinkedList需要 O(N)

c、从存取操作看，ArrayList需要频繁内存拷贝，而LinkedList只需要改变一下指针

综合来看, 数据创建后比较少变动的，需要随机访问的，适合使用ArrayList, 频繁操作的 则适合使用 LinkedList； 举两个应用场景，常用的消费者生产者模式，使用队列就应该使用LinkedList，因为数据一直在变；从数据库读取一批数据在内存中给后续程序使用，使用ArrayList更合理一点

3、Map精讲

I、HashMap -- 哈希表实现 (数组+链表)

HashMap的实现应该是集合里面最重要的数据结构了，对于哈希算法，使用了数组做桶，链表作为冲突的解决方法。

哈希表的优势之一就是寻址/存储都是线性时间，所以引用也是最为广泛

a、容量

初始容量： 默认是 capacity 16 | 最大容量 2^31 | 负载因子 loadfactor 0.75

容量*负载因子，共同决定数组的门限 threshold

需要注意的是，初始化容量后，数组容量并不是 指定的容量，而是 2 ^ N 这个数刚好大于指定容量 X 即 容量 2 ^N-1 <= X <= 2^N

扩容：resize

扩容是创建一个新的 大小 *2 的数组，然后把原先 数组的数据 通过 transfer 方法全部移到新表里面

这里有一个注意点，就是 原先在一个链表的数据 哈希取模后相同的数据，在新的表容量取模可能不在同一个表中（比如 1 和 257 按 256 取模都是在 1 这个槽位，而 按新的 512 取模就不在同一个槽了）

所以，这里transfer 方法，对数据的元素都进行了迭代；因此，扩容基本对所有元素都访问一次，对效率影响较大。需要减少频繁扩容

-- 这也是哈希算法的劣势之一，要预先考虑好桶容量

b、寻址/索引 indexFor

针对hashcode 再计算一次 hash，用hash值 & leng -1 进行索引定位，因为表格大小capacity 都是 2 的倍数，使用 & length - 1效率更高；寻址表格后，再利用 equals 进行循环查找 相同的key

c、存取操作

获取：get 根据key值找到value, 根据indexFor寻址 通过 hashcode 找到数组，通过equals 迭代链表找到数据

存储：put 也是根据key值寻址，因为HashMap不区分增加/修改，所以都是迭代链表直到找到为止，如果没有找到，则把新节点链表放在table[index]位置，如果找到则覆盖

批量存储：putAll 首先需要计算容量，然后再迭代插入

删除：同获取过程类似

Null的特殊处理，因为Null没有hashcode，所以默认放在第 0 个桶，value也支持null -- putForNullKey/getForNullKey

d、其他重要知识点

keySet -- 返回的key值的set集合,通过HashMap提供Entry的iterator迭代器访问

values -- 返回的value值的collection集合,通过HashMap提供Entry的iterator迭代器访问

entrySet -- 返回的key-value集合

返回的这三个对象都是空对象，通过iterator 迭代器完成访问

modCount -- Fast Failture 迅速失败,并发场景下保证数据一致性

序列化

补充点：传统的哈希表 实现，有个比较麻烦的问题，就是哈希碰撞，极端情况下操作就变成了单纯链表操作,O(N),所以一直到Java8,对哈希表进行了改造。

优化1：正常情况下就是普通哈希表实现，put时检查，当链表长度达到8时，立即把该链表转成红黑树，这样效率就会是红黑树O(LogN)，resize时，当长度小于6时，还蜕化为链表。增加了put和get、resize等操作的复杂度。

优化2：索引和转移链表时进行了优化，新增元素也是追加到链表尾，而不是放在表头，不像原先HashMap转移链表会反置链表

更详细的描述参见 http://www.importnew.com/20386.html

II、TreeMap - 红黑树

既然使用了红黑树，那保证了数据的有序,优点和哈希表类似, 插入和查找都非常快,O(logN),相比哈希表 红黑树占用空间只是本节点，而哈希表需要预留很多空间。从这点来看，有点类似 ArrayList和LinkedList的区别

但HashMap的哈希表情况更糟糕一些，因为需要循环迭代，而不能像ArrayList底层内存拷贝。不过红黑树的效率要低于哈希表，特别是热点数据，需要频繁对树进行旋转。

a、寻址/索引

getEntry 对对象进行比较，然后迭代树的子树。所以对于TreeMap使用的数据类型，就需要实现 Comparable 接口

b、存取操作

获取：get 根据key值寻址到树的节点，通过 compareTo 比较获取对应节点的value

存储：put 根据key值寻址，找到节点，如果相等则 更新，否则插入节点，并进行红黑树的旋转；

批量存储：循环调用put进行存储

删除：remove根据key值寻址后，用了一点技巧，并没有真正删除，而是用当前节点的一个叶子节点（左分支的最右边，右分支的最左边）来替换当前节点，然后平衡，删除叶子节点。

TreeMap类型的还支持，除了精确查找外的，一些模糊查找返回 子树集合。

红黑树不支持Null。

c、其他重要知识点

同HashMap基本一样，通过iterator提供三个对象的访问，支持modCount

III、Hashtable - 同HashMap的底层结构

Hashtable 重写后继承了Map接口，实现原理同HashMap，只是Hashtable继承的是老的对象 Dictionary,

但细节上有很多差异，在容量设定、扩容，寻址代码(采用了&fff这种方式)实现层面都有差异，大的差异参见下面

HashMap VS TreeMap

从内存空间来看，HashMap通常空间要大于TreeMap,两者都有引用,但HashMap数组要预留很多桶

从操作效率来看，HashMap要由于TreeMap O(1) 要比 O(logN)快的多，而且红黑树热点旋转的话，就非常苦逼了

另外，TreeMap是有序的结构，如果需要存储数据出来是有序的话，则肯定使用TreeMap

HashMap VS Hashtable

最大的差异在 Hashtable 每个存取方法都加了 synchronized 同步方法，所以是线程安全的，也慢了很多

其次在对于null的操作上，Hashtable没有对null的特殊处理，即key和value都不能放入Hashtable

再次迭代器的使用 HashMap使用了fail-fast，其他线程修改结构(set 值不改变结构并不会导致失败)后迅速失败，Hashtable 还有老的 enumerator迭代器

还有一个小差异，Hashtable的contains方法，HashMap改成了 ContainsKey和ContainsValue，更清晰

ConcurrentHashMap已经取代了Hashtable

4、Set精讲

HashSet 和 TreeSet 分别复用了 HashMap和TreeMap的实现, 作为其Key的使用，没有单独定义数据结构

5、并发编程集合

最简单的并发处理，就是对象存取操作串行化，Collections 提供的线程安全集合，就是这个思路。但这样效率极低。那如何实现高效的并发编程集合呢

可以借鉴数据库对待 锁的思路

思路1：分割数据，减小 锁的范围和 锁的粒度 - 比如行锁，页锁，表锁

思路2：读写分离，区别对待读和写 - 读共享锁，写排他锁

本章节出现的很多 并发编程概念，请参照本博 《java 并发编程精华一页纸》

I、CopyOnWriteXXX

首先从最简单的集合类型，写时复制。这就是读写分离的思路。Copy On write的策略使用范围非常广，比如 Redis内存数据库在持久化时使用该策略保证父子进程读写不受干扰。

以 CopyOnWriteArrayList 为例

读时，不加锁，一旦出现修改时，加锁，然后生成新的数组对象。

和数据库的隔离级别一样。 这里有一个问题，就是在操作瞬间读数据时，并不能保证一致性，这里约等于 数据库的 READ_COMMITED 会有不可重复读和幻读出现。

使用CopyOnWrite只适用于大量多少量写的场景，比如 经常使用的 缓存的元数据，用户信息、设备信息 变更极少。

II、Queue 消费者队列

阻塞 or 非阻塞

阻塞队列： 单向 BlockingQueue | 双向 BlockingDeQue 也有数组和链表的两种实现

原理都是入栈和出栈都加锁。不同的 ArrayBlockingQueue是 一把锁，而LinkedBlockingQueue 是两把锁， 写锁当容量满时 等待notFull的唤醒、发出NotEmpty的唤醒信号； 读锁当容量空时 等待NotEmpty的唤醒、发出NotFull的唤醒信号

优先级队列 PriorBlockingOueue 具有优先级的队列，内部是 红黑树的实现，可以保证offer出来的值有一定顺序

非阻塞队列： ConcurrentLinkedQueue

基本上非阻塞的原理都是采用 CAS 技术 即 不断循环尝试，利用底层的 CAS 进行修改。ConcurrentLinkedQueue 入队和出对都是不断的尝试，直到出队和入队成功

III、ConcurrentHashMap

java6和7 的实现，其实就是 分割数据的思路，把Hashtable的全局锁，改成分段锁，数据也分段处理

多线程编写原则变量隔离,不跨线程访问 > 变量改成不可变 > 同步，从这个原则来看ConcurrentHashMap的设计，就能更清楚了

a、容量

ConcurrentHashMap的容量比单纯的HashMap要复杂一点，增加了一个 concurrencyLevel 并发度的参数。容量不是单纯的一个数组

而是 两层数组，第一层是 segment数组,由并发度决定，第二层根据容量 / segement，以决定每个segment大概有几个元素

初始容量：和HashMap一致，并发度也是 16

扩容：rehash 和 HashMap的扩容差不多也是需要移动链表数据，做了一点优化

i、首先注意扩容，并没有改变并发度，也就是说segment数组没有变，这点很重要；因为表明按照高位落在哪个segment没有变化。不牵涉跨段操作。

ii、因为扩容是翻倍的，所以 最终在segment内的位置只有两种情况：保持不变 i ；或者旧容量 capcity + 位置 i

比如 1 or 17 % 16 都是 1 ，扩容后 1 or 17 % 32， 一个是1 保存不变，一个是 16 + 1

jdk做的优化是，扫描一遍链表，如果发现链表某个位置到尾部，都是没有位置变化的元素，那这部分元素保持不变，只把链表前面部分重新根据hash分组处理

并发度的设置需要通盘考虑，如果并发度过大，极端情况和数组容量一样大，则每次需要跨段处理；并发度过小，极端情况就是1，则和Hashtable一样

b、寻址/索引

i、首先计算一次hash

ii、调用 segmentFor，使用hash后的值 高位 & segment.length，计算出数据在哪个号段

iii、得到具体的Segment，HashEntry.length & hash ，找到在段数组的具体位置

c、存取操作

讲解存储操作之前，先看节点 HsahEntry的设计， hash和key都是final常量不允许修改；value 是volatile，链表指针在6中是final，7中是volatile。所有的数据都为并发做了修订。

首先常量部分不会发生变动，volatile在修改时能够实时被感知。

java 6的存取操作最后都是代理给 Segment 进行操作，到了7-8就彻底改成了Unsafe对象的操作

获取: get 寻址数据过程如上，找到槽位后，链表迭代；get没有加锁，原因如下(只适合6)

如果有线程在修改value，因为volatile所以无需加锁

如果有线程在增加，读到null时，再加锁读一次

如果有线程在删除，采用了类似CopyOnWrite的技术，保证能读到

存储：put/putIfAbsent/putAll 也是先寻找数据，需要加锁

删除：remove 因为next 不可变，所以要把删除节点的后续节点全部复制一遍(CopyOnWrite)；原先的链表如果此时正在访问到这个部分可以继续访问

全局操作：size|containsValue 操作和普通的操作不同，要遍历所有的号段segment，多线程操作时，作者用了一个小技巧，并没有一开始就锁表，而是迭代3次处理，无法获取(获取结果不一致)，才加锁操作

不支持Null 存储 (key/value)这么设计的原因是在ConcurrentHashMap中，一旦value出现null，则代表HashEntry的key/value没有映射完成就被其他线程所见，需要特殊处理。

java8 实现

同HashMap一样，ConcurrentHashMap 在java8做了大幅改进, 传统的数组+链表的哈希表方法，改成同时支持红黑树扩展。所以表结构方面采用了HashMap的大体思路

采用了在并发编程中的底层实现 CAS，不断比较并替换(看起来是不是和NIO、AIO的思想很接近）

a、容量

初始容量：和HashMap一致 16

扩容： addCount 判断容量是否需要扩容；helpTransfer 和 transfer 进行扩容；扩容后新的表需要把原先数据进行迁移，这和HashMap都一样。

首先某一个线程在 执行 addCount时，发现需要扩容，此时 初始化 nextTable 2 倍容量

然后该线程开始 进行 数据节点迁移(迁移过程和6、7 版本里差不多，也使用了i， i+capcity 的思路)，迁移时，循环迭代table，发现表头为空时，插入forward节点

此时如果有线程进行put等操作时,发现正在扩容时(只有 table 表头是forward节点才能发现),执行helpTransfer参与扩容

每个线程处理完当前节点后，把当前节点标记为 forward 节点，其他线程发现为 forward 节点后，就不再处理该节点；在处理过程中对该节点加锁，保证一致性

b、寻址/索引

tabAt 根据哈希和数组，寻找到当前tab中的位置

c、存取操作

获取：get 获取数据没有加锁，索引找到 tab 位置后

判断 头节点 hash值，如果<0 说明此时正在进行扩容，则委托 forward 节点的 find方法寻找

如果 没有扩容，则迭代节点寻址，因为 Node节点的 volatile 保证了修改的可见性，新增节点时会锁住头节点，所以保证了一致性

存储：put 方法，索引到 tab位置后

发现table 头节点正在扩容，参与扩容。 -- 因为有for循环(死循环),只有插入成功才会退出，所以扩容完成后，继续插入

发现空节点通过CAS技术的 casTabAt 插入 -- 因为此时粒度是表级，通过cas可以减少锁的影响

不为空，则锁住节点，进行插入 -- 找到节点后，此时粒度是 槽位节点对应的链表级别，可以加锁

删除：remove方法，索引到 tab位置后

发现正在扩容，参与扩容

然后锁住节点迭代检查并删除

大小：size 因为所有操作都会更新 baseCount ；虽然baseCount 是volatile，但同时多个线程同时操作有先后，读取的值只是瞬间的操作值，并不能保证完全准确

不支持Null

ConcurrentHashmap 总结：

a、forward 节点作为 扩容时的代理节点，作用有两个，一是作为扩容时，多个线程交互的标记；另一个作为扩容过程中，代理查询节点的查询请求

b、根据容量动态调整 链表和红黑树

c、锁的粒度是表格桶的每一个槽位，取的操作不加锁，操作数据时对槽位加锁；同时利用 cas 技术，不用对表整体加锁，提高了效率

IV、其他

除了 哈希表(数组+链表) 红黑树，并发编程集合里面也有跳跃表的实现， 因为跳跃表占用内存较多，只有在 红黑树热点比较明显的情况下，作为替代，平时用的比较少。

对于CAS技术，可以参照 《java 并发编程精华一页纸》