面试官：你看过Redis数据结构底层实现吗？

口试中，redis也是很受口试官亲睐的一部门。我向在这里讲的是redis的底层数据布局，而不是你领略的五大数据布局。你有没有想过redis底层是奈何的数据布局呢，他们和我们java中的HashMap、List、等行使的数据布局有什么区别呢。

1. 字符串处理赏罚(string)

我们都知道redis是用C说话写，可是C说话处理赏罚字符串和数组的本钱是很高的，下面我别离说几个例子。

没稀有据布局支撑的几个题目

1.  极其轻易造成缓冲区溢出题目，好比用strcat()，在用这个函数之前必必要先给方针变量分派足够的空间，不然就会溢出。
2.  假如要获取字符串的长度，没稀有据布局的支撑，也许就必要遍历，它的伟大度是O(N)
3.  内存重分派。C字符串的每次改观(曾长或收缩)城市对数组作内存重分派。同样，假如是收缩，没有处理赏罚许多几何余的空间，也会造成内存走漏。

好了，Redis本身构建了一种名叫Simple dynamic string(SDS)的数据布局，他别离对这几个题目作了处理赏罚。我们先来看看它的布局源码：

struct sdshdr{  
     //记录buf数组中已行使字节的数目  
     //便是 SDS 生涯字符串的长度  
     int len;  
     //记录 buf 数组中未行使字节的数目  
     int free;  
     //字节数组，用于生涯字符串  
     char buf[];  
} 

再来说说它的利益：

1.  开拓者不消担忧字符串改观造成的内存溢出题目。
2.  常数时刻伟大度获取字符串长度len字段。
3.  空间预分派free字段，会默认留够必然的空间防备多次重分派内存。

更多相识：https://redis.io/topics/internals-sds

这就是string的底层实现，更是redis对全部字符串数据的处理赏罚方法(SDS会被嵌套到此外数据布局里行使)。

2. 链表

Redis的链表在双向链表上扩展了头、尾节点、元素数等属性。

2.1 源码

ListNode节点数据布局：

typedef  struct listNode{  
       //前置节点  
       struct listNode *prev;  
       //后置节点  
       struct listNode *next;  
       //节点的值  
       void *value;    
}listNode 

链表数据布局：

typedef struct list{  
     //表头节点  
     listNode *head;  
     //表尾节点  
     listNode *tail;  
     //链表所包括的节点数目  
     unsigned long len;  
     //节点值复制函数  
     void (*free) (void *ptr);  
     //节点值开释函数  
     void (*free) (void *ptr);  
     //节点值比拟函数  
     int (*match) (void *ptr,void *key);  
}list; 

从上面可以看到，Redis的链表有这几个特点：

1.  可以直接得到头、尾节点。
2.  常数时刻伟大度获得链表长度。
3.  是双向链表。

3. 字典(Hash)

Redis的Hash，就是在数组+链表的基本上，举办了一些rehash优化等。

3.1 数据布局源码

哈希表：

typedef struct dictht {  
    // 哈希表数组  
    dictEntry **table;  
    // 哈希表巨细  
    unsigned long size;  
    // 哈希表巨细掩码，用于计较索引值  
    // 老是便是 size - 1  
    unsigned long sizemask;  
    // 该哈希表已有节点的数目  
    unsigned long used;  
} dictht; 

（编辑：河北网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!