更快的散列函數

我想實現我自己的散列函數，我加起來每個字符串的ASCII碼，使用java。我通過查找散列表大小的模和總和來找到散列碼。大小％之和。我想知道在搜索字符串時是否有一種方法可以使用相同的過程，但可以減少衝突？更快的散列函數

在此先感謝。

來源

2012-12-11 Marcello

所以你試圖使String hashcode功能比標準功能更快？我讀了這個嗎？如果是的話，你對這個功能有什麼要求？ –

你的問題太模糊，無法回答。什麼是「每個字符串的統一碼」？你乘以2的指數是多少？你從哪裏讀到的？ – assylias

這裏沒有足夠的上下文，但我從來沒有見過「將索引乘以2 [..]使得哈希函數更快」。在提出此類索賠時，*請提供參考資料*。 – 2012-12-11 17:40:32

我會看看String和HashMap的代碼，因爲它們的衝突率很低，並且不使用%並處理負數。

從源字符串

public int hashCode() { 
    int h = hash; 
    if (h == 0 && value.length > 0) { 
     char val[] = value; 

     for (int i = 0; i < value.length; i++) { 
      h = 31 * h + val[i]; 
     } 
     hash = h; 
    } 
    return h; 
}

爲從源頭HashMap的

/** 
* Retrieve object hash code and applies a supplemental hash function to the 
* result hash, which defends against poor quality hash functions. This is 
* critical because HashMap uses power-of-two length hash tables, that 
* otherwise encounter collisions for hashCodes that do not differ 
* in lower bits. Note: Null keys always map to hash 0, thus index 0. 
*/ 
final int hash(Object k) { 
    int h = 0; 
    if (useAltHashing) { 
     if (k instanceof String) { 
      return sun.misc.Hashing.stringHash32((String) k); 
     } 
     h = hashSeed; 
    } 

    h ^= k.hashCode(); 

    // This function ensures that hashCodes that differ only by 
    // constant multiples at each bit position have a bounded 
    // number of collisions (approximately 8 at default load factor). 
    h ^= (h >>> 20)^(h >>> 12); 
    return h^(h >>> 7)^(h >>> 4); 
}

由於HashMap的是總是2的功率大小，你可以使用

 hash = (null != key) ? hash(key) : 0; 
     bucketIndex = indexFor(hash, table.length);

和

/** 
* Returns index for hash code h. 
*/ 
static int indexFor(int h, int length) { 
    return h & (length-1); 
}

使用&比%快得多，並且僅返回正數，因爲長度爲正數。

來源

2012-12-11 18:05:36

如果我要將總和乘以128，它會減少衝突，但爲什麼數字（如128和37）會造成差異 – Marcello

乘以數字就會混合數字併爲您提供不同的模式。通常素數是一個好主意，因爲這些數字不太可能自然出現，並且在沒有數字時創建模式。乘以128並不是一個好主意，因爲您的最低7位始終爲零，從而有效降低散列值的「隨機性」。 –

Java String.hashcode()在做一個非常好的散列函數和儘可能高效之間進行權衡。簡單地將一個字符串中的字符值相加並不是一個可靠的散列函數。

例如，考慮兩個字符串dog和god。由於它們都包含'd'，'g'和'o'，因此只有加法的方法纔會產生不同的哈希碼。

Joshua Bloch誰實現了Java的一大部分，在他的書Effective Java中討論了String.hashCode（）方法，並討論了在1.3之前的Java版本中，如何使用String.hashCode（）函數僅考慮給定字符串中的16個字符。這比當前的實施運行速度稍快，但是在某些情況下導致性能很差。一般來說，如果你的特定數據集是非常明確的，你可以利用它的一些獨特性，你可能會做出更好的散列函數。對於通用字符串，祝你好運。

來源

2012-12-11 17:57:02 utopianheaven

更快的散列函數

回答

相關問題