[数据结构与算法] 面经总结（五）

????????一致性Hash算法也是使用取模的方法，不过，上述的取模方法是对服务器的数量进行取模，而一致性的Hash算法是对2的32方取模。即，一致性Hash算法将整个Hash空间组织成一个虚拟的圆环，Hash函数的值空间为0 ~ 2^32 - 1(一个32位无符号整型)，整个哈希环如下：

?????????整个圆环以顺时针方向组织，圆环正上方的点代表0，0点右侧的第一个点代表1，以此类推。

????????第二步，我们将各个服务器使用Hash进行一个哈希，具体可以选择服务器的IP或主机名作为关键字进行哈希，这样每台服务器就确定在了哈希环的一个位置上，比如我们有三台机器，使用IP地址哈希后在环空间的位置如图1-4所示：

????????将数据Key使用相同的函数Hash计算出哈希值，并确定此数据在环上的位置，从此位置沿环顺时针查找，遇到的服务器就是其应该定位到的服务器。例如，现在有ObjectA，ObjectB，ObjectC三个数据对象，经过哈希计算后，在环空间上的位置如下：

?????????现在，假设我们的Node C宕机了，我们从图中可以看到，A、B不会受到影响，只有Object C对象被重新定位到Node A。所以我们发现，在一致性Hash算法中，如果一台服务器不可用，受影响的数据仅仅是此服务器到其环空间前一台服务器之间的数据（这里为Node C到Node B之间的数据），其他不会受到影响。如图1-6所示：

????????另外一种情况，现在我们系统增加了一台服务器Node X，也只有该节点附近的点才会受到影响。

????????一致性Hash算法对于节点的增减都只需重定位环空间中的一小部分数据，有很好的容错性和可扩展性。

????????面对数据倾斜问题：在一致性Hash算法服务节点太少的情况下，容易因为节点分布不均匀面造成数据倾斜（被缓存的对象大部分缓存在某一台服务器上）问题。一致性Hash算法引入了虚拟节点机制，即对每一个服务器节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。具体操作可以为服务器IP或主机名后加入编号来实现。

2、添加最少字符串成为回文串

class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        int dp[][] = new int [n][n];
        for(int i = n - 2;i >= 0;i--){
            for(int j = i + 1;j < n;j++){
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = dp[i + 1][j - 1];
                }else{
                    dp[i][j] = Math.min(dp[i + 1][j],dp[i][j - 1]) + 1;
                }
            }
        }
        return dp[0][n - 1];
    }
}

3、Mysql分页查询怎么实现的

? ? ? ? select * from student where name like '% wang' limit 1000,10;

4、java的浮点型数据为什么有精度损失

????????主要原因是因为浮点型不能用精确的二进制来表述，当数据存在小数时，就会不断的乘以2，以消除掉小数，或者直到拥有的位数用完，存在不断乘以2不能得到整数的小数。

5、ArrayList和LinkedList的区别?

是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
底层数据结构： Arraylist 底层使用的是动态的Object数组；LinkedList 底层使用的是双向链表数据结构（JDK1.6之前为循环链表，JDK1.7取消了循环。）
对于新增和删除操作add和remove，LinkedList比较占优势，因为ArrayList要移动数据。： ① ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 ② LinkedList 采用链表存储，所以插入，删除元素时间复杂度不受元素位置的影响，都是近似 O（1）而数组为近似 O（n）。
对于随机访问的get和set方法，ArrayList要优于LinkedList，因为LinkedList要移动指针： LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
内存空间占用： ArrayList的空间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）

6、CopyOnWriteArrayList的实现原理

????????安全的原因：加了锁，并且读写分离。先加锁，再复制一份，在复制的上面进行修改，修改结束将原先数组指向修改后的数组。

内部数据会被copy：当调用这个类的任何有关修改的操作的时候（比如add，remove），CopyOnWriteArrayList里面整个的内容都会被重新copy一份
读写分离：所以当我们做修改操作的时候，我们修改的是重新copy的一份数据同时依旧可以顺畅的迭代读取数组里面的内容。因为当我们调用iterator()函数的时候，其实得到也是一个CopyOnWriteArrayList内部内容的snapshot。
可能的数据延迟：这个snapshot是从iterator()调用的时刻起，被创建的，所以如果在同时有其他线程add or remove元素，这次迭代是看不到的,只有在后续操作中才可以。

????????应用场景：读多写少的并发场景，它读不加锁，性能很高。

缺点：

内存占用问题，毕竟每次执行写操作都要将原容器拷贝一份，数据量大时，对内存压力较大，可能会引起频繁GC；
无法保证实时性，CopyOnWriteArrayList由于其实现策略的原因，写和读分别作用在新老不同容器上，在写操作执行过程中，读不会阻塞但读取到的却是老容器的数据。
大量写操作性能极差。

7、ConcurrentHashMap怎么保证size的线程安全？

? ? ? ? 使用unsafe类进行cas操作以保证size的线程安全。用volatile关键字保证了变量的线程间可见性。其中有两个变量baseCount和counterCells数组，它俩中数字的和为size的值。

8、linux日志中查异常，并显示异常前后日志的内容的命令

查异常
 cat -n abc.log |grep Exception|more
 
	如找到行数为：5201314行，再查看该行前后的异常信息
 cat -n abc.log |tail -n +5201314|head -n 30

? ? ? ?| 则表示一个管道的意思，可以理解为东西从管道的一边流向另外一边。

????????cat 文件名 | grep? ?-10? ?"关键字"? ??注意? 这里的 -10? 表示关键字所匹配的日志前后10行

9、windows系统查看ip的指令

? ? ? ? ipconfig

10、讲一下linux系统的用户态与内核态

????????内核：本质上看是一种软件——控制计算机的硬件资源，并提供上层应用程序运行的环境。cpu可以访问内存的所有数据，包括外围设备，例如硬盘，网卡，cpu也可以将自己从一个程序切换到另一个程序。

????????用户态：上层应用程序的活动空间，只能受限的访问内存，且不允许访问外围设备，占用cpu的能力被剥夺，cpu资源可以被其他程序获取。应用程序的执行必须依托于内核提供的资源，包括CPU资源、存储资源、I/O资源等。为了使上层应用能够访问到这些资源，内核必须为上层应用提供访问的接口：即系统调用。

从用户态到内核态切换可以通过三种方式：

异常：当CPU正在执行运行在用户态的程序时，突然发生某些预先不可知的异常事件，这个时候就会触发从当前用户态执行的进程转向内核态执行相关的异常事件，典型的如缺页异常。
系统调用：其实系统调用本身就是中断，但是软件中断，跟硬中断不同。
外设中断（硬中断）：当外围设备完成用户的请求操作后，会像CPU发出中断信号，此时，CPU就会暂停执行下一条即将要执行的指令，转而去执行中断信号对应的处理程序，如果先前执行的指令是在用户态下，则自然就发生从用户态到内核态的转换。

11、用户态访问内核态资源的方式

系统调用
库函数
Shell脚本

12、JUC

????????在Java中，线程部分是一个重点，本篇文章说的JUC也是关于线程的。JUC就是java.util .concurrent工具包的简称。这是一个处理线程的工具包。

volatile关键字与内存可见性
CountDownLatch（闭锁）?是一个同步辅助类，在完成一组正在其他线程中执行的操作之前，它允许一个或多个线程一直等待
CyclicBarrier（栅栏）之所以叫barrier，是因为是一个同步辅助类，允许一组线程互相等待，直到到达某个公共屏障点，并且在释放等待线程后可以重用。
Semaphore（信号量）?是一个计数信号量，它的本质是一个“共享锁“。信号量维护了一个信号量许可集。线程可以通过调用 acquire()来获取信号量的许可；当信号量中有可用的许可时，线程能获取该许可；否则线程必须等待，直到有可用的许可为止。线程可以通过release()来释放它所持有的信号量许可。
executor(执行者)：是Java里面线程池的顶级接口，但它只是一个执行线程的工具，真正的线程池接口是ExecutorService，里面包含的类有：
- ScheduledExecutorService??解决那些需要任务重复执行的问题
- ScheduledThreadPoolExecutor? ?周期性任务调度的类实现
atomic(原子性包)：是JDK提供的一组原子操作类，包含有AtomicBoolean、AtomicInteger、AtomicIntegerArray等原子变量类，他们的实现原理大多是持有它们各自的对应的类型变量value，而且被volatile关键字修饰了。这样来保证每次一个线程要使用它都会拿到最新的值
locks（锁包）：是JDK提供的锁机制，相比synchronized关键字来进行同步锁，功能更加强大，它为锁提供了一个框架，该框架允许更灵活地使用锁包含的实现类有：
- ReentrantLock? ?它是独占锁，是指只能被独自占领，即同一个时间点只能被一个线程锁获取到的锁。
- ReentrantReadWriteLock? ?它包括子类ReadLock和WriteLock。ReadLock是共享锁，而WriteLock是独占锁。
- LockSupport 它具备阻塞线程和解除阻塞线程的功能，并且不会引发死锁。
collections(集合类)：主要是提供线程安全的集合，?比如
- ArrayList对应的高并发类是CopyOnWriteArrayList，
- HashSet对应的高并发类是?CopyOnWriteArraySet，
- HashMap对应的高并发类是ConcurrentHashMap等等

13、?HTTPS的工作原理

????????HTTPS在传输数据之前需要客户端（浏览器）与服务端（网站）之间进行一次握手，在握手过程中将确立双方加密传输数据的密码信息。TLS/SSL中使用了非对称加密，对称加密以及HASH算法。

握手过程的具体描述如下：

浏览器发起往服务器的443端口发起请求，请求携带了浏览器支持的加密算法和哈希算法。
服务器收到请求，选择浏览器支持的加密算法和哈希算法。
服务器下将数字证书返回给浏览器，这里的数字证书可以是向某个可靠机构申请的，也可以是自制的。
浏览器进入数字证书认证环节，这一部分是浏览器内置的TLS完成的：
- 首先浏览器会从内置的证书列表中索引，找到服务器下发证书对应的机构，如果没有找到，此时就会提示用户该证书是不是由权威机构颁发，是不可信任的。如果查到了对应的机构，则取出该机构颁发的公钥。
- 用机构的证书公钥解密得到证书的内容和证书签名，内容包括网站的网址、网站的公钥、证书的有效期等。浏览器会先验证证书签名的合法性（验证过程类似上面Bob和Susan的通信）。签名通过后，浏览器验证证书记录的网址是否和当前网址是一致的，不一致会提示用户。如果网址一致会检查证书有效期，证书过期了也会提示用户。这些都通过认证时，浏览器就可以安全使用证书中的网站公钥了。
浏览器生成一个随机数R，并使用网站公钥对R进行加密。
浏览器将加密的R传送给服务器。
服务器用自己的私钥解密得到R。
服务器以R为密钥使用了对称加密算法加密网页内容并传输给浏览器。
浏览器以R为密钥使用之前约定好的解密算法获取网页内容。

14、进程可以直接通信吗？

????????由于内存管理的一些机制，导致两个进程间并不能直接的进行通信.

15、进程间的通信方式

管道( pipe )：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。
有名管道 (named pipe) ：有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。
信号量( semophore ) ：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
消息队列( message queue ) ：消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
信号 ( sinal ) ：信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。
共享内存( shared memory ) ：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号两，配合使用，来实现进程间的同步和通信。
socket是应用层与TCP/IP协议通信的中间软件抽象层，是一组接口，复杂的TCP/IP协议隐藏在Socket接口后面。socket是一种“open-read/write-close”的模式实现，服务器和客户端各自维护一个“文件”，建立连接打开后可以向自己文件写入内容共对方读取或者读取对方的内容，通讯结束时关闭文件。是一种可以网间通信的方式。

16、https怎么加密，用到的加密算法是什么

????????HTTPS其实是有两部分组成：HTTP + SSL / TLS，也就是在HTTP上又加了一层处理加密信息的模块。服务端和客户端的信息传输都会通过TLS进行加密，所以传输的数据都是加密后的数据。

加密算法：

对称加密，有流式、分组两种，加密和解密都是使用的同一个密钥。例如：DES、AES-GCM、ChaCha20-Poly1305等
非对称加密：加密使用的密钥和解密使用的密钥是不相同的，分别称为：公钥、私钥，公钥和算法都是公开的，私钥是保密的。非对称加密算法性能较低，但是安全性超强，由于其加密特性，非对称加密算法能加密的数据长度也是有限的。
- 例如：RSA、DSA、ECDSA、 DH、ECDHE
哈希算法：将任意长度的信息转换为较短的固定长度的值，通常其长度要比信息小得多，且算法不可逆。例如：MD5、SHA-1、SHA-2、SHA-256 等
数字签名：签名就是在信息的后面再加上一段内容（信息经过hash后的值），可以证明信息没有被修改过。hash值一般都会加密后（也就是签名）再和信息一起发送，以保证这个hash值不被修改。

17、密钥与加密算法的区别

????????密钥是一种参数（它是在明文转换为密文或将密文转换为明文的算法中输入的数据），加密算法是明文转换成密文的变换函数，同样的密钥可以用不同的加密算法，得到的密文就不一样了。

18、osi七层模型每层分别干啥，有哪些协议

应用层：应用层的任务是通过应用进程之间的交互来完成特定网络应用。应用层协议定义的是应用进程间通信和交互的规则。这里的进程是指主机中正在运行的程序。对于不同的网络应用需要有不同的应用层协议。在互联网中的应用层协议有很多，如域名系统DNS，支持万维网应用的HTTP协议，支持电子邮件的SMTP协议，等等。应用层交互的数据单元是报文 (message)。
运输层：运输层的任务是负责向两台主机进程之间的通信提供通用的数据传输服务。运输层的协议主要有传输控制协议 TCP，它提供面向连接的、可靠的数据传输服务，数据传输单位是报文段(segment)；用户数据报协议 UDP，它提供无连接的、尽最大努力的数据传输服务，数据传输单位是用户数据报。
网络层：网络层的任务是负责为分组交换网上的不同主机提供通信服务，在发送数据时网络层把运输层产生的报文段或用户数据报封装成分组或包进行传送。网络层的另一个任务是选择合适的路由，使源主机运输层传下来的分组能够通过网络中的路由器找到目的主机。网络层的协议有 IP、ARP、ICMP、IGMP 等。网络层使用的中间设备是路由器。
数据链路层：数据链路层的任务是将网络层交下来的 IP 数据报组装成帧，在两个相邻结点之间的链路上传输帧，每一帧包括数据和必要的控制信息（同步信息、地址信息、差错控制等）。数据链路层的协议有 PPP、CSMA/CD 等。数据链路层使用的中间设备是网桥或桥接器。
物理层：物理层的任务是尽可能地屏蔽掉传输媒体和通信手段的差异，使物理层上面的数据链路层感觉不到这些差异，使其只需考虑本层的协议和服务。物理层所传输的数据单位是比特，发送方发送1或0，接收方也接收1或0，物理层需要考虑用多大的电压代表1或0。物理层使用的中间设备是转发器。
会话层(Session Layer)：会话层主要功能是管理和协调不同主机上各种进程之间的通信(对话)，即负责建立、管理和终止应用程序之间的会话。会话层得名的原因是它很类似于两个实体间的会话概念。例如，一个交互的用户会话以登录到计算机开始，以注销结束。结构化查询语言（ SQL, Structured Query Language ），网络文件系统（ NFS ， Network File System ），远程过程调用（ RPC ， Remote Procedure Call ）。
表示层(Presentation Layer):表示层处理流经结点的数据编码的表示方式问题，以保证一个系统应用层发出的信息可被另一系统的应用层读出。如果必要，该层可提供一种标准表示形式，用于将计算机内部的多种数据表示格式转换成网络通信中采用的标准表示形式。数据压缩和加密也是表示层可提供的转换功能之一。

OSI各层协议

应用层	DHCP · DNS · FTP · Gopher · HTTP · IMAP4 · IRC · NNTP · XMPP · POP3 · SIP · SMTP · SNMP · SSH · TELNET · RPC · RTCP · RTP ·RTSP · SDP · SOAP · GTP · STUN · NTP · SSDP
表示层	HTTP/HTML · FTP · Telnet · ASN.1（具有表示层功能）
会话层	ADSP·ASP·H.245·ISO-SP·iSNS·NetBIOS·PAP·RPC· RTCP·SMPP·SCP·SSH·ZIP·SDP（具有会话层功能）
传输层	TCP · UDP · TLS · DCCP · SCTP ·RSVP · PPTP
网络层	IP (IPv4 · IPv6) · ICMP · ICMPv6 · IGMP ·IS-IS · IPsec · BGP · RIP · OSPF ·ARP · RARP
数据链路层	Wi-Fi(IEEE 802.11) · WiMAX(IEEE 802.16) ·ATM · DTM · 令牌环 · 以太网路 · FDDI · 帧中继 · GPRS · EVDO · HSPA · HDLC · PPP · L2TP · ISDN ·STP
物理层	以太网路卡 · 调制解调器 · 电力线通信(PLC) · SONET/SDH（光同步数字传输网）?· G.709（光传输网络） · 光导纤维 · 同轴电缆 · 双绞线

?19、优先级队列的实现原理

????????优先队列是一种用来维护一组元素构成的结合S的数据结构，其中每个元素都有一个关键字key，元素之间的比较都是通过key来比较的。优先队列包括最大优先队列和最小优先队列，优先队列的应用比较广泛，比如作业系统中的调度程序，当一个作业完成后，需要在所有等待调度的作业中选择一个优先级最高的作业来执行，并且也可以添加一个新的作业到作业的优先队列中。Java中，PriorityQueue的底层数据结构就是堆（默认是小堆）。