整數散列函數與精度的字符串

我想散列一個字符數組到一個int或long。結果值必須遵守給定的精度值。我一直在使用的功能下面給出：整數散列函數與精度的字符串

int GetHash(const char* zKey, int iPrecision /*= 6*/) 
{ 
     /////FROM : http://courses.cs.vt.edu/~cs2604/spring02/Projects/4/elfhash.cpp 

     unsigned long h = 0; 
     long M = pow(10, iPrecision); 

     while(*zKey) 
     { 
       h = (h << 4) + *zKey++; 
       unsigned long g = h & 0xF0000000L; 
       if (g) h ^= g >> 24; 
       h &= ~g; 
     }    

     return (int) (h % M); 
}

被散列的字符串類似「SAEUI1210.00000010_1」。

但是，在某些情況下會產生重複值。是否有任何好的替代方案不會爲不同的字符串值重複相同的散列值。

來源

2009-06-18 Gayan

嘗試使用CRC 32：http://en.wikipedia.org/wiki/Crc32 – 2013-04-22 04:36:12

散列的定義是它會爲某些值生成重複值，這是由於散列值範圍小於散列數據的空間。

理論上，32位散列具有足夠的範圍來散列所有〜6個字符的字符串（A-Z，a-z，0-9），而不會導致衝突。在實踐中，哈希不是輸入的完美排列。給定一個32位散列，由於birthday paradox的原因，在散列〜16位隨機輸入之後，您可能會希望得到散列衝突。

給定一組靜態數據值，總是可以構造一個專門爲它們設計的散列函數，它永遠不會與自身發生衝突（當然，它的輸出大小至少爲log(|data set|)。但是，它需要你要提前瞭解所有可能的數據值。這就是所謂的perfect hashing。

話雖這麼說，here是應該讓你開始這幾個備選方案（他們的目的是儘量減少碰撞）

來源

2009-06-18 05:20:27 ASk

這是最好的散列函數，用於您提供的鏈接和我現在使用的鏈接中提供的散列函數。我使用的函數似乎比djb2和sdbm更復雜。這是否意味着避免碰撞更好？ – Gayan 2009-06-18 05:32:23

測試哪個哈希函數對您而言「最好」的唯一方法是對數據樣本執行基準，以便符合您的預期實際數據。您正在使用的函數不會嘗試將輸入位混合在一起，難以創建散列 - 在每個步驟中，最多混合4個最高位;並且在長度小於8的字符串中，即使這種情況不會發生，您的散列只會累積所有字符，並略微重疊。 – ASk 2009-06-18 12:19:17

每個散列都會有衝突。期。這就是所謂的Birthday Problem。

您可能想要檢查密碼具有像MD5一樣的功能（相對較快並且您不關心它不安全），但它也會產生衝突。

來源

2009-06-18 05:20:02 sharptooth

定義完美哈希不。 – MSalters 2009-06-18 10:56:54

哈希生成相同的不同輸入的值 - 這就是他們所做的，你所能做的就是創建一個具有足夠分佈的散列函數（或兩者）來最小化這些衝突。既然你有這個額外的精度約束（0-5？），那麼你將更頻繁地碰撞碰撞。

來源

2009-06-18 05:20:33 Talljoe

MD5或SHA。有很多開放的實現，結果是不太可能產生重複的結果。

來源

2009-06-18 05:29:10

整數散列函數與精度的字符串

回答

相關問題