相关疑难解决方法(0)

很久以前,我以1.25美元的价格从交易台上买了一本数据结构书.在其中,哈希函数的解释说,由于"数学的本质",它最终应该由质数修改.

你对1.25美元的书有什么期望？

无论如何,我有多年的时间来思考数学的本质,但仍然无法弄明白.

当存在大量的桶时,数字的分布是否真的更均匀？或者这是一个老程序员的故事,每个人都接受,因为其他人都接受它？

我已经对哈希表进行了一些研究,并且我一直遵循经验法则,当有一定数量的条目(最大或通过75%的加载因子)时,应该扩展哈希表.

几乎总是,建议是将哈希表的大小加倍(或加倍加1,即2n + 1).但是,我没有找到一个很好的理由.

为什么要加倍大小,而不是将其增加25%,或者将其增加到下一个素数或下一个素数(例如三个)？

我已经知道,选择一个初始哈希表大小是一个素数通常是一个好主意,至少如果你的哈希函数使用模数,如通用哈希.我知道这就是为什么通常建议做2n + 1而不是2n(例如,http://www.concentric.net/~Ttwang/tech/hashsize.htm)

然而正如我所说,我没有看到任何真正的解释,为什么加倍或加倍加一个实际上是一个很好的选择,而不是选择新哈希表的大小的其他方法.

(是的,我已经阅读了关于哈希表的维基百科文章:) http://en.wikipedia.org/wiki/Hash_table

当垃圾收集器运行并释放内存时,此内存会返回到操作系统,或者它是否作为进程的一部分保留.我的印象是,内存从未实际发布回操作系统,而是作为内存区/池的一部分保留,以便由同一进程重用.

结果,进程的实际内存永远不会减少.一篇提醒我的文章是这篇文章和Java的Runtime是用C/C++编写的,所以我想同样的事情适用于此？

更新
我的问题是关于Java.我提到C/C++,因为我假设Java的分配/解除分配是由JRE使用某种形式的malloc/delete完成的

几乎每本教科书和 CS 课程中都引用了两种实现哈希函数的基本方法：

1. 除法方法，我们只是简单地k mod m选择 m 作为素数，不太接近 2 的幂。
2. 乘法方法，我们将 k 与一些精心挑选的无理数（Knuth 建议使用基于黄金比例的数字）相乘，介于 0 到 1 之间，取乘积的小数部分并使用所需的最高有效位数。

大多数教科书和课程都引用了方法 1 的几个缺点，包括它很昂贵并且事情取决于 m。但是，我从未见过任何教科书或课程提到方法 2 的单一缺点。

这使得方法 2 更可取。此外，方法 2 在现代计算机上可以非常有效地消除浮点运算。所以看起来方法 2 是绝对的赢家，没有人应该谈论方法 1。但显然情况并非如此。事实上，我从未见过在任何实际实现中使用方法 2。所以它确实有一些缺点。

问题是它们是什么，为什么尽管方法 1 有缺点，但为什么会更频繁地使用它？