1.集合框架相关知识点

Java的集合框架是一个容器体系，它是Java数据结构的多种实现。

1.1 迭代器 Iterator接口

Iterator接口定义了遍历集合的一种方式，它提供了：

        - boolean hasNext( )：遍历指针后续是否还有元素，如有则返回true，没有返回false。
        - E next( )：返回下一个遍历的元素。
        - void remove( )：移除元素，不会发生异常。
1
2
3

1.2 ListIterator接口

List集合的专属迭代器，继承自Iterator接口。他的特点是可以向前和向后两个方向遍历集合，遍历的同时可以修改集合。

1.3 Collection和Map接口

Collection和Map一起组成了Java集合框架的两个根接口，定义了集合框架通用的一些方法和规则。Collection定义了单元素的集合定义，Map则是对键值对的抽象。

1.4 Collections工具类

Collections是集合框架提供的工具类，内部提供了很多静态方法来操作集合，例如集合的拷贝、排序、线程保证等等。

1.5 Arrays工具类

Arrays工具类是专门操作数组对象的工具类，和Collections工具类类似，他是对数组的一些便利性操作，例如排序、拷贝、转换等。

1.6 Fail-fast 和 Fail-safe

1.6.1 Fail-fast 快速失败

当对集合进行遍历时如果对集合进行了修改，例如增加、删除等操作，就会抛出Concurrent modification Exception。这是因为迭代器在遍历过程中使用一个modCount变量来标识集合的修改状态，一旦集合被修改，迭代器每次向后遍历都会检查这个modCount，不一致就会抛出异常。Java.util包下都是快速失败的策略，不适合多线程模式。

1.6.2 Fail-safe 安全失败

java.util.concurrent包下的集合框架属于安全失败策略，迭代时是对原集合的拷贝对象进行遍历，即便发生了修改也不会抛出异常。

2.java.util包下常见集合

Java集合框架很多底层的数据结构都用transient关键字修饰，是因为集合一般都有很多空闲的未使用的空间，如果采用原生的序列化手段没有必要，而且不同平台和系统的JVM对一些数组和哈希算法可能不一致导致一些问题。所以集合框架一般都自己实现了序列化和反序列化的方法。

3.HashMap

JDK7版本中的HashMap采用的是数组+链表采用头插法拉链形式组成，节点Entry。不过在JDK8版本后，HashMap有了重构，采用数组+链表+红黑树的组合完成。拉链法是为了解决hash冲突的设计，而红黑树的引入是为了提高查询效率，因为链表的查询时间复杂度是O(n)。

• 元素通过hash相应的hash算法映射到数组的某个下标，如果发现下标处有其它元素，说明发生了hash冲突，那么当前元素就挨个儿从这个下标的元素开始查找链表，在尾巴处插入。
• 如果链表的长度>8并且数组长度>=64，那么链表将会树化变成红黑树。
• 如果红黑树的节点数量少于6个，那么红黑树将转变为链表。
• 之所以使用红黑树不适用其他二叉树，是因为红黑树能够保持一定的相对平衡，时间复杂度比较稳定O(logn)，而二叉树不是很稳定，最坏的情况有可能是O(n)。
• 红黑树的平衡保证是通过旋转和染色来实现。

3.1 #hash( )和扰动函数

HashMap通过内部的hash( )方法得到key的hash值进而和数组长度进行与运算得到下标，这个hash( )是将key的hashCode和自己的低16位进行异或运算，得到新的一个hash值返回，这个行为称之为扰动函数。
扰动函数的目的是为了减少hash碰撞的产生，以数组长度16为例，如果没有扰动函数那么key的hashCode和数组长度进行与运算，高28位都是0，只有低4位，碰撞的概率会很大。引入了扰动函数，将key的hashCode和自己的低16位进行异或运算加大了随机性，降低了hash碰撞的概率。

3.2 HashMap的容量始终是2的倍数

即便是通过构造传入一个非2倍数的值，HashMap也会向上取整2的倍数作为数组长度。
1.方便hash的运算。
2.因为扩容后的大小是2的倍数，扩容时方便元素的转移。

3.3 链表树化的阈值定为8的原因

链表转需要链表的长度超过8，且数组的长度超过64。之所以定为8这个阈值，是因为在理想的情况下链表里面的节点符合泊松分布，Node节点数达到8的概率非常低。

3.4 红黑树转链表的阈值定位6的原因

如果定为8，因为8是树化的阈值，如果此时有新的节点加入，就会发生链表和红黑树的不断转换。定为6是错开这个阈值范围。

3.5 加载因子为什么是0.75？

加载因子的选择没有固定的数学算法支撑，0.75是一个经验值，是对时间和空间的一个权衡考虑。如果加载因子过低，会造成空位很大，且容易频繁扩容。如果过大，则hash冲突更加明显，对查找时间复杂度不友好。

3.6 HashMap的扩容resize

因为HashMap的数组容量是2的倍数，扩容也是2倍扩容，所以元素的移动也有规律。并不是通过新数组长度来进行位置的重定位，而是通过(e.hash & oldCap) == 0 来判断，如果==0，那么该节点在新数组中的位置和原数组一致，不过!=0，那么节点在新数组中的位置就是index+oldCap。

3.7 线程安全问题

     - JDK7的HashMap在并发环境+扩容下会出现链表形成环状，当下次get的时候就会发生死循环。
     - 并发put可能导致index相同的元素替换
1
2

3.8 线程安全的保障

     - HashTable
     - Collections.synchronizedMap(Map map )
     - ConcurrentHashMap
1
2
3

4.常见Map的比较

5.ConcurrentHashMap

在JDK1.7版本，ConcurrentHashMap采用的是分段锁机制保证线程安全，他持有一个Segment数组，Segment数组长度是16，每一个Segment就是一段，里面包含了若干个HashEntry。Segment基于ReentrantLock保证线程安全问题，通过分段锁优化了线程效率问题。

在JDK8版本中，ConcurrentHashMap进行了优化，废除了Segment的概念。使用CAS+synchronized的方式保证线程安全问题。ConcurrentHashMap和HashMap的数据结构一致，但是某些特性和HashMap不同，例如ConcurrentHashMap不支持null值和null键。

6.CopyOnWriteArrayList

线程安全的ArrayList结构的选择有3种：Vector、Collections.synchronizedCollection(Collection c)，最后一种就是写时复制容器。CopyOnWriteArrayList结构和ArrayList差不多，他是通过ReentrantLock保证线程安全，不过和ArrayList不同的是它的初始化和扩容不一样。
写时复制容器的扩容不是1.5倍，而是oldCap+1，因为写时复制容器本身设计定位就是读多写少的场景。它不支持指定容量的构造，但是支持传入一个数组或集合的形式。