JAVA面试汇总（三）集合（二）
JAVA面试汇总-集合部分，这部分其实比多线程有意思多了，这个计划四篇，这是第二篇，开卷。标题我就按照上一篇的继续，这样每次一部分总结完了，可以直接串起来来个长篇的。
6.HashMap的实现原理
(1)HashMap创建完毕默认是数组+链表的形式，具体如下图，根据key的不同的hash计算分配到数组不同的位置，如果已经有值则在链表的后边挂上一个新的节点，把value存储到该位置上。
image
(2)由于是通过hash计算，这样就会出现基本随机打散到数组的各个位置，一般来说应该平均，但是极端情况下可能都挂在数组的同一个位置下。
(3)内部节点实现是Node，分别存储了key，hash值，value，以及下一个Node，具体代码：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
(3)向HashMap中存储内容时，实际上先针对key值hash，得到具体的位置，然后到数据位置看是否已经存放了Node，通过key，value，hash值等创建一个Node，如果该位置还没有Node，则直接将新建的Node放到该数组位置；如果已经有了Node，也先通过key，value，hash值等创建一个Node，则向下查找，直到最后一个Node的next为null，将这个next为null的Node的next设置为新建的Node（说白了就是新建的Node要放在链表的尾部）。
(4)通过Key在hashMap中查找时，先把key值hash，找到具体位置，然后再链表上循环查找key值相同的（这个时候注意不是hash值，而是key值），找到后，返回Node的value。
(5)当存入的值过多时候，超过默认容量时候，会再次重新调整位置，创建一个大小为原来数据两倍大小的数据，然后循环原来数组的每个链表，将每个节点分配到新数组的新链表中去。
(6)jdk1.8有个改动，为了查找效率更高，当数组中的某个链表中节点超过8个时，会转换为红黑树。红黑树我后边会详细讲，主要是现在我也没明白。
7.ConcurrentHashMap的实现原理
（1）由于HashMap不是线程安全，主要是由于如果并发访问会造成扩容过程中的链表出现循环链，所以提出了线程安全的ConcurrentHashMap。
（2）在JDK1.7中，使用的是分段锁Segment，每一个segment都可以想象成是一个独立HashMap，这样每个线程请求过来，只能在自己独立的分段操作，互不影响，实现简单，但是这种耗费空间比较大。
（3）在JDK1.8中，放弃了分段锁，采用的是使用Synchronized和CAS来操作，CAS就是compare and swap的缩写，中文翻译成比较并交换。CAS具体步骤：首先从内存位置A取出值B，然后一系列计算后，得到了值C，如果这个时候内存位置的值仍然是B，则修改为C，如果在准备修改前已经变为了D，则修改失败，重新从内存位置A取出新值D，重新上述步骤，直到成功。说完了CAS，再来具体说ConcurrentHashMap如何通过CAS来修改：ConcurrentHashMap仍然是顶层是数组的模式，只是每次来修改，通过hash计算出要修改的数组位置后，将这个数组位置加锁，然后到这个数据的链表上修改，仍然是循环查找到next为null的，把新增的节点设置为next，如果这个链表上的个数超过8个，注意了，超过8个只是扩容（妈蛋，网上帖子都是8个就扩容，骗人的玩意儿），不是转变为红黑树，只有当超过64个时候才转换为红黑树，修改完毕后，释放锁。
8.HashTable实现原理
（1）Hashtable的默认容量为11，默认负载因子为0.75。
（2）不允许值和键为空（null），若为空，会抛空指针。
（3）基本方法都有synchronized关键字，线程安全，其实从个人理解，这个就是HashMap的线程安全版本，但是效率并不高。
（4）每次扩容，新容量为旧容量的2倍加1，而HashMap为旧容量的2倍。Hashtable默认容量为11，HashMap默认容量为16。
（5）根据hashcode计算索引时将hashcode值先与上0x7FFFFFFF,这是为了保证hash值始终为正数
9.HashMap和HashTable的区别
（1）父类不同，HashMap继承自AbstractMap类，而HashTable是继承自Dictionary类。
（2）Hashtable不允许值和键为空。HashMap中key和value可以为null。
（3）Hashtable基本方法都有synchronized关键字，线程安全；而HashMap没有，线程不安全。
（4）Hashtable默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。
（5）hash方法不同，Hashtable直接使用hashCode，然后与上0x7FFFFFFF，保持hash返回的值为正数，最后与数组长度取余；HashMap的key不为空时取hashCode再与 (hashCode >>> 16)异或得到位置。hashCode >>> 16实际上是hashCode无符号右移16位，就是把hashCode的二进制数字的前16位都干掉，保留剩下的得到的值。比如说十进制数字78897121，转换为二进制数字为0000 0100 1011 0011 1101 1111 1110 0001，>>> 16计算后得到了剩下的高16位，0000 0100 1011 0011，转换为十进制为1203。
//HashTable计算位置
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
//HashMap.hash(key)计算位置
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
10.HashMap与HashSet的区别
（1）HashSet的底层实现就是HashMap
（2）HashSet实现了Set接口，所以大家都懂，不允许重复的对象存储，只不过是通过HashMap作为存储实现的Set接口。HashSet是存储的对象（add(E e)），而HashMap是key，value的形式（put(K key, V value)）。
（3）效率上肯定是HashMap更快，因为HashSet存储得在HashMap的基础上在再存储。
