【备战秋招冲击大厂】Java 面试题系列 (1)，springboot 入门程序
当 obj1.equals(obj2)为 true 时，obj1.hashCode() == obj2.hashCode()必须为 true
当 obj1.hashCode() == obj2.hashCode()为 false 时，obj1.equals(obj2)必须为 false
7. map 的分类和常见的情况
java.util.Map：它有四个实现类，分别是 HashMap、Hashtable、LinkedHashMap 和 TreeMap.
Hashmap 是一个最常用的 Map，它根据键的 HashCode 值存储数据，根据键可以直接获取它的值，具有很快的访问速度，遍历时，取得数据的顺序是完全随机的。HashMap 最多只允许一条记录的键为 Null，允许多条记录的值为 Null；HashMap 不支持线程的同步，即任一时刻如果有多个线程同时写 HashMap，可能会导致数据的不一致。如果需要同步，可以用 Collections 的 synchronizedMap 方法使 HashMap 具有同步的能力，或者使用 ConcurrentHashMap。
Hashtable 与 HashMap 类似，它继承自 Dictionary 类，不同的是：它不允许记录的键或者值为空；它支持线程的同步，即任一时刻只有一个线程能写 Hashtable，因此也导致了 Hashtable 在写入时会比较慢。
LinkedHashMap 是 HashMap 的一个子类，保存了记录的插入顺序，在用 Iterator 遍历 LinkedHashMap 时，先得到的记录肯定是先插入的.也可以在构造时用带参数，按照应用次数排序。在遍历的时候会比 HashMap 慢，不过有种情况例外，当 HashMap 容量很大，实际数据较少时，遍历起来可能会比 LinkedHashMap 慢，因为 LinkedHashMap 的遍历速度只和实际数据有关，和容量无关，而 HashMap 的遍历速度和他的容量有关。
TreeMap 实现 SortMap 接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用 Iterator 遍历 TreeMap 时，得到的记录是排过序的。
小结：一般情况下，我们用的最多的是 HashMap，在 Map 中插入、删除和定位元素，HashMap 是最好的选择。但如果您要按自然顺序或自定义顺序遍历键，那么 TreeMap 会更好。如果需要输出的顺序和输入的相同，那么用 LinkedHashMap 可以实现，它还可以按读取顺序来排列.
8. HashMap
哈希表：根据关键码值（key value）而直接进行访问的数据结构。也就是说，它通过关键码值映射到表中一个位置来访问记录，以加快查找速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
哈希：把任意长度的输入通过哈希算法映射成固定长度的输出。
哈希冲突（无法避免）：计算得到的哈希值相同。
解决方法：
1)开放定址法
2)再哈希法：双哈希法计算
3)链址法：HashMap 实现方式，next 指针连接 Node
4)建立公共溢出区：建立基本表和溢出表，哈希值相同的直接放到溢出表
哈希算法要求：
1)高效，能够处理长文本
2)不能逆推原文
3)尽量分散，减少哈希冲突
HashMap
每个数据单元为一个 Node 结构，包含 key，value，hash，next 四个字段
采用懒加载机制，即在进行 put 操作时才真正构建 table 数组。
初始长度为 16，默认负载因子为 0.75，当 HashMap 的长度达到 16*0.75=12 时，就会触发扩容流程，每次扩容为原来的 2 倍（碰撞的概率低）。
允许第一个位置的 key 为空，允许 value 为空
线程不安全，导致 cpu100%：jdk7 链表成环，jdk8 红黑树父子节点成环
JDK1.7：数组+链表；JDK1.8：数组+链表+红黑树（链表长度大于 8 且 table 大于 64 转为红黑树，红黑树节点个数小于 6 转为链表）
红黑树（自平衡二叉查找树）特性：
1)每个结点是黑色或者红色。
2)根结点是黑色。
3)每个叶子结点（NIL）是黑色。 [注意：这里叶子结点
，是指为空(NIL 或 NULL)的叶子结点！]
4)如果一个结点是红色的，则它的子结点必须是黑色的。
5)每个结点到叶子结点 NIL 所经过的黑色结点的个数一样的。
HashMap 的 get 流程：
1)首先会判断数组是否不等于 null，或者数组的长度是否大于 0，如果不满足，就说明 HashMap 里没有数据，直接返回 null。
2)通过 hash & (table.length - 1)获取该 key 对应的数据节点的 hash 槽；
3)判断首节点是否为空，为空则直接返回空；
4)再判断首节点.key 是否和目标值相同，相同则直接返回(首节点不用区分链表还是红黑树)；首节点.next 为空，则直接返回空；
5)首节点是树形节点，则进入红黑树数的取值流程，并返回结果；
6)否则就会进入一个 do while 循环进行查询链表。并返回结果；
HashMap 的 put 流程：
1)如果 table 数组为空数组{}，进行数组填充（为 table 分配实际内存空间），入参为 threshold
2)如果 key 为 null 时被放在了 tab 下标为 0 的位置.
3)根据 hash 值来确认存放的位置。如果当前位置是空直接添加到 table 中
4)如果在首结点与我们待插入的元素有相同的 hash 和 key 值，则先记录。
5)如果首结点的类型是红黑树类型，则按照红黑树方法添加该元素
6)如果首结点类型为链表类型，遍历到末尾时，先在尾部追加该元素结点。当遍历的结点数目大于 8 时，则采取树化结构。
7)modCount++；如果集合在被遍历期间如果内容发生变化则++modCount，只能检测并发修改的 bug，不能保证线程安全（ABA，祥见 CAS）
8)当结点数+1 大于 threshold 时，则进行扩容
9. Hashmap 扩容原理
e.hash & oldCap，就是用于计算位置 b 到底是 0 还是 1 用的，只要其结果是 0，则新散列下标就等于原散列下标，否则新散列坐标要在原散列坐标的基础上加上原 table 长度。
触发扩容时机：
1)当 new 完 HashMap 之后，第一次往 HashMap 进行 put 操作的时候，首先会进行扩容。
2)当 HashMap 的使用的桶数达到总桶数*加载因子的时候会触发扩容；
3)当某个桶中的链表长度达到 8 进行链表扭转为红黑树的时候，会检查总桶数是否小于 64，如果总桶数小于 64 也会进行扩容；
10. Hashmap 拓展问题
为什么 JDK1.8 采用红黑树存储 Hash 冲突的元素？
红黑树本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为 O(log n)。能够加快检索速率。
为什么在长度小于 8 时使用链表，不一直使用红黑树？
桶中元素的插入只会在 hash 冲突时发生，而 hash 冲突发生的概率较小，一直维护一个红黑树比链表耗费资源更多，在桶中元素量较小时没有这个必要。
为什么要使用红黑树而不使用 AVL 树？
红黑树与 AVL 树，在检索的时候效率差不多，都是通过平衡来二分查找。但红黑树不像 AVL 树一样追求绝对的平衡，红黑树允许局部很少的不完全平衡，这样对于效率影响不大，但省去了很多没有必要的调平衡操作，AVL 树调平衡有时候代价较大，所以效率不如红黑树。
为什么数组容量必须是 2 次幂？
索引计算公式为 i = (n - 1) & hash，如果 n 为 2 次幂，那么 n-1 的低位就全是 1，而扩容后只有一位差异，也就是多出了最左位的 1，这样在通过 (length-1) &hash 的时候，只要 hash 对应的最左边的那一个差异位为 0，就能保证得到的新的数组索引和老数组索引一致(高效的数据迁移，大大减少了之前已经散列良好的老数组的数据位置重新调换)，哈希值进行与操作时可以保证低位的值不变，如果低位值为 1，则表示该位置可以插入值，从而保证分布均匀，效果等同于 hash%n，但是位运算比取余运算要高效的多。
为什么单链表转为红黑树要求桶内的元素个数大于 8？
当 hashCode 离散性很好的时候，树型 bin 用到的概率非常小，因为数据均匀分布在每个 bin 中，几乎不会有 bin 中链表长度会达到阈值。但是在随机 hashCode 下，离散性可能会变差，然而 JDK 又不能阻止用户实现这种不好的 hash 算法，因此就可能导致不均匀的数据分布。不过理想情况下随机 hashCode 算法下所有 bin 中节点的分布频率会遵循泊松分布，而一个 bin 中链表长度达到 8 个元素的概率为 0.00000006，几乎是不可能事件。
同理，少于 6 就从红黑树转回单链表是为了节省维护一个树的资源消耗，而选择 6 作为临界值，是因理想情况下一个 bin 中元素个数达到 6 的概率是 0.00001316，达到 7 的概率为 0.00000094，二者跨度较大，可以减小树和链表之间频繁转化的可能性。
为什么 jdk1.8 将头插法改成尾插法？
JDK1.7 中扩容时，每个元素的 rehash 之后，都会插入到新数组对应索引的链表头，所以这就导致原链表顺序为 A->B->C，扩容之后，rehash 之后的链表可能为 C->B->A，元素的顺序发生了变化。在并发场景下，扩容时可能会出现循环链表的情况。而 JDK1.8 从头插入改成尾插入元素的顺序不变，避免出现循环链表的情况。
11. ConcurrentHashMap
JDK1.7：Segment 数组+HashEntry
1)HashEntry 中 value，以及 next(链表)都是 volatile 修饰的，保证了获取时的可见性。
2)原理上来说：ConcurrentHashMap 采用了分段锁技术，其中 Segment 继承于 ReentrantLock。不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理，理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量，默认为 16)的线程并发。每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。
JDK1.8：Node +CAS+Synchorized+volatile
对比 Java7 和 Java8 的异同和优缺点
1)数据结构不同
Java 7 采用数组+链表来实现，而 Java 8 中的 ConcurrentHashMap 使用数组 + 链表 + 红黑树
2)并发度
Java 7 中，每个 Segment 独立加锁，最大并发个数就是 Segment 的个数，默认是 16。
Java 8 中，锁粒度更细，理想情况下 table 数组元素的个数（也就是数组长度）就是其支持并发的最大个数，并发度比之前有提高。
3)保证并发安全的原理
Java 7 采用 Segment 分段锁来保证安全，而 Segment 是继承自 ReentrantLock。
Java 8 中放弃了 Segment 的设计，采用 Node + CAS + synchronized+volatile 保证线程安全。
4)遇到 Hash 碰撞
Java 7 在 Hash 冲突时，会使用拉链法，也就是链表的形式。
Java 8 先使用拉链法，在链表长度超过一定阈值时，将链表转换为红黑树，来提高查找效率。
5)查询时间复杂度
Java 7 遍历链表的时间复杂度是 O(n)，n 为链表长度。
Java 8 如果变成遍历红黑树，那么时间复杂度降低为 O(logn)，n 为树的节点个数。
12. 线程安全的 Map
HashTable
SynchronizedMap：加了一个对象锁，每次操作 hashmap 都需要先获取这个对象锁
ConcurrentHashMap：线程安全是通过 cas+synchronized+volatile 来实现的
ConcurrentSkipListMap： 通过跳表来实现的高并发容器并且这个 Map 是有序排序的，根据 key 来排序
13. HashMap 和 Hashtable 的区别
JDK 1.8 中 HashMap 和 Hashtable 主要区别如下：
父类不同。HashMap 继承自 AbstractMap；Hashtable 继承自 Dictionary。
线程安全性不同。HashMap 线程不安全；Hashtable 中的方法是 Synchronized 的。
HashMap 最多只允许一条记录的键为 Null，允许多条记录的值为 Null；Hashtable 键和值都不允许为空。
默认初始大小和扩容方式不同。HashMap 默认初始大小 16，容量必须是 2 的整数次幂，扩容时将容量变为原来的 2 倍；Hashtable 默认初始大小 11，扩容时将容量变为原来的 2 倍加 1。
迭代器不同。HashMap 的 Iterator 是 fail-fast 迭代器；Hashtable 还使用了 enumerator 迭代器。
hash 的计算方式不同。HashMap 计算了 hash 值；Hashtable 使用了 key 的 hashCode 方法。
是否有 contains 方法。HashMap 没有 contains 方法；Hashtable 包含 contains 方法，类似于 containsValue。
14. TreeMap 底层实现
TreeMap 的实现就是红黑树数据结构，也就说是一棵自平衡的排序二叉树，这样就可以保证快速检索指定节点。
红黑树的插入、删除、遍历时间复杂度都为 O(lgN)，所以性能上低于哈希表。但是哈希表无法提供键值对的有序输出，红黑树因为是排序插入的，可以按照键的值的大小有序输出。
15. HashMap 和 TreeMap
还未添加个人签名 2021.03.18 加入
还未添加个人简介
评论