寫(xiě)在前邊

也當(dāng)過(guò)面試官，面試過(guò)不少應(yīng)聘者镶柱，因?yàn)槭俏易约赫腥俗约河谜疗啵晕也粫?huì)看應(yīng)聘者造火箭的技術(shù)有多牛比烧给，只看擰螺絲的手藝瓷不瓷實(shí)。畢竟以后是一個(gè)整體侵浸，拖了大家后腿團(tuán)隊(duì)都很難受旺韭。面試的題目一般也不會(huì)太難，就像問(wèn)Redis掏觉，我只是想確認(rèn)他真正用過(guò)就夠了区端。Redis 5種基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)和簡(jiǎn)單操作要知道，最基本的要求澳腹，如果這個(gè)時(shí)候他會(huì)說(shuō)出每種數(shù)據(jù)結(jié)構(gòu)大致的應(yīng)用場(chǎng)景织盼，那么這一定是加分的杨何，起碼要比那些只會(huì)說(shuō)出幾種數(shù)據(jù)結(jié)構(gòu)后，在那干瞪眼等我問(wèn)下一個(gè)問(wèn)題的強(qiáng)很多沥邻，千萬(wàn)別冷場(chǎng)危虱。

Redis基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)有哪些？

一唐全、String（字符串）

在任何一種編程語(yǔ)言里槽地，字符串String都是最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)， 那你有想過(guò)Redis中存儲(chǔ)一個(gè)字符串都進(jìn)行了哪些操作嘛芦瘾？

在Redis中String是可以修改的，稱(chēng)為動(dòng)態(tài)字符串(Simple Dynamic String 簡(jiǎn)稱(chēng) SDS)（快拿小本本記名詞集畅，要考的）近弟，說(shuō)是字符串但它的內(nèi)部結(jié)構(gòu)更像是一個(gè) ArrayList，內(nèi)部維護(hù)著一個(gè)字節(jié)數(shù)組挺智，并且在其內(nèi)部預(yù)分配了一定的空間祷愉，以減少內(nèi)存的頻繁分配。

Redis的內(nèi)存分配機(jī)制是這樣：

• 當(dāng)字符串的長(zhǎng)度小于 1MB時(shí)赦颇，每次擴(kuò)容都是加倍現(xiàn)有的空間二鳄。
• 如果字符串長(zhǎng)度超過(guò) 1MB時(shí)，每次擴(kuò)容時(shí)只會(huì)擴(kuò)展 1MB 的空間媒怯。

這樣既保證了內(nèi)存空間夠用订讼，還不至于造成內(nèi)存的浪費(fèi)，字符串最大長(zhǎng)度為 512MB.扇苞。

上圖就是字符串的基本結(jié)構(gòu)欺殿，其中 content 里面保存的是字符串內(nèi)容，0x\0作為結(jié)束字符不會(huì)被計(jì)算len中鳖敷。

分析一下字符串的數(shù)據(jù)結(jié)構(gòu)

struct SDS{
  T capacity;       //數(shù)組容量
  T len;            //實(shí)際長(zhǎng)度
  byte flages;  //標(biāo)志位,低三位表示類(lèi)型
  byte[] content;   //數(shù)組內(nèi)容
}

capacity 和 len兩個(gè)屬性都是泛型脖苏，為什么不直接用int類(lèi)型？因?yàn)?code>Redis內(nèi)部有很多優(yōu)化方案定踱，為更合理的使用內(nèi)存棍潘，不同長(zhǎng)度的字符串采用不同的數(shù)據(jù)類(lèi)型表示，且在創(chuàng)建字符串的時(shí)候 len 會(huì)和 capacity 一樣大崖媚，不產(chǎn)生冗余的空間亦歉，所以String值可以是字符串、數(shù)字（整數(shù)至扰、浮點(diǎn)數(shù)) 或者 二進(jìn)制鳍徽。

1. 應(yīng)用場(chǎng)景：

存儲(chǔ)key-value鍵值對(duì)，這個(gè)比較簡(jiǎn)單不細(xì)說(shuō)了

2. 字符串（String）常用的命令：

set   [key]  [value]   給指定key設(shè)置值（set 可覆蓋老的值）

get  [key]   獲取指定key 的值

del  [key]   刪除指定key

exists  [key]  判斷是否存在指定key

mset  [key1]  [value1]  [key2]  [value2] ...... 批量存鍵值對(duì)

mget  [key1]  [key2] ......   批量取key

expire [key]  [time]    給指定key 設(shè)置過(guò)期時(shí)間  單位秒

setex    [key]  [time]  [value]  等價(jià)于 set + expire 命令組合

setnx  [key]  [value]   如果key不存在則set 創(chuàng)建敢课，否則返回0

incr   [key]           如果value為整數(shù) 可用 incr命令每次自增1

incrby  [key] [number]  使用incrby命令對(duì)整數(shù)值 進(jìn)行增加 number

二阶祭、list(列表)

Redis中的list和Java中的LinkedList很像绷杜，底層都是一種鏈表結(jié)構(gòu)， list的插入和刪除操作非潮裟迹快鞭盟，時(shí)間復(fù)雜度為 0(1)，不像數(shù)組結(jié)構(gòu)插入瑰剃、刪除操作需要移動(dòng)數(shù)據(jù)齿诉。

像歸像，但是redis中的list底層可不是一個(gè)雙向鏈表那么簡(jiǎn)單晌姚。

當(dāng)數(shù)據(jù)量較少的時(shí)候它的底層存儲(chǔ)結(jié)構(gòu)為一塊連續(xù)內(nèi)存粤剧，稱(chēng)之為ziplist(壓縮列表)，它將所有的元素緊挨著一起存儲(chǔ)挥唠，分配的是一塊連續(xù)的內(nèi)存抵恋；當(dāng)數(shù)據(jù)量較多的時(shí)候?qū)?huì)變成quicklist(快速鏈表)結(jié)構(gòu)。

可單純的鏈表也是有缺陷的宝磨，鏈表的前后指針 prev 和 next 會(huì)占用較多的內(nèi)存弧关，會(huì)比較浪費(fèi)空間，而且會(huì)加重內(nèi)存的碎片化唤锉。在redis 3.2之后就都改用ziplist+鏈表的混合結(jié)構(gòu)世囊，稱(chēng)之為 quicklist(快速鏈表)。

下面具體介紹下兩種鏈表

ziplist(壓縮列表)

先看一下ziplist的數(shù)據(jù)結(jié)構(gòu)窿祥，

struct ziplist<T>{
    int32 zlbytes;            //壓縮列表占用字節(jié)數(shù)
    int32 zltail_offset;    //最后一個(gè)元素距離起始位置的偏移量,用于快速定位到最后一個(gè)節(jié)點(diǎn)
    int16 zllength;            //元素個(gè)數(shù)
    T[] entries;            //元素內(nèi)容
    int8 zlend;                //結(jié)束位 0xFF
}

int32 zlbytes： 壓縮列表占用字節(jié)數(shù)
int32 zltail_offset： 最后一個(gè)元素距離起始位置的偏移量,用于快速定位到最后一個(gè)節(jié)點(diǎn)
int16 zllength：元素個(gè)數(shù)
T[] entries：元素內(nèi)容
int8 zlend：結(jié)束位 0xFF

壓縮列表為了支持雙向遍歷株憾，所以才會(huì)有 ztail_offset 這個(gè)字段，用來(lái)快速定位到最后一
個(gè)元素晒衩，然后倒著遍歷

entry的數(shù)據(jù)結(jié)構(gòu)：

struct entry{
    int<var> prevlen;            //前一個(gè) entry 的長(zhǎng)度
    int<var> encoding;            //元素類(lèi)型編碼
    optional byte[] content;    //元素內(nèi)容
}

entry它的 prevlen 字段表示前一個(gè) entry 的字節(jié)長(zhǎng)度号胚，當(dāng)壓縮列表倒著遍歷時(shí)，需要通過(guò)這
個(gè)字段來(lái)快速定位到下一個(gè)元素的位置浸遗。

1. 應(yīng)用場(chǎng)景：

由于list它是一個(gè)按照插入順序排序的列表猫胁，所以應(yīng)用場(chǎng)景相對(duì)還較多的，例如：

• 消息隊(duì)列：lpop和rpush（或者反過(guò)來(lái)跛锌，lpush和rpop）能實(shí)現(xiàn)隊(duì)列的功能
• 朋友圈的點(diǎn)贊列表弃秆、評(píng)論列表、排行榜：lpush命令和lrange命令能實(shí)現(xiàn)最新列表的功能髓帽，每次通過(guò)lpush命令往列表里插入新的元素菠赚，然后通過(guò)lrange命令讀取最新的元素列表。

2. list操作的常用命名：

rpush  [key] [value1] [value2] ......    鏈表右側(cè)插入

rpop    [key]  移除右側(cè)列表頭元素郑藏，并返回該元素

lpop   [key]    移除左側(cè)列表頭元素衡查，并返回該元素

llen  [key]     返回該列表的元素個(gè)數(shù)

lrem [key] [count] [value]  刪除列表中與value相等的元素，count是刪除的個(gè)數(shù)必盖。 count>0 表示從左側(cè)開(kāi)始查找拌牲，刪除count個(gè)元素俱饿，count<0 表示從右側(cè)開(kāi)始查找，刪除count個(gè)相同元素塌忽，count=0 表示刪除全部相同的元素

(PS:   index 代表元素下標(biāo)拍埠，index 可以為負(fù)數(shù)， index= 表示倒數(shù)第一個(gè)元素土居，同理 index=-2 表示倒數(shù)第二 個(gè)元素枣购。)

lindex [key] [index]  獲取list指定下標(biāo)的元素 （需要遍歷，時(shí)間復(fù)雜度為O(n)）

lrange [key]  [start_index] [end_index]   獲取list 區(qū)間內(nèi)的所有元素 （時(shí)間復(fù)雜度為 O（n））

ltrim  [key]  [start_index] [end_index]   保留區(qū)間內(nèi)的元素擦耀，其他元素刪除（時(shí)間復(fù)雜度為 O（n））

三棉圈、hash （字典）

Redis 中的 Hash和 Java的 HashMap 更加相似，都是數(shù)組+鏈表的結(jié)構(gòu)眷蜓，當(dāng)發(fā)生 hash 碰撞時(shí)將會(huì)把元素追加到鏈表上迄损，值得注意的是在 Redis 的 Hash 中 value 只能是字符串.

hset books java "Effective java" (integer) 1
hset books golang "concurrency in go" (integer) 1
hget books java "Effective java"
hset user age 17 (integer) 1
hincrby user age 1  #單個(gè) key 可以進(jìn)行計(jì)數(shù) 和 incr 命令基本一致 (integer) 18

Hash 和String都可以用來(lái)存儲(chǔ)用戶(hù)信息 ，但不同的是Hash可以對(duì)用戶(hù)信息的每個(gè)字段單獨(dú)存儲(chǔ)账磺；String存的是用戶(hù)全部信息經(jīng)過(guò)序列化后的字符串，如果想要修改某個(gè)用戶(hù)字段必須將用戶(hù)信息字符串全部查詢(xún)出來(lái)痊远，解析成相應(yīng)的用戶(hù)信息對(duì)象垮抗，修改完后在序列化成字符串存入。而 hash可以只對(duì)某個(gè)字段修改碧聪，從而節(jié)約網(wǎng)絡(luò)流量冒版，不過(guò)hash內(nèi)存占用要大于 String，這是 hash 的缺點(diǎn)逞姿。

1. 應(yīng)用場(chǎng)景：

• 購(gòu)物車(chē)：hset [key] [field] [value] 命令辞嗡， 可以實(shí)現(xiàn)以用戶(hù)Id，商品Id為field滞造，商品數(shù)量為value续室，恰好構(gòu)成了購(gòu)物車(chē)的3個(gè)要素。
• 存儲(chǔ)對(duì)象：hash類(lèi)型的(key, field, value)的結(jié)構(gòu)與對(duì)象的(對(duì)象id, 屬性, 值)的結(jié)構(gòu)相似谒养，也可以用來(lái)存儲(chǔ)對(duì)象挺狰。

2. hash常用的操作命令：

hset  [key]  [field] [value]    新建字段信息

hget  [key]  [field]    獲取字段信息

hdel [key] [field]  刪除字段

hlen  [key]   保存的字段個(gè)數(shù)

hgetall  [key]  獲取指定key 字典里的所有字段和值 （字段信息過(guò)多,會(huì)導(dǎo)致慢查詢(xún) 慎用：親身經(jīng)歷 曾經(jīng)用過(guò)這個(gè)這個(gè)指令導(dǎo)致線(xiàn)上服務(wù)故障）

hmset  [key]  [field1] [value1] [field2] [value2] ......   批量創(chuàng)建

hincr  [key] [field]   對(duì)字段值自增

hincrby [key] [field] [number] 對(duì)字段值增加number

四、set(集合)

Redis 中的 set和Java中的HashSet 有些類(lèi)似买窟，它內(nèi)部的鍵值對(duì)是無(wú)序的丰泊、唯一 的。它的內(nèi)部實(shí)現(xiàn)相當(dāng)于一個(gè)特殊的字典始绍，字典中所有的value都是一個(gè)值 NULL瞳购。當(dāng)集合中最后一個(gè)元素被移除之后，數(shù)據(jù)結(jié)構(gòu)被自動(dòng)刪除亏推，內(nèi)存被回收学赛。

1. 應(yīng)用場(chǎng)景：

• 好友年堆、關(guān)注、粉絲罢屈、感興趣的人集合：
  1. sinter命令可以獲得A和B兩個(gè)用戶(hù)的共同好友嘀韧；
  2. sismember命令可以判斷A是否是B的好友；
  3. scard命令可以獲取好友數(shù)量缠捌；
  4. 關(guān)注時(shí)锄贷，smove命令可以將B從A的粉絲集合轉(zhuǎn)移到A的好友集合
• 首頁(yè)展示隨機(jī)：美團(tuán)首頁(yè)有很多推薦商家，但是并不能全部展示曼月，set類(lèi)型適合存放所有需要展示的內(nèi)容谊却，而srandmember命令則可以從中隨機(jī)獲取幾個(gè)。
• 存儲(chǔ)某活動(dòng)中中獎(jiǎng)的用戶(hù)ID 哑芹，因?yàn)橛腥ブ毓δ苎妆妫梢员ＷC同一個(gè)用戶(hù)不會(huì)中獎(jiǎng)兩次。

2. set的常用命令：

sadd  [key]  [value]  向指定key的set中添加元素

smembers [key]    獲取指定key 集合中的所有元素

sismember [key] [value]   判斷集合中是否存在某個(gè)value

scard [key]    獲取集合的長(zhǎng)度

spop  [key]   彈出一個(gè)元素

srem [key] [value]  刪除指定元素

五聪姿、zset(有序集合)

zset也叫SortedSet一方面它是個(gè) set 碴萧，保證了內(nèi)部 value 的唯一性，另方面它可以給每個(gè) value 賦予一個(gè)score末购，代表這個(gè)value的排序權(quán)重破喻。它的內(nèi)部實(shí)現(xiàn)用的是一種叫作“跳躍列表”的數(shù)據(jù)結(jié)構(gòu)。

1. 應(yīng)用場(chǎng)景：

zset 可以用做排行榜盟榴，但是和list不同的是zset它能夠?qū)崿F(xiàn)動(dòng)態(tài)的排序曹质，例如： 可以用來(lái)存儲(chǔ)粉絲列表，value 值是粉絲的用戶(hù) ID擎场，score 是關(guān)注時(shí)間羽德，我們可以對(duì)粉絲列表按關(guān)注時(shí)間進(jìn)行排序。

zset 還可以用來(lái)存儲(chǔ)學(xué)生的成績(jī)迅办， value 值是學(xué)生的 ID, score 是他的考試成績(jī)宅静。 我們對(duì)成績(jī)按分?jǐn)?shù)進(jìn)行排序就可以得到他的名次。

2. zset有序集合的常用操作命令：

zadd [key] [score] [value] 向指定key的集合中增加元素

zrange [key] [start_index] [end_index] 獲取下標(biāo)范圍內(nèi)的元素列表站欺，按score 排序輸出

zrevrange [key] [start_index] [end_index]  獲取范圍內(nèi)的元素列表 坏为，按score排序 逆序輸出

zcard [key]  獲取集合列表的元素個(gè)數(shù)

zrank [key] [value]  獲取元素再集合中的排名

zrangebyscore [key] [score1] [score2]  輸出score范圍內(nèi)的元素列表

zrem [key] [value]  刪除元素

zscore [key] [value] 獲取元素的score

總結(jié)

本文很多概念都一帶而過(guò)了，只是給大家粗略的講述一下Redis五種基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)和應(yīng)用場(chǎng)景镊绪，旨在給小伙伴們一個(gè)面試備題的方向匀伏，后續(xù)會(huì)持續(xù)輸出Redis方面的文章，歡迎關(guān)注蝴韭，咱們一起學(xué)習(xí)拿offer够颠。

# 鏈接 Java程序員福利"常用資料分享"