# 0. Hash@数据结构

## 开始的开始 - ziplist

常见的数据结构, 包括set/hash, 在内容较少的时候是通过ziplist来是实现的, 为:

```c
type ziplist struct {
        size         int
        tail_offset  int
        count        int 
        entries      []entry
}

type entry struct {
        prev_len     int8/32
        encoding     int8/32
        data         []byte
}
```

先来看ziplist: count与entries表示数据单元及元素数量, 这很好理解. size字段表示整体的长度, tail\_offset表示从这个位置开始如何定位到最后一个元素.

![](https://3064259429-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MC_ucxnzAClkrgsGdFP%2Fsync%2F523a96d3ef702ba931cffa0783ba9123eea1d4be.png?generation=1597894659199121\&alt=media)

然后我们来看元素entry, data很好理解. encoding则是表示了里面数据的类型, string还是int等等, 关键是`prev_len`, 这里面存了一个数值, 用于表示上一个元素的长度, 帮助我们定位到上一个元素用的.

关键是这个长度是可变的, 它可以是8位, 也可以是32位, 如果是8位那么这个值最多也就是2^8, 但如果上一个元素的长度大于这个长度的话, 我们就会把这个元素变成32位, 其中第一位是`0xFF`表示此32位用于表示长度

## 关于ziplist

从上面我们也能看到ziplist中的每一个元素都是前后紧紧贴在一起的, 这虽然比较省空间, 但也导致插入元素的时候都要重新分配内存.

另一种常见的问题叫做级联更新, 意思是某一瞬间插入的新元素很大, 那么下一个元素的`prev_len`从8位变成32位, 联锁的导致后面的元素扩张

## listpack

listpack可以用来取代ziplist的, 区别是微小的: 没有`tail_offset`字段, 以及

```go
type entry struct {
        encoding   int8/32
        data       []byte
        size       int8/32
}
```

![](https://3064259429-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MC_ucxnzAClkrgsGdFP%2Fsync%2F523a96d3ef702ba931cffa0783ba9123eea1d4be.png?generation=1597894659199121\&alt=media)

最主要的是我们使用了size字段替代了`prev_len`, 并把这个字段放在一个单元的最后面, 那么现在假设我们在data2, 怎么定位到上一个元素data1呢? 我们站在data2上直接向前去读一个整数就能拿到data1的长度, 进而就能定位到data1了x

## dict

在hash/set元素非常少的时候我们使用的是ziplist, 然而等元素多起来了以后, 就会使用dict来存储数据, 这个实现非常简单, 两个hashtable渐进式搬运, 解决冲突的方式是挂链表