整數(shù)集合（intset）是集合鍵的底層實(shí)現(xiàn)之一： 當(dāng)一個(gè)集合只包含整數(shù)值元素， 并且這個(gè)集合的元素?cái)?shù)量不多時(shí)， Redis 就會使用整數(shù)集合作為集合鍵的底層實(shí)現(xiàn)。

127.0.0.1:6379> sadd numbers 1 2 3 4 5
(integer) 5
127.0.0.1:6379> object encoding numbers
"intset"

這么做的好處是當(dāng)集合中只有少量的整數(shù)元素的時(shí)候，采用之前介紹的其他數(shù)據(jù)結(jié)構(gòu)，比如sds，都會占用比較大的內(nèi)存，但如果僅保存為整數(shù)集合的話，則會更加經(jīng)濟(jì)。

整數(shù)數(shù)組數(shù)據(jù)結(jié)構(gòu)

整數(shù)數(shù)組的定義位于intset.h中，具體如下：

typedef struct intset {
    uint32_t encoding;  // 編碼方式
    uint32_t length;   // 保存的元素個(gè)數(shù)
    int8_t contents[];  // 保存元素的數(shù)組
 } 
    intset;

雖然 intset 結(jié)構(gòu)將 contents 屬性聲明為 int8_t 類型的數(shù)組， 但實(shí)際上 contents 數(shù)組并不保存任何 int8_t 類型的值 —— contents 數(shù)組的真正類型取決于 encoding 屬性的值：

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

/* Return the required encoding for the provided value. */
static uint8_t _intsetValueEncoding(int64_t v) {    
    if (v < INT32_MIN    v > INT32_MAX)        
        return INTSET_ENC_INT64;    
    else if (v < INT16_MIN    v > INT16_MAX)        
        return INTSET_ENC_INT32;    
    else
      return INTSET_ENC_INT16;
}

可以看到一共會有三種類型，分別對應(yīng)int_16, int_32, int_64。

整數(shù)數(shù)組中所有的元素在數(shù)組中按值的大小從小到大有序地排列， 并且數(shù)組中不包含任何重復(fù)項(xiàng)。

整數(shù)集合操作

創(chuàng)建整數(shù)集合

// 初始化空的整數(shù)集合intset *intsetNew(void) {
    intset *is = zmalloc(sizeof(intset));    
    is->encoding = intrev32ifbe(INTSET_ENC_INT16); // 默認(rèn)創(chuàng)建int_16的編碼格式
    is->length = 0;    
    return is;
}

插入一個(gè)元素

/* Insert an integer in the intset */intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;    
    if (success) *success = 1;    // 如果超出了當(dāng)前編碼格式所能表示的范圍，則升級整數(shù)集合并添加元素
    if (valenc > intrev32ifbe(is->encoding)) {        
    /* This always succeeds, so we don't need to curry *success. */
        return intsetUpgradeAndAdd(is,value);
    } else {        // 如果元素已經(jīng)存在于集合，success返回0
        // 如果不存在的話， 這個(gè)函數(shù)會返回元素應(yīng)該插入的位置pos
        if (intsetSearch(is,value,&pos)) {            
        if (success) *success = 0;            
        return is;
        }        // 否則，需要重新調(diào)整集合的大小
        is = intsetResize(is,intrev32ifbe(is->length)+1);        // 將pos之后的數(shù)據(jù)全都向后挪動一個(gè)位子
        if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
    }

    _intsetSet(is,pos,value); // 添加數(shù)據(jù)到第pos位
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1); // 調(diào)整元素個(gè)數(shù)
    return is;
}

在插入元素的時(shí)候，需要根據(jù)新元素的大小來重新確定所采用的編碼。如果新元素超出了原有編碼的表示范圍，就需要調(diào)整編碼，同時(shí)調(diào)整集合中所有其他元素的編碼格式。調(diào)整編碼是一個(gè)不可逆的過程，就是說只能從小的編碼調(diào)整到大的編碼，只能升級不能降級。

升級過程

升級整數(shù)集合并添加新元素調(diào)用的是intsetUpgradeAndAdd函數(shù)，共分為三步進(jìn)行：

• 根據(jù)新元素的類型， 擴(kuò)展整數(shù)集合底層數(shù)組的空間大小， 并為新元素分配空間。

• 將底層數(shù)組現(xiàn)有的所有元素都轉(zhuǎn)換成與新元素相同的類型， 并將類型轉(zhuǎn)換后的元素放置到正確的位上， 而且在放置元素的過程中， 需要繼續(xù)維持底層數(shù)組的有序性質(zhì)不變。

• 將新元素添加到底層數(shù)組里面。

/* Upgrades the intset to a larger encoding and inserts the given integer. */static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {    // 當(dāng)前的編碼
    uint8_t curenc = intrev32ifbe(is->encoding);    // 根據(jù)新元素的值獲得新的編碼
    uint8_t newenc = _intsetValueEncoding(value);    
    int length = intrev32ifbe(is->length);    
    // 由于整數(shù)集合是一個(gè)有序集合，所以新的這個(gè)超出范圍的元素，要不插入頭部，要不插入尾部
    // 當(dāng)value大于0的時(shí)候，就是插入到尾部，否則插入到頭部，用參數(shù)prepend來標(biāo)記
    int prepend = value < 0 ? 1 : 0;    
    
    /* First set new encoding and resize */
    // 重新設(shè)置整數(shù)集合的編碼
    is->encoding = intrev32ifbe(newenc);    // 根據(jù)新編碼調(diào)整整數(shù)集合的大小
    is = intsetResize(is,intrev32ifbe(is->length)+1);    // 從尾部向頭部進(jìn)行升級，這樣在挪動其中的元素的時(shí)候，不會覆蓋原來的值
    while(length--)        
          // 如果新元素是插入到尾部，prepend==0， 所以原來最后的元素是挪動到length位置
        // 如果新元素是插入到頭部，prepend==1，所有的元素都要向后挪動一個(gè)位置，將頭部空出來
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));    
        
        /* Set the value at the beginning or the end. */
    if (prepend)        
    // 如果prepend==1， 插入到頭部
        _intsetSet(is,0,value);    
       else
        // 否則，設(shè)置最后一個(gè)位置的元素為value
        _intsetSet(is,intrev32ifbe(is->length),value);    // 元素個(gè)數(shù)加1
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);    
    return is;
}

而整數(shù)集合現(xiàn)在的做法既可以讓集合能同時(shí)保存三種不同類型的值， 又可以確保升級操作只會在有需要的時(shí)候進(jìn)行， 這可以盡量節(jié)省內(nèi)存。

查找元素

查找的時(shí)候，需要先判斷要查找的元素是否在當(dāng)前編碼的有效范圍內(nèi)，如果不在當(dāng)前范圍內(nèi)，可以直接返回。

另外因?yàn)檎麛?shù)集合是一個(gè)有序集合，可以采用二分查找的辦法，

uint8_t intsetFind(intset *is, int64_t value) {    // 獲得目標(biāo)值的編碼
    uint8_t valenc = _intsetValueEncoding(value);    // 只有目標(biāo)值的編碼比當(dāng)前編碼小，才繼續(xù)執(zhí)行查找過程
    return valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,NULL);
}// 如果找到這個(gè)元素，返回1，同時(shí)pos表示這個(gè)值在整數(shù)集合里邊的位置
// 如果沒有找到這個(gè)元素，返回0， 同時(shí)pos表示這個(gè)值可以插入的位置
static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {    
int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
    int64_t cur = -1;    
    
    /* The value can never be found when the set is empty */
    // 如果集合的長度為0， 直接返回0
    if (intrev32ifbe(is->length) == 0) {        
    if (pos) *pos = 0;        
    return 0;
    } else {        
    /* Check for the case where we know we cannot find the value,
         * but do know the insert position. */
        // 如果目標(biāo)值大于當(dāng)前最大值，肯定找不到，返回0， 同時(shí)待插入的位置pos為length
        if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {            
        if (pos) *pos = intrev32ifbe(is->length);            
        return 0;
        } else if (value < _intsetGet(is,0)) {            
        // 如果目標(biāo)址小于當(dāng)前最小值，返回0， 同時(shí)待插入的位置pos為0
            if (pos) *pos = 0;            
            return 0;
        }
    }    // 二分查找
    while(max >= min) {        // 得到中間位置
        mid = ((unsigned int)min + (unsigned int)max) >> 1;        // 得到中間位置的值
        cur = _intsetGet(is,mid);        
        if (value > cur) {
            min = mid+1;
        } else if (value < cur) {
            max = mid-1;
        } else {            
        break;
        }
    }    if (value == cur) {        
    if (pos) *pos = mid;        
    return 1;
    } else {        
    if (pos) *pos = min;        
    return 0;
    }
}

以上就是Redis中整數(shù)小集合 的詳細(xì)內(nèi)容，更多請關(guān)注php中文網(wǎng)其它相關(guān)文章！