map是由什么实现的,你知道红黑树与AVL树的区别吗?
map底层采用红黑树。有人说自从红黑树出来之后,AVL树就被放进了博物馆,其实不然,在我看来,没有谁好谁坏,只有谁更适合。
AVL树中任何左右子树的高度差值不超过1,它是严格意义上的高度平衡树。查找、插入、删除在平均和最坏情况下的时间复杂度都是(log2 n),增加和删除可能需要通过一次或多次旋转来重新平衡这个树。
红黑树的查询性能略微逊色于AVL树,因为他比AVL树会稍微不平衡最多一层,也就是说红黑树的查询性能只比相同内容的AVL树最多多一次比较,但是,红黑树在插入和删除上完爆AVL树,AVL树每次插入删除会进行大量的平衡度计算,而红黑树为了维持红黑性质所做的红黑变换和旋转的开销,相较于AVL树为了维持平衡的开销要小得多。
为什么像map、set都用红黑树实现,你有听过skip-list吗?
map、set的实现只是折衷了两者在search、insert以及delete下的效率。总体来说,RB-tree的统计性能是高于AVL的。理由如下:
1. 如果插入一个node引起了树的不平衡,AVL和RB-Tree都是最多只需要2次旋转操作,即两者都是O(1);但是在删除node引起树的不平衡时,最坏情况下,AVL需要维护从被删node到root这条路径上所有node的平衡性,因此需要旋转的量级O(logN),而RB-Tree最多只需3次旋转,只需要O(1)的复杂度。
2. 其次,AVL的结构相较RB-Tree来说更为平衡,在插入和删除node更容易引起Tree的unbalance,因此在大量数据需要插入或者删除时,AVL需要rebalance的频率会更高。因此,RB-Tree在需要大量插入和删除node的场景下,效率更高。自然,由于AVL高度平衡,因此AVL的search效率更高。
用过vector.reserve()吗,vector的数组是怎么增长的?
vector.reserver()增加了vector的capacity,但是它的size不会改变。它为vector预留空间,但在空间内并不真正创建元素对象,所以在没有添加新的对象之前,不能引用容器内的元素。加入新的元素时,要调用push_back()或insert()。
vector通过一个连续的数组存放元素,如果集合已满,在新增数据时,就要分配一块更大的内存,将原来的数据拷贝过来,释放之前的内存,最后插入新增的元素。不同的版本实现的扩容方式不同,SGI版本是以1.5倍扩容,PJ是以2倍扩容。
map-reduce了解过吗,能否简单说一下?
map和reduce简单来说,就是把一些数据通过map归类,通过reduce将同一类的数据进行处理。
map-reduce之所以有效基于两点:① 大而化小 ② 异而化同。这两点应对了大数据中的volume和variety的挑战。
假设我们手上有许多复杂数据,第一步就是分类,分类后的数据就会简化,这就是异而化同;第二步是分割,把数据切分成小块,这样就可以并发或批量处理,这就是大而化小。
回到map-reduce的概念上,map的工作就是切分数据,然后将它们分类,分类的方式就是输出key、value键值对,key对应类别。分类之后,reducer拿到的都是同类数据,这样处理就很容易了。
Linux中目录权限644代表什么意思,目录有可执行权限代表什么?
目录权限分别对应所有者、所属组、其他人的权限,在linux中:4-->read,2->write,1->execute,即读权限、写权限、可执行权限。644代表如下:
1 2 3 4 5 |
1.文件所有者可读、可写、可执行 2.所属组可读、可执行 3.其它人可读、可执行 |
当我们进入一个目录时(普通用户),必须要有可执行权限。
了解awk、grep的用法吗,平时用gdb调试程序吗?
sed工具的使用方法 awk工具的使用方法 gdb多线程、多进程调试
如何实现TCP的拥塞控制、可靠传输?
数据库的ACID分别代表什么,原子性的定义?
Atomicity 原子性、Consistency 一致性、Isolation 隔离性、Durability 持久性。
原子性:用于标识事务是否完全地完成,一个事务的任何更新要在系统上完全完成,如果由于某种原因出错,事务不能完成它的全部任务,系统将返回到事务开始前的状态。
发表于2019-08-23 12:29 沙发
求二面面经