面試官：Redis中集合數據類型的內部實現方式是什么？

雖然已經是陽春三月，但騎著共享單車騎了這么遠，還有有點冷的。我搓了搓的被凍的麻木的手，對著前臺的小姐姐說：“您好，我是來面試的。”小姐姐問：“您好，您叫什么名字？”我回答：“我叫萬貓學社。”小姐姐笑出了聲，說到：“這名字好怪，誰給你起的啊。”我面無表情地回答：“俺爹。”小姐姐收起了笑容，說到：“跟我來吧。”我被帶到了面試間等候，片刻后一個著干凈滿臉清秀的青年走了進來，一股男士香水的淡香撲面而來。

面試官：Redis中基本的數據類型有哪些？

我：Redis的基本數據類型有：字符串（string）、哈希（hash）、列表（list）、集合（set）、有序集合（zset）。

面試官：集合數據類型的內部實現方式是什么？

我還沉浸在上一個問題的沾沾自喜中，頓時表情凝固了，手心開始冒出冷汗。“這個。。沒有太深入了解”，我支支吾吾的說到。

面試官：回去等消息吧。

這句話說的干凈利落，然后就沒有然后了。失敗是成功的媽媽，我不氣餒，決定馬上惡補一下。

類型和編碼

首先，整明白什么是類型？什么是編碼？在Redis中使用對象來表示內存中的鍵和值。每個對象由一個叫做redisObject結構體表示，其中有三個屬性：類型（type）、編碼（encoding）、指向具體數據的指針（ptr）。

我們通常說的字符串、哈希、列表、集合、有序集合都是redisObject中的類型，實際上針對每一個數據結構在Redis內部都有自己底層的多種內部編碼實現，這樣是為了在合適的場景選擇合適的內部編碼，以達到內存空間和處理效率的平衡，這可能就是中庸之道吧。

在面試中，經常被問到的內部實現方式、內部構造、內部原理，一般指的就是redisObject中的編碼。

集合的編碼

集合的編碼有兩種，分別是：整數集合（intset）和哈希表（hashtable）。

當集合中的所有元素都是整數，并且元素的個數小于set-max-intset-entries（默認為512個）時，使用整數集合作為集合的編碼，集合的所有元素都保存在整數集合里面。比如：

127.0.0.1:6379> sadd one-more-set 1 2 3 4 5 (integer) 5 127.0.0.1:6379> smembers one-more-set 1) "1" 2) "2" 3) "3" 4) "4" 5) "5" 127.0.0.1:6379> object encoding one-more-set "intset"

當集合中的所有元素不都是整數，或者元素的個數大于等于set-max-intset-entries（默認為512個）時，使用哈希表作為集合的編碼，哈希表的每一個鍵都是字符串對象，每一個字符串包含一個集合的元素，哈希表的值全部為NULL。

比如，集合中的所有元素不是整數：

127.0.0.1:6379> sadd one-more-set one more (integer) 2 127.0.0.1:6379> smembers one-more-set 1) "more" 2) "one" 127.0.0.1:6379> object encoding one-more-set "hashtable"

當然，了解以上細節還沒能完全“征服”面試官，我們需要更深入一些:)

集合的編碼轉換

當一個集合是以整數集合為編碼時，再向這個集合添加非整數的元素，或向這個集合添加整數的元素使元素個數過多時，就會執行集合的編碼轉換。

把原來保存在整數集合中的所有元素轉移到哈希表中，并且把集合的編碼用整數集合修改為哈希表。不過，把非整數的元素從集合中移除，或者減少整數元素的個數，以哈希表為編碼的集合也不會轉化為整數集合。

舉個例子，我們先創建一個以整數集合為編碼的集合：

127.0.0.1:6379> sadd one-more-set 1 2 3 4 5 (integer) 5 127.0.0.1:6379> smembers one-more-set 1) "1" 2) "2" 3) "3" 4) "4" 5) "5" 127.0.0.1:6379> object encoding one-more-set "intset"

然后，再向它添加兩個字符串元素，它就是轉換為以哈希表為編碼：

127.0.0.1:6379> sadd one-more-set one more (integer) 2 127.0.0.16379> smembers one-more-set 1) "one" 2) "5" 3) "1" 4) "2" 5) "more" 6) "4" 7) "3" 127.0.0.1:6379> object encoding one-more-set "hashtable"

然后，再把那兩個字符串元素從集合中移除，集合的編碼依然是哈希表：

127.0.0.1:6379> srem one-more-set one more (integer) 2 127.0.0.1:6379> smembers one-more-set 1) "5" 2) "1" 3) "2" 4) "4" 5) "3" 127.0.0.1:6379> object encoding one-more-set "hashtable"

總結

在Redis中，集合的內部實現有整數集合（intset）和哈希表（hashtable）兩種，當集合中的所有元素都是整數并元素個數較少時，使用整數集合作為內部實現，否則使用哈希表作為內部實現。當條件不滿足時，整數集合可以轉換為哈希表，但哈希表不能轉換為整數集合。

竟然已經看到這里了，你我定是有緣人，留下你的和關注，他日必成大器。

Redis 數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。