当前位置: 首页>数据库>正文

倒排索引在技术中的应用 倒排索引的存储方式

1.倒排索引

倒排索引(Inverted Index):倒排索引是搜索引擎数据存储的结构与形式,是实现单词-文档矩阵的一种具体存储形式。通过倒排索引,我们可以根据单词快速的获取包含这个单词的文档列表。倒排索引主要由两个部分组成:单词词典和倒排文件。
2.讲讲redis里面的哈希表? 

在redis中,hash数据类型存储的数据与mysql数据库中存储一条记录极为相似,是一个string类型的field和value的映射表,它特别适合用于存储对象,但字段值只能是字符串,不支持其他类型。
在hash类型中,一个key可以对应多个多个field,一个field对应一个value。将一个对象存储为hash类型的好处之一:较于每个字段都单独存储成string类型来说,更能节约内存。
每一个哈希可以存储超过2的32次方-1个字段-值对。应用场景:可以用来存储用户的基本信息等。
3.happen-before的规则?

(1)程序顺序规则:一个线程中的每个操作,happens-before于该线程中的任意后续操作。
(2)监视器锁规则:对一个锁的解锁,happens-before于随后对这个锁的加锁。
(3)volatile变量规则:对一个volatile域的写,happens-before于任意后续对这个volatile域的读。
(4)传递性:如果A happens-before B,且B happens-before C,那么A happens-before C。
(5)start()规则:如果线程A执行操作ThreadB.start()(启动线程B),那么A线程的ThreadB.start()操作happens-before于线程B中的任意操作。
(6)Join()规则:如果线程A执行操作ThreadB.join()并成功返回,那么线程B中的任意操作happens-before于线程A从ThreadB.join()操作成功返回。
(7)程序中断规则:对线程interrupted()方法的调用先行于被中断线程的代码检测到中断时间的发生。
(8)对象finalize规则:一个对象的初始化完成(构造函数执行结束)先行于发生它的finalize()方法的开始。
4.volatile修饰符,synchronize锁

(1)、volatile保证共享变量的可见性,比Synchronized的使用和执行成本更低,因为它不会引起线程上下文的切换和调度;
(2)、一个字段被声明城volatile类型,java的线程内存模型确保所有线程看到这个变量的值是一致的;
(3)、java中的每一个对象都可以作为锁,任何对象都有一个monitor与之关联,当monitor被持有后,其对象处于锁定状态;
(4)、synchronized用的锁存储在java的对象头里;
(5)、javase 6 为了减少获得锁和释放锁带来的性能消耗,引入了偏向锁和轻量级锁,以及锁的存储结构及升级过程
5.java单例模式的实现,懒汉、饿汉?

懒汉式线程不安全,需要加上同步锁,同步锁影响了程序执行效率。
饿汉式天生线程安全,类加载的时候初始化一次对象,效率比懒汉式高。饿汉式:
设计思想:构造方法私有,这样就保证了在外部是无法实例化对象的;然后先在内部定义一个静态常量对象,再写一个static方法来返回这个对象,这样就保证是前后一个对象了。
区别 :饿汉式是先定义实例的 而懒汉式是先定义引用,当懒汉式第一次调用getInstance的时候 进行对象实例化操作;当然这里考虑到多并发的情况,多个线程同时调用这个方法的时候,会出现问题,所以加上同步锁 synchronized 来保证同一时刻只有一个线程进入方法。
6.进程与线程的区别,多进程和多线程的区别?

(1).概念 
线程:是程序执行流的最小单元,是系统独立调度和分配CPU(独立运行)的基本单位。 
进程:是资源分配的基本单位。一个进程包括多个线程。 

多线程:同一时刻执行多个线程。用浏览器一边下载,一边听歌,一边看视频,一边看网页。。。 
多进程:同时执行多个程序。如,同事运行YY,QQ,以及各种浏览器。

并发:当有多个线程在操作时,如果系统只有一个CPU,则它根本不可能真正同时进行一个以上的线程,它只能把CPU运行时间划分成若干个时间段,再将时间 段分配给各个线程执行,在一个时间段的线程代码运行时,其它线程处于挂起状。这种方式我们称之为并发(Concurrent)。
并行:当系统有一个以上CPU时,则线程的操作有可能非并发。当一个CPU执行一个线程时,另一个CPU可以执行另一个线程,两个线程互不抢占CPU资源,可以同时进行,这种方式我们称之为并行(Parallel)。
(2).区别: 
1).线程与资源分配无关,它属于某一个进程,并与进程内的其他线程一起共享进程的资源。 
2).每个进程都有自己一套独立的资源(数据),供其内的所有线程共享。 
3).不论是大小,开销线程要更“轻量级” 
4).一个进程内的线程通信比进程之间的通信更快速,有效。(因为共享变量)
7.HashMap原理,为什么用红黑树,红黑树的特点?

HashMap中的值都是key,value对吧,其实这里的存储与上面的很像,key会被映射成数据所在的地址,而value就在以这个地址为头的链表中,这种数据结构在获取的时候就很快。但这里存在的问题就是如果hash桶较小,数据量较大,就会导致链表非常的长。比如说上面的长为11的空间我要放1000个数,无论Hash函数如何精妙,后面跟的链表都会非常的长,这样Hash表的优势就不复存在了,反而倾向于线性检索。好了,红黑树闪亮登场。
红黑树也叫自平衡二叉查找树或者平衡二叉B树,
时间复杂度为O(log n)
高度h <= log2(n+1)
性质1. 节点是红色或黑色。  性质2. 根节点是黑色。  性质3 每个叶节点(NIL节点,空节点)是黑色的。
性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
8.快排时间空间复杂度,最好最坏的情况,优化方案?

平均情况和最好的情况的空间复杂度:O(log2n)
最坏情况的空间复杂度:O(n)
优化1:当待排序序列的长度分割到一定大小后,使用插入排序
优化2:在一次分割结束后,可以把与Key相等的元素聚在一起,继续下次分割时,不用再对与key相等元素分割
优化3:优化递归操作
9.TCP的拥塞控制,具体过程是怎么样的?UDP有拥塞控制吗?如何解决?

TCP 拥塞控制的目标是最大化利用网络上瓶颈链路的带宽。
TCP 全称为传输控制协议。这种协议可以提供面向连接的、可靠的、点到点的通信,所谓可靠,在于 TCP 建立连接时双方需要互相确认,类似打电话,在专业术语中称为 3 次握手。
UDP 全称为用户数据报协议,它可以提供非连接的不可靠的点到多点的通信,所谓不可靠,在于 UDP 每一次发送数据需要绑定 IP 和端口号,但是对于已经发送出去的数据来说并不去确认,也不需要类似 TCP 的三次握手的过程,由于没有了这个过程,所以其传输效率较之 TCP 来说要高许多。
(1)、在传输层可采用:重传策略、乱序缓存策略、确认策略、流控制策略和确定超时策略。
(2)、在网络层可采用:子网内部的虚电路与数据报策略、分组排队和服务策略、分组丢弃策略、路由算法和分组生存管理。
(3)、在数据链路层可采用:重传策略、乱序缓存策略、确认策略和流控制策略
Reno
Reno 被许多教材(例如:《计算机网络——自顶向下的方法》)所介绍,适用于低延时、低带宽的网络,它将拥塞控制的过程分为四个阶段:慢启动、拥塞避免、快重传和快恢复。
BBR 算法不将出现丢包或时延增加作为拥塞的信号,而是认为当网络上的数据包总量大于瓶颈链路带宽和时延的乘积时才出现了拥塞,所以 BBR 也称为基于拥塞的拥塞控制算法(Congestion-Based Congestion Control),其适用网络为高带宽、高时延、有一定丢包率的长肥网络,可以有效降低传输时延,并保证较高的吞吐量。
目前有非常多的 TCP 的拥塞控制协议,例如:
基于丢包的拥塞控制:将丢包视为出现拥塞,采取缓慢探测的方式,逐渐增大拥塞窗口,当出现丢包时,将拥塞窗口减小,如 Reno、Cubic 等。
基于时延的拥塞控制:将时延增加视为出现拥塞,延时增加时增大拥塞窗口,延时减小时减小拥塞窗口,如 Vegas、FastTCP 等。
基于链路容量的拥塞控制:实时测量网络带宽和时延,认为网络上报文总量大于带宽时延乘积时出现了拥塞,如 BBR。
基于学习的拥塞控制:没有特定的拥塞信号,而是借助评价函数,基于训练数据,使用机器学习的方法形成一个控制策略,如 Remy。
从使用的角度来说,我们应该根据自身的实际情况来选择自己机器的拥塞控制协议(而不是跟风 BBR),同时对于拥塞控制原理的掌握(尤其是掌握 Reno 的控制机理和几个重要阶段)可以加强对于网络发包机制的了解,在排查问题或面对面试的时候有更好的表现。
此外,拥塞控制只是 TCP 相关考点中的一个部分,还有许多的常见的高频考点可以顺带去看看,例如:
OSI 模型是什么?
有哪些协议是基于 TCP 的,哪些是基于 UDP 的?
为什么建立连接需要三次握手,而断开连接需要四次握手?
TCP首部长度,有哪些字段?
三次握手过程中有哪些不安全性?
补充:UDP主要特点:传输的是用户数据报协议。
(1).UDP是无连接的,即发送数据之前不需要建立连接。
(2).UDP 使用尽最大努力交付,即不保证可靠交付,同时也不使用拥塞控制。
(3).UDP是面向报文的。UDP没有拥塞控制,很适合多媒体通信的要求。
(4).UDP支持一对一、一对多、多对一和多对多的交互通信。
(5).UDP的首部开销小,只有 8个字节。
发送方 UDP对应用程序交下来的报文,在添加首部后就向下交付 IP层。UDP  对应用层交下来的报文,既不合并,也不拆分,而是保留这些报文的边界。应用层交给 UDP多长的报文,UDP就照样发送,即一次发送一个报文。接收方 UDP对 IP  层交上来的 UDP 用户数据报,在去除首部后就原封不动地交付上层的应用进程,一次交付一个完整的报文。
应用程序必须选择合适大小的报文。
10.讲讲了解的垃圾回收算法和回收器,什么时候执行STOP THE WORLD?

目前所有的新生代gc都是需要STW的:Serial:单线程STW,复制算法
ParNew:多线程并行STW,复制算法
Parallel Scavange:多线程并行STW,吞吐量优先,复制算法
Serial old:标记-整理
parallel old:标记-整理
cms:标记清除算法
垃圾回收算法:
引用计数:一个对象被引用计数器加一,取消引用计数器减一,引用计数器为0才能被回收。优点:简单。缺点:不能解决循环引用的问题,比如A引用B,B引用A,但是这两个对象没有被其他任何对象引用,属于垃圾对象,却不能回收;每次引用都会附件一个加减法,影响性能。
标记清除法:分为两个阶段:标记阶段和清除阶段。标记阶段通过根节点标记所有可达对象,清除阶段清除所有不可达对象。缺点:因为清除不可达对象之后剩余的内存不连续,会产生大量内存碎片,不利于大对象的分配。
复制算法:将内存空间分成相同的两块,每次只是用其中的一块,垃圾回收时,将正在使用的内存中的存活对象复制到另外一块空间,然后清除正在使用的内存空间中的所有对象,这种回收算法适用于新生代垃圾回收。优点:垃圾回收对象比较多时需要复制的对象恨少,性能较好;不会存在内存碎片。缺点:将系统内存折半。
标记压缩算法:是一种老年代回收算法,在标记清除的基础上做了一些优化,首先从根节点开始标记所有不可达的对象,然后将所有可达的对象移动到内存的一端,最后清除所有不可达的对象。优点:不用将内存分为两块;不会产生内存碎片。
分代算法:新生代使用复制算法,老生带使用标记清除算法或者标记压缩算法。几乎所有的垃圾回收期都区分新生代和老生带。
分区算法:将整个堆空间分成很多个连续的不同的小空间,每个小空间独立使用,独立回收。为了更好的控制gc停顿时间,可以根据目标停顿时间合理地回收若干个小区间,而不是整个堆空间,从而减少gc停顿时间。
11.了解Go语言吗?

2007年,受够了C++煎熬的Google首席软件工程师Rob Pike纠集Robert Griesemer和Ken Thompson两位牛人,决定创造一种新语言来取代C++, 这就是Golang。出现在21世纪的GO语言,虽然不能如愿对C++取而代之,但是其近C的执行性能和近解析型语言的开发效率以及近乎于完美的编译速度,已经风靡全球。特别是在云项目中,大部分都使用了Golang来开发,不得不说,Golang早已深入人心。而对于一个没有历史负担的新项目,Golang或许就是个不二的选择。

被称为GO语言之父的Rob Pike说,你是否同意GO语言,取决于你是认可少就是多,还是少就是少(Less is more or less is less)。Rob Pike以一种非常朴素的方式,概括了GO语言的整个设计哲学–将简单、实用体现得淋漓尽致。

很多人将GO语言称为21世纪的C语言,因为GO不仅拥有C的简洁和性能,而且还很好的提供了21世纪互联网环境下服务端开发的各种实用特性,让开发者在语言级别就可以方便的得到自己想要的东西。


https://www.xamrdz.com/database/6gn1934690.html

相关文章: