gpt4 book ai didi

java - 更快的哈希函数

转载 作者:行者123 更新时间:2023-12-01 06:35:48 43 4
gpt4 key购买 nike

我正在尝试实现我自己的哈希函数,我使用 java 将每个字符串的 ASCII 数字相加。我通过查找哈希表的大小与总和的模来找到哈希码。大小%总和。我想知道在搜索字符串时是否有一种方法可以使用相同的过程但减少冲突?

提前致谢。

最佳答案

我会查看 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);
}

使用 &% 快得多,并且仅在长度为正时返回正数。

关于java - 更快的哈希函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13825546/

43 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com