關注公眾號“彤哥讀源碼”，解鎖更多源碼、基礎、架構知識！

前言

本文收錄于專輯：http://dwz.win/HjK，點擊解鎖更多數據結構與算法的知識。

你好，我是彤哥，一個每天爬二十六層樓還不忘讀源碼的硬核男人。

相信大家都有過搶票、刷票的經驗，每年年底，這都是一場盛宴。

然而，你有沒有想過12306的搶票算法是怎么實現(xiàn)的呢？

沒有吧，想過，還是沒有頭緒？

今天，我們就來曝光讓人又愛又恨的12306是如何實現(xiàn)搶票的。

位運算回顧

我們知道計算機只能識別0和1，要操作這些0和1，只能通過位運算來進行，那么，一共有幾種位運算呢？

讓我們來回顧一下：

運算	符號	舉例	結果
與	&	? ? 1101 & 0110	0100
或	|	? ? 1101 & 0110	1111
異或	^	? ?1101 ^ 0110	1011
取反	~	1101	0010
左移	<<	1101 << 1	11010
帶符號右移	>>	1101 >> 1	1110
不帶符號右移	>>>	1101>>>1	0110

以上位運算以Java為例，其他語言中可能沒有 >>> 操作。

OK，位運算的簡單回顧就到這里，還有不懂的同學可以自行百度一下。

位圖

雖然大部分語言都有提供位運算，但是，并沒有提供一種類似于位數組的類型，要使用這些位運算，我們只能通過數字類型來實現(xiàn)，比如Java中的int/long等類型。

而這些數字類型的數組，我們一般可以稱之為“位圖”（BitMap）。

比如，我們需要使用128位的內存，可以申請包含兩個long類型的數組long[] bitmap = new long[2];。

不過，位圖有什么用呢？

有大用處哦，比如，我們要統(tǒng)計某個用戶一年的活躍度，就可以使用位圖來實現(xiàn)。

一年有365天，一個long類型可以表示64位，365/64=6，只需要6個long類型就可以記錄一個用戶一年的活躍情況，怎么記錄呢？

很簡單，初始時，位圖中所有位都是0，當這個用戶某天登錄了，就在位圖中找到這天，把其位變成1，一年下來，這張位圖就記錄了這個用戶哪些天登錄了，統(tǒng)計這個位圖中1的數量，除以365，就得到了他的活躍度。

OK，這只是位圖的一個很簡單的用法，位圖還有很多高級的用法，比如統(tǒng)計活躍用戶數、限流、權限控制等，當然，還有我們今天要曝光的12306搶票算法。

12306搶票算法

我們知道，一列火車，有很多個座位，可以到很多站，以北京到廣州的一列火車G67為例：

G67次列車一共有18個站，有的人可能到武漢就下車了，有的人可能到長沙下車，還有的人可能從武漢上車從衡山西下車，甚至還有的人從北京一直坐到廣州，我們假設這趟列車一共有200個座位。

那么，如何實現(xiàn)合理的搶票策略，才能保證這趟列車能夠坐最多的人？（沒有站票）

什么叫做“坐最多的人”呢？假設針對10號位置，一個人從北京到武漢，另一個人從武漢到長沙，再一個人從長沙到廣州，那針對這個位置全程可以坐3個人；針對另一個位置，一個人從北京到廣州，那這個位置全程只能坐一個人。簡單點說，就是針對一個特定的位置，兩個人之間不能有交集，比如一個人從北京到長沙，另一個人從武漢到廣州，那這兩個人不能安排到同一個位置上。

OK，先給你一分鐘時間思考一下，先別急著往下看哦。

---

好了，一分鐘時間已到，讓我們繼續(xù)。

首先，讓我們回顧下G67這趟列車的信息：一共18個站，一共200個座位。

為了方便講解和畫圖，我們假設它只有 北京、信陽、武漢、岳陽、長沙、廣州 6個站，一共有8個座位。

針對這樣的信息，我們可以這樣來實現(xiàn)搶票策略：

1. 創(chuàng)建5個位圖，每個位圖的大小為8位，初始時，每個位的值都是0。

   為什么是5個位圖呢？因為到站就下車了，而廣州站是終點站，到站全部人都得下車。比如，一個人從北京到武漢，他到武漢就下車了，所以，它不會占用武漢的位置。

   

2. 把搶票邏輯放在單線程中來處理，單線程的好處是不用考慮并發(fā)問題，沒有CPU上下文切換的問題等，而且整個操作都是CPU操作，速度很快，使用單線程效率更高。

   當然，我們還有更好的選擇——Redis，Redis本身就是單線程處理的，而且它天然支持BitMap，速度又快又好，有興趣的同學可以了解一下Redis中的BitMap。

3. 假設第一個人的請求過來了，他要搶從北京到武漢的票，此時，我們只需要把北京和信陽兩個位圖做“與”運算，結果中，所有0的位置都表示可搶的位置，在這些位置中隨機返回一個即可，并把此位置在北京和信陽這兩個位圖中標記為1，表示此位置在北京和信陽有人占用了。（武漢為什么不參與運算了，前面講過了，這個人到武漢就下車了。）

   

   假設，此人最后的座位是2號，那么運算之后，各位圖的情況如下：

   

4. 接著，第二個人的請求過來了，假設他要從信陽到長沙，此時，需要把信陽、武漢和岳陽三個位圖做“與”運算：

   

   假設，此人最后的座位是4號，那么，運算之后，各位圖的情況如下：

   

5. 然后，第三個人的請求來了，假設他要從北京到廣州，此時，把所有5個位圖做“與”運算：

   

   假設，此人最后的座位是1號位，那么，運算之后，各位圖的情況如下：

   

6. OK，經過了多個人的請求之后，假設位圖的情況變成了下面這樣：

   

   請思考，此時，還能搶到從北京到廣州的票嗎？

   能？不能？回答能的同學，請從頭再看一遍

好了，關于搶票算法我們就介紹到這里，你有沒有Get到呢？或者你有沒有更好的實現(xiàn)方法呢？

后記

本節(jié)，我們一起重溫了位運算的操作，并學習了如何使用位圖實現(xiàn)12306的搶票算法，關于位圖，其實還有很多用途，比如，各種統(tǒng)計、限流、權限控制等。

彤哥收到最新情報：所有的遞歸都可以改寫成非遞歸，怎么實現(xiàn)呢？有沒有什么套路呢？下一節(jié)，我們一起來聊下這個話題。

關注公號主“彤哥讀源碼”，解鎖更多源碼、基礎、架構知識。