JAVA集合框架的特点及实现原理简介

1. 集合框架总体架构

• 集合大致分为 Set、List、Queue、Map 四种体系, 其中 List,Set,Queue 继承自 Collection 接口，Map 为独立接口
• Set 的实现类有:HashSet，LinkedHashSet，TreeSet…
• List 下有 ArrayList，Vector，LinkedList…
• Map 下有 Hashtable，LinkedHashMap，HashMap，TreeMap…

2. Set

Set 接口继承 Collection，用于存储不含重复元素的集合。
Set 是简化版的 Map。Set 把元素作为 key 存储在自己的 Map 实例中 (Entry)，value 则是一个空的 Object。

HashSet

底层是哈希表，当插入元素时，HashSet 会调用该对象的 hashCode() 方法得到 hashCode，然后根据 hashCode 决定该对象在哈希表中的存储位置。(这里有个问题，如果 hashcode 不是均匀分布的，而是集中在一个区域，极端情况下，hash 表会变成链表)
HashSet 去重原理：通过 equals() 方法比较，且其 hashCode() 方法返回值也相等。（可以通过覆写 hashCode 和 equals 方法改变其去重规则，进行自定义去重）

TreeSet

TreeSet 底层是红黑树; 加入元素时，必须加入同类型的对象，否则会发生 ClassCastException 异常，因为 TreeSet 会调用集合元素的 compareTo() 方法来比较元素之间的大小关系（自然排序）。
compareTo() 方法的返回值决定了顺序:

• -1 表示放在红黑树的左边, 即逆序输出;
• 1 表示放在红黑树的右边，即顺序输出;
• 0 表示元素相同，仅存放第一个元素自然排序（treeset 去重的原理）;

其次，TreeSet 也可以通过比较器排序。

LinkedHashSet

继承自 HashSet, 底层是链表和哈希表。

• 由链表保证元素有序 (插入顺序)。
• 由哈希表保证元素唯一

TreeSet, LinkedHashSet and HashSet 的区别

• 都实现 Set 接口, 不包含重复元素
• 都不是线程安全的，如果要使用线程安全可以 Collections.synchronizedSet()
• TreeSet 的主要功能用于排序
• LinkedHashSet 的主要功能用于保证 FIFO, 即有序的集合 (先进先出)
• HashSet 只是通用的存储数据的集合
• 插入速度: HashSet>LinkHashSet>TreeSet(内部实现排序)
• HashSet 不保证顺序，LinkHashSet 保证 FIFO(先进先出)，TreeSet 安装内部实现排序，也可以自定义排序规则
• HashSet 和 LinkHashSet 允许 null, (只能有一个 null) 但 TreeSet 中插入 null 时会报 NullPointerException

3. List

list 的实现类有 ArrayList,Vector,LinkedList… 其中 ArrayList 和 Vector 很相似，均是以数组作为底层实现，不同之处在于 Vector 是线程安全的。

ArrayList

ArrayList 基于数组实现, 不是线程安全的, 内部维护了一个可变长的对象数组, 集合内所有元素存储于这个数组中，并实现该数组长度的动态伸缩。
ArrayList 使用数组拷贝来实现指定位置的插入和删除。

LinkedList

LinkedList 内部以链表的形式来保存元素，因此随机访问集合时性能较差，但插入, 删除元素时性能较好。
LinkedList 不仅实现了 List 接口, 还实现了 Deque 接口，可以被当成双端队列来使用，即可被当成“栈”来使用，也可以当成队列使用。

ArrayList 和 LinkedList 比较

• 两者都是 List 接口的实现类, 都不是线程安全。List 的另外一个实现类 vector 是线程安全的。
• ArrayList 是基于动态数组的数据结构，而 LinkedList 是基于链表的数据结构。
• 对于随机访问 get 和 set（查询操作），ArrayList 要优于 LinkedList.(LinkedList 要移动指针)
• 对于增删操作（add 和 remove），LinkedList 优于 ArrayList。

4. Map

Map 集合用于保存映射关系的数据，Map 集合中保存了两组值，一组是 key，一组是 value。
Map 的 key 不能重复。
key 和 value 之间存在单向一对一的关系，通过 key，能找到唯一确定的 value。
Map 将 key 和 value 封装至一个叫做 Entry 的对象中，Map 中存储的元素实际是 Entry。只有在 keySet() 和 values() 方法被调用时，Map 才会将 keySet 和 values 对象实例化。

HashMap

key 是通过 hash 表来存储，value 是通过链表来存储。
HashMap 将 Entry 对象存储在一个数组中，并通过哈希表来实现对 Entry 的快速访问。（通过 key 的哈希值计算 Entry 在数组中的 index，以此访问 value） （拉链法，解决 hash 碰撞）

HashTable

几乎和 HashMap 一样，都是通过数组存储 Entry，以 key 的哈希值计算 Entry 在数组中的 index，用拉链法解决哈希冲突。二者最大的不同在于，Hashtable 是线程安全的，其提供的方法几乎都是同步的。

ConcurrentHashMap

ConcurrentHashMap 是 HashMap 的线程安全版，提供比 Hashtable 更高效的并发性能。

Hashtable 在进行读写操作时会锁住整个 Entry 数组，这就导致数据越多性能越差。
ConcurrentHashMap 使用分离锁的思路解决并发性能，其将 Entry 数组拆分至 16 个 Segment 中，以哈希算法决定 Entry 应该存储在哪个 Segment。这样就可以实现在写操作时只对一个 Segment 加锁，大幅提升了并发写的性能。
在进行读操作时，ConcurrentHashMap 在绝大部分情况下都不需要加锁，其 Entry 中的 value 是 volatile 的，这保证了 value 被修改时的线程可见性，无需加锁便能实现线程安全的读操作。
ConcurrentHashMap 它不能保证读操作的绝对一致性。ConcurrentHashMap 保证读操作能获取到已存在 Entry 的 value 的最新值，同时也能保证读操作可获取到已完成的写操作的内容，但如果写操作是在创建一个新的 Entry，那么在写操作没有完成时，读操作是有可能获取不到这个 Entry 的。

HashMap 和 HashTable,ConcurrentHashMap 的区别

• 三者在数据存储层面的机制原理基本一致
• HashMap 不是线程安全的
• Hashtable 是线程安全的，能保证绝对的数据一致性
• ConcurrentHashMap 也是线程安全的，使用分离锁和 volatile 等方法极大地提升了读写性能，同时也能保证在绝大部分情况下的数据一致性。但其不能保证绝对的数据一致性，在一个线程向 Map 中加入 Entry 的操作没有完全完成之前，其他线程有可能读不到新加入的 Entry
• HashTable 不允许使用 null 作为 key 和 value，如果放入 null 将引发 NullPointerException 异常，但 HashMap 可以使用 null 作为 key 或 value（只能有一个 key 为 null, 可以多个 value 为 null）。
• 如果在遍历的同时，修改 HashTable 的大小，容易应发异常。可以用代替，ConcurrentHashMap 是 HashMap 的线程安全版，提供比 Hashtable 更高效的并发性能

参考资料：
JAVA 集合框架中的常用集合及其特点、适用场景、实现原理简介
java 集合框架总结以及源码分析