hashmap
底层实现
底 层 这个数组Entry<K,V>[]存放数据<br>java1.7 是一维数组+链表<br>java1.8 是一维数组+链表/红黑树<br>
数组的下标就是 （n-1）&hash
底层数组+链表实现，可以存储null键和null值，线程不安全
hashtable和concurrenthashmap区别，底层实现
什么时候用hashMap，什么情况用ConcurrentHashMap？
是否线程安全，会导致什么问题（不是，会导致更新丢失，比如balabala）
为什么会有线程安全问题？
除了更新丢失，HashMap还会造成什么问题，1.7和1.8的区别？（1.7头插入会导致死循环，1.8改用尾插法）<br>
当两个对象的hashCode值相等时会发生什么？
会发生hash碰撞，当key相等的时候，旧的value会被替换，否则的话加入到链表的后面，<br>但是当链表的阈值大于8，数组的长度超过64，会转为红黑树，java1.7之前是头插法，1.8是尾插法<br>
HashMap 是基于哈希表实现的，每一个元素是一个键值对，其内部通过单链表或者红黑树解决冲突问题，容量不足(超过了阀值)时，会自动扩容。<br>HashMap是非线程安全的，只适用于单线程环境，多线程环境可以采用并发包下的concurrentHashMap。<br>HashMap 实现了Serializable接口，因此它支持序列化，实现了Cloneable接口，能被克隆。<br>HashMap是基于哈希表的 Map 接口的非同步实现，此实现提供所有可选的映射操作，并允许使用 null 值和 null 键，此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
HashMap 每次扩容都是建立一个新的 table 数组，长度和容量阈值都变为原来的两倍，然后把原数组元素重新映射到新数组上，具体步骤如下：<br>首先会判断 table 数组长度，如果大于 0 说明已被初始化过，那么按当前 table 数组长度的 2 倍进行扩容，阈值也变为原来的 2 倍；如果旧数组容量已经是最大值了，那只需把 threshold 阈值设为整数的最大值即可；<br>若 table 数组未被初始化过，且 threshold(阈值)大于 0 说明调用了 有参构造方法，那么就把数组大小设为 threshold；<br>若table 数组未被初始化，且 threshold 为 0 说明调用无参构造方法，那么就把数组大小设为16，threshold 设为 16*0.75；<br>接着需要判断如果不是第一次初始化，那么扩容之后，要重新计算键值对的位置，并把它们移动到合适的位置上去，如果节点是红黑树类型的话则需要进行红黑树的拆分。
HashMap的初始容量是多少？<br>
初始容量是2的幂次方
为什么？
因为（n-1）&hash后得到的结果（下标）是均匀的
如果初始值不是2的幂次方咋办？
底层有一个方法tableSizeFor（int cap）通过移运算和或运算得到一个容量比传入的initialCapacity大的最小的2的次幂数，<br>并将其作为HashMap的初始容量。例如传入7得到初始容量为8的HashMap，<br>传入9得到初始容量为16的HashMap。会自动把它变为2的幂次方<br>
默认容量是数组大小为16，扩展因子是0.75，所以16*0.75=12，证明当数组中的大小超过12的时候，这个时候就会扩容<br>
时间复杂度
HashMap中Hash冲突怎么解决的
插入新数据时如何计算其在数组的索引？
HashMap首先有一个hashCode方法，获取key的hashcode值h，然后将这个h右移16位获取h的高16位，与之前的低十六位进行异或，返回的值与（数组size-1）进行按位与运算，就得到相应的坐标索引<br>
为什么计算数组索引的时候要将哈希值与哈希值无符号右移16位进行异或运算？
因为当数组长度小的时候，假设是16的话，n-1的二进制表示为1111，在进行按位与的时候，这样的值实际上只用了hash值的后四位，但是有的数组长度很大的时候，低位变化小，高位变化大，就很容易发生hash碰撞，所以这里把高低位都利用起来，从而解决这个问题。<br>
当两个对象的hashCode值相等时会发生什么？
HashTable
底层数组+链表实现，无论key还是value都不能为null，线程安全，实现线程安全的方式是在修改数据时锁住整个HashTable，<br>效率低，ConcurrentHashMap做了相关优化<br>
初始size为11，扩容：newsize = olesize*2+1
TreeMap
与hashMap相比的话，Treemap是可以比较大小的，会对key进行大小排序，其中可以用元素的自然排序，也可以使用集合中自定义的比较器来排序<br>
在使用自然排序的时候，分为两种情况：<br>1.jdk定义的对象<br>2.自定义定义的对象
不同于hashmap的哈希映射，它的结构是红黑树，是一种二叉树<br>
继承了AbstractMap，实现了Map，clonable，NavigableMap，Serializable接口<br>
各自接口的特点
特点
1.不允许存在重复的键
2.可以插入null键，null值；
3.可以对元素进行排序
4.无序集合（插入和遍历的顺序不同）
ConcurrentHashMap
HashMap和ConcurrentHashMap的区别
如果有多个线程对ConcurrentHashMap同一个key的value进行操作会不会出现问题
底层
底层也是数组+链表
java1.7
核心成员变量
final Segment<K,V>[] segments;<br>Segment 数组，存放数据时首先需要定位到具体的 Segment 中<br>
HashEntry的组成<br>
与hashMap非常相似，数组中和链表中的value值都是volatile 修饰，保证了获取时的可见性<br>
原理上来说：ConcurrentHashMap 采用了分段锁技术，其中 Segment 继承于 ReentrantLock。不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理，理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量)的线程并发。每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。
Segment 是 ConcurrentHashMap 的一个内部类，主要的组成如下：<br>static final class Segment<K,V> extends ReentrantLock implements Serializable {<br> private static final long serialVersionUID = 2249069246763182397L;<br>
put方法
1.将当前 Segment 中的 table 通过 key 的 hashcode 定位到 HashEntry。<br><br>2.遍历该 HashEntry，如果不为空则判断传入的 key 和当前遍历的 key 是否相等，相等则覆盖旧的 value。<br><br>3.不为空则需要新建一个 HashEntry 并加入到 Segment 中，同时会先判断是否需要扩容。<br><br>4.最后会解除在 1 中所获取当前 Segment 的锁。<br>
get方法
只需要将 Key 通过 Hash 之后定位到具体的 Segment ，再通过一次 Hash 定位到具体的元素上。<br><br>由于 HashEntry 中的 value 属性是用 volatile 关键词修饰的，保证了内存可见性，所以每次获取时都是最新值。<br><br>ConcurrentHashMap 的 get 方法是非常高效的，因为整个过程都不需要加锁
java1.8
与java1.7的区别
将 1.7 中存放数据的 HashEntry 改为 Node，但作用都是相同的
其中抛弃了原有的 Segment 分段锁，而采用了 CAS + synchronized 来保证并发安全性
put方法
根据 key 计算出 hashcode 。<br><br>判断是否需要进行初始化。<br><br>f 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。<br><br>如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。<br><br>如果都不满足，则利用 synchronized 锁写入数据。<br><br>如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树
get方法
根据计算出来的 hashcode 寻址，如果就在桶上那么直接返回值。<br><br>如果是红黑树那就按照树的方式获取值。<br><br>就不满足那就按照链表的方式遍历获取值。
1.8 在 1.7 的数据结构上做了大的改动，采用红黑树之后可以保证查询效率（O(logn)），甚至取消了 ReentrantLock 改为了 synchronized，这样可以看出在新版的 JDK 中对 synchronized 优化是很到位的
