You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 

1 lines
38 KiB

<!doctypehtml><html lang=zh-CN><meta charset=UTF-8><meta content=width=device-width name=viewport><meta media="(prefers-color-scheme: light)" content=#222 name=theme-color><meta media="(prefers-color-scheme: dark)" content=#222 name=theme-color><meta content="Hexo 7.3.0" name=generator><link href=https://cdnjs.cloudflare.com rel=preconnect><link href=/images/apple-touch-icon-next.png rel=apple-touch-icon sizes=180x180><link href=/images/favicon-32x32-next.png rel=icon sizes=32x32 type=image/png><link href=/images/favicon-16x16-next.png rel=icon sizes=16x16 type=image/png><link color=#222 href=/images/logo.svg rel=mask-icon><meta content=2X6S9P7CAjXjVvw8YyQR8pCu-B0oEu7O9quLgxXuWyA name=google-site-verification><meta content=dV8JGNzi0c name=baidu-site-verification><script>!function(){var t=!1;function e(){var e;t||(t=!0,(e=document.createElement("script")).setAttribute("data-ad-client","ca-pub-7480618470784058"),e.async=!0,e.src="https://pagead2.googlesyndication.com/pagead/js/adsbygoogle.js",document.head.appendChild(e))}function a(){"requestIdleCallback"in window?window.requestIdleCallback(e,{timeout:5e3}):window.setTimeout(e,5e3)}"complete"===document.readyState?a():window.addEventListener("load",a,{once:!0})}()</script><link href=/css/main.css rel=stylesheet><link crossorigin=anonymous href=https://cdnjs.cloudflare.com/ajax/libs/font-awesome/7.0.0/css/all.min.css integrity=sha256-VHqXKFhhMxcpubYf9xiWdCiojEbY9NexQ4jh8AxbvcM= rel=stylesheet><link crossorigin=anonymous href=https://cdnjs.cloudflare.com/ajax/libs/fancyapps-ui/6.1.14/fancybox/fancybox.css integrity=sha256-mdaMxrItEW6hMIVJJNPKuX0B7KCSJQVEv3mVY4N2we4= rel=stylesheet><script class=next-config data-name=main type=application/json>{"hostname":"nicksxs.me","root":"/","images":"/images","scheme":"Pisces","darkmode":true,"version":"8.29.0","exturl":false,"sidebar":{"position":"left","width_expanded":320,"width_dual_column":240,"display":"post","padding":18,"offset":12},"hljswrap":true,"codeblock":{"theme":{"light":"default","dark":"stackoverflow-dark"},"prism":{"light":"prism","dark":"prism-dark"},"copy_button":{"enable":true,"style":"default"},"fold":{"enable":false,"height":500},"language":false},"bookmark":{"enable":false,"color":"#222","save":"auto"},"mediumzoom":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":true,"nav":null},"stickytabs":false,"motion":{"enable":false,"async":false,"duration":200,"transition":{"menu_item":"fadeInDown","post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果:${query}","hits_time":"找到 ${hits} 个搜索结果(用时 ${time} 毫秒)","hits":"找到 ${hits} 个搜索结果"},"algolia":{"appID":"663Q99OQQD","apiKey":"e461a1371d12cec1491c1153b288a9ed","indexName":"nicksxs","hits":{"per_page":10}}}</script><script defer src=/js/config.js></script><meta content="redis是现在服务端很常用的缓存中间件,其实原来还有memcache之类的竞品,但是现在貌似 redis 快一统江湖,这里当然不是在吹,只是个人角度的一个感觉,不权威只是主观感觉。" name=description><meta content=article property=og:type><meta content="redis数据结构介绍-第一部分 SDS,链表,字典" property=og:title><meta content=https://nicksxs.me/2019/12/26/redis%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%BB%8B%E7%BB%8D/index.html property=og:url><meta content="Nicksxs's Blog" property=og:site_name><meta content="redis是现在服务端很常用的缓存中间件,其实原来还有memcache之类的竞品,但是现在貌似 redis 快一统江湖,这里当然不是在吹,只是个人角度的一个感觉,不权威只是主观感觉。" property=og:description><meta content=zh_CN property=og:locale><meta content=https://i.loli.net/2019/12/29/UL4AR1HSEKOh9Qm.png property=og:image><meta content=2019-12-25T16:03:49.000Z property=article:published_time><meta content=2019-12-25T16:03:49.000Z property=article:modified_time><meta content=Nicksxs property=article:author><meta content=Redis property=article:tag><meta content=数据结构 property=article:tag><meta content=源码 property=article:tag><meta content=summary name=twitter:card><meta content=https://i.loli.net/2019/12/29/UL4AR1HSEKOh9Qm.png name=twitter:image><link href=https://nicksxs.me/2019/12/26/redis%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%BB%8B%E7%BB%8D/ rel=canonical><script class=next-config data-name=page type=application/json>{"sidebar":"","isHome":false,"isPost":true,"lang":"zh-CN","comments":true,"permalink":"https://nicksxs.me/2019/12/26/redis%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%BB%8B%E7%BB%8D/","path":"2019/12/26/redis数据结构介绍/","title":"redis数据结构介绍-第一部分 SDS,链表,字典"}</script><script class=next-config data-name=calendar type=application/json>""</script><title>redis数据结构介绍-第一部分 SDS,链表,字典 | Nicksxs's Blog</title><script async src=https://www.googletagmanager.com/gtag/js?id=UA-61358619-1></script><script class=next-config data-name=google_analytics type=application/json>{"tracking_id":"UA-61358619-1","only_pageview":false,"measure_protocol_api_secret":null}</script><script defer src=/js/third-party/analytics/google-analytics.js></script><script defer src=/js/third-party/analytics/baidu-analytics.js></script><script async src=https://hm.baidu.com/hm.js?20f33b3c0c0eff9b1522999c0015646d></script><script crossorigin=anonymous defer integrity=sha256-QnJV4HT5r8i89ovZGRD86iynZqHerEbT2xt69vDM36I= src=https://cdnjs.cloudflare.com/ajax/libs/fancyapps-ui/6.1.14/fancybox/fancybox.umd.js></script><script defer src=/js/utils.js></script><script defer src=/js/sidebar.js></script><script defer src=/js/next-boot.js></script><script data-algolia-integrity=sha256-o49zoHLDPBm9WLg6AiliAVi3axCRTqe3ltTxLvhzAVg= data-algolia-src=https://cdnjs.cloudflare.com/ajax/libs/algoliasearch/5.36.0/lite/builds/browser.umd.js data-search-src=/js/third-party/search/algolia-search.js src=/js/third-party/search/algolia-search-loader.js></script><script defer src=/js/third-party/fancybox.js></script><noscript><link href=/css/noscript.css rel=stylesheet></noscript><link title="Nicksxs's Blog" href=/atom.xml rel=alternate type=application/atom+xml><body itemscope itemtype=http://schema.org/WebPage><div class=headband></div><main class=main><div class=column><header class=header itemscope itemtype=http://schema.org/WPHeader><div class=site-brand-container><div class=site-nav-toggle><div aria-label=切换导航栏 class=toggle role=button><span class=toggle-line></span><span class=toggle-line></span><span class=toggle-line></span></div></div><div class=site-meta><a class=brand href=/ rel=start><i class=logo-line></i><p class=site-title>Nicksxs's Blog</p><i class=logo-line></i></a><p class=site-subtitle itemprop=description>Java 运行时、生产诊断与 AI 工程实践</div><div class=site-nav-right><div class="toggle popup-trigger" aria-label=搜索 role=button><i class="fa fa-search fa-fw fa-lg"></i></div></div></div><nav class=site-nav><ul class="main-menu menu"><li class="menu-item menu-item-home"><a href=/ rel=section><i class="fa fa-home fa-fw"></i>首页</a><li class="menu-item menu-item-专题"><a href=/topics/ rel=section><i class="fa fa-layer-group fa-fw"></i>专题</a><li class="menu-item menu-item-工具"><a href=/tools/ rel=section><i class="fa fa-toolbox fa-fw"></i>工具</a><li class="menu-item menu-item-about"><a href=/about/ rel=section><i class="fa fa-user fa-fw"></i>关于我</a><li class="menu-item menu-item-tags"><a href=/tags/ rel=section><i class="fa fa-tags fa-fw"></i>标签</a><li class="menu-item menu-item-categories"><a href=/categories/ rel=section><i class="fa fa-th fa-fw"></i>分类</a><li class="menu-item menu-item-archives"><a href=/archives/ rel=section><i class="fa fa-archive fa-fw"></i>归档</a><li class="menu-item menu-item-search"><a class=popup-trigger role=button><i class="fa fa-search fa-fw"></i>搜索</a></ul></nav><div class=search-pop-overlay><div class="popup search-popup"><div class=search-header><span class=search-icon><i class="fa fa-search"></i></span><div class=search-input-container><input autocapitalize=off autocomplete=off class=search-input maxlength=80 placeholder=搜索... spellcheck=false type=search></div><span class=popup-btn-close role=button><i class="fa fa-times-circle"></i></span></div><div class=search-result-container><div class=search-result-icon><i class="fab fa-algolia fa-5x"></i></div></div></div></div></header><aside class=sidebar><div class="sidebar-inner sidebar-nav-active sidebar-toc-active"><ul class=sidebar-nav><li class=sidebar-nav-toc>文章目录<li class=sidebar-nav-overview>站点概览</ul><div class=sidebar-panel-container><div class="post-toc-wrap sidebar-panel"><div class="post-toc animated"><ol class=nav><li class="nav-item nav-level-2"><a class=nav-link href=#SDS-%E7%AE%80%E5%8D%95%E5%8A%A8%E6%80%81%E5%AD%97%E7%AC%A6%E4%B8%B2><span class=nav-number>1.</span> <span class=nav-text>SDS 简单动态字符串</span></a><li class="nav-item nav-level-2"><a class=nav-link href=#%E9%93%BE%E8%A1%A8><span class=nav-number>2.</span> <span class=nav-text>链表</span></a><li class="nav-item nav-level-2"><a class=nav-link href=#%E5%AD%97%E5%85%B8><span class=nav-number>3.</span> <span class=nav-text>字典</span></a></ol></div></div><div class="site-overview-wrap sidebar-panel"><div class="site-author animated" itemprop=author itemscope itemtype=http://schema.org/Person><img alt=Nicksxs class=site-author-image itemprop=image src=/uploads/avatar.jpg><p class=site-author-name itemprop=name>Nicksxs<div class=site-description itemprop=description>Nicksxs 的技术博客,深入 Java 运行时与生产诊断、低成本大模型推理和 Agent 工程实践。</div></div><div class="site-state-wrap animated"><nav class=site-state><div class="site-state-item site-state-posts"><a href=/archives/><span class=site-state-item-count>394</span> <span class=site-state-item-name>日志</span></a></div><div class="site-state-item site-state-categories"><a href=/categories/><span class=site-state-item-count>181</span> <span class=site-state-item-name>分类</span></a></div><div class="site-state-item site-state-tags"><a href=/tags/><span class=site-state-item-count>347</span> <span class=site-state-item-name>标签</span></a></div></nav></div><div class="links-of-author animated"><span class=links-of-author-item><a rel="noopener me" title="GitHub → https://github.com/nicksxs" href=https://github.com/nicksxs target=_blank><i class="fab fa-github fa-fw"></i>GitHub</a> </span><span class=links-of-author-item><a rel="noopener me" title="E-Mail → mailto:nicksxs1202@gmail.com" href=mailto:nicksxs1202@gmail.com target=_blank><i class="fa fa-envelope fa-fw"></i>E-Mail</a></span></div><div class="cc-license animated" itemprop=license><a class=cc-opacity href=https://creativecommons.org/licenses/by-nc-sa/4.0/ rel=noopener target=_blank><img alt="Creative Commons" src=https://cdnjs.cloudflare.com/ajax/libs/creativecommons-vocabulary/2020.11.3/assets/license_badges/small/by_nc_sa.svg></a></div><div class="widget-wrap sidebar-tag-cloud"><div class=tag-cloud-tags><a class=tag-cloud-10 href=/tags/Java/ style=font-size:16px>Java</a><a class=tag-cloud-9 href=/tags/leetcode/ style=font-size:15.62px>leetcode</a><a class=tag-cloud-8 href=/tags/LLM/ style=font-size:15.23px>LLM</a><a class=tag-cloud-8 href=/tags/%E7%94%9F%E6%B4%BB/ style=font-size:14.85px>生活</a><a class=tag-cloud-7 href=/tags/%E9%A2%98%E8%A7%A3/ style=font-size:14.46px>题解</a><a class=tag-cloud-6 href=/tags/SpringBoot/ style=font-size:14.08px>SpringBoot</a><a class=tag-cloud-6 href=/tags/MySQL/ style=font-size:14.08px>MySQL</a><a class=tag-cloud-5 href=/tags/C/ style=font-size:13.69px>C++</a><a class=tag-cloud-5 href=/tags/Redis/ style=font-size:13.31px>Redis</a><a class=tag-cloud-4 href=/tags/Tomcat/ style=font-size:12.92px>Tomcat</a><a class=tag-cloud-4 href=/tags/Mybatis/ style=font-size:12.92px>Mybatis</a><a class=tag-cloud-3 href=/tags/%E5%B0%8F%E6%8A%80%E5%B7%A7/ style=font-size:12.54px>小技巧</a><a class=tag-cloud-2 href=/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/ style=font-size:12.15px>数据结构</a><a class=tag-cloud-2 href=/tags/%E6%BA%90%E7%A0%81/ style=font-size:12.15px>源码</a><a class=tag-cloud-2 href=/tags/MQ/ style=font-size:11.77px>MQ</a><a class=tag-cloud-2 href=/tags/%E6%B6%88%E6%81%AF%E9%98%9F%E5%88%97/ style=font-size:11.77px>消息队列</a><a class=tag-cloud-2 href=/tags/RocketMQ/ style=font-size:11.77px>RocketMQ</a><a class=tag-cloud-2 href=/tags/%E8%BF%90%E5%8A%A8/ style=font-size:11.77px>运动</a><a class=tag-cloud-1 href=/tags/php/ style=font-size:11.38px>php</a><a class=tag-cloud-0 href=/tags/Spring/ style=font-size:11px>Spring</a><a class=tag-cloud-0 href=/tags/linux/ style=font-size:11px>linux</a><a class=tag-cloud-0 href=/tags/Docker/ style=font-size:11px>Docker</a><a class=tag-cloud-0 href=/tags/%E5%87%8F%E8%82%A5/ style=font-size:11px>减肥</a><a class=tag-cloud-0 href=/tags/%E8%B7%91%E6%AD%A5/ style=font-size:11px>跑步</a></div></div><div class="affiliate-creative affiliate-creative--sidebar" data-affiliate-id=tencent-cloud-general><a rel="sponsored noopener" aria-label=腾讯云产品优惠 href=https://cloud.tencent.com/act/cps/redirect?redirect=2446&cps_key=2e33a1eedb380997d03618b4a5ba6ca7&from=console target=_blank><img alt=腾讯云服务器、数据库和云产品优惠 decoding=async height=419 loading=lazy src=/uploads/affiliate/tencent-cloud-general.webp width=690> </a><span class=affiliate-disclosure>推广</span></div></div></div></div><div class="sidebar-inner sidebar-blogroll"><div class="links-of-blogroll animated"><div class=links-of-blogroll-title><i class="fa fa-globe fa-fw"></i> 链接</div><ul class=links-of-blogroll-list><li class=links-of-blogroll-item><a href=https://covermusic.cn/ rel=noopener target=_blank title=https://covermusic.cn>69伙伴</a></ul></div></div></aside></div><div class="main-inner post posts-expand"><div class=post-block><article class=post-content itemscope itemtype=http://schema.org/Article lang=zh-CN><link href=https://nicksxs.me/2019/12/26/redis%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%BB%8B%E7%BB%8D/ itemprop=mainEntityOfPage><span hidden itemprop=author itemscope itemtype=http://schema.org/Person><meta content=/uploads/avatar.jpg itemprop=image><meta content=Nicksxs itemprop=name></span><span hidden itemprop=publisher itemscope itemtype=http://schema.org/Organization><meta content="Nicksxs's Blog" itemprop=name><meta content="Nicksxs 的技术博客,深入 Java 运行时与生产诊断、低成本大模型推理和 Agent 工程实践。" itemprop=description></span><span hidden itemprop=post itemscope itemtype=http://schema.org/CreativeWork><meta content="redis数据结构介绍-第一部分 SDS,链表,字典 | Nicksxs's Blog" itemprop=name><meta content="redis是现在服务端很常用的缓存中间件,其实原来还有memcache之类的竞品,但是现在貌似 redis 快一统江湖,这里当然不是在吹,只是个人角度的一个感觉,不权威只是主观感觉。" itemprop=description></span><header class=post-header><h1 itemprop="name headline" class=post-title>redis数据结构介绍-第一部分 SDS,链表,字典</h1><div class=post-meta-container><div class=post-meta><span class=post-meta-item><span class=post-meta-item-icon><i class="far fa-calendar"></i> </span><span class=post-meta-item-text>发表于</span> <time itemprop="dateCreated datePublished" title="创建时间:2019-12-26 00:03:49" datetime=2019-12-26T00:03:49+08:00>2019-12-26</time> </span><span class=post-meta-item><span class=post-meta-item-icon><i class="far fa-folder"></i> </span><span class=post-meta-item-text>分类于</span> <span itemprop=about itemscope itemtype=http://schema.org/Thing><a href=/categories/Redis/ itemprop=url rel=index><span itemprop=name>Redis</span></a> </span>, <span itemprop=about itemscope itemtype=http://schema.org/Thing><a href=/categories/Redis/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/ itemprop=url rel=index><span itemprop=name>数据结构</span></a> </span>, <span itemprop=about itemscope itemtype=http://schema.org/Thing><a href=/categories/C/ itemprop=url rel=index><span itemprop=name>C</span></a> </span>, <span itemprop=about itemscope itemtype=http://schema.org/Thing><a href=/categories/Redis/%E6%BA%90%E7%A0%81/ itemprop=url rel=index><span itemprop=name>源码</span></a> </span>, <span itemprop=about itemscope itemtype=http://schema.org/Thing><a href=/categories/C/Redis/ itemprop=url rel=index><span itemprop=name>Redis</span></a> </span></span><span class="post-meta-item cloudflare-page-counter" data-title="redis数据结构介绍-第一部分 SDS,链表,字典" data-increment=true data-path=/2019/12/26/redis%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%BB%8B%E7%BB%8D/ title=阅读次数><span class=post-meta-item-icon><i class="far fa-eye"></i> </span><span class=post-meta-item-text>阅读次数:</span> <span class=cloudflare-page-counter-count></span></span></div><div class=post-description>redis是现在服务端很常用的缓存中间件,其实原来还有memcache之类的竞品,但是现在貌似 redis 快一统江湖,这里当然不是在吹,只是个人角度的一个感觉,不权威只是主观感觉。</div></div></header><div class=post-body itemprop=articleBody><p>redis是现在服务端很常用的缓存中间件,其实原来还有<code>memcache</code>之类的竞品,但是现在貌似 redis 快一统江湖,这里当然不是在吹,只是个人角度的一个感觉,不权威只是主观感觉。<br>redis 主要有五种数据结构,<code>Strings</code>,<code>Lists</code>,<code>Sets</code>,<code>Hashes</code>,<code>Sorted Sets</code>,这五种数据结构先简单介绍下,<code>Strings</code>类型的其实就是我们最常用的 key-value,实际开发中也会用的最多;<code>Lists</code>是列表,这个有些会用来做队列,因为 redis 目前常用的版本支持丰富的列表操作;还有是<code>Sets</code>集合,这个主要的特点就是集合中元素不重复,可以用在有这类需求的场景里;<code>Hashes</code>是叫散列,类似于 Python 中的字典结构;还有就是<code>Sorted Sets</code>这个是个有序集合;一眼看这些其实没啥特别的,除了最后这个有序集合,不过去了解背后的实现方式还是比较有意思的。<h2 id=SDS-简单动态字符串><a title="SDS 简单动态字符串" class=headerlink href=#SDS-简单动态字符串></a>SDS 简单动态字符串</h2><p>先从<code>Strings</code>开始说,了解过 C 语言的应该知道,C 语言中的字符串其实是个 <code>char[]</code> 字符数组,redis 也不例外,只是最开始的版本就对这个做了一丢丢的优化,而正是这一丢丢的优化,让这个 redis 的使用效率提升了数倍<figure class="highlight c"><table><tr><td class=gutter><pre><span class=line>1</span><br><span class=line>2</span><br><span class=line>3</span><br><span class=line>4</span><br><span class=line>5</span><br><span class=line>6</span><br><span class=line>7</span><br><span class=line>8</span><br></pre><td class=code><pre><span class=line><span class=class><span class=keyword>struct</span> <span class=title>sdshdr</span> {</span></span><br><span class=line> <span class=comment>// 字符串长度</span></span><br><span class=line> <span class=type>int</span> len;</span><br><span class=line> <span class=comment>// 字符串空余字符数</span></span><br><span class=line> <span class=type>int</span> <span class=built_in>free</span>;</span><br><span class=line> <span class=comment>// 字符串内容</span></span><br><span class=line> <span class=type>char</span> buf[];</span><br><span class=line>};</span><br></pre></table></figure><p>这里引用了 redis 在 github 上最早的 2.2 版本的代码,代码路径是<code>https://github.com/antirez/redis/blob/2.2/src/sds.h</code>,可以看到这个结构体里只有仨元素,两个 int 型和一个 char 型数组,两个 int 型其实就是我说的优化,因为 C 语言本身的字符串数组,有两个问题,一个是要知道它实际已被占用的长度,需要去遍历这个数组,第二个就是比较容易踩坑的是遍历的时候要注意它有个以<code>\0</code>作为结尾的特点;通过上面的两个 int 型参数,一个是知道字符串目前的长度,一个是知道字符串还剩余多少位空间,这样子坐着两个操作从 <code>O(N)</code>简化到了<code>O(1)</code>了,还有第二个 free 还有个比较重要的作用就是能防止 C 字符串的溢出问题,在存储之前可以先判断 free 长度,如果长度不够就先扩容了,先介绍到这,这个系列可以写蛮多的,慢慢介绍吧<h2 id=链表><a class=headerlink href=#链表 title=链表></a>链表</h2><p>链表是比较常见的数据结构了,但是因为 redis 是用 C 写的,所以在不依赖第三方库的情况下只能自己写一个了,redis 的链表是个有头的链表,而且是无环的,具体的结构我也找了 github 上最早版本的代码<figure class="highlight c"><table><tr><td class=gutter><pre><span class=line>1</span><br><span class=line>2</span><br><span class=line>3</span><br><span class=line>4</span><br><span class=line>5</span><br><span class=line>6</span><br><span class=line>7</span><br><span class=line>8</span><br><span class=line>9</span><br><span class=line>10</span><br><span class=line>11</span><br><span class=line>12</span><br><span class=line>13</span><br><span class=line>14</span><br><span class=line>15</span><br><span class=line>16</span><br><span class=line>17</span><br><span class=line>18</span><br><span class=line>19</span><br><span class=line>20</span><br><span class=line>21</span><br><span class=line>22</span><br><span class=line>23</span><br></pre><td class=code><pre><span class=line><span class=keyword>typedef</span> <span class=class><span class=keyword>struct</span> <span class=title>listNode</span> {</span></span><br><span class=line> <span class=comment>// 前置节点</span></span><br><span class=line> <span class=class><span class=keyword>struct</span> <span class=title>listNode</span> *<span class=title>prev</span>;</span></span><br><span class=line> <span class=comment>// 后置节点</span></span><br><span class=line> <span class=class><span class=keyword>struct</span> <span class=title>listNode</span> *<span class=title>next</span>;</span></span><br><span class=line> <span class=comment>// 值</span></span><br><span class=line> <span class=type>void</span> *value;</span><br><span class=line>} listNode;</span><br><span class=line></span><br><span class=line><span class=keyword>typedef</span> <span class=class><span class=keyword>struct</span> <span class=title>list</span> {</span></span><br><span class=line> <span class=comment>// 链表表头</span></span><br><span class=line> listNode *head;</span><br><span class=line> <span class=comment>// 当前节点,也可以说是最后节点</span></span><br><span class=line> listNode *tail;</span><br><span class=line> <span class=comment>// 节点复制函数</span></span><br><span class=line> <span class=type>void</span> *(*dup)(<span class=type>void</span> *ptr);</span><br><span class=line> <span class=comment>// 节点值释放函数</span></span><br><span class=line> <span class=type>void</span> (*<span class=built_in>free</span>)(<span class=type>void</span> *ptr);</span><br><span class=line> <span class=comment>// 节点值比较函数</span></span><br><span class=line> <span class=type>int</span> (*match)(<span class=type>void</span> *ptr, <span class=type>void</span> *key);</span><br><span class=line> <span class=comment>// 链表包含的节点数量</span></span><br><span class=line> <span class=type>unsigned</span> <span class=type>int</span> len;</span><br><span class=line>} <span class=built_in>list</span>;</span><br></pre></table></figure><p>代码地址是这个<code>https://github.com/antirez/redis/blob/2.2/src/adlist.h</code><br>可以看下节点是由listNode承载的,包括值和一个指向前节点跟一个指向后一节点的两个指针,然后值是 void 指针类型,所以可以承载不同类型的值<br>然后是 list结构用来承载一个链表,包含了表头,和表尾,复制函数,释放函数和比较函数,还有链表长度,因为包含了前两个节点,找到表尾节点跟表头都是 <code>O(1)</code>的时间复杂度,还有节点数量,其实这个跟 SDS 是同一个做法,就是空间换时间,这也是写代码里比较常见的做法,以此让一些高频的操作提速。<h2 id=字典><a class=headerlink href=#字典 title=字典></a>字典</h2><p>字典也是个常用的数据结构,其实只是叫法不同,数据结构中叫 hash 散列,Java 中叫 Map,PHP 中是数组 array,Python 中也叫字典 dict,因为纯 C 语言本身不带这些数据结构,所以这也是个痛并快乐着的过程,享受 C 语言的高性能的同时也要接受它只提供了语言的基本功能的现实,各种轮子都需要自己造,redis 同样实现了自己的字典<br>下面来看看代码<figure class="highlight c"><table><tr><td class=gutter><pre><span class=line>1</span><br><span class=line>2</span><br><span class=line>3</span><br><span class=line>4</span><br><span class=line>5</span><br><span class=line>6</span><br><span class=line>7</span><br><span class=line>8</span><br><span class=line>9</span><br><span class=line>10</span><br><span class=line>11</span><br><span class=line>12</span><br><span class=line>13</span><br><span class=line>14</span><br><span class=line>15</span><br><span class=line>16</span><br><span class=line>17</span><br><span class=line>18</span><br><span class=line>19</span><br><span class=line>20</span><br><span class=line>21</span><br><span class=line>22</span><br><span class=line>23</span><br><span class=line>24</span><br><span class=line>25</span><br><span class=line>26</span><br><span class=line>27</span><br><span class=line>28</span><br><span class=line>29</span><br><span class=line>30</span><br><span class=line>31</span><br></pre><td class=code><pre><span class=line><span class=keyword>typedef</span> <span class=class><span class=keyword>struct</span> <span class=title>dictEntry</span> {</span></span><br><span class=line> <span class=type>void</span> *key;</span><br><span class=line> <span class=type>void</span> *val;</span><br><span class=line> <span class=class><span class=keyword>struct</span> <span class=title>dictEntry</span> *<span class=title>next</span>;</span></span><br><span class=line>} dictEntry;</span><br><span class=line></span><br><span class=line><span class=keyword>typedef</span> <span class=class><span class=keyword>struct</span> <span class=title>dictType</span> {</span></span><br><span class=line> <span class=type>unsigned</span> <span class="title function_">int</span> <span class=params>(*hashFunction)</span><span class=params>(<span class=type>const</span> <span class=type>void</span> *key)</span>;</span><br><span class=line> <span class=type>void</span> *(*keyDup)(<span class=type>void</span> *privdata, <span class=type>const</span> <span class=type>void</span> *key);</span><br><span class=line> <span class=type>void</span> *(*valDup)(<span class=type>void</span> *privdata, <span class=type>const</span> <span class=type>void</span> *obj);</span><br><span class=line> <span class=type>int</span> (*keyCompare)(<span class=type>void</span> *privdata, <span class=type>const</span> <span class=type>void</span> *key1, <span class=type>const</span> <span class=type>void</span> *key2);</span><br><span class=line> <span class=type>void</span> (*keyDestructor)(<span class=type>void</span> *privdata, <span class=type>void</span> *key);</span><br><span class=line> <span class=type>void</span> (*valDestructor)(<span class=type>void</span> *privdata, <span class=type>void</span> *obj);</span><br><span class=line>} dictType;</span><br><span class=line></span><br><span class=line><span class=comment>/* This is our hash table structure. Every dictionary has two of this as we</span></span><br><span class=line><span class=comment> * implement incremental rehashing, for the old to the new table. */</span></span><br><span class=line><span class=keyword>typedef</span> <span class=class><span class=keyword>struct</span> <span class=title>dictht</span> {</span></span><br><span class=line> dictEntry **table;</span><br><span class=line> <span class=type>unsigned</span> <span class=type>long</span> size;</span><br><span class=line> <span class=type>unsigned</span> <span class=type>long</span> sizemask;</span><br><span class=line> <span class=type>unsigned</span> <span class=type>long</span> used;</span><br><span class=line>} dictht;</span><br><span class=line></span><br><span class=line><span class=keyword>typedef</span> <span class=class><span class=keyword>struct</span> <span class=title>dict</span> {</span></span><br><span class=line> dictType *type;</span><br><span class=line> <span class=type>void</span> *privdata;</span><br><span class=line> dictht ht[<span class=number>2</span>];</span><br><span class=line> <span class=type>int</span> rehashidx; <span class=comment>/* rehashing not in progress if rehashidx == -1 */</span></span><br><span class=line> <span class=type>int</span> iterators; <span class=comment>/* number of iterators currently running */</span></span><br><span class=line>} dict;</span><br></pre></table></figure><p>看了下这个 2.2 版本的代码跟最新版的其实也差的不是很多,所以还是照旧用老代码,可以看到上面四个结构体中,其实只有三个是存储数据用的,dictType 是用来放操作函数的,那么三个存放数据的结构体分别是干嘛的,这时候感觉需要一个图来说明比较好,稍等,我去画个图~<br><img loading=lazy src=https://i.loli.net/2019/12/29/UL4AR1HSEKOh9Qm.png><br>这个图看着应该比较清楚这些都是用来干嘛的了,dict 是我们的主体结构,它有一个指向 dictType 的指针,这里面包含了字典的操作函数,然后是一个私有数据指针,接下来是一个 dictht 的数组,包含两个dictht,这个就是用来存数据的了,然后是 rehashidx 表示重哈希的状态,当是-1 的时候表示当前没有重哈希,iterators 表示正在遍历的迭代器的数量。<br>首先说说为啥需要有两个 dictht,这是因为字典 dict 这个数据结构随着数据量的增减,会需要在中途做扩容或者缩容操作,如果只有一个的话,对它进行扩容缩容时会影响正常的访问和修改操作,或者说保证正常查询,修改的正确性会比较复杂,并且因为需要高效利用空间,不能一下子申请一个非常大的空间来存很少的数据。当 dict 中 dictht 中的数据量超过 size 的时候负载就超过了 1,就需要进行扩容,这里的其实跟 Java 中的 HashMap 比较类似,超过一定的负载之后进行扩容。这里为啥 size 会超过 1 呢,可能有部分不了解这类结构的同学会比较奇怪,其实就是上图中画的,在数据结构中对于散列的冲突有几类解决方法,比如转换成链表,二次散列,找下个空槽等,这里就使用了链表法,或者说拉链法。当一个新元素通过 hashFunction 得出的 key 跟 sizemask 取模之后的值相同了,那就将其放在原来的节点之前,变成链表挂在数组 dictht.table下面,放在原有节点前是考虑到可能会优先访问。<br>忘了说明下 dictht 跟 dictEntry 的关系了,dictht 就是个哈希表,它里面是个dictEntry 的二维数组,而 dictEntry 是个包含了 key-value 结构之外还有一个 next 指针,因此可以将哈希冲突的以链表的形式保存下来。<br>在重点说下重哈希,可能同样写 Java 的同学对这个比较有感觉,跟 HashMap 一样,会以 2 的 N 次方进行扩容,那么扩容的方法就会比较简单,每个键重哈希要不就在原来这个槽,要不就在原来的槽加原 dictht.size 的位置;然后是重头戏,具体是怎么做扩容呢,其实这里就把第二个 ht 用上了,其实这两个hashtable 的具体作用有点类似于 jvm 中的两个 survival 区,但是又不全一样,因为 redis 在扩容的时候是采用的渐进式地重哈希,什么叫渐进式的呢,就是它不是像 jvm 那种标记复制的模式直接将一个 eden 区和原来的 survival 区存活的对象复制到另一个 survival 区,而是在每一次添加,删除,查找或者更新操作时,都会额外的帮忙搬运一部分的原 dictht 中的数据,这里会根据 rehashidx 的值来判断,如果是-1 表示并没有在重哈希中,如果是 0 表示开始重哈希了,然后rehashidx 还会随着每次的帮忙搬运往上加,但全部被搬运完成后 rehashidx 又变回了-1,又可以扯到Java 中的 Concurrent HashMap, 他在扩容的时候也使用了类似的操作。</div><footer class=post-footer><div class="affiliate-creative affiliate-creative--post-end" data-affiliate-id=tencent-cloud-general><a rel="sponsored noopener" aria-label=腾讯云产品优惠 href=https://cloud.tencent.com/act/cps/redirect?redirect=2446&cps_key=2e33a1eedb380997d03618b4a5ba6ca7&from=console target=_blank><img alt=腾讯云服务器、数据库和云产品优惠 decoding=async height=419 loading=lazy src=/uploads/affiliate/tencent-cloud-general.webp width=690> </a><span class=affiliate-disclosure>推广</span></div><div class=reward-container><div>请我一杯咖啡吧!</div><button>赞赏</button><div class=post-reward><div><img alt="Nicksxs 微信" src=https://i.loli.net/2020/01/12/NUlWanT31E8LQGx.png><span>微信</span></div><div><img alt="Nicksxs 支付宝" src=https://ooo.0o0.ooo/2016/08/17/57b421e773057.jpg><span>支付宝</span></div></div></div><div class=post-copyright><ul><li class=post-copyright-author><strong>本文作者: </strong>Nicksxs<li class=post-copyright-link><strong>本文链接:</strong> <a title="redis数据结构介绍-第一部分 SDS,链表,字典" href=https://nicksxs.me/2019/12/26/redis%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%BB%8B%E7%BB%8D/>https://nicksxs.me/2019/12/26/redis数据结构介绍/</a><li class=post-copyright-license><strong>版权声明: </strong>本博客所有文章除特别声明外,均采用 <a href=https://creativecommons.org/licenses/by-nc-sa/4.0/ rel=noopener target=_blank><i class="fab fa-fw fa-creative-commons"></i>BY-NC-SA</a> 许可协议。转载请注明出处!</ul></div><div class=post-tags><a href=/tags/Redis/ rel=tag># Redis</a><a href=/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/ rel=tag># 数据结构</a><a href=/tags/%E6%BA%90%E7%A0%81/ rel=tag># 源码</a></div><div class=post-nav><div class=post-nav-item><a href=/2019/12/21/%E8%81%8A%E8%81%8AJava%E4%B8%AD%E7%9A%84%E5%8D%95%E4%BE%8B%E6%A8%A1%E5%BC%8F/ rel=prev title=聊聊Java中的单例模式><i class="fa fa-angle-left"></i> 聊聊Java中的单例模式</a></div><div class=post-nav-item><a title="redis数据结构介绍二-第二部分 跳表" href=/2020/01/04/redis%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%BB%8B%E7%BB%8D%E4%BA%8C/ rel=next>redis数据结构介绍二-第二部分 跳表 <i class="fa fa-angle-right"></i></a></div></div></footer></article></div><div class=comments id=disqus_thread><noscript>Please enable JavaScript to view the comments powered by Disqus.</noscript></div></div></main><footer class=footer><div class=footer-inner><div class=beian><a href=https://beian.miit.gov.cn/ rel=noopener target=_blank>浙ICP备16002580号-2 </a><img alt src=/uploads/beian.png><a href=https://beian.mps.gov.cn/#/query/webSearch?code=33010602011094 rel=noopener target=_blank>浙公网安备 33010602011094号</a></div><div class=copyright>© <span itemprop=copyrightYear>2026</span><span class=with-love><i class="fa fa-heart"></i> </span><span class=author itemprop=copyrightHolder>Nicksxs</span></div></div></footer><div class="toggle sidebar-toggle" role=button><span class=toggle-line></span><span class=toggle-line></span><span class=toggle-line></span></div><div class=sidebar-dimmer></div><div aria-label=返回顶部 class=back-to-top role=button><i class="fa fa-arrow-up fa-lg"></i><span>0%</span></div><a aria-label="在 GitHub 上关注我" title="在 GitHub 上关注我" class=github-corner href=https://github.com/nicksxs rel=noopener target=_blank><svg viewbox="0 0 250 250" aria-hidden=true height=80 width=80><path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"></path><path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" style="transform-origin:130px 106px" class=octo-arm fill=currentColor></path><path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" class=octo-body fill=currentColor></path></svg></a><noscript><div class=noscript-warning>Theme NexT works best with JavaScript enabled</div></noscript><script data-cloudflare-page-counter-config type=application/json>{"enable":true,"endpoint":"https://counter.nicksxs.me","site":"nicksxs","local_cache":true,"timeout":5000,"icon":"far fa-eye","item_text":true}</script><script src=/js/cloudflare-page-counter.js></script><script class=next-config data-name=disqus type=application/json>{"enable":true,"shortname":"nicksxs","count":false,"i18n":{"disqus":"disqus"}}</script><script defer src=/js/third-party/comments/disqus.js></script>