網站首頁 編程語言 正文
序言
Redis的幾種基本數據結構有字符串(String)、哈希(Hash)、列表(List)、集合(Set)、有序集合(Sorted Set),這些是最常見的,也能在官網上查看到。
官網鏈接:Redis 教程_redis教程
字符串
前面也提到過字符串是設計了簡單動態字符串SDS(Simple Dynamic String)結構來表示字符串。這種數據結構可以提升字符串的操作效率,并可以保存二進制數據。
先思考一個問題:
Redis是用C語言實現的,那么為什么沒有復用C語言的字符串實現方法,而選用了SDS呢?
char*字符串數組
C語言實現字符串使用的是char*字符串數組,它是一塊連續的內存空間,一次存放了字符串的每一個字符,并且最后一個字符是“\0”,用來標識字符串的結尾位置,如下圖,
連續的內存空間的所有字符串沒有分隔符計算機就沒辦法區分字符串與字符串之間的位置。在C語言標準庫中字符串的操作函數就會通過檢查字符串數組中是否有“\0”來判斷字符串是否結束。例如字符串操作函數strlen函數,它就是在遍歷字符串數組中的每一個字符,并進行計數,直到檢查到“\0”,它的時間復雜度是O(n)。流程如下,
簡單動態字符串SDS
SDS的數據結構里包含:字符串實際長度,字符串分配空間長度,SDS類型,字符數組,其中字符數組buf[]用來保存實際數據,如下圖,
再來看看類似的字符操作函數sdslen函數的源碼(在sds.h文件中),直接根據SDS類型返回對應的字符串現有長度,避免了對字符串的遍歷,時間復雜度變成了O(1),當然也會付出一點代價增加了空間復雜度。這都是設計人員讓數據操作更加高效。源碼如下,
static inline size_t sdslen(const sds s) {
unsigned char flags = s[-1];
switch(flags&SDS_TYPE_MASK) {
case SDS_TYPE_5:
return SDS_TYPE_5_LEN(flags);
case SDS_TYPE_8:
return SDS_HDR(8,s)->len;
case SDS_TYPE_16:
return SDS_HDR(16,s)->len;
case SDS_TYPE_32:
return SDS_HDR(32,s)->len;
case SDS_TYPE_64:
return SDS_HDR(64,s)->len;
}
return 0;
}
再來看一下字符串的拷貝源碼,操作都使用了字符串的現有長度,拷貝后進行更新。
sds sdscpylen(sds s, const char *t, size_t len) {
// 判斷字符串數組分配的空間長度是不是小于字符串數組當前長度
if (sdsalloc(s) < len) {
// 根據要追加的長度len-sdslen(s)和現有長度,判斷是否增加新的空間
s = sdsMakeRoomFor(s,len-sdslen(s));
if (s == NULL) return NULL;
}
// 將源字符串t中len長度的數據拷貝到目標字符串結尾
memcpy(s, t, len);
// 拷貝完后,在目標字符串結尾加上\0
s[len] = '\0';
// 設置字符串數組最新當前長度
sdssetlen(s, len);
return s;
}
SDS把目標字符串的空間檢查和擴容封裝在了sdsMakeRoomFor函數中,追加、打印、復制等操作都會調用該函數。可以看到該函數根據sds的信息進行動態擴容,源碼如下,
sds sdsMakeRoomFor(sds s, size_t addlen) {
void *sh, *newsh;
// 獲取sds可用空間
size_t avail = sdsavail(s);
size_t len, newlen;
char type, oldtype = s[-1] & SDS_TYPE_MASK;
int hdrlen;
// 如果可用空間大于等于要增加的空間,則直接返回
if (avail >= addlen) return s;
// sds長度
len = sdslen(s);
// sds指針
sh = (char*)s-sdsHdrSize(oldtype);
// 新字符串長度
newlen = (len+addlen);
// 如果新長度小于最大預分配長度,則進行兩倍擴容
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
type = sdsReqType(newlen);
// SDS類型5轉換為類型8
if (type == SDS_TYPE_5) type = SDS_TYPE_8;
hdrlen = sdsHdrSize(type);
if (oldtype==type) {
newsh = s_realloc(sh, hdrlen+newlen+1);
if (newsh == NULL) return NULL;
s = (char*)newsh+hdrlen;
} else {
/* Since the header size changes, need to move the string forward,
* and can't use realloc */
newsh = s_malloc(hdrlen+newlen+1);
if (newsh == NULL) return NULL;
memcpy((char*)newsh+hdrlen, s, len+1);
s_free(sh);
s = (char*)newsh+hdrlen;
s[-1] = type;
sdssetlen(s, len);
}
sdssetalloc(s, newlen);
return s;
}
?可以看到sdsMakeRoomFor函數中sdshdr5類型不再使用直接轉換成了sdshdr8類型,它們是SDS設計的5種類型,分別表示sdshdr5、sdshdr8、sdshdr16、sdshdr32和sdshdr64,下面就看一下這幾種類型的結構源碼,如下圖,
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* used */
uint8_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len; /* used */
uint16_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len; /* used */
uint32_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len; /* used */
uint64_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
sdshdr5已不再使用,所以在函數中做了處理,把sdshdr5類型轉換為sdshdr8類型。前面也提到過SDS是緊湊型字符串數據結構,以sdshdr8為例,它是用的是uint8_t即8位無符號整型,會占用1字節的內存空間。SDS之所以設計不同的結構是為了能靈活保存不同大小的字符串,從而有效節省內存空間。
另外,__attribute__ ((__packed__))標志可以告訴編譯器在編譯以上數據結構時,不實用字節對齊的方式(不滿8字節的整數倍,則會自動補齊),而是采用緊湊的方式分配內存。
原文鏈接:https://blog.csdn.net/zkkzpp258/article/details/126193448
相關推薦
- 2022-06-07 python字符串的一些常見實用操作_python
- 2022-07-29 C++超詳細講解操作符的重載_C 語言
- 2022-10-20 Flutter投票組件使用方法詳解_Android
- 2022-06-13 正則化DropPath/drop_path用法示例(Python實現)_python
- 2022-08-04 react使用mobx封裝管理用戶登錄的store示例詳解_React
- 2022-04-21 python的變量和運算符你都知道多少_python
- 2022-04-01 PyPy?如何讓Python代碼運行得和C一樣快_python
- 2022-05-09 .NET中常見的加解密算法詳解_實用技巧
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版(
- Linux 中運行的top命令 怎么退出?
- MySQL 中decimal 的用法? 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符,流程控制 Flo
- 1. Int 和Integer 的區別,Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤:Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密?
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串(SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列,發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支