5

我想对 SAS 哈希表中存储桶的定义做一点澄清。问题正是关于hashexp参数。

根据 SAS DOCs，hashexp是：

哈希对象的内部表大小，其中哈希表的大小为 2n。

HASHEXP 的值用作创建哈希表大小的二次幂指数。例如，HASHEXP 的值为 4 等于哈希表大小为 24 或 16。HASHEXP 的最大值为 20。

哈希表大小不等于可以存储的项目数。将哈希表想象成一个“桶”数组。大小为 16 的哈希表将有 16 个“桶”。每个桶可以容纳无限数量的项目。哈希表的效率在于哈希函数将项目映射到桶并从桶中检索项目的能力。

您应该根据散列对象中的数据量设置散列表大小，以最大限度地提高散列对象查找例程的效率。尝试不同的 HASHEXP 值，直到获得最佳结果。例如，如果哈希对象包含一百万个项目，那么大小为 16 (HASHEXP = 4) 的哈希表可以工作，但效率不高。大小为 512 或 1024（HASHEXP = 9 或 10）的哈希表会产生最佳性能。

问题是哈希表大小到底是什么，而不是哈希对象中的数据量？

是否应该将其理解为好像我们想分配尽可能多的内存，但不能少，不能更多。让事情快速运转是二的力量。但它并没有限制可能使用的数据量，它只是表明将要使用多少，对吧？

4

2 回答 2

6

Paul Dorfman（散列大师）在本白皮书的第 10 页详细介绍了一些细节：

http://www2.sas.com/proceedings/forum2008/037-2008.pdf

据我了解，哈希表将其数据存储在二叉树中。hashexp 创建的每个桶代表将用于存储数据的二叉树的数量。hashexp 为 0 将使用单个树，而 hashexp 为 8 将使用 256 棵树。当对散列对象执行查找时，内部算法会确定键应该存在于哪棵树中（基于散列值）。然后它检查该树的值。通过自动知道要查看 256 棵树中的哪棵（例如），与单个二叉树相比，它可以节省 8 次比较 (2^8)。

整个事情似乎比这复杂得多，但这就是我对为什么它运行得更快的解释。

于 2012-07-06T14:01:08.477 回答
3

正如 Rob Penridge 所指出的，Paul Dorfman 确实是 SAS 哈希对象大师。Hashexp 与哈希表的大小无关，正如 Rob 的回答中提到的那样。

如果您有一个包含 100obs 和 10 个数字变量的表被加载到哈希表中，那么哈希表的大小就是 100obs*10vars*8bytes（假设所有数字变量都存储为 8byte 字段） 7.8KB 给或取 10 %。

请记住，SAS 在将记录添加到内存中的哈希表时动态分配 RAM 空间，因此您无需提前指定它应该是什么大小。[我一直在定期使用哈希表，但想不出任何地方可以预先指定尺寸]。

一般提示：如果您想知道哈希表的大小，请在要加载到哈希表中的数据集上运行 PROC CONTENTS 并乘以“观察长度”和“数据集中的 obs 数量”，这将以字节为单位给出所需的内存大小。如果你有那么多内存，那么你可以将它加载到内存中。

于 2012-07-08T23:13:49.270 回答