Java之唯一無序數生成

1 背景介紹

在許多項目中ID號是一個永恆的主題。在絕大多數情況下，這個唯一ID產生相對比較容易，畢竟現在眾多的項目都是基於數據庫的，只要把數據庫的主鍵拿出來作為ID就可以確保ID在整個系統中的唯一性了。但也存在一些特殊情況。比如，一個在線訂單生成。考慮到訂單的特殊性，有時候會被要求訂單號要沒有規律不連續。但是我們也知道訂單號是必須具有唯一性的。然而，一般數據庫的主鍵都是采用自增數作為主鍵的。因此，這裡如果再用主鍵作為訂單號就會存在問題。當然，除了這個情況外，還有許多其他情況。諸如，需要自動的生成一個隨機的用戶ID等。 考慮到以上的背景，我這篇將繼上一篇《Java之Caesar與Vigenere實現》見 http://www.linuxidc.com/Linux/2011-11/46575.htm 做一個唯一的偽隨機數生成。作為對上一篇看上去挺簡陋甚至不怎麼安全的加密算法做一個具有現實意義的應用實現。話說，這兩個坑爹的算法，如果加以合理的組合運用還是挺有用處的。其實大多數的安全問題，都是因為人為因素造成的和算法本身問題沒太大的關系。

2 實現分析

眾所周知，在計算機中，用算法實現的真實隨機數是不可能存在的。當然，如果要從哲學角度考慮的話，那就是偶然和必然的問題了。就拿拋硬幣來說，你可以把拋擲的結果看成是隨機的，但是根據力學分析去分析每一個拋擲過程，你發現拋硬幣的結果又不是隨機的。

2.1 前期分析

扯那麼多廢話，再回到我們的主題上。如果要生成唯一隨機ID，http://www.linuxidc.com眾所周知的辦法是用GUID來實現。但是，如果你了解GUID的生成，就會知道GUID的生成只是將發生相同GUID的幾率降到一定數值之下而已，並不能百分百保證不重復，雖然這個重復的概率比中彩票都低。而且，諸如用戶ID這種情況，要用戶每次登陸都輸入那麼長一串GUID顯然是不現實的。 那麼，我們來看看第二種嚴格符合題意的做法。現在，我們被要求的有兩點:第一是隨機的一個數，第二是唯一的。那麼，生成一個隨機數還是比較簡單的，那就用Random做就OK了。接下來要滿足唯一性，那也不難，把每次生成結果保存起來，之後每生成一個隨機ID，就到歷史裡去查一下有沒有重復，如果有重復就重新生成一個，周而復始直到滿足唯一性。乍看之下這個算法真是"天衣無縫"啊～，話說很多人都一開始會覺得這個算法的確不錯。但是，仔細想想卻存在問題。如果是幾個這樣的ID問題不是很大，但如果要生成數量眾多的ID呢？"理想情況"下，每個ID都要到歷史裡去遍歷一遍所有的ID。但是，對於限定ID位數的情況下，隨著已生成ID的數量增加，發生沖突的幾率也會提高。這樣的話，將直接導致算法不可用。

2.2 實現思路

根據上面的分析，是不是覺得實現這樣一個"小問題"，還需要很多的精力去思考呢？很多時候，我們看似簡單的問題，真正實現起來卻會遇到很多問題。如果作為一個普通的coder，那問題不是很嚴重。但是，如果作為一個leader，不能正確的預見到所要面臨的問題，那就沒有成為leader的資格。 那我們現在透過現象看本質。我們現在最容易拿到具有唯一性的數據是什麼？是數據的ID，但這是一個有序數列。那麼我們接下來要做什麼？就是讓這個有序數列看不出有序，讓人產生迷惑感。那什麼能讓人對"有意義"的東西產生迷惑呢？對，就是加密算法。加密算法的本質就是將一組有意義的數據通過處理變成無意義的。這樣看來，算法的思路就很簡單了。就是把ID經過某個加密算法處理後即可。

3 算法實現

根據剛才的想法，那麼我們首先想到的應該是MD5這類算法，但是那個生成的簽名是固定的128bit數據，轉換成可輸入的字符，有32個字符。這樣的話，用GUID效果或許會更好。那麼，其次我們應該想到的是AES算法，他的雪崩效應令人映像深刻。但是AES每個加密塊都是固定長度，而且加密之後還要字符串化，最主要的是AES加密算法實現也比較復雜。所以，綜合以上考慮，是否突然發現或許可以用Caesar實現呢？

3.1 算法代碼

那麼，根據思路，我們實現了如下的代碼。

import java.util.Random;  
  
public class RandomId {  
    private Random random;  
    private String table;  
    public RandomId() {  
        random = new Random();  
        table = "0123456789";  
    }  
    public String randomId(int id) {  
        String ret = null,  
            num = String.format("%05d", id);  
        int key = random.nextInt(10),   
            seed = random.nextInt(100);  
        Caesar caesar = new Caesar(table, seed);  
        num = caesar.encode(key, num);  
        ret = num   
            + String.format("%01d", key)   
            + String.format("%02d", seed);  
          
        return ret;  
    }  
    public static void main(String[] args) {  
        RandomId r = new RandomId();  
        for (int i = 0; i < 30; i += 1) {  
            System.out.println(r.randomId(i));  
        }  
    }  
}  

這段代碼是基於上一篇《聊勝於無 Java之Caesar與Vigenere實現》的代碼實現的。接受一個有序的ID數字序列，輸出一個至少8位的唯一隨機的字符串。

3.2 代碼分析

通過執行代碼，我們得到一組隨機的由數字組成的ID字符串。由於生成的原理，所以不會因為生成ID的數量增加而造成算法性能下降。接下來我們看看，這個隨機的序列真是唯一的麼？從算法可知，根據這個隨機序列，我們能夠還原出原來的唯一ID。這也就證明，這個隨機的序列是唯一。並且，在第三方不知道key和seed的長度與位置的情況下，以及算法實現的情況下，是很難還原出原本有序的ID的。而且，由於這類ID一般會保存在數據庫中，同時一個有序ID能夠對應多個無序的ID，所以，即使��道整個生成的細節，也很難根據有序ID偽造出一個合法的無序ID。

4 總結

看過上一篇Caesar與Vigenere實現（見 http://www.linuxidc.com/Linux/2011-11/46575.htm ）的人，一定會覺得那樣"古老"的手工密碼，貌似沒有什麼實際可用的意義。但是，通過這篇文章的補充，或許會給你的思路一些拓展。我也希望你能有更多的想法和我們分享。我想，很多看似"無用"的東西，經過合理的運用，就會在不同的時代發揮其不同的作用。