導(dǎo)讀相信大家應(yīng)該都有搶火車(chē)票的經(jīng)驗(yàn)，每年年底，這都是一場(chǎng)盛宴。然而你有沒(méi)有想過(guò)搶火車(chē)票這個(gè)算法是怎么實(shí)現(xiàn)的呢？其實(shí)并沒(méi)有你想的那么難。

12306搶票算法詳解我們以北京到西安這趟高鐵為例，比如我的路線(xiàn)就是從北京到西安，車(chē)上如果只剩最后一張票了，那么如果有其他人，在北京到西安這條路線(xiàn)之間買(mǎi)任何一站，那么我都是買(mǎi)不了票的，換句話(huà)說(shuō)，對(duì)于單個(gè)座位來(lái)說(shuō)，必須是起點(diǎn)到終點(diǎn)之間的所有站都沒(méi)有人買(mǎi)的話(huà)，那么才能被算是有票狀態(tài)。

所以我們可以嘗試用redis的bitmap結(jié)合上位操作來(lái)實(shí)現(xiàn)這種場(chǎng)景，以上述北京到西安為例，我們把問(wèn)題簡(jiǎn)化：

比如一個(gè)火車(chē)上只有4個(gè)座位；

北京到西安，一共是4站，其實(shí)是三個(gè)區(qū)間的，分別為北京-》石家莊，石家莊-》鄭州，鄭州-》西安。

首先我們給每個(gè)區(qū)間構(gòu)建一個(gè)空位圖（0為有票，1為無(wú)票）。接下來(lái)，比如有人買(mǎi)了一張從北京到西安的票。買(mǎi)票這個(gè)動(dòng)作，比如被分配到的座位是編號(hào)為1的座位，那么我們直接把北京到西安的所有站，1號(hào)座位全部設(shè)置為1

接下來(lái)又有人買(mǎi)了一張從石家莊到西安的票。比如這次分配的是座位2，那么我們把石家莊到西安的所有票全部設(shè)置為1就行了

如何知道還剩幾張票？其實(shí)解決這個(gè)問(wèn)題很簡(jiǎn)單，我們直接把上述位圖做一個(gè)或操作就可以了，因?yàn)榛虿僮魇潜仨毴慷紴?，才為0。

或操作結(jié)果有幾個(gè)0，則說(shuō)明還剩幾張票。

總結(jié)其實(shí)解決這個(gè)問(wèn)題主要在于位圖的構(gòu)建，因?yàn)榛疖?chē)票對(duì)于某一個(gè)座位來(lái)說(shuō)，只要起點(diǎn)到終點(diǎn)中間某一個(gè)區(qū)間被占用了（置為1），那么整個(gè)座位都是無(wú)效的這個(gè)特點(diǎn)，很容易想到用或操作的結(jié)果來(lái)判斷買(mǎi)票結(jié)果，我們這里只用了4位是為了方便說(shuō)明問(wèn)題，實(shí)際中應(yīng)該是火車(chē)上有多少座位，位圖的長(zhǎng)度就應(yīng)該是多少。

好了，關(guān)于搶票算法我們就介紹到這里，你有沒(méi)有g(shù)et到呢？或者你有沒(méi)有更好的實(shí)現(xiàn)方法呢？

責(zé)任編輯：haq