關(guān)注公眾號“彤哥讀源碼”，解鎖更多源碼、基礎(chǔ)、架構(gòu)知識！

前言

本文收錄于專輯：http://dwz.win/HjK，點(diǎn)擊解鎖更多數(shù)據(jù)結(jié)構(gòu)與算法的知識。

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

相信大家都有過搶票、刷票的經(jīng)驗(yàn)，每年年底，這都是一場盛宴。

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

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

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

位運(yùn)算回顧

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

讓我們來回顧一下：

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

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

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

位圖

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

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

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

不過，位圖有什么用呢？

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

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

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

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

12306搶票算法

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

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

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

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

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

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

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

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

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

創(chuàng)建5個位圖，每個位圖的大小為8位，初始時，每個位的值都是0。
為什么是5個位圖呢？因?yàn)榈秸揪拖萝嚵耍鴱V州站是終點(diǎn)站，到站全部人都得下車。比如，一個人從北京到武漢，他到武漢就下車了，所以，它不會占用武漢的位置。
把搶票邏輯放在單線程中來處理，單線程的好處是不用考慮并發(fā)問題，沒有CPU上下文切換的問題等，而且整個操作都是CPU操作，速度很快，使用單線程效率更高。
當(dāng)然，我們還有更好的選擇——Redis，Redis本身就是單線程處理的，而且它天然支持BitMap，速度又快又好，有興趣的同學(xué)可以了解一下Redis中的BitMap。
假設(shè)第一個人的請求過來了，他要搶從北京到武漢的票，此時，我們只需要把北京和信陽兩個位圖做“與”運(yùn)算，結(jié)果中，所有0的位置都表示可搶的位置，在這些位置中隨機(jī)返回一個即可，并把此位置在北京和信陽這兩個位圖中標(biāo)記為1，表示此位置在北京和信陽有人占用了。（武漢為什么不參與運(yùn)算了，前面講過了，這個人到武漢就下車了。）
假設(shè)，此人最后的座位是2號，那么運(yùn)算之后，各位圖的情況如下：
接著，第二個人的請求過來了，假設(shè)他要從信陽到長沙，此時，需要把信陽、武漢和岳陽三個位圖做“與”運(yùn)算：
假設(shè)，此人最后的座位是4號，那么，運(yùn)算之后，各位圖的情況如下：
然后，第三個人的請求來了，假設(shè)他要從北京到廣州，此時，把所有5個位圖做“與”運(yùn)算：
假設(shè)，此人最后的座位是1號位，那么，運(yùn)算之后，各位圖的情況如下：
OK，經(jīng)過了多個人的請求之后，假設(shè)位圖的情況變成了下面這樣：
請思考，此時，還能搶到從北京到廣州的票嗎？
能？不能？回答能的同學(xué)，請從頭再看一遍