总览

作用于

• 数量比较少的hash、zset

ziplist数据结构

ziplist是一个用一段特殊编码实现的双向链表，优势是占用内存小，可以存储字符串类型和整数类型。在内存布局中包含一下几个字段

• zlbytes：（4 bytes）整个链表占的内存字节数
• zltail：（4 bytes）链表尾部节点的偏移量，存储这个信息的作用是实现反向遍历，因为需要知道尾部的地址才能从尾部向前遍历节点
• zllen：（2 bytes）节点长度
• entry：（n bytes）数据节点，数据节点包含3个结构，下面详细讲解
• zlend：（1 bytes）结束标识符，固定是0xFF

前言

在研究elasticsearch排序插件的时候，自研的排序算法产生的数值远远大于64位数字的最大值，所以只能选择字符串排序。

字符串数字排序

字符串是按ASCII编码排序的，对于数字排序是存在问题的。比如有一下这些数字字符串：1、2、4、12、3，排序的结果就是1、12、2、3、4。这不符合数字排序的预期，这也正是原先在做solr的时候没有选择字符串排序的原因。在查询资料的时候，找到这个贴子 https://discuss.elastic.co/t/sorting-a-string-field-numerically/9489/7 其中提供了一种方法：把数字的位数追加到原数字的前面，追加的数字需要有占位符，比如已知最长的位数不超过100，追加的数字就是有两位，01、02、12这样。为什么需要这样呢？因为在对比字符串的原理是从0下标开始取出字符做对比，先取出位数做对比就能解决数字字符串排序的问题。

（开局一张图，下面全靠编）

在Redis 3.2之前的版本，Redis使用压缩链表（ziplist）和双端链表（adlist）来实现List。当元素个数比较少的情况下，使用压缩链表，当数据到一定的量，升级为双端链表。这是因为压缩链表可以节省内存空间，但压缩链表的数据是连续的，数据的插入压缩链表需要重新分配内存，这会影响到压缩链表的执行效率，所以升级到双端链表。快速链表是综合考虑时间效率和空间效率引入的新型数据结构。

原理

总览

分析

跳表是一个非常优秀的数据结构，优秀在性能媲美红黑树，优秀在实现起来比红黑树简单（跳表实现也不是很简单）。在一个有序的数组中，我们可以使用二分查找来定位节点的位置，但在普通的链表中则不能，需要把链表从头到尾遍历一个，时间复杂度是O(n)。实际上，我们在链表的基础上做一点改造就能实现类似二分查找的数据结构，这就是链表。

普通的链表数据结构如下：

数据结构

在3.2版本之前，动态字符串的结构是这样的。

struct sdshdr {
    // buf数组的长度
    unsigned int len;
    // buf数组还剩空间
    unsigned int free;
    char buf[];
};

基础知识

链表是比较常用的一个数据结构，在JAVA中的实现是LinkedList，但是在C的标准库中并没有内置的链表可供使用，所以redis实现了一套。我们知道数组的内存地址是连续的，最大的特征是支持随机访问，所以数组的读时间复杂度是O(1)，但是在写的场景时间复杂度是O(N)，在某个位置插入一条数据，需要把这个位置后的所有数据向后移动一位，在内存不足时还需要重新申请内存。

而链表的内存结构是不连续的，不支持随机访问，当需要读取某个位置的数据时，需要从头遍历到尾部才能实现，所有读是O(N)；对链表写入操作时，因为两个节点的内存都是独立不连续的，在这中间插入数据的时候，只要把next、prev指针重新指向即可，所以写是O(1)。这就是数组和链表的基础知识，我们看下在redis中的具体实现是怎么样的吧！

原文链接：https://my.oschina.net/hosee/blog/618828

一、红黑树的介绍

先来看下算法导论对R-B Tree的介绍： 红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

原文链接：https://my.oschina.net/hosee/blog/618953

JDK7中的HashMap

HashMap底层维护一个数组，数组中的每一项都是一个Entry

transient Entry<K,V>[] table;

前言

现在一般都JDK8了，为什么还要说JDK7呢。因为JDK7和JDK8的hashmap实现不一样，JDK7是用数组+链表实现的，而JDK8是红黑树。学习都是个慢慢渐进的过程。

实现

时间复杂度：