Java容器部分下（重要）
21.ArrayList Vector LinkedList的区别?
这三者都是实现集合框架中的List,也就是所谓的有序集合,因此具体功能也比较类似,比如都提供按照位置进行定位 添加或者删除的操作,都提供迭代器以遍历其内容等。但因为具体的设计区别 在行为 性能 线程安全等方面,表现又有很大不同。
Vector是Java早期提供的线程安全的动态数组,如果不需要线程安全,并不建议选择,毕竟同步是有额外开销的。Vector内部是使用对象数组来保存数据,可以根据需要自动的增加容量,当数组以满时,会创建新的数组,并拷贝原有数组数据。
ArrayList是应用更加广泛的动态数组实现,它本身不是线程安全的,所以性能要好很多。与Vector近似,ArrayList也是可以根据需要调整容量,不过两者的调整逻辑有所区别,Vector在扩容时会提高1倍,而ArrayList则是增加50%。
LinkedList顾明思议是Java提供的双向链表,所以它不需要像上面两种那样调整容量,它也不是线程安全的。
Vector和ArrayList作为动态数组,其内部元素以数组形式顺序存储的,所以非常适合随即访问的场合。除了尾部出入元素和删除元素,往往性能会相对较差,比如我们在中间位置插入一个元素,需要移动后续所有元素。而LinkedList进行节点插入 删除却要高效得很多,但是随即访问性能则要比动态数组慢。
22.如何保证集合是线程安全的? ConcurrentHashMap 如何实现高效的线程安全?
Java提供了不同层面的线程安全支持。在传统集合框架内部,除了Hashtable Vector等同步容器,还提供了同步包装器,我们可以调用Collections工具类提供的包装方法,来获取一个同步的包装容器(例如Collections.synchronizedMap),但是它们都是利用非常粗粒度的同步方式,在高并发情况下,性能比较底下,另外,更加普遍的选择是利用并发包提供的线程安全容器类。具体保证线程安全的方式,包括有从简单的synchronize方式,到基于更加精细化的,比如基于分离式锁实现的ConcurrentHashMap等并发实现等。具体选择要看开发的场景需求,总体来说,并发包内提供的容器通用场景,远优于早期的简单同步实现。
23.为什么需要ConcurrentHashMap?
Hashtable本身比较低效,因为它的实现基本就是put get size等各种方法加上"synchronized"。简单来说,这就导致了所有并发操作都要竞争同一把锁,一个线程在进行同步操作时,其他线程只能等待,大大降低了并发操作的效率。前面说过HashMap不是线程安全的,那么能不能利用Collections提供的同步包装器来解决问题?实际上同步器只是利用输入Map构造了另一个同步版本,所有操作不再声明为synchronized方法,但是还是利用了"this"作为互斥的mutex,没有真正意义上的改进。
所以,Hashtable或者同步包装版本,都只是适合在非高度并发的场景下。
24.HashMap中hash函数怎么是是实现的?
我们可以看到在hashmap中要找到某个元素，需要根据key的hash值来求得对应数组中的位置。
如何计算这个位置就是hash算法？
前面说过hashmap的数据结构是数组和链表的结合，所以我们当然希望这个hashmap里面的元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个,这样当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表。
所以我们首先想到的就是把hashcode对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。
但是，“模”运算的消耗还是比较大的，能不能找一种更快速，消耗更小的方式，我们来看看JDK1.8的源码是怎么做的（被楼主修饰了一下）
简单来说就是
1、高16bt不变，低16bit和高16bit做了一个异或(得到的HASHCODE转化为32位的二进制，前16位和后16位低16bit和高16bit做了一个异或)
2、(n·1)&hash=->得到下标
25.拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？
之所以选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢。
而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题。我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少
所以当长度大于8的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。
26.说说你对红黑树的见解？
1、每个节点非红即黑
2、根节点总是黑色的
3、如果节点是红色的，则它的子节点必须是黑色的（反之不一定）
4、每个叶子节点都是黑色的空节点（NIL节点）
5、从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）
27.hashMap解决hash 碰撞还有那些办法？
使用开放定址法。
当冲突发生时，使用某种探查技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找，直到找到给定的地址。
按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、二次探查法、双重散列法等。
下面给一个线性探查法的例子
问题：已知一组关键字为(26，36，41，38，44，15，68，12，06，51)，用除余法构造散列函数，用线性探查法解决冲突构造这组关键字的散列表。
解答：为了减少冲突，通常令装填因子α由除余法因子是13的散列函数计算出的上述关键字序列的散列地址为(0，10，2，12，5，2，3，12，6，12)。前5个关键字插入时，其相应的地址均为开放地址，故将它们直接插入T[0]，T[10)，T[2]，T[12]和T[5]中。当插入第6个关键字15时，其散列地址2(即h(15)=15％13=2)已被关键字41(15和41互为同义词)占用。故探查h1=(2+1)％13=3，此地址开放，所以将15放入T[3]中。当插入第7个关键字68时，其散列地址3已被非同义词15先占用，故将其插入到T[4]中。当插入第8个关键字12时，散列地址12已被同义词38占用，故探查hl=(12+1)％13=0，而T[0]亦被26占用，再探查h2=(12+2)％13=1，此地址开放，可将12插入其中。类似地，第9个关键字06直接插入T[6]中；而最后一个关键字51插人时，因探查的地址12，0，1，…，6均非空，故51插入T[7]中。
28.如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？
默认的负载因子大小为0.75
也就是说，当一个map填满了75%的bucket时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组来重新调整map的大小，并将原来的对象放入新的bucket数组中。
这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置。这个值只可能在两个地方，一个是原下标的位置，另一种是在下标为<原下标+原容量>的位置
29.重新调整HashMap大小存在什么问题吗？
当重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。
在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部
这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。(多线程的环境下不使用HashMap）
30.关于ConcurrentHashMap工作机制（拓展部分）
在早期的ConcurrentHashMap,其实现是基于分离锁,也就是将内部进行分段,里面则是HashEntry的数据。和HashMap类似,哈希相同的条目也是以链表形式存放。(简单点来说,就是在ConcurrentHashMap中,把Map分成了N个Segment,put和get的时候,都是现根据key.hashCode()算出放到哪个Segment中)
在构造的时候,Segment的数量由所谓的concurrentcyLevel来决定,默认是16,也可以在相应构造函数直接指定。注意,Java需要它是2的幂数值,如果输入是类似15这种非幂值,会自动调整到16之类2的幂数值。
看如下的测试代码:
import java.util.concurrent.ConcurrentHashMap;
public class ConcurrentHashMapTest {
private static ConcurrentHashMap<Integer, Integer> map = new ConcurrentHashMap<Integer, Integer>();
public static void main(String[] args) {
new Thread("Thread1"){
@Override
public void run() {
map.put(3, 33);
}
};
new Thread("Thread2"){
@Override
public void run() {
map.put(4, 44);
}
};
new Thread("Thread3"){
@Override
public void run() {
map.put(7, 77);
}
};
System.out.println(map);
}
}
我们创建了3个线程分别向ConcurrentHashMap中添加数据,根据ConcurrentHashMap.segmentFor的算法，当我们向ConcurrentHashMap中put key为3或者4的数据时,此时他们对应的Segment都是segments[1]，而put key为7对应的数据时,此时对应的Segment是segments[12]。那么当线程1在put(3,33)时,线程2也想put(4,44)时,因为线程1和线程2操作的都是同一个Segment,线程1会首先获取到锁,可以进入,线程2则会阻塞在锁上。线程3在put数据时,他对应的segments是12,他不会上锁。 以上就是ConcurrentHashMap的工作机制，通过把整个Map分为N个Segment（类似HashTable），可以提供相同的线程安全，但是效率提升N倍，默认提升16倍。
