Java实习打卡8道面试题

目录

• 1、什么是雪花算法，简单介绍一下？
• 2、请你分析一下红黑树的左右旋转流程？
• 3、什么是DNS污染和DSN劫持？
• 4、说一说操作系统的虚拟内存？
• 4.1、虚拟内存介绍，什么是虚拟内存？
• 4.2、什么是局部性原理？
• 4.3、虚拟存储器(虚拟内存)
• 4.4、虚拟内存技术实现
• 4.5、页面置换算法
• 5、StringBuilder.append(“xxx”); 后创建新对象吗？
• 6、哈希冲突的几种解决方案，各个优缺点？
• 6.1、开放定址法
• 6.2、再哈希法（再散列法）
• 6.3、链地址法（拉链法）
• 7、使用java如何对一个大的文本文件内容进行去重?
• 8、MySQL如何优化慢查询？
• 总结

1、什么是雪花算法，简单介绍一下？

文章参考：带你入门java雪花算法原理

雪花算法是 Twitter 开源的分布式 ID 生成算法。是由 64bit 的 long 类型，生成的全局 ID，引入了 时间戳和 ID保持自增 的属性。

64bit分为四个部分：

• 第一个部分是 1bit，没有实际意义。
• 第二个部分是 41bit，由时间戳组成。
• 第三个部分是 10bit，工作机器 ID，里面分为两个部分，5 个 bit 是的是机房号，代表最多有 2^5 即 32 个机房，5 个 bit 是指机器的ID，代表最多有 2^5 个机器，即 32 个机器。
• 第四部分是 12bit，代表是同一个毫秒类产生不同的 ID，区分同一个毫秒内产生的ID.

总的来说就是一个机房，一台机器，在同一号毫秒时产生的 ID，可能在同一秒钟产生不同的 ID，最后 12bit 序列号可以区分在同一秒钟的不同 ID。

雪花算法保证:

1. 所生成的 ID 按时间递增。
2. 整个分布式系统不会有重复的 ID。

2、请你分析一下红黑树的左右旋转流程？

直接上图，生动形象：

就以左旋为例，首先当前节点（N）所在位置被它的右子节点（R）替代，N 的左子树仍然是它的左子节点（L），但是 R 节点此时将它的左子节点（RL）交给 N，使其成为 N 的右子节点，R 的右子节点还是原来的右子节点（RR）。

红黑树的完整文章，参考往期博客：HashMap底层红黑树实现(自己实现一个简单的红黑树)

3、什么是DNS污染和DSN劫持？

什么是DNS劫持？

• DNS 劫持：就是指 DNS 服务器被劫持了，通过某些手段取得某域名的解析记录控制权，进而修改此域名的解析结果，导致对该域名的访问由原IP地址转入到修改后的指定IP，其结果就是对特定的网址不能访问或访问的是假网址，从而实现窃取资料或者破坏原有正常服务的目的。DNS 劫持通过篡改 DNS 服务器上的数据返回给用户一个错误的查询结果来实现的。
• DNS 劫持症状：在某些地区的用户在成功连接宽带后，首次打开任何页面都指向 ISP 提供的 “电信互联星空”、“网通黄页广告” 等内容页面。还有就是曾经出现过用户访问 Google 域名的时候出现了百度的网站。这些都属于 DNS 劫持。

什么是DNS污染？

• DNS 污染：是一种让一般用户由于得到虚假目标主机 IP 而不能与其通信的方法，是一种 DNS 缓存投毒攻击（DNS cache poisoning）。
• 其工作方式是：由于通常的 DNS 查询没有任何认证机制，而且 DNS 查询通常基于的 UDP 是无连接不可靠的协议，因此 DNS 的查询非常容易被篡改，通过对 UDP 端口 53 上的 DNS 查询进行入侵检测，一经发现与关键词相匹配的请求则立即伪装成目标域名的解析服务器（NS，Name Server）给查询者返回虚假结果。
• DNS污染则是发生在用户请求的第一步上，直接从协议上对用户的DNS请求进行干扰。
• DNS污染症状：目前一些被禁止访问的网站很多就是通过 DNS 污染来实现的，例如 YouTube、Facebook 等网站。

二者的解决方案：

对于DNS劫持，可以采用使用国外免费公用的DNS服务器解决。例如 OpenDNS（208.67.222.222）或 GoogleDNS（8.8.8.8）。

对于DNS污染，可以说，个人用户很难单单靠设置解决，通常可以使用 VPN 或者域名远程解析的方法解决，但这大多需要购买付费的 VPN 或 SSH 等，也可以通过修改 Hosts 的方法，手动设置域名正确的 IP 地址。

总结：

• DNS 劫持，就是指用户访问一个被标记的地址时，DNS 服务器故意将此地址指向一个错误的IP地址的行为。范例，网通、电信、铁通的某些用户有时候会发现自己打算访问一个地址，却被转向了各种推送广告等网站，这就是DNS劫持。
• DNS 污染，指的是用户访问一个地址，国内的服务器(非DNS)监控到用户访问的已经被标记地址时，服务器伪装成DNS服务器向用户发回错误的地址的行为。范例，访问 Youtube、Facebook 之类网站等出现的状况。

4、说一说操作系统的虚拟内存？

4.1、虚拟内存介绍，什么是虚拟内存？

这个在我们平时使用电脑特别是 Windows 系统的时候太常见了。很多时候我们使用点开了很多占内存的软件，这些软件占用的内存可能已经远远超出了我们电脑本身具有的物理内存。

为什么可以这样呢？ 正是因为 虚拟内存 的存在，通过 虚拟内存 可以让程序可以拥有超过系统物理内存大小的可用内存空间。

另外，虚拟内存为每个进程提供了一个一致的、私有的地址空间，它让每个进程产生了一种自己在独享主存的错觉（每个进程拥有一片连续完整的内存空间）。这样会更加有效地管理内存并减少出错。

虚拟内存是计算机系统内存管理的一种技术，我们可以手动设置自己电脑的虚拟内存。不要单纯认为虚拟内存只是“使用硬盘空间来扩展内存“的技术。虚拟内存的重要意义是它定义了一个连续的虚拟地址空间，并且 把内存扩展到硬盘空间。

4.2、什么是局部性原理？

局部性原理是虚拟内存技术的基础，正是因为程序运行具有局部性原理，才可以只装入部分程序到内存就开始运行。

早在 1968 年的时候，就有人指出我们的程序在执行的时候往往呈现局部性规律，也就是说在某个较短的时间段内，程序执行局限于某一小部分，程序访问的存储空间也局限于某个区域。

局部性原理表现在以下两个方面：

• 时间局部性 ：如果程序中的某条指令一旦执行，不久以后该指令可能再次执行；如果某数据被访问过，不久以后该数据可能再次被访问。产生时间局部性的典型原因，是由于在程序中存在着大量的循环操作。
• 空间局部性 ：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，这是因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式簇聚存储的。

时间局部性是通过将近来使用的指令和数据保存到高速缓存存储器中，并使用高速缓存的层次结构实现。空间局部性通常是使用较大的高速缓存，并将预取机制集成到高速缓存控制逻辑中实现。虚拟内存技术实际上就是建立了 “内存一外存”的两级存储器的结构，利用局部性原理实现髙速缓存。

4.3、虚拟存储器(虚拟内存)

基于局部性原理，在程序装入时，可以将程序的一部分装入内存，而将其他部分留在外存，就可以启动程序执行。由于外存往往比内存大很多，所以我们运行的软件的内存大小实际上是可以比计算机系统实际的内存大小大的。

**在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存，然后继续执行程序。另一方面，操作系统将内存中暂时不使用的内容换到外存上，从而腾出空间存放将要调入内存的信息。**这样，计算机好像为用户提供了一个比实际内存大的多的存储器——虚拟存储器。

实际上，我觉得虚拟内存同样是一种时间换空间的策略，你用 CPU 的计算时间，页的调入调出花费的时间，换来了一个虚拟的更大的空间来支持程序的运行。不得不感叹，程序世界几乎不是时间换空间就是空间换时间。

4.4、虚拟内存技术实现

虚拟内存的实现需要建立在离散分配的内存管理方式的基础上。 虚拟内存的实现有以下三种方式：

请求分页存储管理 ：建立在分页管理之上，为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。请求分页是目前最常用的一种实现虚拟存储器的方法。请求分页存储管理系统中，在作业开始运行之前，仅装入当前要执行的部分段即可运行。假如在作业运行的过程中发现要访问的页面不在内存，则由处理器通知操作系统按照对应的页面置换算法将相应的页面调入到主存，同时操作系统也可以将暂时不用的页面置换到外存中。

请求分段存储管理 ：建立在分段存储管理之上，增加了请求调段功能、分段置换功能。请求分段储存管理方式就如同请求分页储存管理方式一样，在作业开始运行之前，仅装入当前要执行的部分段即可运行；在执行过程中，可使用请求调入中断动态装入要访问但又不在内存的程序段；当内存空间已满，而又需要装入新的段时，根据置换功能适当调出某个段，以便腾出空间而装入新的段。

请求段页式存储管理

这里多说一下？很多人容易搞混请求分页与分页存储管理，两者有何不同呢？

请求分页存储管理建立在分页管理之上。他们的根本区别是是否将程序全部所需的全部地址空间都装入主存，这也是请求分页存储管理可以提供虚拟内存的原因，我们在上面已经分析过了。

它们之间的根本区别在于是否将一作业的全部地址空间同时装入主存。请求分页存储管理不要求将作业全部地址空间同时装入主存。基于这一点，请求分页存储管理可以提供虚存，而分页存储管理却不能提供虚存。

不管是上面那种实现方式，我们一般都需要：

• 一定容量的内存和外存：在载入程序的时候，只需要将程序的一部分装入内存，而将其他部分留在外存，然后程序就可以执行了；
• 缺页中断：如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操作系统将相应的页面或段调入到内存，然后继续执行程序；
• 虚拟地址空间 ：逻辑地址到物理地址的变换。

4.5、页面置换算法

地址映射过程中，若在页面中发现所要访问的页面不在内存中，则发生缺页中断 。

注：缺页中断 就是要访问的页不在主存，需要操作系统将其调入主存后再进行访问。 在这个时候，被内存映射的文件实际上成了一个分页交换文件。

当发生缺页中断时，如果当前内存中并没有空闲的页面，操作系统就必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。用来选择淘汰哪一页的规则叫做页面置换算法，我们可以把页面置换算法看成是淘汰页面的规则。

• OPT 页面置换算法（最佳页面置换算法） ：最佳(Optimal, OPT)置换算法所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。但由于人们目前无法预知进程在内存下的若千页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现。一般作为衡量其他置换算法的方法。
• FIFO（First In First Out） 页面置换算法（先进先出页面置换算法） : 总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面进行淘汰。
• LRU （Least Currently Used）页面置换算法（最近最久未使用页面置换算法） ：LRU算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 T，当须淘汰一个页面时，选择现有页面中其 T 值最大的，即最近最久未使用的页面予以淘汰。
• LFU （Least Frequently Used）页面置换算法（最少使用页面置换算法） : 该置换算法选择在之前时期使用最少的页面作为淘汰页。

5、StringBuilder.append(“xxx”); 后创建新对象吗？

• 看这一篇就够了！String StringBuilder StringBuffer区别以及源码分析

答案是，没有创建新对象：

因为 StringBuilder，和 String 不同，它的 char[]数组没有被 final 修饰，所以它可以在添加新char字符时，根据字符数组容量，进行动态扩容，而不需要新创建一个 StringBuilder 对象！

如图所示：

StringBuilder.append()方法如下代码所示：

// java.lang.StringBuilder 类中
@Override
public StringBuilder append(String str) {
    // 调用父类 AbstractStringBuilder 的append(String str) 方法
    super.append(str);
    return this;
}
// java.lang.AbstractStringBuilder 类中（有兴趣可以自己点进去阅读该类的源码，还是很有收获的，这里只作简述！）
public AbstractStringBuilder append(String str) {
    if (str == null)
        return appendNull();
    int len = str.length();
    // 其成员属性value[]数组扩容，类似于ArrayList 的扩容
    // 扩容算法：int newCapacity = (value.length << 1) + 2;
    // 注意容量有上限：MAX_ARRAY_SIZE
    ensureCapacityInternal(count + len);
    str.getChars(0, len, value, count);
    count += len;
    return this;
}

注： 同理，StringBuffer 也是一样的！

6、哈希冲突的几种解决方案，各个优缺点？

6.1、开放定址法

这种方法也称再散列法，其基本思想是：当关键字 key 的哈希地址 p=H（key）出现冲突时，以 p 为基础，产生另一个哈希地址 p1，如果 p1 仍然冲突，再以 p 为基础，产生另一个哈希地址 p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：

Hi=（H（key）+di）% m i=1，2，…，n

其中 H（key）为哈希函数，m 为表长，di 称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。主要有以下三种：

① 线性探测再散列

dii = 1，2，3，…，m-1

这种方法的特点是：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。ThreadLocal 解决 hash 冲突就采用这种方法！

② 二次探测再散列

di = 12，-12，22，-22，…，k2，-k2 ( k<=m/2 )（2为2次方）

这种方法的特点是：冲突发生时，在表的左右进行跳跃式探测，比较灵活。

③ 伪随机探测再散列

di = 伪随机数序列

具体实现时，应建立一个伪随机数发生器，（如i=(i+p) % m），并给定一个随机数做起点。

例如，已知哈希表长度m=11，哈希函数为：H（key）= key % 11，则 H（47）=3，H（26）=4，H（60）=5，假设下一个关键字为69，则H（69）=3，与47冲突。

如果用线性探测再散列处理冲突，下一个哈希地址为 H1=（3 + 1）% 11 = 4，仍然冲突，再找下一个哈希地址为 H2=（3 + 2）% 11 = 5，还是冲突，继续找下一个哈希地址为 H3=（3 + 3）% 11 = 6，此时不再冲突，将69填入5号单元。

如果用二次探测再散列处理冲突，下一个哈希地址为 H1=（3 + 12）% 11 = 4，仍然冲突，再找下一个哈希地址为 H2=（3 - 12）% 11 = 2，此时不再冲突，将69填入2号单元。

如果用伪随机探测再散列处理冲突，且伪随机数序列为：2，5，9，………，则下一个哈希地址为 H1=（3 + 2）% 11 = 5，仍然冲突，再找下一个哈希地址为 H2=（3 + 5）% 11 = 8，此时不再冲突，将69填入8号单元。

6.2、再哈希法（再散列法）

这种方法是同时构造多个不同的哈希函数：

Hi=RH1（key） i=1，2，…，k

当哈希地址Hi=RH1（key）发生冲突时，再计算 Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

6.3、链地址法（拉链法）

这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

HashMap 解决 hash 冲突就采用的这种方式！

7、使用java如何对一个大的文本文件内容进行去重?

一般可能会想到一次将文本内容读取到内存中，用 HashSet 对内容去重，但是很不幸这个过程 jvm 会内存溢出，无奈，只能另想办法，首先将这个大文件中的内容读取出来，对每行 String 的 hashCode 取模取正整数，可用取模结果作为文件名，将相同模数的行写入同一个文件，再单独对每个小文件进行去重，最后再合并。

8、MySQL如何优化慢查询？

首先可以通过 explain 命令查看 SQL 执行状态，如果是没有加索引，则需要添加索引后再进行查询。如果已经加了索引，但是表中数据量过多，这时候可以考虑水平分表，或者通过 limit 限制一次查询的记录总数。如果已经加了索引，表中数据量较少，但是表字段多，大字段检索效率慢，这时候可以考虑垂直分表！

总结

本篇文章的内容就到这了，希望大家可以多多关注我们的其他精彩内容！