Java集合

ArrayList和LinkedList的区别和底层实现？如何实现线程安全？

数据结构实现：ArrayList 是动态数组的数据结构实现，而 LinkedList 是双向链表的数据结构实现。
随机访问效率：ArrayList 比 LinkedList 在随机访问的时候效率要高，因为 LinkedList 是线性的数据存储方式，所以需要移动指针从前往后依次查找。
增加和删除效率：在非首尾的增加和删除操作，LinkedList 要比 ArrayList 效率要高，因为 ArrayList 增删操作要影响数组内的其他数据的下标。
内存空间占用：LinkedList 比 ArrayList 更占内存，因为 LinkedList 的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。
实现线程安全：ArrayList 不是线程安全的，如果遇到多线程场景，可以通过 Collections 的 synchronizedList 方法将其转换成线程安全的容器后再使用。

List遍历时如何删除元素？fail—fast是什么？fail—safe是什么？

fail-fast也就是快速失败，它是Java集合的一种错误检测机制。当多个线程对集合进行结构上的改变的操作时，有可能会产生fail-fast机制。例如：假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就会抛出 ConcurrentModificationException 异常，从而产生fail-fast机制。迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。只要是涉及了改变ArrayList元素的个数的方法都会导致modCount的改变。
在单线程环境下遍历时，可以使用迭代器的remove方法来删除元素，但不能使用集合的remove方法来删除。
多线程保证安全
读写均加锁，比如使用Collections.SynchronizedList
使用Fail-Safe集合，比如使用 CopyOnWriteArrayList
fail—safe安全失败，fail-safe任何对集合结构的修改都会在一个复制的集合上进行修改，因此不会抛出ConcurrentModificationException。任何对结构或内容的修改，过程都是：
加锁保证线程安全
复制底层数组，保证不影响读线程
写入
将底层数组回写覆盖原数组
解锁
虽然fail-safe不会抛出异常，但存在以下缺点
复制时需要额外的空间和时间上的开销。
不能保证遍历的是最新内容。

ArrayList扩容机制

默认构造函数的初始容量为10，为空数组。当执行add方法时，先执行ensureCapacityInternal(size + 1)得到minCapcity，(当 要 add 进第 1 个元素时，minCapacity 为 1，在 Math.max()方法比较后，minCapacity 为 10。), 然后执行ensureExplicitCapacity(int minCapacity)，minCapacity - elementData.length > 0成立，会进入 grow(minCapacity) 方法，先计算一个新容量newCapacity = oldCapacity + (oldCapacity >> 1)，所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右。 如果新容量大于MAX_ARRAY_SIZE,进入(执行) hugeCapacity() 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，如果 minCapacity 大于最大容量，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8。最后调用Arrays.copyOf(elementData, newCapacity)。得到新数组。

详细介绍HashMap。角度：数据结构+扩容情况+put查找的详细过程+哈希函数+容量为什么始终都是2^N+JDK1.7与JDK1.8的区别。

底层结构：在 JDK1.7 和 JDK1.8 中有所差别：
在 JDK1.7 中，由“数组+链表”组成，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的。
在 JDK1.8 中，由“数组+链表+红黑树”组成。当链表过长，则会严重影响 HashMap 的性能，红黑树搜索时间复杂度是 O(logn)，而链表是糟糕的 O(n)。因此，JDK1.8 对数据结构做了进一步的优化，引入了红黑树，链表和红黑树在达到一定条件会进行转换：当链表长度超过 8 且数据总量大于等于 64 才会转红黑树。将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树，以减少搜索时间。
put过程：
判断数组是否为空，为空进行初始化;
不为空，计算 k 的 hash 值，通过 (n - 1) & hash计算应当存放在数组中的下标 index ;
查看 table[index] 是否存在数据，没有数据就构造一个Node节点存放在 table[index] 中；
存在数据，说明发生了hash冲突, 继续判断key是否相等，相等，用新的value替换原数据(onlyIfAbsent为false)；
如果不相等，判断当前节点类型是不是树型节点，如果是树型节点，创建树型节点插入红黑树中；
如果不是树型节点，创建普通Node加入链表中；判断链表长度是否大于 8， 大于的话链表转换为红黑树；
插入完成之后判断当前节点数是否大于阈值，如果大于开始扩容为原数组的二倍。
Hash函数：先拿到通过key 的hashcode，是32位的int值，然后让hashcode的高16位和低16位进行异或操作。这么设计的原因是：当数组的长度很短时，只有低位数的hashcode值能参与运算。而让高16位参与运算可以更好的均匀散列，减少碰撞，进一步降低hash冲突的几率。并且使得高16位和低16位的信息都被保留了。而在这里采用异或运算而不采用& ，| 运算的原因是 异或运算能更好的保留各部分的特征，如果采用&运算计算出来的值的二进制会向1靠拢，采用|运算计算出来的值的二进制会向0靠拢。另外Java1.8相比1.7做了调整，1.7做了四次移位和四次异或，但明显Java 8觉得扰动做一次就够了，做4次的话，多了可能边际效用也不大，所谓为了效率考虑就改成一次了
扩容：
Hashmap 在容量超过负载因子所定义的容量之后，就会扩容。方法分为两步，创建一个新的Entry空数组，长度是原数组的2倍。transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。
1.7和1.8区别
数组+链表改成了数组+链表或红黑树；
链表的插入方式从头插法改成了尾插法
扩容的时候1.7需要对原数组中的元素进行重新hash定位在新数组的位置，1.8采用更简单的判断逻辑，只需要看看原来的 hash 值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引 + oldCap ”。这个设计非常的巧妙，省去了重新计算 hash 值的时间。

HashMap如何实现线程安全？ConcurrentHashMap的底层实现？JDK1.7与JDK1.8的区别

Collections.synchronizedMap、以及ConcurrentHashMap可以实现线程安全的Map。Collections.synchronizedMap是使用Collections集合工具的内部类，通过传入Map封装出一个SynchronizedMap对象，内部定义了一个对象锁，方法内通过对象锁实现。
底层结构：
JDK1.7 中的 ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成，即 ConcurrentHashMap 把哈希桶数组切分成小数组（Segment ），每个小数组有 n 个 HashEntry 组成。首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一段数据时，其他段的数据也能被其他线程访问，实现了真正的并发访问。Segment 继承了 ReentrantLock，所以 Segment 是一种可重入锁，扮演锁的角色。Segment 默认为 16，也就是并发度为 16。
存放元素的 HashEntry，也是一个静态内部类，用 volatile 修饰了 HashEntry 的数据 value 和 下一个节点 next，保证了多线程环境下数据获取时的可见性。
JDK1.8 中的ConcurrentHashMap 选择了与 HashMap 相同的Node数组+链表+红黑树结构；在锁的实现上，抛弃了原有的 Segment 分段锁，采用CAS + synchronized实现更加细粒度的锁。将锁的级别控制在了更细粒度的哈希桶数组元素级别，也就是说只需要锁住这个链表头节点（红黑树的根节点），就不会影响其他的哈希桶数组元素的读写，大大提高了并发度。
Put过程：
1.7：先根据hash定位到相应的 Segment ，然后再进行 put 操作。
首先会尝试获取锁，如果获取失败肯定就有其他线程存在竞争，则利用 scanAndLockForPut()自旋获取锁：尝试自旋获取锁。如果重试的次数达到了 MAX_SCAN_RETRIES 则改为阻塞锁获取，保证能获取成功。
1.8：根据 key 计算出 hash 值；如果是第一次put需要进行初始化；
根据定位到 Node，拿到首节点 f，判断首节点 f：
如果为 null ，则通过 CAS 的方式尝试添加；
如果为 f.hash = MOVED = -1 ，说明其他线程在扩容，参与一起扩容；
如果都不满足 ，synchronized 锁住 f 节点，判断是链表还是红黑树，遍历插入；
当在链表长度达到 8 的时候，数组扩容或者将链表转换为红黑树。
区别
数据结构：取消了 Segment 分段锁的数据结构，取而代之的是数组+链表+红黑树的结构。
保证线程安全机制：JDK1.7 采用 Segment 的分段锁机制实现线程安全，其中 Segment 继承自 ReentrantLock 。JDK1.8 采用CAS+synchronized保证线程安全。
锁的粒度：JDK1.7 是对需要进行数据操作的 Segment 加锁，JDK1.8 调整为对每个数组元素加锁（Node）。
链表转化为红黑树：定位节点的 hash 算法简化会带来弊端，hash 冲突加剧，因此在链表节点数量大于 8（且数据总量大于等于 64）时，会将链表转化为红黑树进行存储。
查询时间复杂度：从 JDK1.7的遍历链表O(n)， JDK1.8 变成遍历红黑树O(logN)。