1.Map的存储特点 在Map这个结构中，数据是以键值对（key-value）的形式进行存储的，每一个存储进map的数据都是一一对应的。 创建一个Map结构可以使用new HashMap()以及new TreeMap()两种方式，两者之间的区别是：TreeMap是支持 排序的。 2.HashMap的底层存储方式

 

总结: 1. 用hashMap存储数据(key,value)的时候使用put方法 2. put方法会调用putVal方法,把hash(hey)和当前的key，value作为参数传进来 3. 判断数组是否为空，即判断是否是第一次添加数据,如果是的话，会先调用resize方法扩容 4. 之后,根据当前key的hash值找到它在数组中的下标 (怎么算的? index = (n - 1) & hash)，判断当前下标位置是 否已经存在元素 5. 如果不存在，直接把key、value包装成Node节点作为链表头存入数组 6. 如果存在，分为三种情况 1. ）比较一下已有数据和存入数据 如果hash值等于传过来的hash，并且他们的key值也相等 最后会把 value的值覆盖处理 2. ）上一步不相等，就判断一下当前是不是红黑树结构，是则调用putTreeVal()把它加入到红黑树 3. ）既不相等，也不是红黑树结构，说明是普通链表结构，遍历这个链表，将数据存到链表尾部 1. 在遍历过程中，如果是最后一个节点，则插入新节点 newNode(hash, key, value, null) 2. 如果链表长度超过了8，则转化为红黑树 treeifyBin(tab, hash)3. 如果遍历的时候遇到了相同的key 把value的值覆盖处理 7. 如果当前数组中的元素个数超过阈值，则扩容 resize(); 8. putVal（）方法 没修改value就返回NULL 修改了就返回旧值（之前的value） 3.什么是hash碰撞 Hash Collision 就是我们说的 Hash 碰撞或者 Hash 冲突。 这个其实也非常好理解，就是 2 个输入不同的数据，经过 Hash 算法后，得到的 Hash 值是一样的。 在HashMap的查询和添加过程中，绕不过去的是计算元素在数组的位置index，key的HashCode作为这个计算的 基础。计算后的Hash值存在相同的情况，hash与长度取余的结果也有相同的情况，这个时候运算结果相同的两个 对象就需要存储到同一个链表中，这就是HashMap中的Hash碰撞。 4.如何解决hash碰撞 1.开放地址方法 1）线性探测 按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上往后加一个单位，直至不发生哈希冲突。 就是在 此空间不足时，直接放入此空间的后一个空的空间 2）再平方探测 按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上先加1的平方个单位，若仍然存在则减1的平方个 单位。随之是2的平方，3的平方等等。直至不发生哈希冲突。 要注意平方不能超过容量的值 Size=16的时候，找备 选的单元只能取i=1,2,3，也就是距离冲突单元1,4,9个单位的位置了。 3）伪随机探测 按顺序决定值时，如果某数据已经存在，通过随机函数随机生成一个数，在原来值的基础上加上随机数，直至不发 生哈希冲突。 2.链式地址法（HashMap的哈希冲突解决方法） 对于相同的值，使用链表进行连接。使用数组存储每一个链表。 就是hashmap的底层原理 ：数组+链表 就是没有 红黑树 补充：在JDK1.8中HashMap通过链式寻址法以其红黑树来解决哈希冲突的，其中红黑树是为了优化哈希表的链表 过长 导致遍历时间复杂度增加的问题。当链表长度大于8并且哈希表的容量大于64,再向链表中添加元素,会转化为 红黑树。优点： 1）拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较 2） 由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况； （ 3）开放定址法为 减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉 链法中增加的指针域可忽略不计，因此节省空间； （ 4）在用拉链法构造的散列表中，删除结点的操作易于实现。 只要简单地删去链表上相应的结点即可。 缺点： 1） 指针占用较大空间时，会造成空间浪费，若空间用于增大散列表规模进而提高开放地址法的效率。 3.建立公共溢出区 建立公共溢出区存储所有哈希冲突的数据 4.再哈希法 对于冲突的哈希值再次进行哈希处理，直至没有哈希冲突。 5.如何解决并发 HashMap的线程不安全主要体现在下面两个方面： 1.在JDK1.7中，当并发执行扩容操作时会造成环形链和数据丢失的情况。 2.在JDK1.8中，在并发执行put操作时会 发生数据覆盖的情况。 1、if((p = tab[i =(n -1)& hash])==null)// 1、此处线程不安全——用来判定索引位置是否 hash碰撞，比如两个线程A、B都在进行put操作，并且hash函数计算出的插入下标是相同的，当线程A执行完第六 行代码后由于时间片耗尽导致被挂起，而线程B得到时间片后在该下标处插入了元素，完成了正常的插入，然后线 程A获得时间片，由于之前已经进行了hash碰撞的判断，所有此时不会再进行判断，而是直接进行插入，这就导致 了线程B插入的数据被线程A覆盖了，从而线程不安全。 2、if (++size > threshold)中的++size：同样还是线程A、B，这两个线程同时进行put操作时，假设当前HashMap 的zise大小为10，当线程A执行到此行代码时，从主内存中获得size的值为10后准备进行+1操作，但是由于时间片 耗尽只好让出CPU，线程B快乐的拿到CPU还是从主内存中拿到size的值10进行+1操作，完成了put操作并将 size=11写回主内存，然后线程A再次拿到CPU并继续执行(此时size的值仍为10)，当执行完put操作后，还是将 size=11写回内存，此时线程A、B都执行了一次put操作，但是size的值只增加了1，所有说还是由于数据覆盖又导 致了线程不安全。 解决方法： 1.Hashtable HashTable为了实现多线程安全，在几乎所有的方法上都加上了synchronized锁（锁的是类的实例,也就是整个 map结构），当一个线程访 问 Hashtable 的同步方法时，其他线程如果也要访问同步方法，会被阻塞住。 2.Collections.synchronizedMap(一般不用) 缺点:从锁的角度来看，基本上是锁住了尽可能大的代码块.性能会比较 差 3.ConcurrentHashMap（常用） JDK 1.7 中，采用分段锁的机制，实现并发的更新操作，底层采用数组+链表的 存储结构，包括两个核心静态内部类 Segment 和 HashEntry。 ①、Segment 继承 ReentrantLock（重入锁） 用 来充当锁的角色，每个 Segment 对象守护每个散列映射表的若干个桶； ②、HashEntry 用来封装映射表的键-值 对； ③、每个桶是由若干个 HashEntry 对象链接起来的链表 分段锁：Segment数组中，一个Segment对象就是一 把锁,对应一个HashEntry数组,该数组中的数据同步依赖于同一把锁,不同HashEntry数组的读写互不干扰 JDK 1.8中抛弃了原有的 Segment 分段锁，来保证采用Node + CAS + Synchronized来保证并发安全性。取消类 Segment，直接用table 数组存储键值对；当 Node对象组成的链表长度超过TREEIFY_THRESHOLD 时，链表转换 为红黑树，提升性能。底层变更为数组 + 链表 + 红黑树。 CAS性能很高，但synchronized之前一直都是重量级的 锁，jdk1.8 引入了synchronized，采用锁升级的方式。