Redis數(shù)據(jù)結(jié)構(gòu)之intset整數(shù)集合使用學(xué)習(xí)
Redis數(shù)據(jù)結(jié)構(gòu)intset
整數(shù)集(intset)是集合鍵的底層實(shí)現(xiàn)之一,當(dāng)一個(gè)集合只包含整數(shù)值元素,并且這個(gè)集合的元素?cái)?shù)量不多時(shí),Redis 就會(huì)使用整數(shù)集合作為集合鍵的底層實(shí)現(xiàn)。
整數(shù)集合可以保存類型為 int16_t,int32_t,int64_t 的整數(shù)值,并且保證集合中不會(huì)出現(xiàn)重復(fù)元素。
1、整數(shù)集合
以下是整數(shù)集合的結(jié)構(gòu):
typedef struct intset{ // 編碼方式 uint32_t encoding; // 集合包含的元素?cái)?shù)量 uint_32_t length; // 保存元素的數(shù)組 int8_t contents[]; }
其中,encoding 屬性的值為 INTSET_ENC_INT16
,INTSET_ENC_INT32
,INTSET_ENC_INT64
,分別表示 contents 數(shù)組里存儲(chǔ)的整數(shù)類型是 int16_t
,int32_t
,int64_t
。
當(dāng) encoding 的值為 INTSET_ENC_INT16
,contents 數(shù)組里每個(gè)項(xiàng)都是 int16_t 類型的整數(shù)值,范圍在 -215 ~ 2 15 - 1 之間,也就是 -32768 ~ 32767
當(dāng) encoding 的值為 INTSET_ENC_INT32
,contents 數(shù)組里每個(gè)項(xiàng)都是 int32_t 類型的整數(shù)值,范圍在 -231 ~ 2 31 - 1 之間
當(dāng) encoding 的值為 INTSET_ENC_INT64
,contents 數(shù)組里每個(gè)項(xiàng)都是 int64_t 類型的整數(shù)值,范圍在 -263 ~ 2 63 - 1 之間
length 屬性記錄的是整數(shù)集合中包含的元素?cái)?shù)量,也就是 contents 數(shù)組的長度。
contents 數(shù)組中的數(shù)值按值的大小從小到大有序排列,并且不包含重復(fù)項(xiàng)。
contents 數(shù)組中包含的元素類型都是一樣的,比如當(dāng)前數(shù)組中元素的類型是 int16_t,如果要向其中插入的整數(shù)值的類型是 int32_t,那么 contents 數(shù)組就要將 contents 數(shù)組的元素類型先升級(jí)再插入,這個(gè)就涉及升級(jí)的操作。
2、升級(jí)
當(dāng)我們要添加到整數(shù)集合中的元素的類型比現(xiàn)有所有元素類型都要長時(shí),整數(shù)集合需要進(jìn)行升級(jí)(upgrade)操作,然后才能將新元素插入整數(shù)集合中。
升級(jí)并添加新元素共分為三步進(jìn)行:
- 根據(jù)新元素類型,擴(kuò)展整數(shù)集合底層數(shù)組的空間大小,并為新元素分配空間
- 將底層數(shù)組所有元素轉(zhuǎn)換成與新元素相同的類型,并將類型轉(zhuǎn)換后的元素放在正確的位上,且維持其有序性不變
- 將新元素添加到底層數(shù)組里面
對(duì)于整數(shù)的三種類型,int16_t,int32_t,int64_t,每種類型的數(shù)據(jù)占用的位數(shù)分別是 16,32,64
假設(shè)當(dāng)前 contents 數(shù)組有三個(gè)元素:1,2,3。類型是 int16_t,對(duì)應(yīng)的元素和位數(shù)展示如下:
位 | 0-15位 | 16-31位 | 32-47位 |
---|---|---|---|
元素 | 1 | 2 | 3 |
接下來需要添加一個(gè)整數(shù),65535,類型是 int32_t,那么就需要先分配額外的空間,新分配的空間長度等于元素總數(shù) 新類型的位數(shù) - 原有空間長度 = 4 32 - 48 = 80:
位 | 0-15位 | 16-31位 | 32-47位 | 48-127位 |
---|---|---|---|---|
元素 | 1 | 2 | 3 | 新分配空間 |
然后分別將元素 3,2,1 移動(dòng)到對(duì)應(yīng)的空間內(nèi),再將新元素 65535 放在對(duì)應(yīng)的空間上:
位 | 0-31位 | 32-63位 | 64-95位 | 96-127位 |
---|---|---|---|---|
元素 | 1 | 2 | 3 | 65535 |
然后將整數(shù)集合 encoding 屬性的值從 INTSET_ENC_INT16 改為 INTSET_ENC_INT32,length 屬性的值從 3 改為 4。
3、升級(jí)的好處
為整數(shù)集合使用升級(jí)策略有兩個(gè)好處,一個(gè)是提升整數(shù)集合的靈活性,一個(gè)是盡可能的節(jié)約內(nèi)存
因?yàn)?C語言是靜態(tài)類型語言,通常不會(huì)將兩種不同類型的值放在一個(gè)數(shù)據(jù)結(jié)構(gòu)里,但是整數(shù)集合可以通過自動(dòng)升級(jí)底層數(shù)組來適應(yīng)新元素,所以我們可以隨意將 int16_t,int32_t,int64_t 類型的整數(shù)添加到集合中,而不必?fù)?dān)心出現(xiàn)類型錯(cuò)誤
另外,要讓數(shù)組可以同時(shí)保存 int16_t,int32_t,int64_t 這三種類型的整數(shù),最簡單的方式是直接使用 int64_t 類型的數(shù)組去保存數(shù)據(jù),但這樣的話如果元素都是 int16_t,int32_t 類型的值,那么會(huì)出現(xiàn)浪費(fèi)內(nèi)存的情況。
因此現(xiàn)在升級(jí)策略可以盡量節(jié)約內(nèi)存。
4、降級(jí)
整數(shù)集合不支持降低操作,一旦對(duì)數(shù)組進(jìn)行了升級(jí),編碼就會(huì)一直保持升級(jí)后的狀態(tài)。
比如前面的數(shù)組 1,2,3,65535,如果我們刪除了 65535,整數(shù)集合還是會(huì)維持原有 INTSET_ENC_INT64 的編碼,底層數(shù)組也還是 int64_t 類型的。
以上就是Redis數(shù)據(jù)結(jié)構(gòu)之intset整數(shù)集合使用學(xué)習(xí)的詳細(xì)內(nèi)容,更多關(guān)于Redis數(shù)據(jù)結(jié)構(gòu)intset的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
- redis底層數(shù)據(jù)結(jié)構(gòu)之ziplist實(shí)現(xiàn)詳解
- Redis數(shù)據(jù)結(jié)構(gòu)之跳躍表使用學(xué)習(xí)
- Redis數(shù)據(jù)結(jié)構(gòu)之listpack和quicklist使用學(xué)習(xí)
- Redis數(shù)據(jù)結(jié)構(gòu)面試高頻問題解析
- Redis數(shù)據(jù)結(jié)構(gòu)類型示例解析
- Redis數(shù)據(jù)結(jié)構(gòu)原理淺析
- redis底層數(shù)據(jù)結(jié)構(gòu)之skiplist實(shí)現(xiàn)示例
相關(guān)文章
Redis如何使用zset處理排行榜和計(jì)數(shù)問題
Redis的ZSET數(shù)據(jù)結(jié)構(gòu)非常適合處理排行榜和計(jì)數(shù)問題,它可以在高并發(fā)的點(diǎn)贊業(yè)務(wù)中高效地管理點(diǎn)贊的排名,并且由于ZSET的排序特性,可以輕松實(shí)現(xiàn)根據(jù)點(diǎn)贊數(shù)實(shí)時(shí)排序的功能2025-02-02Redis分布式鎖的正確實(shí)現(xiàn)方法總結(jié)
在本篇文章里小編給大家整理的是關(guān)于Redis分布式鎖的正確實(shí)現(xiàn)方式介紹,有興趣的朋友們可以學(xué)習(xí)下。2020-02-02Redis模擬延時(shí)隊(duì)列實(shí)現(xiàn)日程提醒的方法
文章介紹了如何使用Redis實(shí)現(xiàn)一個(gè)簡單的延時(shí)任務(wù)隊(duì)列,通過Redis的有序集合特性來存儲(chǔ)和管理延時(shí)任務(wù),通過定期檢查集合中小于等于當(dāng)前時(shí)間的任務(wù)并執(zhí)行,可以實(shí)現(xiàn)延時(shí)任務(wù)的管理,感興趣的朋友跟隨小編一起看看吧2024-11-11Redis基本數(shù)據(jù)類型Zset有序集合常用操作
這篇文章主要為大家介紹了redis基本數(shù)據(jù)類型Zset有序集合常用操作,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2022-05-05