04-Java集合框架

Java集合框架

Collection、Collections的区别

Collection

集合框架两大父接口是Map和Collection
Collection接口包含[Set、List、Queue](# List、Set、Map是区别)
- Set接口包含HashSet、TreeSet、LinkedHashSet
- List接口包含[ArrayList、LinkedList](# ArrayList、linkedList的区别)、Vector
- Queue接口包含Deque、ConcurrentLinkedQueue、BlockingQueue
Map接口包含[HashMap、Hashtable、ConcurrentHashMap](# HashMap、Hashtable、ConcurrentHashMap的区别)、TreeMap

Collections

Collections是集合框架提供的一个工具类，常用的方法就是排序sort()、洗牌shuffle()、翻转reverse()

List、Set、Map是区别

List有序可重复、可以用下标和迭代器进行遍历
Set无序不重复、只能使用迭代器进行遍历
Map保存的是键值对，键不重复值重复，只能使用迭代器进行遍历

ArrayList、linkedList的区别

ArrayList底层采用的是动态数组，所以查询快，增删慢，支持随机访问
LinkedList底层采用的是循环双向链表，所以增删快，查询慢；不支持随机访问，所以使用下标遍历损耗会更大，最好使用迭代器遍历

只有在数据量很大或者操作很频繁的情况下，两者差异才会很大

如果[容量固定](# ArrayList扩容机制)，并且只会向尾部添加元素，优先采用ArrayList，因为LinkedList还需要创建大量的节点，也会有比较大的性能损耗

ArrayList扩容机制

因为数组长度固定，所以在超出数组长度时，需要创建新数组，然后将旧数组中的数据拷贝到新数组

只有添加元素时才会引起扩容，如果不是向尾部添加元素，还会涉及到元素向后移的操作，Arraylist默认容量是10，之后数组扩容是按照，当前容量的1.5倍进行扩容，容量最大不能超过Integer的最大值

在移除元素的时候没有自动缩容机制，但是有手动缩容方法trimToSize()；手动缩容时也需要注意，如果在扩容和缩容边界上，频繁的添加和删除元素，就会导致一直触发扩容和缩容，性能会很受影响

HashMap、Hashtable、ConcurrentHashMap的区别

JDK1.7是数组+链表，JDK1.8是数组+链表+红黑树结构

当某个槽的元素大于等于8个节点时，就会转为红黑树，之所以将阈值设置为8，是因为红黑树的节点占用空间是链表的两倍，因为链表只有指向下一个节点的指针，而二叉树需要左右两个指针，当数据量并不大，红黑树性能优势并不大，作者进行了泊松分布的函数计算，得到想要哈希冲突达到8个的概率只有千万分之一，所以为了在这种极端情况下提高查询效率，就选择了8作为阈值

默认装载因子都是0.75，如果hash冲突太多，可以通过降低装载因子，空间换时间来降低hash冲突

HashMap

HashMap在JDK1.2才进行发布，可存储Null键Null值
HashMap继承的是AbstractMap，AbstractMap也实现了Map接口
HashMap的初始长度为 16，之后每次扩充变为2的n次方，之所以这样扩容，是因为位运算比模运算效率高，在取模操作中，如果模数是2的幂次，就等价于和该模数减一的与操作（hash % length == hash &(length - 1)）
HashMap是非线程安全的
- 多个线程同时put，哈希冲突时，就会导致先放入的数据被覆盖
- 多个线程同时扩容，就会导致后面扩容线程会覆盖掉前面线程扩容的结果；如果是JDK1.7，还可能会造成循环链表，导致死循环

Hashtable

Hashtable在JDK1.0发布，不可存储Null键Null值
Hashtable继承Dictionary，实现了map接口
Hashtable的初始长度是 11，之后每次扩充容量变为2n+1
Hashtable中大部分public方法都用synchronized修饰，是线程安全的

ConcurrentHashMap

ConcurrentHashMap在JDK1.6发布，不可存储Null键Null值
ConcurrentHashMap继承的是AbstractMap，AbstractMap也实现了Map接口
JDK1.7中采用分段锁机制实现
- 每个段上都是一个可扩容的HashMap，段与段之间独立上[ReentrantLock锁](# volatile、synchronized、ReentrantLock的区别)，提高了并发效率
- 默认有16个段，也就是说，最多可以同时有16个线程进行并发写操作，前提是分布在不同的段上
- 段的个数也可在初始化时设置，一旦设置就无法更改，因为是段是无法扩容的
JDK1.8中使用了和他同期的HashMap的数据结构，为了做到并发，采用锁住node，减小锁的粒度，从而提高并发度，利用[CAS算法](# CAS)部分的代替了锁

hash设计

hash函数设计

hash函数应该具有分布均匀、值等hash值也等、计算高效的特点

如果是整数就取模，得到的值永远不会超过模数，尽量模一个素数，可以减少哈希冲突
如果是浮点数，就将浮点数的二进制表示，使用整型方式进行解析得到整数，再通过取模方式
如果是字符串，将对应的字符转化成整数，使用进制计算换算成整数，再通过取模方式；如果字符串过长，进制的指数部分就会越大，计算就会越慢，可以通过数学方法，其转化成单个字符取模的方式

解决hash冲突

链地址法：数组中对应的位置存放成一个链表或者树
线性探测法：若当前位置已经有元素后，就从这个位置向后遍历
平方探测法：在线性探测法基础，每次向后遍历的步长，是上一次步长的两倍（步长依次加：1的平方、负1的平方、2的平方、-2的平方依次类推）
再哈希法：在线性探测法基础，每次向后遍历的步长，由第二个哈希函数计算得到

fail-fast和fail-safe的区别

快速失败机制（ArrayList）：一个线程通过集合迭代器进行遍历，同时集合的内容被其他线程所改变，那么遍历线程就会抛出ConcurrentModificationException异常，原理其实就是在遍历之前，把modCount记下来，存储为expectModCount，每次遍历元素都会使用expectModCount去和modCount进行比较，如果不相等了，证明已被修改了，然后就抛出ConcurrentModificationException异常

安全失败机制（CopyOnWriteArrayList）：一个线程通过集合迭代器进行遍历，其实是将容器拷贝一份，对副本进行的遍历，在遍历过程中所作的修改，在遍历结束后，会将容器的引用指向这个副本

安全失败机制相对与快速失败机制，虽然解决了多线程并发修改问题，但是却存在数据不能实时同步问题和内存占用打问题