Java集合类和通用数据结构的区别
Java集合类是从数据使用方式的角度，对复杂数据类型进行分类的
- List存储有序的单列数据，是纯数值集合，可以根据位置查找数据
- Set存储无序的单列数据，是纯数值集合，但是没有顺序和位置的概念
- Map存放双列数据集合，是键值対集合，每个数据包含关键字和实际值两列，可以通过关键字查对应值
通用数据结构则是从数据内存结构的角度，对复杂数据类型进行分类的
误区
大多时候，数据的使用方式，就已经决定了其底层采纳的内存结构
比如一想到List，就想到数组、链表，一想到Map，就想到哈希表
它们的关联性太强了，以至于没经过系统学习的，经常将它们混为一谈
但当我们系统学习完全部的集合类和数据结构后，就会发现
其实一种集合类，底层可能通过不同的数据结构都可以实现，但是效率和特性是不一样的
也有的集合类，是由多种数据结构一起组合来实现的
集合类，更像是一种封装给开发者使用的高级数据结构
而我们学习的通用数据结构，则是一种跨语言的，通用的底层数据结构
当然，在平时工作中，我们用到的大多时候可能就是最简单的ArrayList和HashMap
我们就简单地把集合类说成数据结构也无妨
Java常用集合类
这里是一份Java集合类的大纲总结图
大家可以点击拖拽查看大图，也可以看下面的文字说明
至于每种数据结构到底是什么样的，每种集合类的实现代码是怎么样的
每一点都足够写成一篇博客了，我们后面再逐个讲解，本篇博客只是一篇总结索引
但是对于只想了解Java常用集合类特性的同学来说，已经足够了，毕竟不是所有人都愿意撸一遍源码
Collection和Map接口
Collection用于存放单列数据
Map用于存放双列数据，一列是关键字，一列是实际值，可通过关键字查找实际值
List和Set
List元素存放有顺序，相同数据可以存放多份，可以按位置访问数据
Set元素存放无顺序，相同数据会被覆盖，无法按位置访问数据
List子类特性比较
List子类常见的有ArrayList、LinkedList、Vector
- ArrayList底层通过动态数组来实现List功能 当数组长度不够时，就再新建一个1.5倍长度的新数组来存储数据
ArrayList读取效率较高，但插入删除效率不高 - LinkedList底层通过双向链表来实现List功能 维护成本稍微大一些，但插入删除效率更高 由于双向链表更加灵活，所以方便做其它操作
比如查找上一个，查找下一个，移除首尾元素等 - ArrayList和LinkedList都不是线程安全的 Vector所有操作都做了同步锁处理，因此是线程安全的
Vector和ArrayList一样，底层是通过动态数组实现的 所以Vector可以被视为SynchronizedArrayList
Set子类特性比较
Set集合都是通过Map来实现的，因为Map的键是唯一的，和Set值唯一性的特征正好吻合
所以对Map做一下简单的包装，Map的Value为null时，就可以把EntryKey当Set来使用了
Set常见子类有HashSet、LinkedHashSet、TreeSet
- HashSet底层是通过HashMap实现的，数据是无序的
- LinkedHashSet底层是通过LinkedHashMap实现的，数据是有序的，按插入顺序排序
- TreeSet底层是通过TreeMap实现的，数据是有序的，按对象大小排序，对象必须实现Comparable接口
Set我们不细讲，后面讲完Map后，自然就知道Set怎么一回事了
Map子类特性比较
Set常见子类有HashMap、LinkedHashMap、TreeMap、HashTable、Properties
- HashMap底层是通过哈希表（数组+链表）实现的，因此是无序的
- LinkedHashMap在HashMap的基础上，通过双向链表将所有Entry连接起来，这样就实现了按插入排序的功能
- TreeMap底层是通过红黑树实现的，是有序的
TreeMap默认是按Key的大小进行排序的，Key必须实现Comparable接口，或是在构造方法中指定Comparator - HashTable和HashMap功能几乎完全一样，底层是通过哈希表（数组+链表）实现的
HashTable主要是做了线程安全处理，所有操作都加了同步锁，可以被视为SynchronizedHashMap
另外，HashTable的Key和Value都不能为null，HashTable继承自Dictionary，而HashMap继承自AbstractMap - Properties是JDK中专门用来保存属性和配置的一个数据结构类
容器的线程安全
- Vector和HashTable虽然能保证线程安全，但是对全部数据进行加锁的，会导致其它线程阻塞等待，因此效率很低
- 通过Collections.synchronizedList和Collections.synchronizedMap，可以将普通的list/map转换为线程安全的list/map
这两个方法的实质，是创建了一个新的list/map，用它包裹旧的list/map
新的容器在执行函数时，会调用旧容器的相同函数来处理，只是加了一层同步锁，实际工作的还是旧的容器
通过这种方式转换出来的新容器，使用的是最粗暴的同步策略，所以效率也很低 - Vector和HashTable虽然能保证线程安全，但是对全部数据进行加锁的，会导致其它线程阻塞等待，因此效率很低
- java.util.concurrent包提供了几个高性能的同步容器
比较有代表性的是CopyOnWriteArrayList和ConcurrentHashMap，它们代表了实现容器线程安全的两种典型策略 - CopyOnWrite采用的是一种读写分离的策略 写操作不直接写入原数组，而是拷贝一个数组，在新数组上进行修改
- CopyOnWriteArrayList写数据的流程是：加锁 > 创建newArray > 将array的数据拷贝到newArray > 向newArray中写入数据改动 > 将newArray赋值给array > 解锁
由于写操作是在拷贝的新数组上进行的，所以并不影响其它线程读操作的安全性，因此读操作不用加锁
由于读的次数一般要比写的次数多，因此对效率还是有明显提升的 - ConcurrentHashMap采用的是一种分块上锁的策略 只对部分数据进行加锁，而不是全部数据进行加锁
- ConcurrentHashMap将所有的Entry数据，划分为若干个Segment
当对Entry进行读写时，只需要对其所在的Segment加锁就行了，其它线程只有正好访问该Segment数据，才需要等待锁资源
这样产生锁等待的几率就大幅减小了，因此可以明显提升效率
