關(guān)于 redis 相信大家都不陌生了，之前有從 0 -1 分享過 redis 的基本使用方式，用起來倒是都沒有啥問題了，不過還是那句話，會應(yīng)用之后，我們必須要究其原理，知其然知其所以然

今天我們來分享一下關(guān)于 redis 的存儲結(jié)構(gòu)的原理

redis 的存儲結(jié)構(gòu)的原理

我們都知道 redis 是一個 K-V 內(nèi)存數(shù)據(jù)庫，類似于 memcache ，那么一般存儲這種 K-V 鍵值對的數(shù)據(jù)結(jié)構(gòu)是什么呢？

是 紅黑樹 ， 那么我們對于紅黑樹的增刪改查的時間復(fù)雜度是 **O(logN)**，對于紅黑樹而言，只要內(nèi)存足夠，那么這個 N 是可以無限大的

這對于 redis 來說是沒有辦法滿足 redis 的需求，那么我們是否可以將復(fù)雜度降低到 O(1） 呢，感興趣的，我們可以來探索一下？

hash 表

能滿足 O(1) 時間復(fù)雜度的數(shù)據(jù)結(jié)構(gòu)有啥呢？我們是不是可以想到 hash 表

具體 hash 表是怎樣的一種結(jié)構(gòu)，前面有文章已經(jīng)分享過一些，redis 基礎(chǔ)性的數(shù)據(jù)結(jié)構(gòu)可以查看歷史文章：【Redis 系列】redis 學(xué)習(xí)四，set 集合，hash 哈希，zset 有序集合初步

redis 的 key 支持哪些類型？

redis 支持的 key 有：

• long

• double

• int

• string ?- 可見的字符串和二進(jìn)制字符串，key 都是 string 類型

實(shí)際上最終到 redis 處理的時候，上述類型，都是對應(yīng)按照 sring 類型進(jìn)行存儲的

這個 key 是有規(guī)律的 key，并且是強(qiáng)隨機(jī)性的

redis 的 value 支持哪些類型？

• string

• list

• set

• zset

• hash

• Geospatial 地理位置

• Hyperloglog 基數(shù)統(tǒng)計

• Bitmap 位圖場景

我們知道 O(1) 的索引時間復(fù)雜度，數(shù)組就是一個很好的例子，我們訪問數(shù)組元素的時候，直接通過下標(biāo)訪問即可

那么對應(yīng) hash 表，其實(shí)就是 數(shù)組 + hash 函數(shù) 來進(jìn)行處理的，數(shù)組的下標(biāo)索引就是 hash 函數(shù) 對 key（字符串） 進(jìn)行 hash 算法計算出來的一個整數(shù)

例如這樣

通過 hash 函數(shù)計算出來的整數(shù)是一個 64 位 的整型

hash 沖突

使用上述 hash 表的話，肯定會出現(xiàn) hash 沖突，hash 沖突是什么樣的效果呢？

就向上面的對 key （是一個各種組合的字符串），進(jìn)行 hash 計算之后，得到一個整型的值，這個值是 64 位的整型

這也就意味著， key 的字符串組合是無限的，但是 64 整型的大小是固定的，總有有機(jī)會字符串計算出來的整數(shù)是會重復(fù)的，這個時候就出現(xiàn)了 hash 沖突

咱們可以舉一個類型的形象例子：

假如說有 3 個盒子，4 個蘋果，蘋果要裝在盒子里面，那么至少有一個抽屜是會放 2 個蘋果，圖下圖所示，那么放 2 個蘋果的這個抽屜就出現(xiàn)了 hash 沖突，就需要解決

例如放到我們的 hash 表中，數(shù)組大小我們設(shè)定了長度為 3，那么所有的整數(shù)我們都要對 3 取余，然后就結(jié)果對號入座

解決 hash 沖突

根據(jù)上述情況，出現(xiàn)了 hash 沖突，我們需要如何處理呢，如何才能解決 hash 沖突？

解決沖突的方式：

• 使用鏈表，也就是鏈地址法 ， 數(shù)組 + 鏈表的 方式

將出現(xiàn)沖突的元素，插入到以原有沖突元素作為鏈表頭的鏈表中，使用頭插法

一般是使用頭插法， 這是遵循緩存淘汰算法的邏輯原理 LRU

數(shù)據(jù)庫也是使用的頭插法，表示新插入的數(shù)據(jù)，是最近就要使用的

• 再使用一個 hash 函數(shù)來進(jìn)行計算，得出另一個值，這是 再 hash 法

• 再加一個數(shù)組來存放沖突的數(shù)據(jù)（這種方式不太好）

原有數(shù)組的每一個坑占一個放一個蘿卜，如果有沖突出現(xiàn)，那么就把出現(xiàn)沖突的元素放到?jīng)_突數(shù)組中，并記下他所在沖突數(shù)組的索引位置，這個比較麻煩，不可持續(xù)

擴(kuò)容和縮容

那么當(dāng)咱們數(shù)據(jù)量比較大的時候，發(fā)生 hash 沖突的情況就會比較多，若大部分時間都是去解決沖突了，那么非常低效的，因此需要擴(kuò)容

擴(kuò)容的原則又是如何擴(kuò)容的呢？

擴(kuò)容的時候是，當(dāng)持久化的數(shù)據(jù)量大于數(shù)組長度的時候，就會進(jìn)行翻倍的擴(kuò)容，例如上述 數(shù)組長度為 3 ，當(dāng)我們有 4 個 或者 5 個數(shù)據(jù)的時候，數(shù)組的長度會擴(kuò)到 6，12， 24 ... ?這樣的來進(jìn)行翻倍擴(kuò)容

那么 縮容的時候，是不是也是要進(jìn)行翻倍縮容的？

我們可以來看看效果，如果是翻倍縮容的話

如果是翻倍縮容的話，就會出現(xiàn)這么一個情況，原有數(shù)組長度為 4，如果數(shù)據(jù)變成 5 個，就會翻倍擴(kuò)容數(shù)組長度為 8，如果數(shù)據(jù)又變回 4 個，那么數(shù)組長度又會翻倍縮容到長度為 4

就會出現(xiàn)上述的這類情況，可能會存在一會擴(kuò)容，一會縮容，這是非常消耗資源和性能和，因此定了一個數(shù)據(jù)是 當(dāng)數(shù)據(jù)量小于數(shù)組長度的 10% 的時候，會進(jìn)行縮容

本次暫且分享這么多，下一部分分享具體的 hash 表在 redis 中的數(shù)據(jù)結(jié)構(gòu)，和具體的實(shí)現(xiàn)方式

今天就到這里，學(xué)習(xí)所得，若有偏差，還請斧正

歡迎點(diǎn)贊，關(guān)注，收藏

朋友們，你的支持和鼓勵，是我堅持分享，提高質(zhì)量的動力

好了，本次就到這里

技術(shù)是開放的，我們的心態(tài)，更應(yīng)是開放的。擁抱變化，向陽而生，努力向前行。

我是阿兵云原生，歡迎點(diǎn)贊關(guān)注收藏，下次見~