- 博客(69)
- 资源 (3)
- 收藏
- 关注
RSS订阅原创 Redis源码剖析——数据库
数据库的实现服务器状态rediServer结构体如下：struct redisServer { // 配置文件的绝对路径 char *configfile; // serverCron() 每秒调用的次数 int hz; // 数据库 redisDb *db; // 命令表（受到 renam...
2018-05-21 15:06:06
614
原创 Redis源码剖析——有序集合对象
有序集合对象有序集合的对象的编码可以为ziplist或者skiplistziplist实现有序集合当满足下面两个条件时，有序集合的底层数据结构为skiplist 1. 元素数量小于128个 2. 所有元素成员的长度都小于64字节...
2018-05-14 19:35:57
647
原创 Redis源码剖析——ziplist的实现
有序集合对象ziplist为Redis中的压缩列表，是列表键和哈希键的底层实现之一，用于存储长度短的字符串和小整数。ziplist采用一段连续的内存来存储节点ziplist的表示因为ziplist的数据结构的长度是变化的所有没有特定的结构体，ziplist在内存中的布局如下 entry也是不定长的，没有特定的结构体，entry在内存中的布局如下 previous_ent...
2018-05-14 16:18:12
863
原创 Redis源码剖析——skiplist的实现
跳跃表skiplist跳跃表是一种有序的数据结构，它通过用空间换时间，在每个节点中维持多个指向其他节点的指针，从而达到快速访问的目的。跳跃表插入、删除的平均复杂度为O（logN），最坏为O（N），可以和红黑树相媲美，但是在实现起来，比红黑树简单很多。Redis使用跳跃表来实现有序集合对象基本结构// 跳跃表节点typedef struct zskiplistNode { ...
2018-05-12 16:58:11
492
原创 Redis源码剖析——集合对象
集合对象集合对象的编码可以为intset 或则 hashtableintset编码的的集合对象当满足下面两个条件时，集合对象将使用intset编码 1. 集合对象的所有元素都是整数值 2. 集合对象的元素个数小于等于512当执行命令 SADD numbers 1 2 3 4 时 键numbers的值对象将使用Intset编码，内存布局如下图 hashtable编码的集合...
2018-04-30 15:04:53
208
原创 Redis源码剖析——哈希对象
哈希对象哈希对象的编码可以为ziplist或者hashtableziplist编码的哈希对象满足下面两个条件时，哈希对象使用ziplist编码 1. 所有键值对的键和值的字符串长度都小于等于64字节 2. 键值对数量小于512连续执行下面三个命令后 HSET profile name “Jack” HSET profile age 20 HSET profile ca...
2018-04-30 14:36:40
200
原创 Redis源码剖析——列表对象
列表对象列表对象的编码为ziplist或linkedlistziplist编码的列表对象当满足下面两个条件时列表对象用ziplist编码 1. 列表对象保存的所有字符串元素的长度都小于等于64字节 2. 元素数量小于等于512 当执行RPUSH numbers 1 “three” 5 命令后numbers键的值对象的布局如下 linkedlist编码的列表对象当不符合z...
2018-04-30 13:33:20
176
原创 Redis源码剖析——字符串对象
字符串对象字符串对象有三种编码方式，int、raw、embstrint编码的字符串对象对于int编码的字符串对象，为了节省内存，int将会占用ptr的空间，布局如图 raw编码的字符串对象当字符串值的长度大于39字节时，字符串对象将用SDS来保存字符串值 如使用 SET story “Long，long，long ago there lived a king …”命令后...
2018-04-30 13:12:46
194
原创 Redis源码剖析——Redis五种基本对象
Redis五大对象Redis使用对象来表示数据库中的键和值。 Redis有五种基本对象，分别为字符串对象、列表对象、哈希对象、集合、有序集合对象的表示Redis中的对象由RedisObject表示typedef struct redisObject { // 类型 unsigned type:4; // 编码 unsigned encodi...
2018-04-30 12:35:51
217
原创 Redis源码剖析——intset的实现
intsetintset为Redis中的整数集合， 当一个集合只包含整数值元素， 并且这个集合的元素数量不多时， Redis 就会使用整数集合作为集合键的底层实现。intset采用一段连续内存空间实现，默认采用16bit的整数，当新加入的整数16bit放不下时会对整个空间进行扩容，因为每加入/删除一个元素就要进行扩容/缩容，频繁的进行内存释放、拷贝，很明显不适用于频繁的增删元素大小端存...
2018-04-12 13:18:33
472
原创 《Linux内核设计与实现》读书笔记——进程管理
进程管理进程概念进程：进程是处于执行期的程序以及相关资源的总称 线程：线程是进程中活动的对象。每个线程都有独立的程序计数器、进程栈和寄存器。内核调度的是线程而不是进程内核并不区分进程和线程，只是创建时传递给创建函数的参数不一样进程结构进程队列组成双向循环链表，类型为task_struct,此结构体最为重要，保存了进程的所有信息，进程栈中有thread_info结构...
2018-04-09 13:07:18
254
原创 Redis源码剖析——dict的实现
dict字典为Redis的基本数据结构之一有着非常广泛的用途，由哈希表实现。Redis的数据库由字典实现基本结构#define DICT_OK 0#define DICT_ERR 1// 指示字典是否启用 rehash 的标识static int dict_can_resize = 1;// 强制 rehash 的比率static unsigned int dict...
2018-04-06 14:24:22
374
原创 Redis源码剖析——adlist的实现
adlistadlist为Redis基本数据结构之一，为双向链表，记录了链表长度，adlist的迭代器记录了迭代节点和方向，个人觉得实现优于STL的list几个重要结构adlist实现比较精简，基本上写过链表相关的代码就能很快写出所有实现函数/* * 双端链表节点 */typedef struct listNode { // 前置节点 struct listN...
2018-03-31 14:24:14
445
原创 Redis源码剖析——SDS的实现
SDS的实现SDS即简单动态字符串，为Redis的几大基本数据结构之一，有广泛的用途基本函数总览 函数 功能 复杂度 sdsnewlen 由给定字符串创建SDS O(N) sdslen 返回字符串长度 O(1) sdsdup 复制一个SDS O(N) sdsfree 释放字符串空间 O(1)...
2018-03-30 17:15:33
378
原创 Redis源码剖析——内存管理
开始阅读Redis3.0版本源码，并以此为剖析对象，因为此版本有注释，并且网上有文章，便于初学者学习参考，了解以前的版本才能更好地学习最新的4.x版本内存管理Redis的内存管理仅仅对malloc,，free做了一层封装，并未实现内存池，远没有STL的内存分配器巧妙内存管理函数内存管理函数如下：void *zmalloc(size_t size); //封装ma...
2018-03-28 17:13:47
236
原创 可变参数模板实现求n个数的最小公倍数
前几天面试CVTE的时候，面试官要手撸了个题，求三个数的最小公倍数，题目很简单，当时想炫技说我可以求任意多个数的最小公倍数，还是忍住了，很长时间没看了，怕装逼失败。。。。。。 回来后简单写了下，使用variadic templates，很简单，前面博客有介绍 代码如下：/* 可变参数模板实现求n个数的最小公倍数，不考虑整形溢出 不考虑传入的b为0*/ #include <...
2018-03-26 11:00:14
204
原创 Variadic templates
Variadic Templates可变参数模板，函数的参数可以有任意多个，参数的类型任意1. 实现函数递归调用实现打印任意多个不同类型参数#include <iostream>using namespace std;//无参数版本void print() {}//n+1 个参数版本 template <class T, class... Types>void print(const T&
2017-12-11 18:27:35
302
原创 STL源码剖析——RB_TREE
花了差不多一个星期的时间读完了STL红黑树的实现，并凭理解自己写了出来 参考了《算法导论》，教你透彻了解红黑树，强烈推荐，《STL源码剖析》 记录下自己的理解RB_TREE红黑树优点： 与BST相比插入，查找，删除在最坏情况下的复杂度仍为O（lgn），相比BST应用范围更广 STL容器set，map都以红黑树为底层容器实现，Linux进程调度算法也用红黑树实现四种性质： 1. 每个结点要
2017-12-09 20:19:01
354
原创 =default, =delete
=default, =delete=default如果自己定义了一个ctor,那么编译器就不会再合成一个default ctor 如果强制加上=default, 编译器就会合成一个default ctor=delete禁止编译器合成class Test {public: Test(int i, int j):d1(i), d2(j) {} //默认构造函数 Te
2017-12-05 18:02:11
281
原创 STL源码剖析——deque的实现
deque简介deque是一个双向开口的容器，可在头尾两端插入和删除元素，deque由动态的连续空间组合而成，因为迭代器的良好设计，提供了随机访问，造成一种deque为连续空间的假象deque的数据结构deque有一个二级指针map，map指向一小块空间，其中的每个元素都是指针，指向一段连续线性空间，称为缓冲区，缓冲区为deque存储的主体，其中存放元素tempalte <class T, clas
2017-11-01 17:39:57
503
原创 STL源码剖析——type traits编程技法
type traits 负责萃取元素类型的特性，如果元素具有某个性质则我们调用某个函数，如果不具有某个性质则调用另一个函数。它充分利用了C++模板编程和编译器的参数推导功能(编译器只有面对类类型参数才会进行参数推导)。STL大量运用了traits编程技巧，通过模板特化，函数重载让编译器选择正确的处理方式，在编译器就能完成函数分发，极大的提高了灵活性。先看一个例子#include <iostream>
2017-09-08 17:02:15
326
原创 leetcode93. Restore IP Addresses
难度：medium题目：IP 地址是一个32位的整数，每8位的十进制组成一个数，用 . 分隔很明显是一个回朔法的题，特别注意的是遇到0时的情况，还有每个数值要小于256，进行剪枝减小运算量AC解：class Solution {public: vector<string> restoreIpAddresses(string s) { int len = s.length()
2017-09-04 19:20:14
324
原创 leetcode115. Distinct Subsequences
难度：hard题目：被hard程度吓到了，首先想到的是用递归求解，写了一个多小时没做出来，其实是一个简单的动态规划AC解：class Solution {public: int numDistinct(string s, string t) { int m = s.length(); int n = t.length(); vector<ve
2017-09-04 19:11:30
249
原创 leetcode 44. Wildcard Matching
难度：hard题目：与leetcode10. Regular Expression Matching此题类似，同样采用动态规划，这两题解法很精彩，比较经典AC解：class Solution {public: bool isMatch(string s, string p) { int slen = s.length(); int plen = p.leng
2017-09-04 17:48:39
283
原创 leetcode10. Regular Expression Matching
难度：hard题目：AC解：class Solution {public: bool isMatch(string s, string p) { int slen = s.length(); int plen = p.length(); if (slen == 0 && plen == 0) return true;
2017-09-04 17:36:03
274
原创 STL源码剖析——内存空间管理
STL内存空间管理工具alloc1.第一级配置器__malloc_alloc_templatestaic void *allocate(size_t n) { void *result = malloc(n);//直接调用malloc if (0 == n) result = oom_malloc(n); return result;}static void *deallo
2017-09-03 17:33:52
906
1
原创 leetcode 76. Minimum Window Substring
题目： 难度： hard思路： O（n）复杂度下感觉要用哈希表，使用两个指针，指向进行的首尾，当发现有包含T字符串的序列时，移动首指针，缩小氛围，大体思路是这样，但是具体细节和代码实现写不出来-，-。 再读懂了其他解答的情况下实现了代码AC解：class Solution {public: string minWindow(string s, string t) { //
2017-08-01 16:11:29
432
1
原创 leetcode 96. Unique Binary Search Trees
题目： 思路： 以k为根节点的树，左子树为【1，…，K - 1】，右子树为【K + 1，…，N】，定义f(n)为【1，…，n】能产生不同的二叉搜索树的个数，则以K为根节点能产生f(k - 1) * f(n - k)种不同的树。显然f(0) = f(1) = 1。 f(2) = f(0) * f(1) + f(1) * f(0) f(3) = f(0) * f(2) + f(1) * f(1)
2017-06-04 23:04:36
244
原创 leetcode100. Same Tree
easy程度题Q:Given two binary trees, write a function to check if they are equal or not.Two binary trees are considered equal if they are structurally identical and the nodes have the same value. 判断两个二叉树是否
2017-05-20 16:34:24
293
原创 leetcode101. Symmetric Tree
Q:Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).For example, this binary tree [1,2,2,3,4,4,3] is symmetric:1 / \ 2 2 / \ / \ 3 4 4 3But the
2017-05-20 16:17:18
335
转载 Morris二叉树遍历算法
Morris二叉树遍历算法 时间复杂度O（N），空间复杂度O（1） 这种方法借鉴了线索化二叉树的思想，但是不占用空间中序遍历方法如下：如果当前节点的左孩子为空，则输出当前节点并将其右孩子作为当前节点。如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。b) 如果前驱节点
2017-05-19 23:36:16
318
原创 leetcode8. String to Integer (atoi)
medium程度题题目:Implement atoi to convert a string to an integer.Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are t
2017-04-25 10:47:58
286
原创 leetcode28. Implement strStr()
easy程度题题目：Implement strStr().Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.字符串匹配，暴力匹配复杂度O(M * N)AC解:class Solution {public
2017-04-24 09:51:34
359
原创 leetcode125. Valid Palindrome
easy程度题题目:Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.For example,"A man, a plan, a canal: Panama" is a palindrome."rac
2017-04-23 12:32:03
275
原创 leetcode143. Reorder List
medium程度题题目:Given a singly linked list L: L0→L1→…→Ln-1→Ln,reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…You must do this in-place without altering the nodes' values.For example,Given {1,2,
2017-04-22 12:53:52
277
原创 leetcode141. Linked List Cycle
easy程度题题目：Given a linked list, determine if it has a cycle in it.Follow up:Can you solve it without using extra space?可以建立一个set集合，每次访问一个新节点，如果集合中没有则将节点放入set,如果有则说明存在环。不占用额外空间，想不出来
2017-04-22 10:18:07
297
原创 leetcode25. Reverse Nodes in k-Group
Hard程度题题目:Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.k is a positive integer and is less than or equal to the length of the linked lis
2017-04-20 15:20:49
397
原创 leetcode92. Reverse Linked List II
medium程度题目：Reverse a linked list from position m to n. Do it in-place and in one-pass.For example:Given 1->2->3->4->5->NULL, m = 2 and n = 4,return 1->4->3->2->5->NULL.Note:Giv
2017-04-12 22:15:08
333
原创 leetcode260. Single Number III
先说第一种题题目:Given an array of integers, every element appears twice except for one. Find that single one.Note:Your algorithm should have a linear runtime complexity. Could you implement it
2017-04-09 20:00:20
294
原创 leetcode134. Gas Station
medium程度题题目:There are N gas stations along a circular route, where the amount of gas at station i is gas[i].You have a car with an unlimited gas tank and it costs cost[i] of gas to travel
2017-04-07 16:07:15
338
教学计划编制
2017-06-03
数据结构课程设计——教学计划编制（极其详细）
2017-06-03
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人