Map

title: Map

一、反射和new的区别

1.反射和new都是创建对象实例的，但是new对象无法调用该类里面私有private的属性，而反射可以调用类中private的属性！

2.new属于静态编译。就是在编译的时候把所有的模块都确定，如果有添加或删除某些功能，需要重新编译。但系统不可能一次就把把它设计得很完美，当发现需要更新某些功能时，采用静态编译的话，需要把整个程序重新编译一次才可以实现功能的更新。也就是说，用户需要把以前的软件卸载了，再重新安装才会重新编译！这样的系统耦合严重，难以扩展！

3.反射属于动态编译。在运行时确定类型并创建对象，通过反射指定模板，动态的向模板中传入要实例化的对象。动态编译最大限度发挥了Java的灵活性，体现了多态的应用，有以降低类之间的藕合性。其中spring中ioc的核心就是利用了反射解耦合。

springIOC容器为什么用反射创建对象？

IOC容器的工作模式看做是工厂模式的升华，可以把IOC容器看作是一个工厂，这个工厂里要生产的对象都在配置文件中给出定义，然后利用编程语言提供的反射机制，根据配置文件中给出的类名生成相应的对象。从实现来看，IOC是把以前在工厂方法里写死的对象生成代码，改变为由配置文件来定义，也就是把工厂和对象生成这两者独立分隔开来，目的就是提高灵活性和可维护性。

二、Map

1.Map集合的选择问题

hashMap:读取快，插入慢,线程不安全

LinkedHashMap:读取快，插入慢

HashMap和双向链表合二为一即是LinkedHashMap。所谓LinkedHashMap，其落脚点在HashMap，由于LinkedHashMap是HashMap的子类，所以LinkedHashMap自然会拥有HashMap的所有特性。比如，LinkedHashMap的元素存取过程基本与HashMap基本类似，只是在细节实现上稍有不同。当然，这是由LinkedHashMap本身的特性所决定的，因为它额外维护了一个双向链表用于保持迭代顺序。

链接:https://www.jianshu.com/p/cb3573eb1890

treeMap:排序

concurrentHashMap:线程安全，支持高并发的操作

(1) JDK1.7 的ConcurrentHashMap

在JDK1.7中ConcurrentHashMap采用了数组+Segment+分段锁的方式实现。

• Segment(分段锁)：ConcurrentHashMap中的分段锁称为Segment，它即类似于HashMap的结构，即内部拥有一个Entry数组，数组中的每个元素又是一个链表,同时又是一个ReentrantLock（Segment继承了ReentrantLock）。

• 内部结构：
  ConcurrentHashMap使用分段锁技术，将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问。如下图是ConcurrentHashMap的内部结构图：
  

从上面的结构我们可以了解到，ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作。第一次Hash定位到Segment，第二次Hash定位到元素所在的链表的头部。

2 JDK1.8之后的ConcurrentHashMap

JDK8中ConcurrentHashMap参考了JDK8 HashMap的实现，采用了数组+链表+红黑树的实现方式来设计，内部大量采用CAS操作。并发控制使⽤synchronized 和 CAS 来操作。（JDK1.6 以后 对 synchronized 锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；

JDK1.8的Node节点中value和next都用volatile修饰，保证并发的可见性。

1.volatile关键字是防止在共享的空间发生读取的错误。只保证其可见性，不保证原子性；使用volatile指每次从内存中读取数据，而不是从编译器优化后的缓存中读取数据，简单来讲就是防止编译器优化。

2.volital和synchronized的区别

volatile仅能使用在变量上，synchronized可以使用在变量和方法上；

volatile仅能实现变量的可见性，不能保证原子性，synchronized可以保证变量的可见性和原子性；

volatile不会造成线程阻塞，synchronized可能会造成线程阻塞（因为volatile只是将当前变量的值及时告知所有线程，而synchronized是锁定当前变量不让其它线程访问）；

volatile标记的变量不会被编译器优化（因为不能指令重排），synchronized标记的变量可以被编译器优化；

volatile修饰变量适合于一写多读的并发场景，而多写场景一定会产生线程安全问题（因此使用volatile而不是synchronized的唯一安全情况是类中只有一个可变的域）。

因为所有的操作都需要同步给内存变量，所以volatile一定会使线程的执行速度变慢。

可以理解为，synchronized 只锁定当前链表或红⿊⼆叉树的⾸节点，这样只要 hash 不冲突，就不会产⽣并发，效率⼜提升 N 倍。

3 ConcurrentHashMap和HashTable的区别

Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采⽤ 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突⽽存在的；

Hashtable(同⼀把锁) :使⽤ synchronized 来保证线程安全，效率⾮常低下。当⼀个线程访问同步⽅法时，其他线程也访问同步⽅法，可能会进⼊阻塞或轮询状态，如使⽤ put 添加元素，另⼀个线程不能使⽤ put 添加元素，也不能使⽤get，竞争会越来越激烈效率越低；

ConcurrentHashMap不论1.7还是1.8，他的执行效率都比HashTable要高的多，主要原因还是因为Hash Table使用了一种全表加锁的方式。

要避免 HashMap 的线程安全问题，有多个解决方法，比如改用 HashTable 或者 Collections.synchronizedMap() 方法。

但是这两者都有一个问题，就是性能，无论读还是写，他们两个都会给整个集合加锁，导致同一时间的其他操作阻塞。

ConcurrentHashMap 的优势在于兼顾性能和线程安全，一个线程进行写操作时，它会锁住一小部分，其他部分的读写不受影响，其他线程访问没上锁的地方不会被阻塞。

当项目中的全局变量有多线程操作时需要用concurrentHashMap,若只是单线程则可以使用hashmap。

在多线程环境下使用hashMap会造成的问题:

hashMap,底层是数组+链表 结构，当两个线程同时插入需要扩容的时候，获得改map的size()大小不一样，则会报错。当有两个线程在读，第三个线程正好在对map扩容时，这两个线程就会进入死循环，cup占用率就会高。

concurrentHashMap,线程安全，读写快，底层实现是一种以空间换时间的结构，创建的时候直接分了16个segment，每个segment实际上存储的还是哈希表，写入的时候先找到对应的segment，然后对segment加锁，写完，解锁。锁segment的时候其他segment还可以继续工作。

2.HashMap

2.1 扩容操作（JDK8HashMap）

数组：初始容量为16（2^4），初始负载因子为0.75，即当存储元素个数超过threshold（当前容量）*0.75（负载因子）时会进行扩容，每次扩容后容量为之前得2倍。

链表：使用哈希函数计算存储位置后，如果数组中该位置已经被使用，那么就会在该位置处添加链表，链表的最大容量为8，如果超过8，就会转换为红黑树来存储。
红黑树：使用红黑树的查询效率高于普通链表，因为使用红黑树相当于二分查找，二分查找的效率要高于顺序查找，并且红黑树会自动保持平衡，从而进一步保证查询效率。当红黑树结点减少到6时，会转换回链表。

2.2 hashmap的put,get实现原理

注意：当添加元素时会进行扩容，同理，减少元素时也会进行减少容量的操作。所以，Map集合会在增加、减少等修改Map集合时对整体结构进行维护（修改内部结构和容量）。

为什么默认值都为2^n?
为了减少碰撞，源码中计算索引位置为了效率考虑使用的是按位与操作（&），并不是直接取余，所以2的幂的效率相比于其他更高。
扩容时为二倍，因为当扩容完成后会将键值对全部移入新的Map中（所以扩容是耗时操作），而直接扩容为原来的二倍能更有效的是之前的元素均匀的分部在新的Map中（散列均匀，减少哈希冲突）。

哈希表其实就是一个存放哈希值的一个数组，哈希值是通过哈希函数计算出来的，那么哈希冲突就是两个不同值的东西，通过哈希函数计算出来的哈希值相同，这样他们存在数组中的时候就会发生冲突，这就是哈希冲突。就像是高铁座位，一般是一人一座的，但是突然系统可能出了问题，两个人可能买到了同一个座位的票，那么这时候就发生了冲突。

2.3其他的几个问题

(1) 为什么大于8之后会变成红黑树？

理想情况下，在随机哈希代码下，桶中的节点频率遵循
泊松分布，文中给出了桶长度k的频率表。
由频率表可以看出，桶的长度超过8的概率非常非常小。所以作者应该是根据
概率统计而选择了8作为阀值。

(2) 那么为什么要把链表变成红黑二叉树呢?

因为红黑二叉树的时间复杂度底，红黑树查找事件复杂度为O(logn)，链表为O(n),检索效率要高于链表，当链表长度大于8的时候使用红黑二叉树检索效率高。

（3）为什么会有链表会达到阈值将结构修改为红黑树，而不是直接为红黑树？

红黑树结点基本上为链表结点大小的两倍，所以在存储元素较少时，不宜使用较多的存储空间。

（4）为什么会在红黑树结点数量为6的时候转换回链表，而不是和链表转换为红黑树时一样为8？

避免在阈值附近增加删除元素而引起频繁的链表和红黑树的转换。

（5）JDK8之前存在的多线程情况下的死循环问题？

JDK 1.7 扩容采用的是“头插法”，会导致同一索引位置的节点在扩容后顺序反掉。而 JDK 1.8 之后采用的是“尾插法”，扩容后节点顺序不会反掉，不存在死循环问题。

https://blog.csdn.net/zzzgd_666/article/details/120988963

（6）JDK8对Map的优化。

底层数据结构从“数组+链表”改成“数组+链表+红黑树”；
计算 table （底层数组）初始容量的方式发生了改变；
优化了 hash 值的计算方式，新的计算方式是让高16位参与了运算；
扩容时插入方式从“头插法”改成“尾插法”，避免了并发下的死循环；
扩容时计算节点在新表的索引位置方式从“h & (length-1)”改成“hash & oldCap”。