1.队列的实际使用
HTTP2 解决了 HTTP1.1 的队头阻塞问题。
为什么 HTTP1.1 有队头阻塞问题?
根本原因是使用了队列这个数据结构。
协议规定,同一个 TCP 连接,所有的 HTTP1.0 请求放入队列,只有前一个请求的响应被收到,才能发送下一个请求。这个阻塞主要发生在客户端。
HTTP/1.0 每个请求都需要建立一次 TCP 连接。请求结束的时候立即断开连接。
HTTP/1.1 每个连接都默认是长连接。同一个 TCP 连接可以发送多个请求。解决了 HTTP/1.0 的队头阻塞问题。也就是 HTTP/1.1 中管道的概念。 但是 HTTP/1.1 规定,服务端发送的响应按照请求被接收的顺序排队。先收到的请求先响应。如果先收到的请求时间比较长,那么响应的就会慢。阻塞已经处理完的其他请求的响应。也会造成队头部阻塞,但是队头阻塞发生在服务器端。
HTTP/2 如何解决队头阻塞问题?
HTTP/2 为了解决队头阻塞的问题,HTTP/2 采用二进制分帧和多路复用等方法。帧 HTTP/2 数据通信的最小单位。HTTP/1.1 的数据包是文本格式。HTTP/2 的数据包是二进制格式。
帧传输的方式可以把请求和响应的数据分割的更小。二进制协议可以被高效的解析。HTTP/2 下,同一域名下的所有通信都在同一个连接。并且这个连接可以承载任意数量的双向数据流。每个数据刘都以消息的信息发送。消息由一个或者多个帧组成。多个帧指尖可以乱序发送。可以根组帧首部的流标识重新组装。
多路复用
用来代替原来的序列和拥塞机制。在 HTTP1.1 并发的多个请求需要多个 TCP 连接,单个域名有 6 ~ 8 个 TCP 连接请求(这个限制是浏览器限制的)在 HTTP/2 中同一个域名下的所有的通信在单个连接完成,仅仅占用一个 TCP 连接。在这个连接上可以进行并行请求和响应,互不干扰。
协议长连接是指的 TCP 连接,而并非 HTTP 连接,因为 HTTP 是建立 TCP 连接之上的,所以间接的也说 HTTP 可以分为长连接和短连接了。 HTTP1.0 协议不支持长连接,从 HTTP1.1 协议以后,连接默认都是长连接。
2. 栈的应用
栈常见的应用,进制转化,括号匹配。中缀表达式子,后缀表达式。栈混洗。n 个元素的栈混洗有多少种, n 对括号的合法表达式就有多少种。
3.树
树的重要性质: 如果树有 n 个节点,那么就有 n-1 条遍。树的顶点数和边数是同阶的。
4.二叉树
94.binary-tree-inorder-traversal
102.binary-tree-level-order-traversal
103.binary-tree-zigzag-level-order-traversal
144.binary-tree-preorder-traversal
145.binary-tree-postorder-traversal
199.binary-tree-right-side-view
5.堆
堆其实就是一种优先级队列。
在⼀个 最⼩堆 (min heap) 中,如果 P 是 C 的⼀个⽗级节点,那么 P 的 key (或 value) 应⼩于或等于 C 的对应值。 正因为此,堆顶元素 ⼀定是最⼩的,我们会利⽤这个特点求最⼩值或者第 k ⼩的值。
6.查找树
- 左子树的所有节点的值均小于根节点的数。
- 右子树的所有节点的值均小于根节点的数。
7.前缀树
用来统计,排序,和保存大量的字符串。搜索引擎用来统计文本词频统计。 利用字符串的公共前缀来减少查询的时间,最大限度的减少无谓的字符串的比较。
- 根节点不包含字符。除根节点外的每个节点都只包含一个字符。
- 从根节点到某个节点,节点经过的字符都连接起来为该节点对应的字符串。
- 每个节点的子节点都不相同。
208.implement-trie-prefix-tree
211.add-and-search-word-data-structure-design
212.word-search-ii