Redis有5種數(shù)據(jù)結(jié)構(gòu)：String、List、Hash、Set和Sorted Set。
這里僅僅談String和Hash.
Redis沒有使用C語言傳統(tǒng)的字符串，而是使用了SDS（simple dynamic string）
struct sdshdr {
int len; //字符串長度，不含空字符
int free; // 未使用字節(jié)的數(shù)量，不含空字符
char buf[]; // 保存字符串，最后一個字符是空字符
}
C語言字符串用長度是N+1的字符數(shù)組表示長度是N的字符串，字符數(shù)組最后一個元素是空字符'\0'。這種字符串的長度是靜態(tài)的，所以安全性較差，當(dāng)字符串?dāng)U展時容易發(fā)生溢出（buffer flow），這樣會覆蓋其他內(nèi)存。而sds會檢查擴(kuò)展時的空間是否足夠，所以說sds是一種可以動態(tài)擴(kuò)展的字符串，通過預(yù)分配內(nèi)存來實(shí)現(xiàn)擴(kuò)展：
如果擴(kuò)展之后，sds的長度len小于1M，那么將分配和len相同的空閑內(nèi)存，此時buf數(shù)組的長度是len + len + 1.
如果擴(kuò)展之后，sds的長度大于等于1M，那么將分配1M的空閑內(nèi)存，此時buf數(shù)組的長度是len + 1MB + 1.
當(dāng)sds縮短時不會釋放空閑內(nèi)存，這樣避免重復(fù)分配內(nèi)存。只有在真正有需要時，才會真正釋放未使用的內(nèi)存。
C語言字符串只能保存文本數(shù)據(jù)，不能保存二進(jìn)制文件的數(shù)據(jù)，因?yàn)槎M(jìn)制文件中可能包含空字符，而sds卻可以自如存取。
sds用途不僅僅是實(shí)現(xiàn)字符串，還被用作緩沖區(qū)，比如實(shí)現(xiàn)AOF緩沖區(qū)和客戶端輸入緩沖區(qū)。
Hash是一種保存鍵值對（key-value pair）的數(shù)據(jù)結(jié)構(gòu)，其實(shí)現(xiàn)與JDK HashMap類似。
動態(tài)數(shù)據(jù)結(jié)構(gòu)都要考慮擴(kuò)展的策略。比如Hash，當(dāng)K-V較多時，會影響性能，這就需要把原來的數(shù)據(jù)結(jié)構(gòu)擴(kuò)展，也就是rehash。
負(fù)載因子 load_factor = node_size / hash_size （有幾個桶）
當(dāng)load_factor大于等于1時，會擴(kuò)展hash，當(dāng)小于0.1時，會收縮hash。
當(dāng)擴(kuò)展時，hash_size 是 第一個大于等于node_size * 2^n
當(dāng)收縮時，hash_size是 第一個大于等于node_size * 2^n
redis內(nèi)有兩個hash，互相作為rehash的對象。redis采用的是漸進(jìn)式rehash，不會一次性、集中式地完成，而是分多次、漸進(jìn)式地完成。這是因?yàn)閔ash中的元素一般會比較多，這樣做的成本太高，所以要分?jǐn)偟矫看尾僮髦小?/p>
在rehash的過程中，hash的操作是在兩個表中進(jìn)行的，比如查找，如果在第一個表中找不到，會在第一個表中尋找。
2017-12-26再閱：
本文看似簡單，但涉及到不少重要的計(jì)算機(jī)思想。
- 數(shù)據(jù)結(jié)構(gòu)大小（所占內(nèi)存）動態(tài)擴(kuò)展或者動態(tài)收縮，這種擴(kuò)展策略可能分不同層級
- C語言字符串的缺點(diǎn)：容易溢出，不能存儲某些特殊字符。
- 批量操作和逐個操作各有利弊，前者勝在一次集中處理，后者勝在多次漸進(jìn)分?jǐn)偂?/li>
- 2015年，架構(gòu)中使用AB結(jié)構(gòu)，現(xiàn)在在數(shù)據(jù)結(jié)構(gòu)這一層次上也看到了這種設(shè)計(jì)。
2019-07-24
靜態(tài)的數(shù)據(jù)結(jié)構(gòu)能應(yīng)對的非常簡單，就是因?yàn)閱我?，而動態(tài)的數(shù)據(jù)結(jié)構(gòu)則能應(yīng)對多種場景。具體的例子是C語言字符串和Redis的SDS
