Bitmap（點陣圖演算法），多研究演算法可以強身健體

截止目前，一共兩千多粉絲，竟然99.36%是男僧。。。我果然是個不受女僧待見的人。

當然這個無所謂啦，畢竟作為一個三旬老漢，兒女雙全，不該想的就不多想了。

為什麼研究演算法可以強身健體？答曰：年輕人精力旺盛，難免看點啥做點啥的傷身體，如果多拿出來點時間研究點演算法，是不是用在不該用的方面時間就少了，對身體傷害也就少了，進而增強體質了？哦，挺有道理的樣子。都搬個板凳過來默默的看我裝A-C吧。哈哈

要做一個用戶畫像系統，維護用戶的多個維度信息比如：性別，年齡，籍貫，身體，體重，手機型號，是否健身，飲食愛好。。。。。亂七八糟的可能有上萬個維度（某些朋友別較真這合理不合理，就為了說明問題而已！以前寫的文章還真有人非得跟我討論我舉的例子人家騰訊公司會不會真拿來做解決方案。。。。我了個去，身體傷的不輕，準是看多了，要節制），那麼問題來了，如果我們用mysql數據保存這些的話，大約會是下面這個熊樣：

我能力有限只寫了4個屬性，剩下的9996個屬性大家自動腦補進去吧。好了，存儲問題解決。來看檢索：

10000個屬性，寫完了程序員也該老了，直接去辦退休得了。執行效率如何？目測肯定慢的驚人。萬一再複雜一點，來個distinct關鍵字。。。酸爽了。

Bitmap說明：

看來這方案玩不通了，怎麼辦？bitmap登場吧。

bitmap是點陣圖演算法，但是這個真的跟「圖形」沒多大關係哈。演算法核心：用bit這個最小的存儲單位（僅能表示0和1兩個值）來構建演算法，來表示很多信息，從而提高海量存儲檢索條件下的效率。

例子：

給10bit的內存空間，如何來表示9,5,2,7這4個數字？

1. 非bitmap：

   以java為例，表示一個整形最節約的是byte，每個整數8bit，顯然完不成任務。別的short，int，long更別提了

2. bitmap實現：

如上圖，1-10這10個bit，黃顏色的賦值為1，其餘賦值為0，好啦！任務完成。

有點奇技淫巧的既視感。

其實我們偷偷的加入了一個參數——bit位的位置或者說排序，最終我們賦值和位置（排序），來完成了標記。

（如果不好理解，可以想象成一個數組，每個位置都賦值1或者0，值為1的下標就是我們要保存的數字，這樣通過賦值和數組的下標，構建成我們期望的結果）

問題解決方案：

上面我們簡單的說明了什麼是bitmap，現在來看如何解決我們開篇的問題：

用戶畫像需求，如果按照慣性思維肯定是「某人，擁有某屬性1，屬性2，屬性3。。。。。」，立即一個mysql的table就設計出來了，剛才說了這方案有問題。我們轉化一下思路——改為「某屬性，被user1，user2，user3。。。。。擁有」，比如年齡33的用戶有user1，user4，user9。。。。等等。套用上面的bitmap就是

如果我們有10億用戶，那麼我們大不了把bit的位數提高到2的30次方。。。存儲空間大約是1G而已。

總結：

本文不做過多的延伸，僅僅解釋一下思路。

bitmap是空間利用率和檢索效率最高的方式。當然在我們使用的過程中會有很多奇葩的關聯需求出現，bitmap未必能全部解決，我後續還會針對bitmap寫一些關聯演算法和優化，請持續關注。

謝謝各位。

福利圖：