备战2024秋招面试题（1）

$前言：$

💞快秋招了，那么这个专栏就专门来记录一下，同时呢整理一下常见面试题
💞部分题目来自自己的面试题，部分题目来自网络整理

干，被KPI啦

面试题

1. 根据简历来面试：详细介绍简历中的项目

   这个需要根据自己的简历来做准备了。我也在准备中。

2. Map具体是怎么实现的？

   	key-value是否可为null	线程安全	是否有序	实现方式	继承类	实现类	效率
   hashMap	可	不安全	无序	数组加链表，1.8以后增加红黑树	AbstractMap	Map Cloneable Serializable	高
   hashTable	非	安全	无序	和hashMap 一样也是散列表	Dictionary	MapCloneable Serializable	低
   linkedHashMap	可	不安全	有序	在hashMap基础上加了双向的链表	HashMap	Map Serializable	高
   ConcurrentHashMap	可	安全	无序	分多个桶，减少开销	AbstractMap	ConcurrentMap Serializable	高

   map 是个 key-value 的存储结构，常用的实现有两种，HashMap和TreeMap。

     HashMap 是通过hash方式实现的map，底层存储在一个数组中。hashmap在初始化时，默认会创建一个长度为16的数组。当我们调用put方法时（例如map.put(2,'hxl')），hashmap会获取key的hash值。将这个hash值与长度进行&操作，算出的值就是数据存在数组中的下标。

     & 的性能比较高，在和数组的长度计算时，要求数组的长度必须是$2^n$，当初始化长度指定长度不是$2^n$，会将其进行一个转换。

     Hash碰撞。 如果两个key算出的下标是同一位置，那么就会出现hash碰撞。在JDK8之前，hashmap采用了链表的方式解决碰撞问题，也就是说新数据会作为一个链表的节点链接在前一个节点中。该方法会存在链表问题，时间复杂度为$O(n)$，所以在JDK8之后就把链表改成了链表+红黑树。在碰撞数小于8时，采用的是链表。到8个时会转换成红黑树。另外map的数组小于64时，不会转换成数，而是进行依次扩容。
     当调用map的put方法时，hashmap是用equals方法判断两个key是否相等，相等则覆盖。因为需要用hash算出key，所以当把对象作为key时，需要重写两个方法，一个是equals方法，还有一个是重写hashcode方法。
     扩容 hashmap的底层是数组存储，会涉及到扩容的问题。hashmap计算新数组长度的方式就是用旧的长度向左移1位，也就是新数组是旧数组的2倍。
     扩容时间 第一种：碰撞数大于等于8，且数组小于64。第二种：当$存储的数据个数>数组长度\ast 0.75$ 这个0.75是默认的加载因子。在初始化hashmap的时候就可以进行指定。
     扩容的方式，就是把旧数组中的数据重新计算hash(rehash)，然后放到新数组中，rehash是比较消耗性能的，所以我们要尽量减少rehash的出现。

   ConcurrentHashMap与HashMap的区别就是ConcurrentHashMap是线程安全的
LinkedHashMap是一个有序的hashmap，每次操作时，重新把节点放置到链表尾部。原本的hashmap的key是无序的。

  Treemap是一个标准红黑树的实现。相比Hashmap，Treemap是一个可以排序的map，但操作的时间复杂度O(logn)，比hashmap性能稍差，但没有扩容问题，所以如果需要有序的map，选择Treemap，否则使用hashmap

算法题

$题目来源：$ 力扣101. 对称二叉树
$等级：简单$

👉题目描述
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例一：

输入：root = [1,2,2,3,4,4,3]
输出：true
1
2

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false
1
2

提示：

• 树中节点数目在范围 [1, 1000] 内
• -100 <= Node.val <= 100

👉代码编写

👉👉方法1

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }

        return compare(root.left, root.right);
    }

    public boolean compare(TreeNode left, TreeNode right) {
        if (left == null && right != null) {
            return false;
        }
        if (left != null && right == null) {
            return false;
        }
        if (left == null && right == null) {
            return true;
        }
        if (left.val != right.val) {
            return false;
        }
        boolean out = compare(left.left, right.right);
        boolean inner = compare(left.right, right.left);
        return out && inner;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

再次寻找到的题目

1. HashMap中get方法的原理

• 底层会调用key的hashcode()方法，通过hash函数将hash值转换为数组下标，通过数组下标快速定位到数组的指定位置上，如果这个位置上没有任何元素，那么返回null。

• 如果这个位置上有单向链表（该位置上有元素），那么会拿着我们get(key)中的key和单向链表中的每个节点的key进行equals，如果说所有的equals都返回false，那么这个get方法返回false。

• 只要其中有一个节点的key和参数key的equals对比的结果返回true,那么这个节点的value就是我们想要找的value，get方法返回这个value.

2. HashMap线程安全问题
   HashTable是线程安全的,HashMap是线程非安全的.在多线程的情况下, HashMap会出现死循环的情况。

HashMap不是线程安全的，多线程下可能会发生这些问题：

1.多线程下扩容死循环。JDK 1.7 中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此，JDK 1.8 使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。

2.多线程的 put 可能导致元素的丢失。多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在 JDK 1.7 和 JDK 1.8 中都存在。

3.put 和 get 并发时，可能导致 get 为 null。线程 1 执行 put 时，因为元素个数超出 threshold 而导致 rehash，线程 2 此时执行 get，有可能导致这个问题。这个问题在 JDK 1.7 和 JDK 1.8 中都存在。

解决HashMap线程不安全的问题呢？

Java 中有 HashTable、Collections.synchronizedMap、以及 ConcurrentHashMap 可以实现线程安全的 Map。

HashTable ：是直接在操作方法上加 synchronized 关键字，锁住整个 table 数组，粒度比较大；

Collections.synchronizedMap ：是使用 Collections 集合工具的内部类，通过传入 Map 封装出一个 SynchronizedMap 对象，内部定义了一个对象锁，方法内通过对象锁实现；

ConcurrentHashMap 在 JDK 1.7 中使用分段锁，在 JDK 1.8 中使用 CAS + synchronized。

ConcurrentHashmap 的实现：ConcurrentHashmap 线程安全在 JDK 1.7 版本是基于分段锁实现的，在 JDK 1.8 是基于 CAS + synchronized 实现。

3. HashMap的value能不能存null，key能不能为null

   HashMap对象的key、value值均可为null。

   HahTable对象的key、value值均不可为null。

   且两者的的key值均不能重复，若添加key相同的键值对，后面的value会自动覆盖前面的value，但不会报错。

   对于key是否存在一般会使用map.containskey(key)。对于值是否存在一般会使用map.get(key)