红黑树是什么样的数据结构？红黑树和B🌲的区别？

红黑树是一个近似平衡的二叉查找树。它具有以下四个要求，而且后续的平衡调整操作都是按照这四个要求来调整的。

根节点是黑色的
叶子节点不存储数据，而且是黑色节点
不存在相邻的红色节点，红色节点一定有黑色节点隔开
每一个节点，该节点到达其可达的叶子节点的所有路径，包含的黑色节点数目都是相同的。

B树，是低级版的B+树，我们现实开发中多使用B+树，为什么呢？因为他实现了高效的查询，删除，插入以及修改功能。为什么呢？

B+🌲存储的是数据的索引，而红黑树存的是数据
B+🌲一般用于数据库的设计，红黑树用于数据的存储，查找
B+🌲对数据的查询是通过索引，设计的结构，最后叶子节点通过链表链接起来，而红黑树最后的叶子节点是不存储数据的
B+树是一棵m叉🌲，有多个叉，其实多个叉是为了让数据对磁盘的读写性能的提高，毕竟叉多了，高度就降低了。红黑树是一个二叉树
对比红黑树的左右旋调整，B+树通过分裂节点或者合并节点来调整，以支持读写效率不会退化得太严重
B+树，m叉🌲，节点不能超过m，但是不小于m/2

变量的定义和声明有什么区别？声明的关键字？（extern）

先来看看一段代码

int i; // 这就是声明
int de_ = 42; // 这就是定义

区别是什么？emmm，不能这么看...这题考的是分离式编译，C++支持 分离式编译。因为这种分离式编译使得每个文件可以被独立编译。而代码共享的方案，就是将声明与定义可以区分开。例如std::cout与std::cin，定义于标准库，却被我们写程序使用。

声明，使得名字为程序所知，一个文件如果想使用另外一个文件的名字，则必须包含对这个名字的声明
定义，负责创建与名字相关联的实体

声明定义了变量和名字，而定义除此之外，还申请了存储空间，也可能会为变量赋予一个初始值。
因此，如果想声明一个变量而不是定义它就可以如下操作

extern int i; // 声明而非定义
int j;// 声明并定义j

如果多个文件需要使用同一个变量，那么就需要把声明与定义分离。这样变量的定义就只能出现在一个文件当中。
那么模版为什么不支持分离式编译呢？因为存在一个实例化的过程。因为在编译器编译到执行文件，需要经过编译，链接，生成可执行文件。那么在编译的过程中，需要调用一个函数就会有一条call指令，在链接的时候去其他文件寻找fact函数的具体实现，如果找不到这样一个fact函数，就会发生一个连接期的错误。那么模版呢？模版是需要实例化没实例化都会有不同的实现方式。分离式编译的时候，某个模版的未被使用，所以不会产生相应的代码段，链接的时候，编译器就链接不上，所以就出错了。所以一般来说，模版实现和模版的声明是写在一起的。

malloc的认识？new的具体实现机制是什么样的？（先分配内存，再调用构造函数）

malloc是C的分配内存的做法。malloc在底层中是采取先预定内存，即分配一个空指针，等到使用的时候，就给你凑齐内存来给你分配。
先来看看malloc的函数吧

void *malloc(size_t size);

malloc分配指定字节数的存储区。此存储区的初始值不确定。动态分配内存，与free一起使用。动态分配的都是链表分配。
那么new呢？new在堆中申请了一个新内存空间，调用构造函数，返回指针。emmm

A* pa = new A();// 就等于

就等于这样

A *pa = (A*)malloc(sizeof(A));
pa->A();
return pa;

就等于申请了一个内存空间，得到一个有效的指向堆上的A对象的指针。但是区别在于malloc失败时候，他不会调用分配内存失败处理程序new_handler，直接返回null，而使用new是会调用new handler。new operator,operator new,placement new是C++一贯使用的new含义。

new operator就是我们平常使用的new 一般不建议修改
operator new就是在new operator完成的。这里的new是可以重载的

/***
 * 其实operatornew是可以重载的，就是调用分配内存的代码
 ****/
void *operator new(size_t size){
    return malloc(size);
}

其实重载了new最好一起重载delete，上帝说，打了左脸请继续打我右脸一样。

placement new就是用来定位构造的。取得了内存之后，就开始在这块内存上构造一个对象

要引用<new>其实不太建议使用这些操作，因为在真正的工业开发，并不会实现，会造成使用的不方便，而且实现了placement new还要手工实现析构函数。麻烦。

哈希冲突的解决算法？（开放地址法和拉链法）一致哈希了解吗？

开发寻址法和拉链法。开放寻址法，为了更好的处理散列冲突，一般会使用二次探测与双重散列。

二次探测是指二次方探测位置，hash(key)+n^2
双重散列是指用多个散列函数探测空槽，一个散列找不到，就找第二个继续计算，然后继续找空位，如此循环。

一致性哈希有了解，他是处理分布式存储的。可能有n多的数据请求到达数据库，我们通过hash处理，将数据分片到相应的数据库，并请求访问相应的数据库，但是，如果数据量过大，导致需要增加数据库，那么原来的hash函数就不起作用了，这样，就会造成所有的请求直接请求数据库，导致，数据库有些请求不过来，压垮数据库，造成雪崩效应。这时就需要一致性哈希的存在。一致性哈希可以解决分布式存储的情况下，动态增加或者删除节点而带来的类似雪崩的问题。

一致性哈希通过环形设计，将通过哈希击中的缓存，能够不会受到太大的影响。例如一个节点增加了一个数据库，那么相应的哈希就会根据哈希运算查找到下一个后继节点作为数据库，也就是击中新增加的数据库。如果删除了一个节点，相应的，哈希就会寻找下一个数据库作为后继节点，如此运算，就能将分布式存储的数据库都充分利用。要是导致所有的哈希都访问了同一个数据库，其实一致性哈希通过引入虚拟节点解决这个问题，通过物理节点映射虚拟节点，这样虚拟节点就对应相应的hash，这样做，有利于均衡整个hash环。

Provide feedback

Saved searches

Use saved searches to filter your results more quickly