更快的散列函数

我想实现我自己的散列函数，我加起来每个字符串的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

更快的散列函数

回答

相关问题