ziplist vs 普通数组，redis hash 实现

@[TOC](ziplist vs 普通数组以及redis hash 在ziplist的实现)

## zipList 特点

1. 需要连续的内存地址。同时也需要预分配地址。

2. 可以存不定长的数据，但是有长度限制。

3. 从数组尾巴插入，不会造成数组移位的情况。

4. 插入，删除，都有可能造成数组移位，而造成的大量内存copy 的行为，插入，删除平均时间复杂度为O(n)， 最差的时间时间复杂度为O(n2)

5. 查询效率跟普通数组相同为O(n)

**ziplist的模型如下图：**

这是整个ziplist的结构最开头

zlbytes: 是一个4字节的无符号整数，来表示整个ziplist的长度，单位为字节，好处是当ziplist做扩容的时候，我们不需要遍历整个ziplist

zltail: zltail是记录最后一个entry的起始位置，这样的好处是在于不需要在做pop操作的时候便利整个ziplist。ziptail是一个

zllen: zllen 表示整个entry的个数(注意跟上面的单位字节做区分），当需要注意的当总的entry个数超过2^16-2个的时候，这个部分是2^16-1 ，即 11111111 11111111。 所以当zllen 是这个值的时候如果需要知道整个entry 的个数，则要遍历整个entry。

zlend: 是一个字节为255的特殊entry，来表示整个ziplist的结尾位置。

entry: 可以认为是一个可变长度的数组结构，具体的entry 内部构造下面会详解。单个entry的长度是不固定

* The general layout of the ziplist is as follows:
*
* <zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
*
* NOTE: all fields are stored in little endian, if not specified otherwise.
*
* <uint32_t zlbytes> is an unsigned integer to hold the number of bytes that
* the ziplist occupies, including the four bytes of the zlbytes field itself.
* This value needs to be stored to be able to resize the entire structure
* without the need to traverse it first.
*
* <uint32_t zltail> is the offset to the last entry in the list. This allows
* a pop operation on the far side of the list without the need for full
* traversal.
*
* <uint16_t zllen> is the number of entries. When there are more than
* 2^16-2 entries, this value is set to 2^16-1 and we need to traverse the
* entire list to know how many items it holds.
*
* <uint8_t zlend> is a special entry representing the end of the ziplist.
* Is encoded as a single byte equal to 255. No other normal entry starts
* with a byte set to the value of 255.

上面是原文的注解

**entry的结构图如下：**

entry 分为3个部分，

prevlength: 表示前一个entry的长度， prevlength 可能占用1个字节或者4个字节，当前面entry小于254个字节时候用一个字节来表示

如果前面entry长度大于254的是第一个字节表示为 11111110 为标示位（这样就是区分了zlend这个字段），后面3位来表示具体前面entry的长度。

d

encoding: 主要分为两大类，第一类是数字，第二类是字符，具体我们下面分析

data：表示具体存进来的数据。

数字类型：encoding 会占用一个字节

111111110: 表示1个字节的整数

11000000: 表示2字节的整数

11110000: 表示3字节的整数

11010000: 表示4字节的整数

11100000: 表示8字节的整数

最后一个表示的是11110001到11111101范围内，则encoding 和data 会在一起，表示 1到13.

相关代码如下

/* Read integer encoded as 'encoding' from 'p' */
int64_t zipLoadInteger(unsigned char *p, unsigned char encoding) {
    int16_t i16;
    int32_t i32;
    int64_t i64, ret = 0;
    //#define ZIP_INT_8B 0xfe
    if (encoding == ZIP_INT_8B) {
        ret = ((int8_t*)p)[0];
    } 
    //#define ZIP_INT_16B (0xc0 | 0<<4)
    else if (encoding == ZIP_INT_16B) {
        memcpy(&i16,p,sizeof(i16));
        memrev16ifbe(&i16);
        ret = i16;
     //#define ZIP_INT_16B (0xc0 | 0<<4)   
    } else if (encoding == ZIP_INT_32B) {
        memcpy(&i32,p,sizeof(i32));
        memrev32ifbe(&i32);
        ret = i32;
     // ZIP_INT_24B (0xc0 | 3<<4) 
    } else if (encoding == ZIP_INT_24B) {
        i32 = 0;
        memcpy(((uint8_t*)&i32)+1,p,sizeof(i32)-sizeof(uint8_t));
        memrev32ifbe(&i32);
        ret = i32>>8;
        //ZIP_INT_64B (0xc0 | 2<<4)
    } else if (encoding == ZIP_INT_64B) {
        memcpy(&i64,p,sizeof(i64));
        memrev64ifbe(&i64);
        ret = i64;
        //ZIP_INT_IMM_MIN 0xf1    /* 11110001 */  ZIP_INT_IMM_MAX 0xfd    /* 11111101 */
    } else if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX) {
        //实际返回的是0-12因为还减去1
        //ZIP_INT_IMM_MASK 为00001111 ZIP_INT_IMM_MAX 0xfd    /* 11111101 */
        ret = (encoding & ZIP_INT_IMM_MASK)-1;
    } else {
        assert(NULL);
    }
    return ret;
}

字符串的encoding 主要由第一个字节的前两位来判断分别是00，01，10，为标示位然后econding由分别会占用1字节， 2字节和5字节。

1. 前面两位00，表示这是一个长度小于63字节字符串，pppppp表示字符串的长度，单位为字节，比如 00111111，即表示后面字符串是63个字节。
2. 前面两位01， 则后面14位来表示长度即0到2^14-1，总共两个字节
3. 前面两位为10，但是第一个字节后6位不用来表示长度，即第一个8位为10000000，后面还有4个字节表示字符的具体长度

具体的代码如下

unsigned int zipStoreEntryEncoding(unsigned char *p, unsigned char encoding, unsigned int rawlen) {
    unsigned char len = 1, buf[5];
		//如果是string encoding
    if (ZIP_IS_STR(encoding)) {
        /* Although encoding is given it may not be set for strings,
         * so we determine it here using the raw length. */
        if (rawlen <= 0x3f) {
            if (!p) return len;
            buf[0] = ZIP_STR_06B | rawlen;
        } else if (rawlen <= 0x3fff) {
            len += 1;
            if (!p) return len;
            buf[0] = ZIP_STR_14B | ((rawlen >> 8) & 0x3f);
            buf[1] = rawlen & 0xff;
        } else {
            len += 4;
            if (!p) return len;
            buf[0] = ZIP_STR_32B;
            buf[1] = (rawlen >> 24) & 0xff;
            buf[2] = (rawlen >> 16) & 0xff;
            buf[3] = (rawlen >> 8) & 0xff;
            buf[4] = rawlen & 0xff;
        }
    } else {
        /* Implies integer encoding, so length is always 1. */
        if (!p) return len;
        buf[0] = encoding;
    }

    /* Store this length at p. */
    memcpy(p,buf,len);
    return len;
}

总的来说，是一个比较灵活节省内存的数据结构，在redis 数据结构里面hash，set，和zset 会使用到该数据结构

## 一般数组的特点：

1. 需要连续的内存地址。

2. 数组的元素是定长，需要一开始就要去做声明，所以会出现一个什么的情况了即使我们一个数组里面可能大多数都是小于100的数字，但是因为我们长度限定的问题，所以会有， 数组单位长度>= 数组元素的最大长度。

**整型数组**

**引用类型数组（在java 里面一切皆为引用）：**

## hash的key和value 在ziplist的存储

首先我们看到官网的的描述:

我们拿redis 的hash 来举例， 首先redis 的hash 也是通过链地址法来实现，entry 即为链表中的对象所以在总的**总entry数量少于512个****且单个entry的key或者value 不超过64个字节**的时候，hash会使用ziplist 这种数据结构来存储。

那么疑问来了，如何在一个ziplist的里面来表现形式了， **key 和value 在ziplist 为两个相邻的元素**

比如 我们在redis 客户端执行 hset test1 123 456， 那么该内存的表现形式如下图：

其它相关参考地址：

https://www.jianshu.com/p/afaf78aaf615