如何隨機生成一個整數的排列函數<10000

Question

我想允許用戶使用相同的用戶名，但有一些額外的ID在形式#XXXX其中X是一個數字（例如，BestUserName＃3421 ），類似於Battle.net上的做法。

沒有兩個用戶應該有相同的用戶名和#id組合。

此外，我不希望我的用戶能夠輕鬆預測其他用戶的額外ID。所以，我不能只從BestUserName＃0000開始，然後是BestUserName＃0001，BestUserName＃0002 ...）。因此，我想爲每個用戶名生成一個雙向註冊f（n），從0000和9999之間的所有數字到0000和9999之間的每個數字。f必須很難猜測f（n-1）是當你知道f（n）時。另外，對於所有用戶名，f（n）必須不相同。

然後，第一個用戶將是BestUserName＃f（0000），第二個用戶名BestUserName＃f（0001）等，我的用戶將無法猜測對方的#id。

我該如何在Java中做到這一點？

Answer 1

你想要一個雙射。加密是一種雙向注入，所以只需對數字0,1,2,3 ...進行加密，只要您使用相同的密鑰，就不會有重複。加密確保沒有顯示數字的明顯順序。

你想要一個不尋常的範圍，0000..9999所以你可能需要Hasty Pudding cipher，它可以處理許多不同的範圍，包括你的。

Answer 2

在構造函數中，創建一個用值0000 - 9999初始化的ArrayList，對其進行混洗，並將計數器初始化爲-1（或10000）。每次添加用戶時，遞增（或遞減）計數器並使用它來索引ArrayList的下一個元素。或者，如果您將額外的ID添加爲用戶的屬性，則可以將計數器丟棄並僅刪除並分配ArrayList的最後一個（或第一個）元素。

如果作業應該是永久性的，則必須存儲先前的作業，洗牌ArrayList和計數器值，以便您可以選取上次停止的位置。

Answer 3

所以，我碰巧在這方面做的參數搜索，發現以下14位散列函數：

int h(int x) { 
    x &= 0x3fff; 
    x ^= x >> 8; 
    x *= 0x68ab; 
    x &= 0x3fff; 
    x ^= x >> 8; 
    x *= 0x594b; 
    x &= 0x3fff; 
    x ^= x >> 8; 
    return x; 
} 

此散列遵循murmur3 mix功能建設。 &=操作是保持算術在14位溢出域中運行，但除此之外每一步都是雙向注入，因此整體散列是雙向注入。

每次乘法都是奇數的（使它與模2 ** 14共素，從而保證所有結果都是唯一的），並且可以通過在一個位置解除操作一位來反轉移位異或操作時間。

但上面的功能不僅保證映射小於16384一個號碼到另一個號碼小於16384。我們需要把這個限制爲小於10000

如果您在下面的循環包裹它，它會受限於小於10000的值（不用擔心，平均迭代次數可證明爲1。6384所以它是相當安全）：

int f(int x) { 
    do { 
    x = h(x); 
    } while (x >= 10000); 
    return x; 
} 

由於循環內的散列函數是雙射，只有一個輸入x可以映射到任何給定的結果。如果結果超出範圍，但x處於範圍內，則哈希的下一次迭代必須映射到新值。即使它指向一個新的超出範圍的價值鏈最終必須被迫回到範圍內。

一個完全超出範圍的週期可以存在，但它將無法從範圍內的值，因爲其含義是一個鏈接在該週期有兩個值映射到它（一來自外部，來自內部），這不能通過雙射函數來實現。

這意味着輸入到f()必須已經在範圍內才能從無限循環中安全。

我們使之成爲每個用戶名不同，試試這個：

int f(int x, int username_hash) { 
    int m = (username_hash * 2 + 1) & 0x3fff; 
    int c = (username_hash >> 13) & 0x3fff; 
    do { 
    x = (x * m + c) & 0x3fff; 
    x = h(x); 
    } while (x >= 10000); 
    return x; 
} 

同樣，乘以奇數模二的冪是雙射，並且增加模二的冪也是雙射。根據username_hash，在那裏拋出這兩個額外的操作有效地擴展了散列並擾亂了它的行爲。並且外部循環將結果保持在10000以下。

我不確定您的意思是將用戶總數限制爲10000，還是對每個爭用用戶名分別計數，但如果您傳遞給f()該數字（保證小於10000）以及用戶名的一些整數哈希值以配置操作，然後您將得到一個數字，與您傳入的數字一樣唯一。