Redis 学习 基础数据结构篇 之 压缩列表(ziplist)
[TOC] 基于 Redis 6.2.1 图片截取自《Redis设计与实现》 压缩列表（ziplist） 压缩列表（ziplist）是列表键和哈希键的底层实现之一。 当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么Redis 就会使用压缩列表来做列表键的底层实现 当一个哈希键只包含少量键值对，并且每个键值对的键和值要么就是小整数值，要么就是长度比较短的字符串，那么Redis 就会使用压缩列表来做哈希键的底层实现 压缩列表是 Redis 为了节约内存而开发的，是由一系列特殊编码的连续内存快组成的顺序行（sequential）数据结构，是一个特殊编码的双向链表。一个压缩列表可以包含任意过个节点（entry），每个节点可以保存一个字节数组或者一个整数值。 压缩列表结构 ziplist.c 文件顶部的注释内容，解释了ziplist的结构。 ziplist本身声明为一个unsigned char *类型的字符串，总体布局如下： <zlbytes> <zltail> <zllen> <entry> ...
Redis 学习 基础数据结构篇 之 整数集合(intset)
[TOC] 基于 [Redis 6.2.1](redis/redis at 6.2.1 (github.com)) 图片截取自《Redis设计与实现》 整数集合（intset） 整数集合（intset）是Set底层实现之一，当集合只包含整数值元素，且这个集合的元素数量不多时，Redis就会使用整数集合作为集合的底层实现。 整数集合的实现 整数集合比较简单，简单来说就是用整数数存储整数是在来维护集合。十几年了也没更新过。 整数集合的结构体定义在intset.h 12345typedef struct intset { uint32_t encoding; uint32_t length; int8_t contents[];} intset; encoding 编码方式：这里有三种INTSET_ENC_INT16、INTSET_ENC_INT32、INTSET_ENC_INT64，分表表示contents中存储的元素的实际类型，所以整数集合真正存储的只有int16_t、int32_t、int64_t这三种类型。 length 集合的元素数 ...
为什么总是爱瞎鼓捣呢？就是不能专注
作为一名不怎么样的C++后台开发工程师，还是应当学习专业技能。这样才好更好的干活，从而晋升加薪走向。混不下去了跳个槽也能用得上。 但是我这个人真的是很奇怪。就是不能专心的学习。。。 大学最开始学了几天C语言就开始搞上了ACM，开始了无尽的刷题生活。这一切都还不错，电脑也就普通用一用罢了。 不过慢慢的觉得Code::Blocks颜色太丑了，于是开始鼓捣了，开始搜Code::Blocks的代码高亮方法。找到了几个暗色的但又不好看，鼓捣鼓捣者用起了Sublime Text. 颜色啥的还都好看，但是编译代码不好用，又开始配置Sublime Text. 折腾了不少，同时发现他可以安装好多插件，于是开始研究插件。就这样浪费了很多时间。 回到正轨之后呢有开始搞ACM，正式比赛都是用的Ubuntu，于是安装上了Ubuntu，从此走上使用 Linux 桌面的不归路。Ubuntu里面的各种配置、软件安装都是命令行完成的。在鼓捣了Linux桌面美化之后开始TUI的折腾。最开始折腾VIM，主题折腾完折腾插件，各种琳琅满目的插件，用的不爽还想自己改，开始看vim script的写法，然后也没做出自己的一个插件 ...
前端学习
想学的东西有点多… [ ] HTML [ ] CSS [ ] JavaScript [ ] TypeScript [ ] Vue [ ] Electron 基础知识 前端最基础的就是 HTML,CSS,JavaScript 了。所以还是先从这几个学起。 B 站上找了个扫盲视频，还挺好的。 HTML, CSS, JavaScript 有空再看下 DOM 的这个。
LeetCode 第241场周赛
GG 5759. 找出所有子集的异或总和再求和 模拟题目 二进制枚举所有集合 计算每个集合的异或和， 最后加起来就好 123456789101112131415class Solution {public: int subsetXORSum(vector<int>& nums) { int n = nums.size(); int ans = 0; for(int i=1;i<(1<<n);i++) { int tmp = 0; for(int j=0;j<n;j++) { if(i>>j&1) tmp ^= nums[j]; } ans += tmp; } return ans; }}; 5760. 构成交替字符串需要的最小交换次数 模拟就好， ...
LeetCode 第52场双周赛
GG 5742. 将句子排序 简单模拟， 用py实现的，方便点。 123456class Solution: def sortSentence(self, s: str) -> str: sl = s.split(' ') sl.sort(key=lambda x: x[-1]) return ' '.join([s[:-1] for s in sl]) 5743. 增长的内存泄露 简单模拟 123456789101112131415161718class Solution {public: vector<int> memLeak(int memory1, int memory2) { int cnt = 0; int i=0; for(i=1;memory1 >= i || memory2 >= i; i++) { if(memory1 >= memory2) ...
Redis 学习 基础数据结构篇 之 跳表(skiplist)
[TOC] 基于 Redis 6.2.1 参考资料： https://www.jianshu.com/p/9d8296562806 画图工具是真的难用啊， 找不到好用的工具。。。 跳表 跳表（skiplist）是一种有序的数据结构，它通过在每个节点中维护多个指向其他节点的指针，从而达到快速访问的目的。 跳跃表支持平均O(logN)O(log N)O(logN), 最坏O(N)O(N)O(N)复杂度的节点查找，还可以通过顺序性操作来批量处理节点。 跳表的数据结构 跳表既然是叫什么什么表，那么本质上还是链表。下面先看一下普通单链表的结构： 图片graphviz源码 展开/收起 12345678910111213141516171819digraph link { rankdir = LR; //让图片横过来 node[shape = record]; //record形状是专门用来做类似”结构体“的东西的 1[label = "{1|}"];//每个的'|'都是一列 2[label = " ...
LeetCode 第51场双周赛
GG 5730. 将所有数字用字符替换 简单模拟题目 123456789class Solution {public: string replaceDigits(string s) { for(int i=0;i<s.size(); i+=2) { s[i+1] = s[i]+(s[i+1]-'0'); } return s; }}; 5731. 座位预约管理系统 数据结构题， 维护一个set就可以了 123456789101112131415161718class SeatManager { set<int> s;public: SeatManager(int n) { s.clear(); for(int i=1;i<=n;i++) s.insert(i); } int reserve() { in ...
Redis 学习 基础数据结构篇 之 dict
[TOC] 基于 Redis 6.2.1 dict（字典） 字典， 又称符号表（symbol table）、关联数组（associative array）或者映射（map）， 是一种用于保存键值对（key-value pair）的抽象数据结构。 在字典中，一个键（key）和一个值（value）关联，关联上的键和值被称为键值对 很多语言都提供了字典的实现，如C++ STL中的map，python中的dict，Go中的map等等。C语言中并为提供字典实现，因此Redis自行实现了字典。 Redis中很多地方用到了字典，Redis的数据库，HASH类型等。 dict的实现 src/dict.h 中定义了字典 1234567// hashtable 哈希表结构typedef struct dictht { dictEntry **table; // dictEntry 二维指针， 被当成指针数组用的。 unsigned long size; // 哈希表容量大小 unsigned long sizemask; // 等于size-1， 方便 ...
Redis 学习 基础数据结构篇 之SDS
[TOC] 这篇文章基本是抄来的。 好不要脸啊我。 带有空还是要自己整理一下。 基于 [Redis 6.2.1](redis/redis at 6.2.1 (github.com)) SDS Redis 没有直接使用 C 语言传统的字符串表示（以空字符结尾的字符数组，以下简称 C 字符串）， 而是自己构建了一种名为简单动态字符串（simple dynamic string，SDS）的抽象类型， 并将 SDS 用作 Redis 的默认字符串表示。 Redis 中除了字符串字面量，当作常量使用的地方用了C语言传统字符串。 其他可以想见的涉及到字符串的东西都是用SDS实现的。 redis 3.2 版本更新了 sds 2.0， 本文简单总结下sds1.0，再总结下sds2.0. SDS 1.0 SDS 1.0 内容copy 自 《Redis 设计与实现（第二版）》 sds1.0 定义 每个 sds.h/sdshdr 结构表示一个 SDS 值： 12345678910111213struct sdshdr { // 记录 buf 数组中已使用字节的数量 // ...