我們通常比較喜歡確定性，不喜歡隨機性。但是在計算機科學中，很多時候我們故意要把確定的東西變成隨機的，這種思維顯然和我們人類的思維不同。我們前幾天提到了查找和搜索需要用到這種方法，今天我們填上這個坑。另外，每個人都不知不覺地使用的信息加密，也離不開隨機化。我們今天說比特幣是安全的，其實也是靠隨機化來做保障。當然，我們還是從查找信息這件事說起。

 

我們前幾天講到有效地查找信息可以藉助索引這個工具。比如說我們要找李強的訊息，有了索引之後，計算機可以先在索引中找到李強的訊息所存放的位置，然後才是進一步獲取所要的信息。但是在前幾天的課中，我們忽略了一個問題，就是在索引中，我們怎麼找到李強的位置，如果我們的索引包括北京市戶籍中所有的人名，這個索引本身就很大，可能有幾百萬，或者上千萬。雖然在索引中找到李強比在數據庫中找到他容易，但畢竟是件不小的事倩。類似地，在搜索引擎中，雖然我們根據每一個詞把所有的文檔建立了索引，但是在 Google 的詞表中，全世界有上千萬個不同的詞，要在索引中找到〝得到〞這個詞也不容易。

 

讀了前幾天內容的朋友可能會想到， 把索引排個序，用二分查找即可。沒錯， 這確實是一個好方法。對於規模不大的數據庫，索引也是這麼建立的。這種方法最大的好處是不會浪費任何空間，存儲的效率比較高。那麼用二分查找，在索引中找到〝李強〞要查找多少次呢？我們假定北京市人名索引中有 800 萬個不同的人名，或者 Google 的詞表中有 800 萬個單詞，通過二分查找需要 23 次可以找到〝李強〞，或者〝得到〞，也就是 log ( 800萬）。

 

23次算不算多呢，這對計算機科學家來講不算一件了不得的事清，但是在工程上這個次數算不算多，得看具體的應用了。對於查戶籍這件事，23次查找真算不上什麼，但是對於語音識別或者機器翻譯，識別或者翻譯一句話要查找上萬次詞語，如果每一個詞都要先在索引中查23次才能找到，就是一個大負擔了。我們希望最好有一個辦法，能夠三下兩下就找到〝李強〞或者〝得到〞在索引中的位置，這樣可以節省十倍的時間了。能夠上面這樣的想法現實不現實呢？事實上是可以做到的，但是要付出一點代價， 它就需要用到我所說的隨機化了。下面我就來講講隨機化是怎麼進行的。

 

首先，我們來看一個笨辦法，有些時候，笨辦法是好辦法的基礎。

 

我們知道，漢字大約有兩萬多個，我們就放大一下，假設是3萬個吧！這樣每個漢字就對應了一個從 0 ~ 29,999 的數字。假如〝李〞這個字對應 3,500，〝強〞這個字對應 4,003，那麼〝李強〞就對應一個數字組 3,500 和 4,003。注意這個對應是唯一的， 沒有歧義性。

 

接下來，我們做一個簡單的數學變換，把上面兩個數字變成一個，方法是： 30, 000 * 3,500 + 4,003 = 105,004,003，也就是說拿 105,004,003 這個數字作為李強這個名字的編號。注意，這個數字和〝李強〞這個名字的對應關係也是唯一的。類似地，我們假設〝得〞對應509，〝到〞對應10,032，我們用 509 *  30,000 + 10,032= 15,280,032，作為〝得到〞這個詞的編號。這樣一來，每一個中國人的名字，或者漢語的詞都可以對應一個數字。

 

再接下來就簡單了，我們建立索引的時候，直接把〝李強〞存放到第 105,004,003 個存儲單元，把〝得到〞存放到第 15,280,032 個存儲單元，將來查找時，無論是看到一個詞，還是看到一個名字，只要用上面的公式做一次計算，就能直接找到〝李強〞，或者〝得到〞在索引中的位置了。這個方法確實決，把原來 23 次查找變成了一次，但是什麼事清都是有成本的， 這個方法有兩個大問題。

 

其一，非常浪費。不會有人起名為〝豬狗〞或者類似的名字，於是對應數字所佔據的單元就被浪費掉了。大約會浪費多少呢，如果漢字是3萬個，每個人都是兩字的名字，一共有9億個不同的編號。再假如北京市不重複的人名是800萬，大約浪費了 99％ 以上的編號（ 以及對應的內存單元 )。這顯然不是一個好方法。

 

其二，空間不夠。這也是更糟糕的，當大家起了三字名，甚至是四字名，名字對應的編號就可能非常大，以至於超出計算機的存儲範圍。

 

一方面是浪費，另一方面空間不夠用，就必須解決這個問題。這就要說到我們的第二個方法了。

 

方法二，只保留編號的尾數。

 

我們注意到無論是〝李強〞的編號，還是〝得到〞的編號，都特別長，這麼長的編號是不太會重複的，那麼稍微短一點行不行，比如我們不管編號有多少位，只保留最後的 7 位數字，也就是說將編號的範圍從 9 億縮小到 1000 萬。由於北京市只有 800 萬不同的人名，照理說準備 1000 萬個代號是夠用的，之所以不夠用是因為兩個不同的人名計算出的編號，尾數可能冶巧重複這種情況並不少見。

 

那麼接下來該怎麼辦？這其實是我給你的問題。通常這時候人會有兩個態度， 一種是退回來，另一種是遇到問題，解決問題。

 

在 Google 時，每當下屬對我講什麼事清有困難時，我一般會先判斷一下能解決的可能性有多大，如果我覺得還是能解決的，就會對他們說，〝遇到問題，解決問題，這時候正是顯示你科班出身的工程師的水平的時候，否則你和半路出家的人有什麼區別，〞幾乎所有的時候，他們發揮主動性，問題還真就解決了。

 

對於上述問題，當年研究算法的科學家們也是本著這個態度解決問題的。具體講，就是在尾號出現相同清況時，想辦法找一個沒有那個詞或者名字對應的尾號， 作為備選方案。我們既然有 1000 萬個代號，只有 800 萬個名字，這個備選的號碼，一定是能夠找到的。

 

為了方便你理解其中的原理。我們不妨看這樣一個例子。假如火車站買票時是隨機安排座位的，到了火車上，一定有一些人拿到相同的座號。但是，如果火車能載 1000 人，只賣了 800 張票，一定有辦法安排每一個人就座的。具體的做法是，先來的先坐下，如果後來的發現自己票上的座位已經被佔據了，那麼沒關係，找最近的坐下即可。如果火車上真有 20％ 的空座終大家其實都能在附近找到一個空座。往計算機中，安排這種相同尾數的編號的方法和火車上安排座位的原理是一樣的。

 

當然，對於任何事清，我們都應該問問，是否還有更好的方法。對於這個問題也是有的那麼就要講到方法三了。

 

方法三，隨機指定一個名字或者詞語的編號。

 

我們在方法一和方法二中，其實是按照一個公式，將人的名字或者一個詞，變成一個編號的，然後再取它的尾數。這時，兩個不同的名字有可能得到相同的編號尾數。後來計算機科學家們發現，如果隨機地給每個名字，或者詞語進行編號， 重複的可能性最小。於是，計算機科學又有了一個小分支，如何產生偽隨機數。

 

為什麼說是偽隨機數呢，因為它們並非真的隨機，只是看上去非常像隨機產生的。至於為什麼隨機的比確定的好，我們這裡就省略了大家記住這個結論就好。

 

偽隨機數要想像真的隨機數，就需要懂得很多數學原理，於是很多數學家也就加入了這方面的研究。

 

後來，數學家和計算機科學家發現， 如果一個信息（比如名字或者詞語），對應的偽隨機數足夠長，別人是無法通過這個數字還原出原來的信息的，但是產生這個偽隨機數的人卻可以。於是，這個方法就能用來進行數據加密。當然，這裡面還有一個問題，如果加密的人和接收到信息後解密的人不是一個人，解密的一方需要知道加密的方法。如果這個方法給了對方，萬一泄露出去，就麻煩了。後來，數學家們想出了一個不讓對方知道自己怎麼加密，卻能夠對某個信息解密的方法。這種方法在密碼學上被稱為公開密鑰，今天大部分加密算法都採用這種技術。

 

最後講一下比特幣。比特幣產生的算法，外面的人是不知道的，即使挖幣的礦工也不知道，否則你自己就能製造比特幣了。產生比特幣的過程，和我們說的將〝李強〞對應一個數字類似，它要產生一個比特幣對應的隨機數，也被稱為私鑰 ( 不公開的 )，誰拿到它，就擁有了比特幣，這個隨機數不能丟，否則比特幣就不是你的。 

 

那麼大家要怎麼知道你的比特幣是真的呢？比特幣協議還會產生一個公開的密鑰，它可以用來驗證比特幣的真假。你可以把比特幣產生的協議看成是印鈔機，它怎麼印鈔，不能讓你知道。而比特幣的公開密鑰，則相當於驗鈔機，你可以拿它驗證比特幣的真偽。如果驗證完了確認為真，你收了那個比特幣，私鑰就歸你了， 當然，比特幣的所有權和使用權也就給了你了。

 

我們今天從查找講到比特幣，內容跨度很大，我把它們總結如下：

 

1. 從查找到比特幣，很多技術背後的道理是相通的，這也就是我喜歡講原理， 不喜歡講具體的實戰技術的原因，原理搞懂了，一通百通。一些朋友講，能不能講一些我明天就用得上的內容。非常抱歉， 我只能說他們找錯了人。我希望我的讀者朋友都是能舉一反十的，不是死記硬背方法的。

 

2. 我們今天的內容是一層層遞進的， 這樣講的目的是要強調一種做事清的方法就是遇到問題解決問題

 

3. 今天我們對隨機性和隨機化開了一個頭，今後我們還會講到相關的內容。從隨機性在一些領域相比確定性的好處，我們應該了解，世界上很多時候，好和壞和我們想像的不一樣，而且這種客觀陛不隨我們的好惡改變。

 

4. 回顧這一周的內容，我們講查找信息的成本從幾千萬次，甚至十多億次降到了幾十次，又通過隨機化降到了幾次，甚至是一次直接成功，這也說明了技術無止境，我們對自己的要求也不應該有止境。

 

 

來源：《吳軍-從Windows Vista系統的失敗看到哪些商業邏輯？》