经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 数据库/运维 » Redis » 查看文章
Redis 学习笔记(篇一):字符串和链表
来源:cnblogs  作者:风中抚雪  时间:2019/6/17 8:56:02  对本文有异议

本次学习除了基本内容之外主要思考三个问题:why(为什么)、what(原理是什么)、which(同类中还有哪些类似的东西,相比有什么区别)。

由于我对 java 比较熟悉,并且 java 中也有字符串和链表。所以本篇暂拿 redis 中的字符串和链表与 java 进行对比。

字符串

先看几个问题:

  • redis 中有没有使用 C 语言的字符数组作为字符串? 答案:没有
  • 那么 C 语言的字符数组有着什么局限性以至于java和redis都重新定义了自己的字符串呢?
  • redis 定义的字符串结构是什么?java的呢?
  • java 和 redis 的字符串结构有什么区别?为什么会形成这样的区别?两者哪一个更好呢?

C 语言数组的局限性

  1. 取字符串长度不方便,c语言的字符数组没有存储字符串的长度,所以需要遍历。Time(时间复杂度):O(n)
  2. 不安全,两个字符数组进行拼接时可能会造成缓存区溢出,导致别的数据受损。
  3. 每次增删字符串都会导致重新分配或者回收内存,影响效率。
  4. 以\0判断是否结尾,只能存储文本数据。
  5. 比较两个字符串是否相等,需要循环比较每个字符,Time:O(n)。

由于 C 语言的字符数组有着以上的局限性,所以 redis 和 java 都重新定义了自己的字符串结构。

redis 定义的字符串结构是什么?java 的呢?

redis 中的字符串是自己构建了一种叫做简单动态字符串(SDS)的抽象类型标识的。它的具体结构如下:

  1. struct sdshdr {
  2. //字符串长度
  3. int len;
  4. // buf中未使用的字节数
  5. int free;
  6. // 字节数组,用于保存字符串
  7. char buf[];
  8. }

redis 的这个数据结构,很好的解决了 C 语言字符数组的第1、2、3、4点局限性。而且值得注意的是 sdshdr 中的 buf 数组,也是以“\0”结尾的,所以buf的总长度为:len + free + 1。那么为什么要浪费这一个字节呢?主要是想重用 C 语言对于字符串的一些函数,比如连接、输出等等。

这里有一个点需要注意一下,就是 redis 不会对存储的字符串进行编码,存储和获取都是直接通过二进制进行传输的,所以理论上来说只要客户端的编码和解码方式一样,是不会出现乱码的。这也是上面 buf 的注释里写字节数组的原因。

java 的字符串呢?则是直接把字符串搞成了一个常量。如下:

  1. public final class String
  2. implements java.io.Serializable, Comparable<String>, CharSequence {
  3. /** The value is used for character storage. */
  4. private final char value[];
  5. /** Cache the hash code for the string */
  6. private int hash; // Default to 0
  7. ......
  8. }

java 的字符串也解决了c语言字符数组的第 1/2/3/4 点。

  • 因为 java 中数组直接存储了长度,所以规避了 C 语言数组的第 1/4 点局限性。
  • 因为 String 是常量,所以c语言字符数组的第 2/3 点局限性不存在。
  • 为了解决第 5 点局限性,所以java中的字符串引入了 hashCode 的概念。
    正是因为 hash 直接存储在字符串中,所以才把字符串设置成常量(否则,每改一次字符串的值,都需要重新计算 hashcode 的值,太浪费效率)。正因为字符串是常量,所以才有了 StringBuilder、StringBuffer 的可变字符串。。。。。。

现在我们再回去看一下 redis 中字符串的结构,有一个数组,有数组中存储数据的长度。想到了什么?Java中 StringBuilder、StringBuffer、ArrayList 是不是都是这个结构?他们的共同点呢?是不是都是可变的数组( StringBuilder、StringBuffer 可以看成可变的字符数组)?

java 和 redis 的字符串比较

  1. redis 字符串中的字符数组(buf)是以“\0”结尾的,Java 中的不是。为什么呢?
    因为 redis 的设计之初就是效率高、运行快的缓存。所以才会选择以 C 语言实现(因为c是所有结构化语言中运行最快的),并且和c的字符数组一样的结尾,以便可以直接使用c的函数而不重复造轮子。
    java 的设计之初就是一门跨平台的语言,所以字符串的所有函数都是自己实现的,所以不需要额外浪费一个字节的空间。
  2. redis 定义了一个 sds 的字符串,但也是基于 C 的字符数组。而java直接把c的数组都重新定义了( C 的数组不能直接获得数组长度)。
  3. 关于字符串比较是否相等的问题:
    java 中有 hashcode 的概念来提升字符串比较是否相等的速度。redis 中又是如何做的呢?比如 get key 时,如何定位的一个具体的 key,而得到的 value 呢? 这个问题,暂时还不知道。

造成这些差异的原因,主要就是其定位不一样。redis 的定位是缓存、要求快。java 的定位是语言,最重要的是跨平台及扩展性。

链表

也同样看三个问题:

  1. 链表为什么产生?
  2. 原理是什么,和别的数据结构再来个对比。
  3. 和 java 的链表有什么不一样?

链表为什么产生?

链表的产生主要是因为数组的局限性。
比如:插入、删除慢。不能动态增加元素。

原理是什么

redis 的链表结构如下:

  1. typedef struct listNode {
  2. struct listNode *prev; //前驱节点,如果是list的头结点,则prev指向NULL
  3. struct listNode *next;//后继节点,如果是list尾部结点,则next指向NULL
  4. void *value; //万能指针,能够存放任何信息
  5. } listNode;
  6. typedef struct list {
  7. listNode *head; //链表头结点指针
  8. listNode *tail; //链表尾结点指针
  9. //下面的三个函数指针就像类中的成员函数一样
  10. void *(*dup)(void *ptr); //复制链表节点保存的值
  11. void (*free)(void *ptr); //释放链表节点保存的值
  12. int (*match)(void *ptr, void *key); //比较链表节点所保存的节点值和另一个输入的值是否相等
  13. unsigned long len; //链表长度计数器
  14. } list;

java 的链表结构如下:

  1. public class LinkedList<E>
  2. extends AbstractSequentialList<E>
  3. implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
  4. transient int size = 0;
  5. /**
  6. * Pointer to first node.
  7. * Invariant: (first == null && last == null) ||
  8. * (first.prev == null && first.item != null)
  9. */
  10. transient Node<E> first;
  11. /**
  12. * Pointer to last node.
  13. * Invariant: (first == null && last == null) ||
  14. * (last.next == null && last.item != null)
  15. */
  16. transient Node<E> last;
  17. .......
  18. }

redis 的链表和 java 的链表有什么不一样?

基本一致,都是双向不循环链表。

双向的优点就是可以向前遍历,也可以向后遍历。缺点就是每个节点都需要浪费一个指针去指向前一个节点。

原文链接:http://www.cnblogs.com/wind-snow/p/11019260.html

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号