相关疑难解决方法(0)

在.NET GetHashCode方法中,很多地方都使用.NET 方法.特别是在快速查找集合中的项目或确定相等性时.是否有关于如何GetHashCode为我的自定义类实现覆盖的标准算法/最佳实践,因此我不会降低性能？

每Java文档中,哈希代码的String对象被计算为:

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

Run Code Online (Sandbox Code Playgroud)

使用int算术,其中s[i]是 字符串的第i个字符,是字符串n的长度,并^指示取幂.

为什么31用作乘数？

我知道乘数应该是一个相对较大的素数.那么为什么不是29岁,37岁,甚至97岁？

作为非密码学家,有一件事总是让我感到震惊:为什么使用Prime数字这么重要？是什么让他们在密码学方面如此特别？

有没有人有简单的简短解释？(我知道有许多引物,应用密码学是圣经,但正如所说的:我不打算实施我自己的加密算法,我发现的东西只是让我的大脑爆炸 - 没有10页的数学公式请 :))

谢谢你的所有答案.我已经接受了让我对这个实际概念最清楚的那个.

我只是想知道为什么在类的hashCode()方法中使用素数？例如,当使用Eclipse生成我的hashCode()方法时,总会使用素数31:

public int hashCode() {
     final int prime = 31;
     //...
}

参考文献:

这是关于Hashcode的一篇很好的入门文章和关于我如何找到哈希工作的文章(C#但概念是可转移的): Eric Lippert的GetHashCode指南和规则()

什么整数散列函数是好的,接受整数散列键？

Eclipse 3.5有一个非常好的功能来生成Java hashCode()函数.它会产生例如(稍微缩短:)

class HashTest {
    int i;
    int j;        
    public int hashCode() {
        final int prime = 31;
        int result = prime + i;
        result = prime * result + j;
        return result;
    }
}

(如果类中有更多属性,result = prime * result + attribute.hashCode();则对每个附加属性重复.对于int.可以省略.hashCode().)

这似乎很好,但选择31为素数.它可能来自Java String的hashCode实现,它被用于性能原因,这些原因在引入硬件乘法器之后很久就消失了.对于i和j的小值,这里有许多哈希码冲突:例如(0,0)和(-1,31)具有相同的值.我认为这是一个Bad Thing(TM),因为经常出现小值.对于String.hashCode,您还会发现许多具有相同哈希码的短字符串,例如"Ca"和"DB".如果选择大素数,如果选择素数,此问题就会消失.

所以我的问题是:选择什么是好的素数？你用什么标准来找到它？

这是一个普遍的问题 - 所以我不想给i和j一个范围.但我认为在大多数应用中,相对较小的值比较大的值更常出现.(如果你有大的值,素数的选择可能不重要.)它可能没有多大区别,但更好的选择是一种简单明了的方法来改善这一点 - 那么为什么不这样做呢？Commons lang HashCodeBuilder也提出了奇怪的小值.

(澄清:这不是重复为什么String中的Java的hashCode()使用31作为乘数？因为我的问题不关心JDK中31的历史,而是关于新代码中更好的值使用相同的基本模板.没有任何答案试图回答.)

假设简单的统一散列,即任何给定值同样地散列到散列的任何槽中.为什么使用大小为127而不是128的表更好？我真的不明白2号码的力量有什么问题.或者它实际上如何产生任何差异.

使用除法时,我们通常会避免使用某些m值(表大小).例如,m不应该是2的幂,因为如果m = 2 ^ p,则h(k)只是k的p个最低位.

假设可能的元素只在1和10000之间,我选择表格大小为128. 127如何才能更好？所以128是2 ^ 6(1000000),127是0111111.这有什么区别？所有数字(当经过哈希处理时)仍然是127的p的最低位数.我弄错了吗？

我正在寻找一些例子,因为我真的不明白为什么这么糟糕.非常感谢提前!

PS:我知道: 哈希表:为什么大小应该是素数？

我正在使用一个使用大量字典(最多10 ^ 6个元素)的应用程序,其大小事先未知(尽管我可以在某些情况下猜测).我想知道字典是如何实现的,即如果我不对字典大小进行初步估计,效果有多糟糕.它是否在内部以List的方式使用(自增长)数组？在这种情况下,让字典增长可能会在LOH上留下许多大的未引用数组.

可能重复:
为什么散列函数应使用素数模数？

为什么哈希表(数据结构)大小必须是素数？

据我所知,它确保了更均匀的分布,但还有其他原因吗？

当我点击这段时,我正在阅读Eric Lippert 关于GetHashCode指南和规则的最新博客帖子:

我们在这里可能更聪明; 就像List在它满了时调整自身大小一样,bucket set也可以自行调整大小,以确保平均bucket长度保持低位.此外,由于技术原因,通常最好将存储桶设置长度设为素数,而不是100.我们可以对此哈希表进行大量改进.但是这个哈希表的简单实现的快速草图现在可以做到.我想保持简单.

所以看起来我错过了一些东西.为什么将它设置为素数是一个好习惯？