hashtable - hashexp 指定的 SAS HashTable 中的表大小究竟是多少？

Question

我想对 SAS 哈希表中存储桶的定义进行一些说明。问题正是关于 hashexp 参数。

根据 SAS DOC，hashexp 是:

hash对象的内表大小，其中hash表的大小为2n。

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

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

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

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

是否应该理解为我们想要分配尽可能多的内存，但不是更少，不是更多。使事情快速进行是两个的幂。但是它并没有限制可能使用的数据量，它只是表明将要使用多少，对吗？

Answer 1

Paul Dorfman(散列大师)在本白皮书的第 10 页详细介绍了以下内容:

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

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

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