共计 1936 个字符，预计需要花费 5 分钟才能阅读完成。
对于 redis 置信大家都不生疏了，之前有从 0 -1 分享过 redis 的根本应用形式，用起来倒是都没有啥问题了，不过还是那句话，会利用之后，咱们必须要究其原理，知其然知其所以然
明天咱们来分享一下对于 redis 的存储构造的原理
redis 的存储构造的原理
咱们都晓得 redis 是一个 K-V 内存数据库，相似于 memcache，那么个别存储这种 K-V 键值对的数据结构是什么呢？
是 红黑树，那么咱们对于红黑树的增删改查的工夫复杂度是 O(logN)，对于红黑树而言，只有内存足够，那么这个 N 是能够无限大的
这对于 redis 来说是没有方法满足 redis 的需要，那么咱们是否能够将复杂度升高到 O(1）呢，感兴趣的，咱们能够来摸索一下？
hash 表
能满足 O(1) 工夫复杂度的数据结构有啥呢？咱们是不是能够想到 hash 表
具体 hash 表是怎么的一种构造，后面有文章曾经分享过一些，redis 基础性的数据结构能够查看历史文章：【Redis 系列】redis 学习四，set 汇合，hash 哈希，zset 有序汇合初步
redis 的 key 反对哪些类型？
redis 反对的 key 有：
- long
- double
- int
- string – 可见的字符串和二进制字符串，key 都是 string 类型
实际上最终到 redis 解决的时候，上述类型，都是对应依照 sring 类型进行存储的
这个 key 是有法则的 key，并且是强随机性的
redis 的 value 反对哪些类型？
- string
- list
- set
- zset
- hash
- Geospatial 地理位置
- Hyperloglog 基数统计
- Bitmap 位图场景
咱们晓得 O(1) 的索引工夫复杂度 ， 数组 就是一个很好的例子，咱们拜访数组元素的时候，间接通过下标拜访即可
那么对应 hash 表 ，其实就是 数组 + hash 函数 来进行解决的，数组的下标索引就是 hash 函数 对 key（字符串）进行 hash 算法计算出来的一个整数
例如这样
通过 hash 函数计算出来的整数是一个 64 位 的整型
hash 抵触
应用上述 hash 表的话，必定会呈现 hash 抵触，hash 抵触是什么样的成果呢？
就向下面的对 key（是一个各种组合的字符串），进行 hash 计算之后，失去一个整型的值，这个值是 64 位的整型
这也就意味着，key 的字符串组合是有限的，然而 64 整型的大小是固定的，总有有机会字符串计算出来的整数是会反复的，这个时候就呈现了 hash 抵触
咱们能够举一个类型的形象例子：
如果说有 3 个盒子，4 个苹果，苹果要装在盒子外面，那么至多有一个抽屉是会放 2 个苹果，图下图所示，那么放 2 个苹果的这个抽屉就 呈现了 hash 抵触，就须要解决
例如放到咱们的 hash 表中，数组大小咱们 设定了长度为 3，那么所有的整数咱们都要对 3 取余，而后就后果对号入座
解决 hash 抵触
根据上述状况，呈现了 hash 抵触，咱们须要如何解决呢，如何能力解决 hash 抵触？
解决抵触的形式：
- 应用链表，也就是 链地址法，数组 + 链表的 形式
将呈现抵触的元素，插入到以原有抵触元素作为链表头的链表中，应用 头插法
个别是应用 头插法 ， 这是遵循缓存淘汰算法的逻辑原理 LRU
数据库也是应用的头插法，示意新插入的数据，是最近就要应用的
- 再应用一个 hash 函数来进行计算，得出另一个值，这是 再 hash 法
- 再加一个数组来寄存抵触的数据（这种形式不太好）
原有数组的每一个坑占一个放一个萝卜，如果有抵触呈现，那么就把呈现抵触的元素放到抵触数组中，并记下他所在抵触数组的索引地位，这个比拟麻烦，不可继续
扩容和缩容
那么当咱们数据量比拟大的时候，产生 hash 抵触的状况就会比拟多，若大部分工夫都是去解决抵触了，那么十分低效的，因而须要扩容
扩容的准则又是如何扩容的呢？
扩容的时候是，当长久化的数据量大于数组长度的时候，就会进行翻倍的扩容，例如上述 数组长度为 3，当咱们有 4 个 或者 5 个数据的时候，数组的长度会扩到 6，12，24 … 这样的来进行 翻倍扩容
那么 缩容的时候，是不是也是要进行翻倍缩容的？
咱们能够来看看成果，如果是翻倍缩容的话
如果是翻倍缩容的话，就会呈现这么一个状况，原有数组长度为 4，如果数据变成 5 个，就会 翻倍扩容数组长度为 8，如果数据又变回 4 个，那么数组长度又会 翻倍缩容到长度为 4
就会呈现上述的这类状况，可能会存在一会扩容，一会缩容，这是十分耗费资源和性能和，因而定了一个数据是 当数据量小于数组长度的 10% 的时候，会进行缩容
本次暂且分享这么多，下一部分分享具体的 hash 表在 redis 中的数据结构，和具体的实现形式
明天就到这里，学习所得，若有偏差，还请斧正
欢送点赞，关注，珍藏
敌人们，你的反对和激励，是我保持分享，提高质量的能源
好了，本次就到这里
技术是凋谢的，咱们的心态，更应是凋谢的。拥抱变动，背阴而生，致力向前行。
我是 小魔童哪吒，欢送点赞关注珍藏，下次见~
