- 整數(shù)集合(intset)是集合鍵的底層實(shí)現(xiàn)之一亏钩，當(dāng)一個(gè)集合只包含整數(shù)值元素契沫，并且這個(gè)集合的元素?cái)?shù)量不多時(shí)沛婴，Redis就會(huì)使用整數(shù)集合作為集合鍵的底層實(shí)現(xiàn)吼畏。
6.1整數(shù)集合的實(shí)現(xiàn)
- 整數(shù)集合可以保存的類型為int16_t , int32_t , int64_t的整數(shù)值，并且集合中不會(huì)出現(xiàn)重復(fù)的元素嘁灯。
結(jié)構(gòu)表示：
typedef struct inset{
//編碼方式
uint32_t encoding;
//集合包含的元素?cái)?shù)量
uint32_t length;
//保存元素的數(shù)組
int8_t contents[];
}intset;
WechatIMG64.jpeg
- contents 數(shù)組是整數(shù)集合的底層實(shí)現(xiàn)泻蚊；數(shù)組中按值的大小從小到大的有序排列，數(shù)組中不包含任何重復(fù)項(xiàng)丑婿。
- length 記錄了整數(shù)集合中元素的數(shù)量
雖然intset結(jié)構(gòu)將contents屬性聲明為int8_t類型的數(shù)組性雄，實(shí)際上contents數(shù)組不保存任何int8_t類型的值没卸，真正的類型取決于encoding屬性的值：
- 如果encoding 值為 INTSET_ENC_INT16 那么contents就是一個(gè)int16_t類型的數(shù)組（-32768 ~ 32767）
- 如果encoding 值為 INTSET_ENC_INT32 那么contents就是一個(gè)int32_t類型的數(shù)組（-2147483648 ~ 2147483647）
- 如果encoding 值為 INTSET_ENC_INT64 那么contents就是一個(gè)int64_t類型的數(shù)組（-9223372036854775808 ~ 9223372036854775807 ）
當(dāng)向一個(gè)底層為int16_t數(shù)組的整數(shù)集合中添加一個(gè)int64_t類型的數(shù)值時(shí)，整數(shù)集合中所有的元素都會(huì)被轉(zhuǎn)換為int64_t類型秒旋！
6.2升級(jí)
- 將一個(gè)新元素添加到整數(shù)集合里面约计，新元素類型比整數(shù)集合現(xiàn)有所有元素類型都要長(zhǎng)時(shí)，整數(shù)集合需要先進(jìn)行升級(jí)迁筛，才能將新元素添加到整數(shù)集合里面煤蚌。
升級(jí)步驟：
- 根據(jù)新元素的類型，擴(kuò)展整數(shù)集合底層數(shù)組的空間大小细卧，并為新元素分配空間尉桩。
- 將底層數(shù)組現(xiàn)有的所有元素都轉(zhuǎn)換成與新元素相同的類型，將類型轉(zhuǎn)換后的元素放到正確的位置上贪庙，在放置元素過程中蜘犁，繼續(xù)維持底層數(shù)組的有序性質(zhì)不變
- 將新元素添加到底層數(shù)組里面
每次向整數(shù)集合添加新元素都可能會(huì)引起升級(jí)，每次升級(jí)都需要對(duì)底層數(shù)組中已有的所有元素進(jìn)行類型轉(zhuǎn)換止邮；時(shí)間復(fù)雜度為O(n)
6.3升級(jí)的好處
升級(jí)策略有兩個(gè)好處：
- 提升整數(shù)的靈活性:整數(shù)集合通過自動(dòng)升級(jí)底層數(shù)組來適應(yīng)新的元素这橙，隨意的將int16_t, int32_t, 或者int64_t 的整數(shù)添加到集合中，不必?fù)?dān)心出現(xiàn)類型錯(cuò)誤导披，這種做法非常靈活屈扎。
- 盡可能的節(jié)約內(nèi)存：可以讓集合能同時(shí)保存三種不同類型的值，又可以確保升級(jí)操作只會(huì)在有需要的時(shí)候進(jìn)行盛卡，這可以盡量節(jié)省內(nèi)存助隧。
6.4降級(jí)
- 整數(shù)集合不支持降級(jí)操作，一旦對(duì)數(shù)組進(jìn)行了升級(jí)滑沧，編碼就會(huì)一直保持升級(jí)后的狀態(tài)并村。
整數(shù)集合API
| 函數(shù): 作用 | 時(shí)間復(fù)雜度 |
|---|---|
| intsetNew:創(chuàng)建一個(gè)新的整數(shù)集合 | O(1) |
| intsetAdd:將給定的元素添加到整數(shù)集合里面 | O(n) |
| intsetRemove:從整數(shù)集合中移除給定元素 | O(n) |
| intsetFind:檢查給定值是否存在于集合 | O(logN) |
| intsetRandom:從整數(shù)集合中隨機(jī)返回一個(gè)元素 | O(1) |
| intsetGet:取出底層數(shù)組在給定索引上的元素 | O(1) |
| intsetLen:返回整數(shù)集合包含的元素個(gè)數(shù) | O(1) |
| intsetBlobLen:返回整數(shù)集合占用的內(nèi)存字節(jié)數(shù) | O(1) |
