文章还没写完，提前放出防止出现 404。稍后慢慢更新，敬请期待： 细说编码与字符集 - "地瓜哥"博客网
文章还没写完，提前放出防止出现 404。稍后慢慢更新，敬请期待： 细说编码与字符集 - "地瓜哥"博客网
文章还没写完，提前放出防止出现 404。稍后慢慢更新，敬请期待： 细说编码与字符集 - "地瓜哥"博客网
前段时间要研究 Hessian 编码格式，为了搞清楚 Hessian 对字符串的编码，就顺路查了好多编码和字符集的工作，理清了很多以前模糊的知识点。下面整理一下笔记，也梳理一下自己的思路和理解。
ASCII 码 计算机起源于美国，他们对英语字符与二进制位之间的对应关系做了统一规定，并制定了一套字符编码规则，这套编码规则被称为 American Standard Code for Information Interchange，简称为 ASCII 编码
其实，ASCII 最早起源于电报码。最早的商业应用是贝尔公司的七位电传打字机。后来于 1963 年发布了该标准的第一版。在网络交换中使用的 ASCII 格式是在 1969 年发布的，该格式在 2015 年发展成为互联网标准。点击 RFC 20: ASCII format for network interchange，感受一下 1969 年的古香古色。
ASCII 编码一共定义了128个字符的编码规则，用七位二进制表示（0x00 - 0x7F）, 这些字符组成的集合就叫做 ASCII 字符集。完整列表如下：
ASCII 码可以说是现在所有编码的鼻祖。
编码乱战及 Unicode 应运而生 ASCII 编码是为专门英语指定的编码标准，但是却不能编码英语外来词。比如 résumé，其中 é 就不在 ASCII 编码范围内。
随着计算机的发展，各个国家或地区，甚至不同公司都推出了不同的编码标准，比如中国推出了 GB2312、GBK 以及 GB18030；微软推出了 Windows character sets 。
在上一篇文章中，通过阅读 《In Search of an Understandable Consensus Algorithm》 前三节的内容，对论文的大致内容做了简介，简单说明了一下 Replicated state machines 的用途以及 Paxos 本身存在的问题。
4. Designing for understandability several goals in designing Raft:
it must providea complete and practical foundation for system building;
it must be safe under all conditions and available under typical operating conditions;
it must be efficient for common operations.
Our most important goal — and most difficult challenge — was understandability.
从这里可以看出，Raft 设计的初衷就是为了易于理解和便于构建。
There were numerous points in the design of Raft where we had to choose among alternative approaches. In these situations we evaluated the alternatives based on understandability.
前一段时间，在一次开组会的时候，给小组成员简单介绍了一下 Raft 协议。大概四年前读过 Raft 的论文，这次分享的时候，好多好多细节都忘了。所以，再次把 《In Search of an Understandable Consensus Algorithm》 这篇论文找出来，重读一遍，做个笔记和摘要，方便后续学习和复习。
Abstract Raft is a consensus algorithm for managing a replicated log. 开篇摘要就点出了 Raft 的特点： Raft 是一种管理复制日志的共识算法。
In order to enhance understandability, Raft separates the key elements of consensus, such as leader election, log replication, and safety, and it enforcesa stronger degree of coherency to reduce the number of states that must be considered. 为了增强可理解性，Raft 将共识分解成几个关键元素，例如 Leader 选举，日志复制，以及安全性等；同时，为了降低需要考虑的状态的数量，还强制实施了更强的一致性。
1. Introduction Consensus algorithms allow a collection of machines to work as a coherent group that can survive the failures of some of its members.
无论是在计算机课上，还是在网上，对数据结构有一定了解的童鞋，应该都对树的遍历不陌生。常见的遍历方式有如下两种：
基于栈的遍历：需要额外的空间复杂度。实现略复杂。
基于递归的遍历：实现简单。空间复杂度上，与栈类似，只是这里的栈维护是由系统自动完成的。
在看左程云的《程序员代码面试指南》时，里面介绍了一种只需 O(1) 的额外空间复杂度的遍历方法：Morris 树遍历。感觉非常神奇。这里给大家介绍一下。
Morris 树遍历的神奇之处在于，它充分利用了树里面大量的空闲节点（比如叶子节点的左右子树节点就为空，可以利用起来）来建立起必要的连接，推动遍历的进行。核心思想非常简单：找出当前节点左子树的最右节点，此时最右节点的右子树为空，将最右节点的右子树指向当前节点。然后左移，递归完成所有相关连接。没有左子树时，则向右移动，依次完成上述操作。我们来结合图来说明。如图：
图 1. Morris 树遍历 如上图所示，当访问根节点 4 时，它的左子树的最右节点就是 3，将 3 的右子树指向当前节点 4，如线条 ⑥ 所示。向左启动，建立起 1 到 2 的连接 ④。再向左移动到 1，1 没有左子树，则向右移动，此时就利用上了刚刚建立起的连接 ④。依次类推，即可完成遍历。在遍历过程中，也需要把建立的临时连接给取消掉。
/** * Morris 树遍历 * * @author D瓜哥 · https://www.diguage.com */ public void morris(TreeNode head) { TreeNode curr = head; TreeNode mostRight = null; while (curr != null) { // 当前节点左子树的最右节点，当然是从左子树开始了 mostRight = curr.left; if (mostRight != null) { // 左子树不为空，则找出左子树的最右节点 while (mostRight.right != null // 由于需要建立最右节点到当前节点的连接，所以，需要判断是否已建立连接来打破死循环 && mostRight.right != curr) { mostRight = mostRight.right; } if (mostRight.right == null) { // 最右节点的右子树为空，则第一次访问，那么建立起连接 mostRight.right = curr; curr = curr.left; continue; } else { // 最右节点的右子树不为空，则第二次访问，打破连接，恢复原貌 mostRight.right = null; } } // 最子树为空，则向右移动 curr = curr.right; } } 根据代码，结合图示，很容易得到 Morris 遍历的结果： 4、2、1、22、3、42、6、5、62、7。分析这个结果可以发现：有左子树的节点都会被访问两次。
前根遍历 那么该树的前根遍历是什么呢？这个也很容易得出：4、2、1、3、6、5、7。如何从 Morris 遍历中，得到前根遍历的结果呢？对比两边的结果，可以很容易发现：将访问两次的元素，只在第一次访问时输出；只访问一次的原始直接输出即可。代码如下：
/** * Morris 树前根遍历 * * @author D瓜哥 · https://www.diguage.com */ public void morrisPre(TreeNode head) { TreeNode curr = head; TreeNode mostRight = null; while (curr != null) { // 当前节点左子树的最右节点，当然是从左子树开始了 mostRight = curr.left; if (mostRight != null) { // 左子树不为空，则找出左子树的最右节点 while (mostRight.right != null // 由于需要建立最右节点到当前节点的连接，所以，需要判断是否已建立连接来打破死循环 && mostRight.right != curr) { mostRight = mostRight.right; } if (mostRight.right == null) { // 最右节点的右子树为空，则第一次访问，那么建立起连接 mostRight.right = curr; // 第一次访问时，即输出 System.out.print(curr.val + " "); curr = curr.left; continue; } else { // 最右节点的右子树不为空，则第二次访问，打破连接，恢复原貌 mostRight.right = null; } } else { // 前面内容已经分析过：有左子树的节点就会被访问两次 // 那么没有左子树的节点，就自会访问一次，访问到时直接输出即可。 System.out.print(curr.val + " "); } // 最子树为空，则向右移动 curr = curr.right; } }
传输控制协议（英语：Transmission Control Protocol，缩写：TCP）是一种面向连接的、可靠的、基于字节流的传输层通信协议，由 IETF 的 RFC 793 定义。在简化的计算机网络 OSI 模型中，它完成第四层传输层所指定的功能。
毫不夸张地说，TCP 协议是目前整个互联网的基础。它解决了一系列的网络问题。带来的结果，就是协议本身非常复杂。考虑到文章篇幅问题，本文着重说明 TCP 建立连接时的三次握手过程和关闭连接时的四次挥手过程。
三次握手 图 1. TCP 三次握手 第一次握手(SYN=1, seq=x):
客户端发送一个 TCP 的 SYN 标志位置 1 的包，指明客户端打算连接的服务器的端口，以及初始序号 x，保存在包头的序列号(Sequence Number)字段里。
发送完毕后，客户端进入 SYN_SEND 状态。
第二次握手(SYN=1、seq=y；ACK=1、ACKnum=x+1):
服务器发回确认包(ACK)应答。即 SYN 标志位和 ACK 标志位均为 1。服务器端选择自己 ISN 序列号，放到包头的序列号(Sequence Number)字段里，同时将确认序号(Acknowledgement Number)设置为客户的 ISN 加 1，即 x+1。
发送完毕后，服务器端进入 SYN_RCVD 状态。
第三次握手(ACK=1，ACKnum=y+1)
客户端再次发送确认包(ACK)，SYN 标志位为 0，ACK 标志位为 1，并且把服务器发来 ISN 的序号字段+1，放在确定字段中发送给对方，即数据段放写 y+1。
发送完毕后，客户端进入 ESTABLISHED 状态，当服务器端接收到这个包时，也进入 ESTABLISHED 状态，TCP 握手结束。
SYN Flood 攻击 在三次握手过程中，服务器发送 SYN-ACK 之后，收到客户端的 ACK 之前的 TCP 连接称为半连接(half-open connect)。此时服务器处于 SYN_RCVD 状态。当收到 ACK 后，服务器才能转入 ESTABLISHED 状态.
在 单调栈实践（一）：入门 中对单调栈做了一个初步介绍，同时使用一个类似单调栈的题目做了入门的尝试。在本文中，将分析正式单调栈的使用案例。
实践： LeetCode 503. 下一个更大元素 II 单调栈主要就是为了解决选择下一个更大或者更小元素的相关问题。来看一下 LeetCode 503. 下一个更大元素 II。
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的下一个更大元素。
数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
如果熟悉单调栈，这道题的解法就一目了然：将数组从后向前遍历，如果单调栈栈顶元素比当前元素小，就将栈顶元素弹出；重复上述操作，直到栈顶元素大于当前元素，或者栈为空。如果栈不为空，则栈顶元素就是当前元素的后继更大元素。代码如下：
/** * LeetCode 503. 下一个更大元素 II * * @author D瓜哥 · https://www.diguage.com * @since 2024-07-05 23:08:39 */ public int[] nextGreaterElements(int[] nums) { if (nums == null || nums.length == 0) { return nums; } int[] result = new int[nums.length]; Deque<Integer> stack = new LinkedList<>(); // 只需要将数组“拼接”，遍历两遍数组，就可以解决所有元素后继更大元素的问题 // 从后向前遍历，再加上单调递增栈，就是时间复杂度为 O(n) 的解决方案 for (int i = 2 * nums.length - 1; i >= 0; i--) { // 取余即可获取当前需要处理的元素 int index = i % nums.length; // 在单调栈不为空的情况下，将栈中小于等于当前元素的值都弹出 while (!stack.isEmpty() && stack.peek() <= nums[index]) { stack.pop(); } // 剩下元素既是比当前元素大的后继元素。为空则是没有更大元素 // 这里还有一个隐含变量： // 由于栈是从后向前添加，则栈顶元素距离当前元素更近。 // 如果栈不为空，则栈顶元素就是符合条件的元素。 result[index] = stack.isEmpty() ? -1 : stack.peek(); stack.push(nums[index]); } return result; } 使用单调栈，一个关键点是确定使用的是单调递增栈，还是单调递减栈。 这里给大家留一个思考题：本文提供的答案是从后向前遍历数组。尝试一下从前向后遍历数组的解决方案。 实践： LeetCode 42. 接雨水 下面再来看一下： LeetCode 42. 接雨水。
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
最近刷 LeetCode 算法题中，遇到了一些需要单调栈的题目，就顺便学习了一下单调栈。分享出来，以备后续深入学习。
学习单调栈之前，先了解一些栈。
栈 Stack 栈是一个众所周知的线性数据结构，它遵循先入后出（First In Last Out，简称 FILO）或后入先出（Last In First Out，简称 LIFO）的访问顺序。操作示意图如下：
图 1. 入栈与出栈 单调栈 Monotonic Stack 单调栈是一种特殊的栈，添加了一些限制条件：内部元素只能是递增或递减的顺序存储；添加元素时，如果新元素不符合单调性，则将其内部元素弹出，直到符合添加时，才添加元素。根据元素顺序，又可分为单调递增栈和单调递减栈。操作示意图如下：
图 2. 单调递增栈 图 3. 单调递减栈 代码示例 在写代码时，一般基于 Deque 来实现，通常用到以下四个方法：
deque.isEmpty()：如果 deque 不包含任何元素，则返回 true，否则返回 false。因为要栈顶元素在满足要求的时候要弹出，所以需要进行空栈判断。有些场景，可能栈一定不会空的时候，就不需要该方法进行空栈判断。
deque.push(e)：将元素 e 入栈。
deque.pop()：将栈顶元素弹出，并返回当前弹出的栈顶元素。
deque.peek()：获取栈顶元素，不弹出。
// 定义一个单调栈 Deque<Integer> stack = new LinkedList<>(); // 第一个元素，直接添加 stack.push(0); // 这里存的是数组下标 for (int i = 1; i < nums.length; i++) { // 单调递增栈这里就是大于，即 nums[i] > nums[deque.peek()] if (nums[i] < nums[stack.peek()]) { stack.push(i); } else if (nums[i] == nums[stack.peek()]) { stack.push(i); // 此处除了入栈，在有些场景下，还有可能有其他操作 // .............. } else { // 循环比较，直到遇到当前元素小于栈顶的元素情况，跳出循环 // 单调递增栈，这里是小于，即nums[i] < nums[deque.peek()] while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) { //主要逻辑 // ............ // ............ // 弹出栈顶元素 stack.pop(); } stack.push(i); } } 应用： LeetCode 155. 最小栈 来看一个 LeetCode 算法提： LeetCode 155. 最小栈，D瓜哥愿意称之为单调栈入门最佳试题。
题目描述 题目是 LeetCode 的第 538 题： 把二叉搜索树转换为累加树。
给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。
思路分析 一棵二叉搜索树，如果是中根遍历，那么，其序列正好是一个升序序列。但，题目要求的是大于等于自身的节点值之和。正常的中根遍历是“左中右”，反过来“右中左”，就是降序序列，累计求和就符合题目要求了。
解题代码 中序遍历，可以用栈，也可以使用 Morris 遍历。在 题解：找到二叉搜索树中两个错误的节点 中就是用了 Morris 遍历。网上也很少有反向的 Morris 中根遍历。正好练习一下。
/** * 基于 Morris 的倒序中根遍历 * * @author D瓜哥 · https://www.diguage.com */ public TreeNode convertBST(TreeNode root) { int sum = 0; // 反向 Morris TreeNode cur = root; TreeNode mostLeft = null; while (cur != null) { // 向右转 mostLeft = cur.right; if (mostLeft != null) { // 寻找最左边的节点 while (mostLeft.left != null && mostLeft.left != cur) { mostLeft = mostLeft.left; } if (mostLeft.left == null) { // 第一次访问，将最左节点的左子树指向当前节点 mostLeft.left = cur; cur = cur.right; continue; } else { // 第二次访问，掐断中间建立的连接 mostLeft.left = null; } } // 计算累加和 sum += cur.val; cur.val = sum; cur = cur.left; } return root; } 得益于 Morris 的优秀本质，这个解法的时间复杂度是： O(n)，空间复杂度是： O(1)。
关于 Morris 树遍历的更多介绍，请看： 神奇的 Morris 树遍历。
在上一篇文章： Redis 核心数据结构（1） 中，介绍了链表、ziplist、quicklist 数据结构。这篇文章，来介绍一下 skiplist、dict。
skiplist 跳跃表是一种有序数据结构，支持平均 O(logN)、最坏 O(N) 复杂度的节点查找；大部分情况效率可以和平衡树相媲美，实现却比平衡树简单。
跳跃表就是 Redis 中有序集合键的底层实现之一。
server.h typedef struct zskiplistNode { sds ele; double score; struct zskiplistNode *backward; struct zskiplistLevel { struct zskiplistNode *forward; unsigned long span; } level[]; } zskiplistNode; typedef struct zskiplist { struct zskiplistNode *header, *tail; unsigned long length; int level; } zskiplist; typedef struct zset { dict *dict; zskiplist *zsl; } zset; skiplist，顾名思义，首先它是一个list。实际上，它是在有序链表的基础上发展起来的。
当我们想查找数据的时候，可以先沿着跨度大的链进行查找。当碰到比待查数据大的节点时，再回到跨度小的链表中进行查找。
skiplist正是受这种多层链表的想法的启发而设计出来的。按照上面生成链表的方式，上面每一层链表的节点个数，是下面一层的节点个数的一半，这样查找过程就非常类似于一个二分查找，使得查找的时间复杂度可以降低到 O(logN)。但是，存在的一个问题是：如果插入新节点后就会打乱上下相邻两层节点是 2:1 的对应关系。如果要维持，则需要调整后面所有的节点。
skiplist为了避免这一问题，它不要求上下相邻两层链表之间的节点个数有严格的对应关系，而是为每个节点随机出一个层数(level)。
插入操作只需要修改插入节点前后的指针，而不需要对很多节点都进行调整。这就降低了插入操作的复杂度。实际上，这是 skiplist 的一个很重要的特性，这让它在插入性能上明显优于平衡树的方案。
skiplist，翻译成中文，可以翻译成“跳表”或“跳跃表”，指的就是除了最下面第1层链表之外，它会产生若干层稀疏的链表，这些链表里面的指针故意跳过了一些节点（而且越高层的链表跳过的节点越多）。这就使得我们在查找数据的时候能够先在高层的链表中进行查找，然后逐层降低，最终降到第1层链表来精确地确定数据位置。在这个过程中，我们跳过了一些节点，从而也就加快了查找速度。
在中间插入一个有比较高 Level 的节点，如何维护前面节点到这个节点的这些链接？
在平衡树种，如何做范围查找？先确定边界，然后其他节点怎么查找？
skiplist 中 key 允许重复。
在比较时，不仅比较分数（即key），还要比较数据自身。
第一层链表是双向链表，并且反向指针只有一个。
在 skiplist 中可以很方便计算每个元素的排名。
Redis 中的有序集合（sorted set），是在 skiplist, dict 和 ziplist 基础上构建起来的:
当数据较少时，sorted set是由一个 ziplist 来实现的。其中集合元素按照分值从小到大排序。
当数据多的时候，sorted set 是由一个叫 zset 的数据结构来实现的，这个 zset 包含一个 dict + 一个 skiplist。dict 用来查询数据到分数(score)的对应关系，而 skiplist 用来根据分数查询数据（可能是范围查找）。
Redis 目前是使用最广泛的缓存中间件。其突出特点就是支持多种常见的数据结构。对比 JDK 集合类的实现，Redis 的实现表现出很多独到之处，很多地方设计得别具匠心。下面就来简要介绍一下。
linkedlist Redis 底层也有很多地方使用到 linkedlist，并且也是双向链表。
adlist.h typedef struct listNode { struct listNode *prev; struct listNode *next; void *value; } listNode; typedef struct listIter { listNode *next; int direction; } listIter; typedef struct list { listNode *head; listNode *tail; void *(*dup)(void *ptr); void (*free)(void *ptr); int (*match)(void *ptr, void *key); unsigned long len; } list; Redis 的 linkedlist 实现特点是：
双向：节点带有前后指针；
无环：首尾没有相连，所以没有构成环状；
链表保存了首尾指针；
多态：可以保存不同类型的值，这里成为泛型也许更符合 Java 中的语义。
Redis 在 2014 年实现了 quicklist，并使用 quicklist 代替了 linkedlist。所以，现在 linkedlist 几乎已经是废弃状态。
ziplist Redis 官方在 ziplist.c 文件的注释中对 ziplist 进行了定义：
The ziplist is a specially encoded dually linked list that is designed to be very memory efficient. It stores both strings and integer values, where integers are encoded as actual integers instead of a series of characters. It allows push and pop operations on either side of the list in O(1) time. However, because every operation requires a reallocation of the memory used by the ziplist, the actual complexity is related to the amount of memory used by the ziplist.
