阿里搜索引擎
1.大量url，如何去重
问题：
有大量的字符串格式的URL，如何从中去除重复的，优化时间空间复杂度
1）. 内存够用，将URL存入hash链表，每个URL读入到hash链表中，遇到重复的就舍弃，否则加入到链表里面，最后遍历得到所有不重复的URL。空间复杂度M，时间复杂度为O(N+N/M)，M为不重复的URL，N为总URL数，但是M无法预测，所以存在风险，可能内存不足以存储所有的不重复URL。
2）为了解决内存可能不足的问题，需要把hash链表变化成普通的hash表，每个hash表元素指向一个文件文件，这个文件记录了所有该hash值对应的无重复的URL，那么在加入URL的时候就遍历对应文件中的URL，没有重复则加入到文件中。这样做时间复杂度没有提升，但是每次都要读写文件，消耗的时间应该是上一种方式的三倍（依赖于io速度），而对内存的要求比较小。一个改进是加入URL的时候进行排序，这样能减少比对的次数。
2.普通成员函数寻址的方式
普通的成员函数在被调用时有两大特征：
1） 普通的成员函数是静态绑定的，
2 ）普通的成员函数调用时编译器隐式传入this指针的值。
3.C++变量存储位置
C语言在内存中一共分为如下几个区域，他们分别是：
1 ）内存栈区： 存放局部变量名；
2 ）内存堆区： 存放new或者malloc出来的对象；
3 ）常数区：存放局部变量或者全局变量的值；
4 ）静态区： 用于存放全局变量或者静态变量；
5 ）代码区： 二进制代码。
栈区（stack）:程序运行时由编译器自动分配
存放:函数的参数值，局部变量的值。
存储连续，其操作方式类似于数据结构中的栈。
栈区处于相对较高的地址以地址的增长方向为上的话，栈地址是向下增长的，所以空间有限，windows下大多1-2M。
堆区（heap）: 在内存开辟另一块存储区域。一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收 。
存放：程序员申请的内存空间。
存储不连续，数据结构中的堆是两回事，类似于链表，受限于虚拟内存，32bit系统可达到4G。
堆区是向上增长的用于分配程序员申请的内存空间。
全局区（静态区）（static）—编译器编译时即分配内存。
全局变量和静态变量的存储是放在一块的，
初始化的全局变量和静态变量在一块区域，
未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。
程序结束后由系统释放。
附：静态局部变量只对自己定义的函数体可见。
静态全局变量具有文件作用域，两个不同的源文件可以名字相同的静态全局变量，表示两个变量。
而全局变量定义的源文件需要用extern 关键字再次声明这个全局变量。
只读区
常量区:常量字符串就是放在这里的。程序结束后由系统释放。
程序代码区:存放函数体的二进制代码。
栈中的存储内容
栈： 在函数调用时进栈顺序
a.主函数中函数调用后的下一条指令（函数调用语句的下一条可执行语句）的地址
b.数的各个参数，在大多数的C编译器中，参数是由右往左入栈的
c.然后是函数中的局部变量。（注意静态变量是不入栈的，在全局区）。
出栈顺序，逆序。
**堆的内容：**堆的头部用一个字节存放堆的大小
//main.cpp
int a = 0; 全局初始化区
char *p1; 全局未初始化区
main()
{
int b;// 栈
char s[] = "abc"; //栈
char *p2; //栈
char *p3 = "123456"; 123456\0";//在常量区，p3在栈上。
static int c =0； //全局（静态）初始化区
p1 = (char *)malloc(10);
p2 = (char *)malloc(20);
//分配得来得10和20字节的区域就在堆区。
strcpy(p1, "123456"); //123456\0放在常量区，编译器可能会将它与p3所指向的"123456"优化成一个地方。
}
从浏览器输入一个URL（www.baidu.com）的全过程
1.根据域名到DNS中找到IP
2.根据IP建立TCP连接(三次握手)
3.连接建立成功发起http请求
4.服务器响应http请求
5.浏览器解析HTML代码并请求html中的静态资源（js,css）
6.关闭TCP连接（四次挥手）
7.浏览器渲染页面
一、解析DNS域名
1.浏览器查找自己的DNS缓存，如果有直接返回，如果没有进行步骤二
2.操作系统查找自己的DNS缓存，如果有直接返回给浏览器，如果没有进行步骤三
3.操作系统查找自己的本地host文件，如果有返回给浏览器，如果没有则进行步骤四
4.操作系统向本地域名服务器发起请求，查找本地DNS缓存，如果有，返回给操作系统，然后操作系统返回给浏览器，如果没有进行步骤五
5.操作系统向根域名服务器发起请求得到顶级域名服务器的IP，然后根域名服务器向顶级域名服务器发起请求得到权限域名服务器的IP，顶级域名服务器再向权限域名服务器发起请求得到IP，本地域名服务器返回给操作系统IP，同时将IP缓存起来，操作系统将IP返回给浏览器，同时将IP缓存起来。
二、过程中使用到的协议
该过程中使用到了ARP,IP,SOFP
ARP（地址解析协议）：他主要解决的是同一个局域网内主机或路由器IP地址和MAC地址之间的映射问题。
工作过程：当源主机要发送数据的时候，他会查看自己的ARP高速缓存中是否有目的主机IP地址对应的MAC地址，如果与，则直接发送，如果没有，他就会向本网段所有主机发送ARP请求分组，接到请求的主机查看目的IP与自己的IP是否相等，如果不等就忽略，如果相等，就把源主机的IP和MAC写入自己的ARP高速缓存，如果之前有就覆盖掉，然后把自己的MAC写入ARP相应包，源主机接到ARP响应包后把目的主机的IP和MAC地址写入ARP高速缓存，并且利用此信息发送数据。
路由选择协议
1.内部网关协议
1)RIP协议
RIP基于UDP的应用层协议，他认为一个好的路由是他通过的路由器少，RIP允许一条路径最多可以包含15个路由，16个即为不可达了。
工作过程：假设路由器R0向R1发送一个报文段
首先修改R0发来的RIP报文中所有的项目，把吓一跳字段的地址改为R0，把所有距离字段值加1，
对于修改后的RIP报文的每一项进行如下步骤，
步骤一、首先看原来的路由表中是否有目的网络N，如果没有直接加入到路由表中，如果有进行步骤2
步骤二、然后看吓一跳，如果吓一跳的地址是R0则用新的项目替换原来的项目，如果吓一跳不同则进行步骤三
步骤三、对比距离，如果距离小于源路由器的项目，那么更新，否则什么都不做。
首先将R0发来的路由更新信息的距离都+1，下一跳都改为R0
Net1在源路由表中没有所以直接写入，Net2中吓一跳相同，直接覆盖原路由表中的Net2那一行，Net3的吓一跳不同，所以选择路径最小的。
2）OSPF(最短路径优先)
OSPF是网络层协议基于IP，当路由的链路状态发生变化时，他会使用洪泛法向本自治系统中所有路由发送自己的的链路状态（链路状态就是自己和那些路由相邻）
2.外部网关协议
BGP
BGP是不同自治系统路由器之间交换路由信息的协议，他只是力求寻找能达到目的网络的比较好的协议，而并非最佳路由。
BGP发言人：每一个自治系统的管理员都需要至少有一个路由器作为BGP发言人，BGP发言人一般是边界路由器，当然也有不是边界路由器的情况。
BGP交换路由信息：BGP发言人如果想和别的自治系统的BGP发言人交换信息（到达某个网络所要经历的一系列AS），他需要先建立起TCP连接，连接建立成功后在此链接上交换BGP报文，建立BGP会话，使用TCP是因为可以提供可靠的服务，也简化了路由选择协议。
三、HTTP报文格式
Http请求报文结构
http报文结构由请求行，请求头，空行、请求正文组成（Get请求，没有请求正文）
请求行：请求方法、url、版本号
请求头：Host:接收请求的服务器地址，可以是ip也可以是端口号
User-Agent：发送请求的应用程序名称
Connection:指定与连接相关的属性，Connection:Keep-Alive
Accept-Charset:指定可接收的编码格式
Accept-Encoding:指定可接收的数据压缩格式
Accept-Language:指定可以接收的语言
空行：表示请求头结束
请求正文：可选，get就没有请求正文
Http响应报文结构
http响应报文由状态行、响应头、空行、响应正文四部分组成
状态行：协议版本、状态码、状态描述，之间用空格分开
响应头：Server:服务器应用程序软件的名称和版本号
Content-Type:相应正文的类型（是图片还是二进制）
Content-Length:相应正文的长度
Content-Charset:相应正文的使用编码
Content-Encoding:相应正文使用的数据压缩格式
Content-Language:相应正文使用的语言
空行：表示响应头结束
响应正文
四、C++智能指针（及循环引用）
所谓智能指针？
所谓的智能指针就是智能/自动化的管理指指针所指向的动态资源的释放。
智能指针的产生是由于C++中没有内存的自动回收机制，每次new出来的空间都需要delete，而个别情况下，总是无法及时的delete，或者异常导致程序提早退出，造成内存泄漏，故而产生智能指针。
智能指针的发展可分为三个阶段
（1）auto_ptr c++98
（2）scoped_ptr/shared_ptr/weak_ptr boost库
（3）unique_ptr/shared_ptr/weak_ptr c++11
1、auto_ptr
auto_ptr实际上是管理权限的转移，此设计本身带有缺陷，建议什么情况下都不要使用。
#include<iostream>
using namespace std;
template <typename T>
class Auto_ptr
{
public:
Auto_ptr(T* ptr = 0)
:_ptr(ptr)
{
}
Auto_ptr(Auto_ptr<T>& p)
:_ptr(p._ptr)
{
p._ptr = NULL;
}
~Auto_ptr()
{
delete _ptr;
}
Auto_ptr<T>&operator=(Auto_ptr<T>&p)
{
if (_ptr != p._ptr)
{
if (_ptr)
{
delete _ptr;
}
_ptr = p._ptr;
p._ptr = NULL;
}
}
T& operator*()
{
return *_ptr;
}
T& operator->()
{
return _ptr;
}
private:
T* _ptr;
};
int main()
{
Auto_ptr<int> p1(new int(10));
cout << *p1 << endl;
Auto_ptr<int> p2(p1); //p1拷贝构造出p2
cout << *p1 << endl; //再次访问p1的空间
system("pause");
return 0;
}
auto_ptr的核心思想就是管理权限的转移，通过赋值运算符的重载或拷贝构造时，把p1置空，即将p1开辟的空间的管理权限转交给p2后，我们进行简单操作时并不会有问题：
2、scoped_ptr
scoped_ptr又叫守卫指针，用来防止拷贝，可以解决Auto_ptr的问题。
解决的方法：
（1）拷贝构造和赋值运算符的操作可以只声明，不定义。
（2）将声明为私有，防止定义。
template<class T>
class Scoped_ptr
{
public:
Scoped_ptr(T*ptr)
:_ptr(ptr)
{
}
~Scoped_ptr()
{
if (_ptr)
{
delete _ptr;
}
}
T& operator*()
{
return *_ptr;
}
T* operator->()
{
return _ptr;
}
private:
Scoped_ptr(const Scoped_ptr<T>& ptr);
Scoped_ptr<T>& operator=(Scoped_ptr& ptr);
private:
T* _ptr;
};
int main()
{
Scoped_ptr<int>p1(new int(1));
Scoped_ptr<int>p2(p1);
return 0;
}
3.shared_ptr
当auto_ptr和scoped_ptr都不能满足我们实际需求时，这是我们引入shared_ptr，它的主要思想是引入了引用计数，使得多个指针可以指向同一块空间，当最后一个指针释放时才真正释放这块空间。
template<class T>
class Shared_ptr
{
public:
Shared_ptr(T* ptr)
:_ptr(ptr)
,_count(new int(1))
{
}
~Shared_ptr()
{
Release();
}
Shared_ptr(Shared_ptr<T>& p)
:_ptr(p._ptr)
, _count(p._count)
{
(*_count)++;
}
Shared_ptr<T>operator=(Shared_ptr<T>& p)
{
if (_ptr != p._ptr)
{
Release(); //先释放*this中的指针指向的空间
_ptr(p._ptr);
_count(p._count);
(*_count)++;
}
return *this;
}
T& operator*()
{
return *_ptr;
}
T* operator->()
{
return _ptr;
}
void Release()
{
if (--(*_count) == 0)
{
delete _ptr;
delete _count;
_ptr = NULL;
_count = NULL;
}
}
int GetCount()
{
return *_count;
}
T* GetPtr()const //获取指针
{
return _ptr;
}
private:
T* _ptr;
int* _count;
};
int main()
{
Shared_ptr<int> p1(new int(1));
Shared_ptr<int> p2(p1);
*p1 = 10;
cout << *p1 << endl;
cout << p1.GetCount() << endl;
cout << p2.GetCount() << endl;
system("pause");
return 0;
}
上面的代码虽然简单的实现引用计数版的简化版智能指针Shared_ptr;但是存在着以下问题：
（1）引用计数更新存在着线程安全。
（2）循环引用的问题。
（3）定制删除器。
转载：https://blog.csdn.net/qq_35927741/article/details/117304355