redis的快主要展現在我們可以根據鍵值對能以微妙級别的速度找到資料，并快速完成操作。
redis這樣迅速的表現主要展現在以下幾點：
(1)他是記憶體模式的非關系型資料庫，所有操作都在記憶體上完成，記憶體的通路速度本身就很快。
(2)取決于redis合理的資料結構特性，鍵值對按一定的資料結構來存儲，我們操作redis的鍵值對最終就是對資料結構進行增删改查操作，是以在合适的場景我們也應該采用合适的資料結構。
在平常開發中我們主要會用到這些資料結構，即：
(1)String - 字元串
(2)List - 清單
(3)Hash - 哈希
(4)Set - 集合
(5)Sorted Set - 有序集合
上述的資料結構中他們的底層也有着底層資料結構的實作，分别是簡單動态字元串、雙向連結清單、壓縮清單、哈希表、跳表和整數集合。他們對應的redis資料結構如下圖所示：
可以看到，String類型的底層實作隻有一種資料結構即簡單動态字元串。其餘四種資料結構底層實作都有兩種實作結構。并且他們的相同點在于都屬于集合類型，一個key對應這樣一個集合的資料。
一、鍵值對如何存儲
為了實作redis的快速通路，是以redis會使用一個哈希表來存儲所有的鍵值對。
這裡的哈希表和hashMap的思想一樣，一個哈希表是一個數組，數組的每個元素叫做哈希桶，哈希桶中的元素儲存的不是值的本身，而是指向具體值的指針。
redis的哈希表如下圖所示：
Hash表最大好處在于可以以時間複雜度為O(1)來根據key快速查找到鍵值對，因為我們隻需要計算key對應的hash值，在映射到hash桶位置，就可以通路這個key對應的entry元素。
但是Hash表的存在避免不了hash沖突問題，如果每一時刻往redis中插入了大量資料後，發現性能突然慢了，也有可能是hash表的沖突問題和擴容操作導緻了操作阻塞。
二、redis的哈希表如何解決hash沖突
redis的哈希沖突示意圖：
上述桶6中出現了hash沖突，hash沖突的存在會導緻要查找entry3的key對應的value值時，隻能先找到第一個entry1，再通過next指針依次進行查找。如果沖突越來越多，會導緻這條鍊越來越長，查找性能降低。
為了解決上述的問題，redis采用了rehash操作，即對hash桶進行擴容，使entry資料更加散列儲存在數組中。
先來看下普通的hashMap擴容的思想。
普通的hashMap是當entry數量達到一定門檻值時，進行擴容，擴容後數組 = 擴容前數組 * 2。然後依次計算key的hash值，将value放到正确的位置中。
如果redis采用這種思想，可能會涉及到大量的資料拷貝，如果需要将擴容前的資料全部遷移完，會造成redis線程的阻塞，這在redis的使用中不是我們希望看到的。
· 漸進式rehash
為了避免上述的問題，redis采用了漸進式擴容方式。
redis預設使用了2個全局hash表，哈希表1和哈希表2。當擴容前或者剛插入資料時，預設使用hash表1。随着資料增多，開始進行rehash。進行如下操作：
1、給hash表2配置設定更大的空間，一般是hash表1的2倍。
2、如果沒有請求，背景會有個子線程開啟定時任務将hash表1中的資料重新映射并拷貝到hash表2中。
如果有請求，就不能一下子将hash表1中的資料全部拷貝給hash表2中，否則會造成阻塞。
此時redis仍可以正常處理用戶端請求，每處理一個請求，從hash表1中的第一個索引位置開始，将這個索引下面的entry資料全部進行重新映射并拷貝給hash表2。
等處理下一個請求時，開始進行hash表1中下一個索引位置的entry資料的映射與拷貝。依次類推。
3、全部資料拷貝完畢，釋放hash表1中的空間。
漸進式rehash如下圖所示：
redis通過漸進式rehash的方式将一次性大量拷貝的開銷分攤到了多次請求拷貝中，避免了阻塞操作。
三、集合資料操作效率
集合類型底層的資料結構主要分為整數數組、雙向連結清單、哈希表、壓縮清單和跳表。
整數數組、雙向連結清單、哈希表比較常見，并且前2個的查詢時間複雜度都是O(n)，哈希表的查詢複雜度是0(1)。這裡我們主要看下壓縮清單和跳表。
· 壓縮清單
壓縮清單實際上和數組類似，數組中的每一個元素都儲存資料，但是和數組不同的是有四個特殊字段zlbytes、zltail、zllen、alend分别來表示清單長度，清單尾的偏移量，清單中的entry個數，清單結束标記。
壓縮清單如下圖所示：
在壓縮清單中，如果我們需要定位第一個元素或者最後一個元素可以通過表頭的三個字段來直接進行定位，複雜度為O(1)，查找其他元素的話隻能依次周遊查找，複雜度變為了O(n)。
· 跳表
有序清單隻能周遊依次進行查找資料，而跳表是在有序清單的基礎上建立多級索引，通過索引快速定位到資料。
跳表如下圖所示：
如果不使用跳表，隻使用普通的有序清單，那麼查找50這個值，就需要周遊8次才能查詢到。
如上圖所示的跳表，隻需要先在二級索引中判斷50處于索引13和索引55之間。然後再去一級索引中判斷50處于索引25和索引55之間，最後查找到50。隻需要查找4次就可以查詢到。
跳表的時間複雜度為O(logn)
· 資料結構的讀取時間複雜度
1、哈希表 - O(1)
2、跳表 - O(logn)
3、雙向連結清單 - O(n)
4、壓縮清單 - O(n)
5、數組 - O(n)
四、總結
本文主要學習了redis的底層資料結構，首先是全局用來儲存鍵值對的hash表，其次是底層的集合資料結構 - 雙向連結清單、壓縮清單、整數數組、哈希表和跳表。redis之是以能快速操作鍵值對，一方面可以通過鍵值對從hash表中快速的定位到元素。另一方面底層的資料結構也起到了決定作用。
比如支援排序的sorted set采用了壓縮清單和跳表，set采用了哈希表和數組，hash采用了哈希表和壓縮清單，list采用了雙向連結清單和壓縮清單。
問題一：整數數組和壓縮清單在查找時間複雜度方面沒有很大的優勢，為什麼redis還會把他們當做底層資料結構？
整數數組和壓縮清單的設計，主要展現了redis可用這兩個資料結構來節省空間，因為這2個資料結構，都是在記憶體中配置設定一塊位址連續的空間，然後把集合一個接一個的放在這塊空間内，非常緊湊，正式由于這個連續的空間和資料連續的放置我們不用像其他資料結構一樣使用指針來串接起來，減少了建立指針時帶來的空間開銷。
問題二：redis什麼時候做rehash？
redis會使用裝載因子來判斷是否需要rehash，裝載因子 = 所有entry個數 ÷ 哈希桶的個數。結果分為2種情況。
1、裝載因子 >= 1。
2、裝載因子 >= 5。
第一種情況裝載因子大于等于1，小于5的情況。如果計算結果是1，可以假設一個哈希桶儲存了一個資料。如果有新的資料寫入時，就需要采用鍊式哈希。如果此時redis沒有進行aof和rdb的寫入，那麼就可以進行rehash。
第二種情況，裝載因子大于等于5，表示目前的資料量遠遠大于哈希桶的個數，會有大量的哈希鍊存在，需要馬上進行rehash操作。
問題三：采用漸進式rehash時，如果沒有收到新的請求，是不是無法進行rehash？
redis的子線程會開啟定時任務，在rehash被觸發後，即使沒有收到新請求，redis也會定時執行一次rehash操作。而且每次的rehash操作不會超過1ms，以免對其他操作造成影響。
參考資料 - 《Redis核心技術與實戰》(資料結構：快速的Redis有哪些慢操作)