生成一個字符串

一個唯一的整數（4個字節或8個字節）如果餘有由字符組成的字符串列表L（a到z和。）即總27個字符，並且每個串可具有最大尺寸爲256字節。我可以有一個散列函數，它會有0次碰撞（實際上，而不是理論上）？完美的散列函數將在這裏工作爲L可（即它不只是只讀）生成一個字符串

我感興趣的只是實用的東西修改。我知道無法生成0碰撞的散列函數。

我可以使用的md5sum但是這將產生一個16字節的整數。我只想查找4字節或最大8字節的整數。

可能嗎？

感謝您的耐心

〜GC〜

來源

2011-06-29 kartik

由於2^64小於27^256，所以*不能*具有*實際上*沒有碰撞的散列函數。雖然你需要散列函數的隨機性嗎？ –

一個解決方案：只需使用如MD5一個已知的哈希函數，並使用最低的4首或8個字節。

來源

2011-06-29 06:59:05 Mehrdad

其實無論最低還是最高還是中間還是哪個都沒關係。例如。 git使用SHA1散列的十六進制表示的起始部分，如果散列實際上被編寫爲數字，則將是高部分。 –

@Jan：是的，對於像SHA/MD5/etc這樣的好東西來說應該沒什麼問題，因此我爲什麼說* one *而不是*解*。 ;） – Mehrdad

某種校驗或哈希的是正確答案。

你是對的，你不能避免碰撞。但是，如果您將校驗和或散列值縮短到只有4個字節，那麼碰撞頻率將大大增加。

如果那也沒關係，你可以看看像http://en.wikipedia.org/wiki/Hash_function找到一個你覺得舒服。

來源

2011-06-29 07:00:57

Git使用SHA1哈希來標識所有對象並將它們縮短爲唯一的前綴。大多數情況下，7個十六進制數字是3.5個字節，所以4個字節在實踐中可能會很好。 –

其他人提出正確的解決方案（使用散列總和）了，但如果你在有儘可能少的衝突儘可能真正感興趣，這裏有兩個想法，考慮在較大規模的問題：

如果您持有一些（或全部）要爲內存中的ID生成的字符串，可以使用該字符串存儲的內存地址作爲ID。假設在原地更改字符串是可以的，這個ID甚至可以在字符串更改時保持穩定。
使用一些簡單的壓縮系統（例如miniLZO）將列表中的字符串壓縮爲某些內部表示可能是實用的。你可能會得到更少的散列數據，所以更簡單的散列函數可能是可能的。當然，這樣計算哈希值會更加昂貴，但是您可能能夠避免衝突。

來源

2011-06-29 07:27:31

由於您的數據是有限的，您可以使用它來指導哈希。

假設字符串是空終止的ASCII，你可以通過映射開始小整數。

char *charset = "abcdefghijklm" 
       "nopqrstuvwxyz."; 
int c = strchr(charset, *s++) - charset;

然後，將每個值作爲基數爲27的基數。在將當前字符加入0-26「單位」之前，將總和乘以27進行解碼。你提到最大長度。我猜這意味着字符串存儲在固定長度的數組中。如果是這樣，並且數組不僅僅是終止而是填充。那麼您可以將陣列向後解碼，以將基數27號碼的最低有效位置置於顯着差異。但是，如果大小隻是一個慷慨的高估，大部分字符串預計會更短，那麼最好是向前掃描並終止nul。

int sum; 
sum *= 27; 
sum += c;

來源

2011-06-29 07:44:36

27 ** 256比64位大得多...您的算法基本上忽略了前14個字節。 –

@Jim，老鼠！你是對的。也許某種循環移位比乘法更好。 –

生成一個字符串

回答

相關問題