尋找一個哈希函數/有序的Int/to/Shuffled Int/

我在尋找恆定時間的算法可以將一個有序的整數索引值變成一個隨機的哈希索引。如果它是可逆的，它會很好。我需要這個散列鍵對每個索引都是唯一的。我知道這可以通過在大文件中查找表來完成。 I.E.創建一個有序的所有整數，然後隨機隨機混合並以隨機順序寫入文件。你可以在需要的時候閱讀它們。但這需要尋找一個大文件。我想知道是否有一種簡單的方法來使用僞隨機生成器來根據需要創建序列？尋找一個哈希函數/有序的Int/to/Shuffled Int/

Generating shuffled range using a PRNG rather than shuffling answer by erikkallen線性反饋移位寄存器看起來是正確的。我只是嘗試過，但它會產生重複和漏洞。

問候大衛·芬奇艾倫

來源

2009-02-11 David Allan Finch

我不認爲這裏有足夠的信息來提出一個好的解決方案。你需要整理多少個整數？那個整數列表中是否有重複項？你的名單的價值範圍是什麼？ – EvilTeach 2009-02-12 01:24:33

有序整數是否允許爲負數？ – EvilTeach 2009-02-12 01:25:20

我打算使用無符號長整型或長整型（即32位或64位）的全部範圍。 – 2009-02-12 10:29:06

現在的問題是如果你需要一個真正的隨機映射，或者只是一個「弱」排列。假設後者，如果用2的補碼算術運算無符號的32位整數（比如說），乘以任何奇數是一個雙射和可逆映射。當然XOR也是如此，因此您可能嘗試使用的簡單模式是

unsigned int hash(int x) { 
    return (((x^0xf7f7f7f7) * 0x8364abf7)^0xf00bf00b) * 0xf81bc437; 
}

數字沒有什麼神奇的。所以你可以改變它們，甚至可以隨機化。唯一的是被乘數必須是奇數。你必須用滾動計算（忽略溢出）。這可以倒過來。做反轉，則需要能夠計算出正確的互補被乘數A和B，之後反轉是

unsigned int rhash(int h) { 
    return (((x * B)^0xf00bf00b) * A)^0xf7f7f7f7; 
}

可以計算A和B數學，但你更容易的方式就是運行一個循環並搜索它們（一旦離線，就是這樣）。

該公式使用XOR與乘法混合使映射非線性。

來源

2009-02-12 04:16:07

假設你的目標是要在整個範圍內展開分組值，
好像在一些預先定義的順序可能做的伎倆洗牌位。
即給出8位ABCDEFGH，像EGDBHCFA那樣排列它們，或者一些這樣的模式。

該代碼只是一個簡單的掩碼，移位和添加序列。

來源

2009-02-11 21:19:55 AShelly

嗯...取決於如果您有很多的數字，你可以用一個「亂」的標準使用正常的STL名單，並責令

bool 
nonsort(int i, int j) 
{ 
    return random() & 31 >16 ? true : false; 
} 

std::list<int> li; 
// insert elements 
li.sort(nonsort);

然後，你可以得到所有的整數一個正常的迭代器。請記住用時間或任何其他僞隨機值對srand（）進行隨機初始化。

來源

2009-02-11 21:26:10

你可以嘗試建立一個合適的Feistel network。這些通常用於密碼學（如DES），但至少有64位，因此您可能需要自己構建一個適合您的需求。他們是可逆的建設。

來源

2009-02-11 21:33:14 starblue

對於這組約束，實際上沒有解決方案。將32位無符號散列成32位無符號散列的嘗試會給你帶來衝突，除非你做了一件簡單的事情，比如1對1的映射。每個數字都是它自己的散列。

來源

2009-02-13 15:40:44 EvilTeach

尋找一個哈希函數/有序的Int/to/Shuffled Int/

回答

相關問題