HashMap与ConcurrentHashMap 详解
说一下你对HashMap的理解；他的底层结构是什么样的；
jdk7之前底层使用的是数组+链表的形式，1.8之后改成了数据加链表加红黑二叉树，提高查询性能，
一个数据是怎么存到，map里面的；
1.首先创建hashmap，默认大小是16，负载因子是0.75，我们可以去指定他的长度size，如果自己传入初始大小k，初始化大小为 大于k的 2的整数次方。那么为什么2的整数次方，例如如果传10，大小为16。
2.然后我们进行一个插入，首先他会对key取一个hash值，是32位的int值，让他的高16位和低16位进行一个异或运算，原因的是因为后16位有可能是相同的 为了使我们hash的值分布的更加均匀，并且使用位运算也非常高效 。
源码里面就把散列值和（（数组的长度-1 ）因为-1之后他的地位全都是1高位都为0这种形式）做了与运算 算出数组的下标。之所以要做是因为int值的范围是 -2的31次方-1到2的32次方 前后加起来大概与40亿的映射空间 但问题是一个40亿长度的数组 内存是放不下的。
3.之后我们把hashCode的节点组装成一个entry节点 把这个entry节点存储到数组下表里面 存储的时候首先会判断一下这个数组的下标是不是有值 如果说有值得话 他首先去判断这个key的值是不是是相等的 如果是相等的 说明我们是相同的一个值 那我们就要用现在的值替换掉原来的值如果是不相等的 那就使用链表的形式将他串联起来。存储之后链表也会做一个判断如果说链表他是大于8的 我们会把它转化成一个红黑二叉树进行排列。
这里有一个jdk7和jdk8的区别
- 数组+链表改成了数组+链表或红黑树；
- 链表的插入方式从头插法改成了尾插法，原因是因为我们在非线程安全下使用hashmap的时候会出现一个死循环的问题 这个问题在1.8之后进行了一个修复.
- 扩容的时候1.7需要对原数组中的元素进行重新hash定位在新数组的位置，1.8采用更简单的判断逻辑，位置不变或索引+旧容量大小；
- 在插入时，1.7先判断是否需要扩容，再插入，1.8先进行插入，插入完成再判断是否需要扩容；
怎么可以让HashMap的碰撞变小；
算法让他分布的更均匀 位运算 扩容
为什么不能用可变类型做键值呢；
因为可变类型作为key，如果修改会造成数据无法找到。
链表什么时候转成红黑树；为什么要转成红黑树；
我们在jdk1.8使用了红黑树，原因是因为我们在发生hash碰撞的时候，我们会把数据按照链表的形式把他插入进去，那么这个时候因为我们链表只能从头结点进行一个遍历，那么他的一个时间复杂度就On，非常影响性能，所以我们当他大于2三次方8的时候就会转成红黑树；原因是使用红黑二叉树之后，当我们在查询数据的时候复杂度就会降为O1，可以大大的提高我们的性能
红黑树是什么样的，他的结构是什么样的；他还要其他什么特征吗；
他的结构的话我们平常会像这种平衡二叉树来维护他，但是平衡二叉树可能说是我每插入一个节点，他就要去维护这种情况，比较频繁，就有了红黑二叉树这种红黑节点相互交替，他有四个规则，
CocurrentHashMap历史变化、数据结构及原理
在并发编程里面使用的CocurrentHashMap，在1.7我们使用sengment分段锁，每一次key进来之后，他都会判断你这个key是属于哪一个分段里面的，从而拿到sengment。锁主要是加在链表上的，因为链表会导致我们线程安全的问题，1.8之后我们将锁改成了CAS+synchronized，解决分段锁的弊端。
为什么1.7到1.8要换一种方式
之所以改锁机制是因为sengment分段锁他可以设置，但是他默认是16段，这个时候我们的并发量就会有一个限制，包括我们需要去估sengment的个数，如果估少了，就会导致锁的空闲，估大了会导致锁的一些竞争，而且一旦初始化以后，它是不可以扩容的，所以之后改成了自旋锁，大大提高了性能。
分段锁是的底层怎么实现的；
分段锁底层维护了一个数组，我们默认的话是16段，每一个段就相当于一把锁，然后最大的并发量可能到达16；
他的继承结构；
它继承了ReentrantLock，然后ReentrantLock继承了AQS(AbstractQueuedSynchronizer)
自旋锁是怎么实现的
思想是给 table的每一个下标都加锁，也就是当对下标进行操作时都会加锁（CAS+Synchronize）。ConcurrentHashMap 成员变量使用 volatile 修饰，免除了指令重排序，同时保证内存可见性，另外使用 CAS操作和 synchronized结合实现赋值操作，多线程操作只会锁住当前操作索引的节点。
如果俩个key都在同一个分段上面，是怎么保证安全的；
CAS的实现原理
CAS其实就是CompareAndSwap首先他会传入一个值还有他的地址，然后进行一个CAS的判断，当前的值与我们现在的值进行比较，如果说一样的话，那我再会进行一个数据的插入，当前的第三个值插入进去，如果不相同从新获取值，然后进行修改，进行插入，这个值可能会有一个ABA的问题，所以每次拿到值以后，会给他加一个版本号，然后进行比较插入的。