java集合面经

HashMap解析

https://www.jianshu.com/p/0a70ce2d3b67
###LinkedHashMap解析
https://www.jianshu.com/p/181df0893158
###ConcurrentHashMap（jdk1.7）解析
https://www.cnblogs.com/heqiyoujing/p/10928423.html
###ConcurrentHashMap（jdk1.8）解析

红黑树解析

https://zhuanlan.zhihu.com/p/79980618?utm_source=cn.wiz.note

1.哈希HashMap的底层实现

底层由链表+数组实现（java8以后当链表长度超过8转变为红黑树实现）

可以存储null键和null值，线性不安全
初始容量为16，扩容每次都是2的n次幂（保证位运算）
加载因子为0.75，当Map中元素总数超过Entry数组的0.75，触发扩容操作.
并发情况下，HashMap进行put操作会引起死锁（单链表变为循环链表），导致CPU利用率接近100%

HashMap底层是数组和链表的结合。HashMap通过key的HashCode经过扰动函数处理过后得到Hash值，然后通过位运算判断当前元素存放的位置，如果当前位置存在元素的话，就判断该元素与要存入的元素的hash值以及key是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突，把新元素添加到链表中。当Map中的元素总数超过Entry数组的0.75时，触发扩容操作，为了减少链表长度，提高访问速度，使元素分配更均匀。

HashMap基于哈希思想，实现对数据的读写。
当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，然后后找到bucket位置来储存值对象。
当get()获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap使用链表来解决碰撞问题，当发生碰撞了，对象将会储存在链表的下一个节点中。HashMap在每个链表节点中储存键值对对象。当两个不同的键对象的hashcode相同时，它们会储存在同一个bucket位置的链表中，可通过键对象的equals()方法用来找到键值对。如果链表大小超过阈值8，链表就会被改造为树形结构。

JDK1.8以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间。（一个是链表的长度达到8个，一个是数组的长度达到64个）

那为什么当链表长度大于阈值8时才会选择使用红黑树呢？
为了配合使用分布良好的hashCode，树节点很少使用。并且在理想状态下，受随机分布的hashCode影响，链表中的节点遵循泊松分布，而且根据统计，链表中节点数是8的概率已经接近千分之一，而且此时链表的性能已经很差了。所以在这种比较罕见和极端的情况下，才会把链表转变为红黑树。因为链表转换为红黑树也是需要消耗性能的，特殊情况特殊处理，为了挽回性能，权衡之下，才使用红黑树，提高性能。也就是大部分情况下，hashmap还是使用的链表，如果是理想的均匀分布，节点数不到8，hashmap就自动扩容。

哈希冲突：如果两个不同对象的hashCode相同，这种现象称为hash冲突。
有以下的方式可以解决哈希冲突：
开放定址法
再哈希法
链地址法
建立公共溢出区

ConcurrentHashMap原理概览

参考链接：https://www.cnblogs.com/zerotomax/p/8687425.html

在ConcurrentHashMap中通过一个Node<K,V>[]数组来保存添加到map中的键值对，而在同一个数组位置是通过链表和红黑树的形式来保存的。但是这个数组只有在第一次添加元素的时候才会初始化，否则只是初始化一个ConcurrentHashMap对象的话，只是设定了一个sizeCtl变量，这个变量用来判断对象的一些状态和是否需要扩容，后面会详细解释。

　　第一次添加元素的时候，默认初期长度为16，当往map中继续添加元素的时候，通过hash值跟数组长度取与来决定放在数组的哪个位置，如果出现放在同一个位置的时候，优先以链表的形式存放，在同一个位置的个数又达到了8个以上，如果数组的长度还小于64的时候，则会扩容数组。如果数组的长度大于等于64了的话，在会将该节点的链表转换成树。

　　通过扩容数组的方式来把这些节点给分散开。然后将这些元素复制到扩容后的新的数组中，同一个链表中的元素通过hash值的数组长度位来区分，是还是放在原来的位置还是放到扩容的长度的相同位置去 。在扩容完成之后，如果某个节点的是树，同时现在该节点的个数又小于等于6个了，则会将该树转为链表。

　　取元素的时候，相对来说比较简单，通过计算hash来确定该元素在数组的哪个位置，然后在通过遍历链表或树来判断key和key的hash，取出value值。

　　往ConcurrentHashMap中添加元素的时候，里面的数据以数组的形式存放的样子大概是这样的：

这个时候因为数组的长度才为16，则不会转化为树，而是会进行扩容。

　　扩容后数组大概是这样的：

如果数组扩张后长度达到64了，且继续在某个节点的后面添加元素达到8个以上的时候，则会出现转化为红黑树的情况。

　　转化之后大概是这样：

3.请你说明HashMap和Hashtable的区别？

HashMap和Hashtable都实现了Map接口，因此很多特性非常相似。但是，他们有以下不同点：
HashMap允许键和值是null，而Hashtable不允许键或者值是null。
Hashtable是同步的，而HashMap不是。HashMap更适合于单线程环境，而Hashtable适合于多线程环境。
HashMap提供了可供应用迭代的键的集合，因此，HashMap是快速失败的。

HashMap和TreeMap的区别
HashMap：数组方式存储key/value，线程非安全，允许null作为key和value，key不可以重复，value允许重复，不保证元素迭代顺序是按照插入时的顺序，key的hash值是先计算key的hashcode值，然后再进行计算，每次扩容会重新计算key的hash值，会消耗资源，要求key必须重写equals和hashcode方法。它默认初始容量为16，加载因子0.75，扩容为旧容量的2倍，查找元素快。
TreeMap:基于红黑树的NavigableMap实现，线程非安全，不允许null作为key和value，key不可以重复，value允许重复，存入TreeMap的元素应当实现Comparable接口或者实现Comparator接口，会按照排序后的顺序迭代元素。主要用于存入元素的时候对元素进行自动排序，迭代输出的时候就按照排序顺序输出。

4.请你说明一下TreeMap的底层实现？
TreeMap 的实现就是红黑树数据结构,一棵自平衡的排序二叉树，这样就可以保证当需要快速检索指定节点。
红黑树的插入、删除、遍历时间复杂度都为O(lgN)，所以性能上低于哈希表。但是哈希表无法提供键值对的有序输出，红黑树因为是排序插入的，可以按照键的值的大小有序输出。

红黑树的性质：
1.节点是红色或黑色。
2.根节点是黑色。
3.每个叶子节点都是黑色的空节点（NIL节点）。
4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

平衡二叉树的性质：
它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。

区别：
1、红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。
2、平衡二叉树追求绝对平衡，条件苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知。