幾乎所有程式設計語言中都提供了"生成一個随機數"的方法,也就是調用這個方法會生成一個數,我們事先也不知道它生成什麼數。比如在.Net中編寫下面的代碼:
|
運作後結果如下:
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsISPrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdsATOfd3bkFGazxCMx8VesATMfhHLlN3XnxCMwEzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsYTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5iZiJTMkFjMycTMlZDM0UWZ4YjNxAzYkdTZ0AjZ2QmM28CX2IzLcdDMxIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjL5M3Lc9CX6MHc0RHaiojIsJye.png)
Next()方法用來傳回一個随機數。同樣的代碼你執行和我的結果很可能不一樣,而且我多次運作的結果也很可能不一樣,這就是随機數。
一、陷阱
看似很簡單的東西,使用的時候有陷阱。我編寫下面的代碼想生成100個随機數:
|
太奇怪了,竟然生成的"随機數"有好多連續一樣的,這算什麼"随機數"呀。有人指點"把new Random()"放到for循環外面就可以了:
|
運作結果:
确實可以了!
二、這是為什麼呢?
這要從計算機中"随機數"産生的原理說起了。我們知道,計算機是很嚴格的,在确定的輸入條件下,産生的結果是唯一确定的,不會每次執行的結果不一樣。那麼怎麼樣用軟體實作産生看似不确定的随機數呢?
生成随機數的算法有很多種,最簡單也是最常用的就是 "線性同餘法": 第n+1個數=(第n個數*29+37) % 1000,其中%是"求餘數"運算符。很多像我一樣的人見了公式都頭疼,我用代碼解釋一下吧,MyRand是一個自定義的生成随機數的類:
|
如下調用:
|
執行結果如下:
生成的資料是不是看起來"随機"了。簡單解釋一下這個代碼:我們建立MyRand的一個對象,然後構造函數傳遞一個數51,這個數被指派給seed,每次調用Next方法的時候根據(seed * 29 + 37) % 1000計算得到一個随機數,把這個随機數指派給seed,然後把生成的随機數傳回。這樣下次再調用Next()的時候seed就不再是51,而是上次生成的随機數了,這樣就看起來好像每一次生成的内容都很"随機"了。注意"%1000"取餘預算的目的是保證生成的随機數不超過1000。
當然無論是你運作還是我每次運作,輸出結果都是一樣的随機數,因為根據給定的初始資料51,我們就可以依次推斷下來下面生成的所有"随機數"是什麼都可以算出來了。這個初始的資料51就被稱為"随機數種子",這一系列的516、1、66、951、616……數字被稱為"随機數序列"。我們把51改成52,就會有這樣的結果:
三、樓主好人,跪求種子
那麼怎麼可以使得每次運作程式的時候都生成不同的"随機數序列"呢?因為我們每次執行程式時候的時間很可能不一樣,是以我們可以用目前時間做"随機數種子"
|
Environment.TickCount為"系統啟動後經過的微秒數"。這樣每次程式運作的時候Environment.TickCount都不大可能一樣(靠手動誰能一微秒内啟動兩次程式呢),是以每次生成的随機數就不一樣了。
當然如果我們把new MyRand(Environment.TickCount)放到for循環中:
|
運作結果又變成"很多是連續"的了,原理很簡單:由于for循環體執行很快,是以每次循環的時候Environment.TickCount很可能還和上次一樣(兩行簡單的代碼運作用不了一毫秒那麼長事件),由于這次的"随機數種子"和上次的"随機數種子"一樣,這樣Next()生成的第一個"随機數"就一樣了。從"-320"變成"-856"是因為運作到"-856"的時候時間過了一毫秒。
四、各語言的實作
我們看到.Net的Random類有一個int類型參數的構造函數:
public Random(int Seed)
就是和我們寫的MyRand一樣接受一個"随機數種子"。而我們之前調用的無參構造函數就是給Random(int Seed)傳遞Environment.TickCount類進行構造的,代碼如下:
public Random() : this(Environment.TickCount)
{
}
這下我們終于明白最開始的疑惑了。
同樣道理,在C/C++中生成10個随機數不應該如下調用:
|
而應該:
1 2 3 4 5 6 | |
五、"奇葩"的Java
Java學習者可能會提出問題了,在Java低版本中,如下使用會像.Net、C/C++中一樣産生相同的随機數:
|
因為低版本Java中Rand類的無參構造函數的實作同樣是用目前時間做種子:
public Random() { this(System.currentTimeMillis()); }
但是在高版本的Java中,比如Java1.8中,上面的"錯誤"代碼執行卻是沒問題的:
為什麼呢?我們來看一下這個Random無參構造函數的實作代碼:
|
這裡不再是使用目前時間來做"随機數種子",而是使用System.nanoTime()這個納秒級的時間量并且和采用原子量AtomicLong根據上次調用構造函數算出來的一個數做異或運算。
最核心的地方就在于使用static變量AtomicLong來記錄每次調用Random構造函數時使用的種子,下次再調用Random構造函數的時候避免和上次一樣。
六、高并發系統中的問題
前面我們分析了,對于使用系統時間做"随機數種子"的随機數生成器,如果要産生多個随機數,那麼一定要共享一個"随機數種子"才會避免生成的随機數短時間之内生成重複的随機數。但是在一些高并發的系統中一個不注意還會産生問題,比如一個網站在伺服器端通過下面的方法生成驗證碼:
Random rand = new Random();
Int code = rand.Next();
當網站并發量很大的時候,可能一個毫秒内會有很多個人請求驗證碼,這就會造成這幾個人請求到的驗證碼是重複的,會給系統帶來潛在的漏洞。
再比如我今天看到的一篇文章《當随機不夠随機:一個線上撲克遊戲的教訓》裡面就提到了"由于随機數産生器的種子是基于伺服器時鐘的,黑客們隻要将他們的程式與伺服器時鐘同步就能夠将可能出現的亂序減少到隻有 200,000 種。到那個時候一旦黑客知道 5 張牌,他就可以實時的對 200,000 種可能的亂序進行快速搜尋,找到遊戲中的那種。是以一旦黑客知道手中的兩張牌和 3 張公用牌,就可以猜出轉牌和河牌時會來什麼牌,以及其他玩家的牌。"
這種情況有如下幾種解決方法:
- 把Random對象作為一個全局執行個體(static)來使用。Java中Random是線程安全的(内部進行了加鎖處理);.Net中Random不是線程安全的,需要加鎖處理。不過加鎖會存在會造成處理速度慢的問題。而且由于初始的種子是确定的,是以攻擊者存在着根據得到的若幹随機數序列推測出"随機數種子"的可能性。
- 因為每次生成Guid的值都不樣,網上有的文章說可以建立一個Guid計算它的HashCode或者MD5值的方式來做種子: new Random(Guid.NewGuid().GetHashCode()) 。但是我認為Guid的生成算法是确定的,在條件充足的情況下也是可以預測的,這樣生成的随機數也有可預測的可能性。當然隻是我的猜測,沒經過理論的證明。
- 采用"真随機數發生器",快看下一節分解!
七、真随機數發生器
根據我們之前的分析,我們知道這些所謂的随機數不是真的"随機",隻是看起來随機,是以被稱為"僞随機算法"。在一些對随機要求高的場合會使用一些實體硬體采集實體噪聲、宇宙射線、量子衰變等現實生活中的真正随機的實體參數來産生真正的随機數。
當然也有聰明的人想到了不借助增加"随機數發生器"硬體的方法生成随機數。我們操作計算機時候滑鼠的移動、敲擊鍵盤的行為都是不可預測的,外界指令計算機什麼時候要執行什麼程序、處理什麼檔案、加載什麼資料等也是不可預測的,是以導緻的CPU運算速度、硬碟讀寫行為、記憶體占用情況的變化也是不可預測的。是以如果采集這些資訊來作為随機數種子,那麼生成的随機數就是不可預測的了。
在Linux/Unix下可以使用"/dev/random"這個真随機數發生器,它的資料主來來自于硬體中斷資訊,不過産生随機數的速度比較慢。
Windows下可以調用系統的CryptGenRandom()函數,它主要依據目前程序Id、目前線程Id、系統啟動後的TickCount、目前時間、QueryPerformanceCounter傳回的高性能計數器值、使用者名、計算機名、CPU計數器的值等等來計算。和"/dev/random"一樣CryptGenRandom()的生成速度也比較慢,而且消耗比較大的系統資源。
當然.Net下也可以使用RNGCryptoServiceProvider 類(System.Security.Cryptography命名空間下)來生成真随機數,根據StackOverflow上一篇文章介紹RNGCryptoServiceProvider 并不是對CryptGenRandom()函數的封裝,但是和CryptGenRandom()原理類似。