经过漫长的等待后，果然头条的面试挂掉了。突然发现自己打了这么久的ACM，很多基础数据结构的概念掌握的还不是非常的牢固。这些数据结构可能并不难，特别是跳表和线段数组这样的数据结构，但是由于平日的疏忽导致这些概念有少许的以往。那么今天就要对这些掌握不是特别牢固的数据结构一一进行总结。

一 跳表

 跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。

 跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。

 跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。

 假设每M个元素构建索引，元素链表中总共有N个元素，那么构建的索引数如下：

第一级有：n/M 个
第二级有：n/(M^2)个元素
…….
第k级有：n/(M^k)个元素

 假设第k级为最后一级则可知，n/(M^k) = M, k = logn - 1, 再加上原始链表总共logn级平均每级搜索元素个数 = M + 1 ;

时间复杂度 = O(log(n))

空间复杂度 = n/M + n/(M^2) + … + n/(M^k) = O(n)

引用自简书liuzhengqiu

二 线段树

 了解线段树前我们需要了解二叉树，线段树是二叉树的一种，他是一颗二叉搜索树。线段树上的每一个节点代表一个区间，同样也可以理解为一个线段，搜索则是在这些线段上进行搜索从而获得答案。

 为了进一步的学习线段树，我们首先需要了解线段树的功能是什么，有过OI基础/ACM基础的同学们通常会认为线段树主要用于处理区间查询问题。但是在实际应用中可能线段树的功能比区间查询更加丰富，当然这里我们还是需要从区间查询问题开始说起。

更新点，查询区间

更新区间，查询点

更新区间，查询区间

 通常来说，利用线段树处理的问题分为上面三种，通常而言线段树的时间复杂度是O(log2(N))，线段树的空间复杂度<4n。下面通过一张图来显示线段树每个节点储存的信息，例子采用的是区间长度为10的数组。

 可以发现，每个叶子结点的值就是数组的值，每个非叶子结点的度都为二，且左右两个孩子分别存储父亲一半的区间。每个父亲的存储的值也就是两个孩子存储的值的最大值。

 通过对上图的观察我们现在可以清晰的了解线段树点更新，区间更新，点查询，区间查询的方法。具体的代码需要在网上寻找，每个人都有自己独特的写法，如果是竞赛选手，强烈建议形成自己的一套模板。

参考CSDN代码

三 线段数组

 要了解线段数组，我们需要先了解树状数组，顾名思义，树状数组即利用数组构建树形结构。这种结构相比树形结构可以极大程度的降低内存的消耗，故在比赛中我们常常利用树状数组来解决线段树的问题，而不是动态开点。

 与普通的线段树相同，利用线段数组可以轻松的完成区间的修改、查询。他的复杂度和线段树相同均为O(logN)，但是相比线段树，树状数组拥有更小的常数，所以最终运行的速度更快。

四 红黑树

红黑树具有下面五种特征：

性质1：每个节点要么是黑色，要么是红色。

性质2：根节点是黑色。

性质3：每个叶子节点（NIL）是黑色。

性质4：每个红色结点的两个子结点一定都是黑色。

性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

 红黑树是一种特殊的二叉平衡树，它通过左旋，右旋和变色来保持自平衡。他是一个非常负责的数据结构，在本篇中仅简单介绍其功能。更加丰富的内容日后会开专题介绍。

 刚刚经历了大学以来的第一次面试，不得不说头条作为宇宙厂面试有非常高的难度，平日进行的简单开发和底层的深入理解不可而与，为了更加透彻的理解进程与线程，这里特别对进程和线程相关的知识进行总结。并且利用准确的术语来表述进程和线程的特点以及关系。

一 进程的基本概念

 进程是并发执行的程序在执行过程中分配和管理资源的基本单位，是一个动态概念，竞争计算机系统资源的基本单位。作为一个程序执行的一个实体，是系统分配资源的基本单位。

 进程通信主要有五种通信方式，分别是管道、命名管道、信号量、消息队列、共享内存。

二 线程的基本概念

 线程是进程的一个执行单元，是进程的一个特定执行路径。当一个线程修改了进程的资源，同一个进程下的其他线程将会立即看到这种变化。

 相较于进程，由于线程共享进程中的全局变量，所以通常而言不需要特别的线程通信方式，在C/C++中我们常利用volatile关键词使编译器不对代码段进行优化，无需将该值放入寄存器中，使该值可以被外部改变。或者利用windows消息队列进行线程通信。此外还可以利用std中std::promise、std::packaged_task来进行线程通信。

三 进程和线程的主要区别及优势

区别：

1.代码段、内存:进程间相互独立，同一进程的各线程间共享。线程仅在同一个进程内可见。

2.通信：进程间通信IPC（管道、命名管道、信号量、共享内存、消息队列），线程间通信相对进程间通信更为简单，直接使用全局变量即可。但是使用时需要考虑锁机制和同步机制。

3.调度和切换：线程上下文切换比进程上下文切换快得多。

4.在多线程OS中，进程不是一个可执行的实体。

选择：

1.需要频繁创建销毁的优先使用线程；因为对进程来说创建和销毁一个进程的代价是很大的。

2.线程的切换速度快，所以在需要大量计算，切换频繁时使用线程，还有耗时的操作时用使用线程可提高应用程序的响应。

3.因为对CPU系统的效率使用上线程更占优势，所以可能要发展到多机分布的用进程，多核分布用线程。

4.并行操作时用线程，如C/S架构的服务器端并发线程响应用户的请求。

5.需要更稳定安全时，适合选择进程；需要速度时，选择线程更好。

资源引用：什么是进程？什么是线程？进程和线程之间的区别是什么？

 在学校里学习计算机网络的过程中，由于《计算机网络》课本内容较为底层基础，许多人在学习完这本书后都会产生一定的困惑。譬如，现在互联网有哪些地方运用到了哪些协议，这些协议最新的标准是什么样子的等等。为了解决心中的困惑，我决定先对日常中最常用的http-web中所采用的协议进行更深一步的了解，为此我在图灵社区中购置了《图解http》一书。接下来将按照自己的思路从书中获取一些问题的答案。

 本文是购置该书籍后发表的第一篇记录，在这篇记录里，我将揭秘在浏览器中输入url后发生的一系列事情。

浏览器中输入url后主要会发生下面的几件事

一 负责域名解析的DNS服务

 计算机可以被赋予ip地址，同样的也可以被赋予主机名和域名。例如本博客的ip地址是185.199.109.153（github io服务器地址），域名地址为 blog.100innovate.com。我们通常使用域名去访问不同的计算机和网站，域名相比一串数字来说更有利于人们的记忆，但是计算机更擅长于处理ip地址这样的数字。

 为了解决计算机和人的矛盾，DNS服务在这个时候就产生了，通过DNS服务我们可以通过域名查询ip，或者利用ip查询域名。（通常而言，人们仅利用域名查询ip，很少利用ip查询域名）

 在浏览器中输入url并键入回车后的第一步，浏览器将会向DNS服务器发送查询请求，从而获取目标服务器的ip地址。

二 互联网的基础TCP/IP协议

 计算机想要相互通信，就需要一个标准的数据交换协议，这个协议就是TCP/IP协议。通常而言浏览器访问web网站时采用的是TCP协议，TCP协议是一种面向连接的、可靠的、基于字节流的传输层通信协议，为了保证通信的可靠新，首先需要进行三次握手，三次握手的主要流程为：

1.客户端向服务器端发送SYN标记的数据包

2.服务器端向客户端发送SYN/ACK标记的数据包

3.客户端向服务器端发送ACK标记的数据包

 采用三次握手而不是两次握手有许多原因，原因之一是防止延期到达的数据包传输到服务器，服务器会因此创建一个无效的连接。

三 通过HTTP协议传输数据

 HTTP协议的职责是生成针对目标Web服务器的HTTP请求报文，主要有如下的请求方法：

GET:获取资源

POST:传输实体主体

HEAD:获取报文首部

PUT:传输文件

DELETE:删除文件

OPTIONS:询问支持的方法

TRACE:追踪路径

……

 利用上述的数种请求报文向服务器发送请求报文，从而获取用户需要访问的内容。请求报文主要包含请求方法、URI、协议版本三个信息。

 在向服务器发送完请求报文后，服务器会返回请求的结果。当然每一次返回的结果并非绝对正确，为了表达服务器对用户请求的各种状态，http协议设置了规定了状态码，通过返回状态码告知浏览器服务器处理的情况，状态码通常的定义如下：

 通常来说，只要遵守上述状态码的规则，服务提供商可以自行创建状态码。

 通过上述请求协议和服务器返回报文，最终浏览器可以获得用户需要的数据和信息。

四 浏览器解析并渲染页面

 在浏览器成功获取html信息后，将会按照顺序从头至尾解析html文件，在解析到外部的css、js等其他外部资源文件的时候，根据服务器、浏览器的版本不同将会直接向服务器请求资源文件，或者重新建立TCP连接，然后请求资源文件。值得一提的是，在解析html文件时，浏览器将会构建DOM树，为了加速这一过程，浏览器还会使用预解析等功能。

 在完成html的解析后，浏览器还需要根据浏览器的窗口位置等信息，逐像素的将网页绘制出来。最终我们可以获得想要看到的网页。

五 小结

 通过对《图解http》进行全篇大致浏览，解决了一大问题。但是需要学习的仍然还有人多，譬如现代浏览器一些处理机制问题以及近年来我们常常使用的https与http有什么不同，这些疑惑就留到日后逐一破解。