java基础总结（面试高频问题）四：Hashtable,HashMap,ConcurrentHashMap底层原理及线程安全
1：HashMap原理概述：
假设存在一个数组，数组中每个元素都是一条链表。当要添加一个新元素（key-value）进入数组时，就要先根据key值计算hash值，以此确定要插入数组的位置。但是可能该位置已经存在相同hash值的其他元素，这就是哈希冲突，处理方法是把这一新元素添加到旧元素的后面，他们在数组的同一位置，但是形成了链表的存在形式。也就说数组中存放的是无数的链表，每一条链表的hash值都是相同的。而当链表长度超过阈值8的时候，链表就转为红黑树，这样大大提高了查找的效率；
JDK1.6和JDK1.7中，HashMap采用的是数组+链表的形式来处理哈希冲突，当同一hash值的元素过多时，通过key值依次查找的效率就降低了。在JDK1.8中，HashMap采用了数组+链表+红黑树的形式实现，当链表长度超过阈值8时，就将链表转换为红黑树，这样大大减少了查找时间；
2：不同key值为什么计算出的hash值相同：
举一个例子，如果学校要把学生的成绩存入数据库，需要保存的信息有姓名和成绩；我们把学生的姓名作为key值，通过hash算法把key值转换为hash值，这里就假设按照（学生姓名的拼音字母数长度）%（数组长度）来作为hash值，数组长度假设为10。可以发现，不同姓名的学生，其姓名拼音长度可能是一样的，那么计算出的hash值就是一样的，我们把hash值一样的学生成绩存放在数组的同一个位置下，这就形成了链表，通过遍历链表中元素的key值来找到要查询的学生的成绩即可。
详解可以看：https://www.zhihu.com/question/355013552
3：HashMap实现原理：
HashMap的主干是一个Entry数组，Entry数组是HashMap的基本组成单元，每一个Entry都包含一个key-value键值对；
其结构原理图如下：
结合原理图可以看出，HashMap是由数组+链表组成的，数组是HashMap的主体，链表是为了解决哈希冲突存在的。如果定位到数组的某个位置，发现不含链表（当前entry的next指向null），对于查找，添加等操作而言，是非常迅速的，仅需一次操作即可。如果定位到数组的某个位置，发现包含链表，对于添加操作，其时间复杂度为O（n），需要遍历链表，存在即覆盖，否则新增。对于查找操作，仍需遍历链表，并通过equals 方法逐一比对key值。根据这一规律可以看出，HashMap中出现的链表越少，其性能才能越好；
JDK1.8新加红黑树实现：
5：ConcurrentHashMap的实现原理：
（1）ConcurrentHashMap是从JDK1.5开始引入的，主要是为了解决HashMap线程不安全以及Hashtable效率不高的问题；众所周知，HashMap在多线程编程中是线程不安全的，而Hashtable由于使用了synchronized修饰方法而导致执行效率不高；因此，在concurrent包中，实现了ConcurrentHashMap以使在多线程编程中可以使用一个高性能的线程安全HashMap方案。
在JDK1.8之前，ConcurrentHashMap使用分段锁机制实现，JDK1.8中使用数组+链表+红黑树和CAS原子操作实现；
（2）分段锁机制及ConcurrentHashMap实现原理（JDK1.7）：
Hashtable之所以效率低下主要是因为其实现使用了synchronized关键字对put等操作进行加锁，而synchronized关键字加锁是对整个对象进行加锁，也就是说在进行put等修改Hash表的操作时，锁住了整个Hash表，从而使得其表现的效率低下；因此，在JDK1.5~1.7版本，Java使用了分段锁机制实现ConcurrentHashMap；
简而言之，ConcurrentHashMap在对象中保存了一个Segment数组，即将整个Hash表划分为多个分段；而每个Segment元素，即每个分段则类似于一个Hashtable；这样，在执行put操作时首先根据hash算法定位到元素属于哪个Segment，然后对该Segment加锁即可。因此，ConcurrentHashMap在多线程并发编程中可以实现多线程put操作。
我们用下面这一幅图来看下 ConcurrentHashMap 的内部结构,从下面的结构我们可以了解到，ConcurrentHashMap 定位一个元素的过程需要进行两次Hash操作，第一次 Hash 定位到 Segment，第二次 Hash 定位到元素所在的链表的头部，因此，这一种结构的带来的副作用是 Hash 的过程要比普通的 HashMap 要长，但是带来的好处是写操作的时候可以只对元素所在的 Segment 进行操作即可，不会影响到其他的 Segment，这样，在最理想的情况下，ConcurrentHashMap 可以最高同时支持 Segment 数量大小的写操作（刚好这些写操作都非常平均地分布在所有的 Segment上），所以，通过这一种结构，ConcurrentHashMap 的并发能力可以大大的提高。
（3）JDK1.8的ConcurrentHashMap实现：
在JDK1.8之前，ConcurrentHashMap是通过分段锁机制来实现的，所以其最大并发度受Segment的个数限制，虽然解决了并发问题，但是查询效率却不高。因此，在JDK1.8中，ConcurrentHashMap的实现原理摒弃了这种设计，而是选择了与HashMap类似的数组+链表+红黑树的方式实现，而加锁则采用CAS无锁机制实现；
CAS原理：
一般地，锁分为悲观锁和乐观锁：悲观锁认为对于同一个数据的并发操作，一定是为发生修改的，因此一定要通过加锁来确保线程的安全性；而乐观锁则认为对于同一个数据的并发操作是不会发生修改的，可以肆无忌惮的做事，认为发生线程安全问题的概率特别小；
因此，可以认为，加锁是一种悲观策略，无锁是一种乐观策略，无锁总是假设对共享资源的访问没有冲突，线程可以不停执行，无需加锁，无需等待，一旦发生冲突，无锁策略采用CAS技术来保证线程执行的安全性；
CAS（Compare And Swap，比较交换）：CAS有三个操作数，内存值V、期望值E、要修改的新值N，当且仅当期望值E和内存值V相等时才会将内存值V修改为新值N，否则什么都不做（CAS的循环时间长，开销大是一个缺点）。
这个原理可以理解为，当内存值V和期望值E相同时，证明内存值还未被其他线程修改，此时当前线程可以进行访问修改，于是将内存值V更新为新值N；如果内存值V和期望值E不同，则证明内存值V已经被其他线程修改，为了保证线程安全，不进行任何操作。接下来，可以选择重新读取期望值E，然后再次判断是否与内存值V相同（该过程可以多次循环），也可以放弃操作；
图解：
CAS总结：
CAS操作属于乐观派，它总认为自己可以成功完成操作，当多个线程同时使用CAS操作一个变量时，只有一个会胜出，并成功更新，其余均会失败，但失败的线程并不会被挂起，仅是被告知失败，并且允许再次尝试，当然也允许失败的线程放弃操作，这点从图中也可以看出来。基于这样的原理，CAS操作即使没有锁，同样知道其他线程对共享资源操作影响，并执行相应的处理措施。同时从这点也可以看出，由于无锁操作中没有锁的存在，因此不可能出现死锁的情况，也就是说无锁操作天生免疫死锁。
ConcurrentHashMap结构：
相对于JDK1.7，JDK1.8的ConcurrentHashMap结构简单很多，采用和HashMap一样的数据结构，数组+链表+红黑树实现；主干为Entry数组，每个数组位置对应一条链表，当链表长度超过阈值8时，升级为TreeBin类型的红黑树结构；另外，JDK1.8中的ConcurrentHashMap中还包含一个重要属性sizeCtl，其是一个控制标识符，不同的值代表不同的意思：其为0时，表示hash表还未初始化，而为正数时这个数值表示初始化或下一次扩容的大小，相当于一个阈值；即如果hash表的实际大小>=sizeCtl，则进行扩容，默认情况下其是当前ConcurrentHashMap容量的0.75倍；而如果sizeCtl为-1，表示正在进行初始化操作；而为-N时，则表示有N-1个线程正在进行扩容。
ConcurrentHashMap的初始化：
初始化包含三个参数，初始容量initialCapacity，加载因子loadFactor和预估并发度concurrencyLevel，通过这三个参数来计算table数组的初始大小以及sizeCtl的值；
在构造ConcurrentHashMap时，并不会对hash表（Node<K, V>[] table）进行初始化，hash表的初始化是在插入第一个元素时进行的。在put操作时，如果检测到table为空或其长度为0时，则会调用initTable()方法对table进行初始化操作；
initTable()方法使用一个循环实现table的初始化；在循环中，首先会判断sizeCtl的值，如果其小于0，则说明其正在进行初始化或扩容操作，则不执行任何操作，调用yield()方法使当前线程返回等待状态；而如果sizeCtl大于等于0，则使用CAS操作比较sizeCtl的值是否是-1，如果是-1则进行初始化。初始化时，如果sizeCtl的值为0，则创建默认容量的table；否则创建大小为sizeCtl的table；然后重置sizeCtl的值为0.75n，即当前table容量的0.75倍，并返回创建的table，此时初始化hash表完成。
链表和红黑树的转换：
首先，在table中添加一个元素时，如果添加元素的链表节点个数超过8，则会触发链表向红黑树结构转换。具体的实现方法如下：
该方法首先会检查hash表的大小是否大于等于MIN_TREEIFY_CAPACITY，默认值为64，如果小于该值，则表示不需要转化为红黑树结构，直接将hash表扩容即可；
如果当前table的长度大于64，则使用CAS获取指定的Node节点，然后对该节点通过synchronized加锁，由于只对一个Node节点加锁，因此该操作并不影响其他Node节点的操作，因此极大的提高了ConcurrentHashMap的并发效率。加锁之后，便是将这个Node节点所在的链表转换为TreeBin结构的红黑树；
然后，在table中删除元素时，如果元素所在的红黑树节点个数小于8，则会触发红黑树向链表结构转换。具体实现如下：
ConcurrentHashMap的get和put操作：
首先需要获取key值的hash值，在JDK1.8中，ConcurrentHashMap通过spread()方法获取hash值（这与HashMap和Hashtable不一样，他们计算hash值是调用的hashCode() 方法）；
spread()方法将key的hash值进行再hash，让hash值的高位也参与hash运算，从而减少哈希冲突，增加其散列度，然后再查询对应的value值。
4：面试提问点：
（1）HashMap基于Map接口实现，元素以键值对的方式存储，并且允许使用null 建和null值，因为key不允许重复，因此只能有一个键为null，另外HashMap不能保证放入元素的顺序，它是无序的，和放入的顺序并不能相同。HashMap是线程不安全的。
（2）public class HashMap<K,V>extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
HashMap继承自AbstractMap，实现了Map接口；
（3）HashMap和Hashtable的区别
<1>线程安全
两者最主要的区别在于Hashtable是线程安全，而HashMap则非线程安全。
Hashtable的实现方法里面都添加了synchronized关键字来确保线程同步，因此相对而言HashMap性能会高一些，我们平时使用时若无特殊需求建议使用HashMap，在多线程环境下若使用HashMap需要使用Collections.synchronizedMap()方法来获取一个线程安全的集合。
<2>针对null的不同
HashMap可以使用null作为key，而Hashtable则不允许null作为key
虽说HashMap支持null值作为key，不过建议还是尽量避免这样使用，因为一旦不小心使用了，若因此引发一些问题，排查起来很是费事。
注意：HashMap以null作为key时，总是存储在table数组的第一个节点上。table(0)；
<3>继承结构
HashMap是对Map接口的实现，HashTable实现了Map接口和Dictionary抽象类。
<4>初始容量与扩容
HashMap的初始容量为16，Hashtable初始容量为11，两者的填充因子默认都是0.75。
HashMap扩容时是当前容量翻倍即:capacity2，Hashtable扩容时是容量翻倍+1即:capacity2+1。
<5>两者计算hash（散列）的方法不同
Hashtable计算hash是直接使用key的hashcode对table数组的长度直接进行取模。
HashMap计算hash对key的hashcode进行了二次hash，以获得更好的散列值，然后对table数组长度取摸。
<6> ConcurrentHashMap 在 JAVA8 和 JAVA7 对比有哪些不同
JAVA7之前ConcurrentHashMap主要采用锁机制，在对某个Segment进行操作时，将该Segment锁定，不允许对其进行非查询操作，而在JAVA8之后采用CAS无锁算法，这种乐观操作在完成前进行判断，如果符合预期结果才给予执行，对并发操作提供良好的优化；
<7>ConcurrentHashMap中变量使用final和volatile修饰有什么用
使用final来实现不变模式，他是多线程安全里最简单的一种保障方式；使用volatile来保证某个变量在主内存的改变对其他线程即时可见，再配合CAS可以实现不加锁对并发操作的支持；
<8>HashTable与ConcurrentHashMap有什么区别
HashTable容器在竞争激烈的并发环境下表现出效率低下的原因，是因为所有访问HashTable的线程都必须竞争同一把锁，那假如容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效的提高并发访问效率，这就是ConcurrentHashMap所使用的锁分段技术；
（4）HashMap有4个构造器，其他构造器如果用户没有传入initialCapacity （容量）和loadFactor（负载因子）这两个参数，会使用默认值，initialCapacity默认为16，loadFactory默认为0.75。