如何设计一个可精确扩展到n个元素的哈希函数?

不足以知道 n . 将项目分配到bucket是项目本身的函数,因此,如果您想要一个完美的哈希函数(每个bucket一个项目),您需要知道数据。

在任何情况下,如果将元素的数量限制为已知的 n 你已经在技术上找到了。上限将基于常量 n . 即使对于非哈希解决方案,这也是正确的。

您最好的选择是使用您拥有的散列函数,并让每个bucket都成为冲突项的链接列表。即使哈希不够完美,您仍然可以大大减少所用的时间。

只有当哈希完全不完美时(全部 n 元素放在一个桶中)它会和普通的链接列表一样坏吗?

如果您不提前知道数据,则不可能实现完美的哈希。当然,除非你用 h 作为哈希键而不是 h%n 但这将占用大量的存储空间:—)

我的建议是使用链表路由进行足够好的散列。我不怀疑你能根据人们名字中字母在整个人群中的相对频率来建立一个更好的哈希函数,但是即使你拥有的哈希(这对于所有具有相同频率的字母都是理想的)也足够了。

而且,不管怎样,如果你开始依赖频率,你会得到来自那些似乎不使用元音的国家(一个波斯尼亚 ^一 ,最后会发生更多的碰撞。

但要记住,这真的取决于 n 你正在使用的。

如果 n 如果足够小,您甚至可以通过连续搜索未排序的数组来逃脱惩罚。我假设你 n 这里足够大,您已经确定(或平衡二叉树)不会给您足够的性能。

一个很好的例子:我们有一些代码可以在问题摘要中搜索留下评论的人的名字(这样我们就可以在团队中建立最后一个响应的成员)。我们团队中只有大约10名成员,所以我们只需要对他们进行顺序搜索——使用更快的数据结构来提高性能被认为是太麻烦了。

^一 无意冒犯。我只记得很久以前那篇幽默的文章,关于克林顿授权空运元音到波斯尼亚。我相信还有其他国家也有类似的“问题”。

你所追求的被称为 完美散列 . 它是一个散列函数,所有的键都是提前知道的,其设计目的是不发生冲突。

这个 gperf 程序生成C代码以实现完美的哈希。

听起来您正在寻找 perfect hash function 或者甚至是最小的完美散列函数。根据维基百科的网页, CMPH 可以 满足您的需求。免责声明:我从未使用过。

映射优化算法 n 字符串到整数 1 - n 是在终止状态为整数的情况下构建DFA 一 - n . (我敢肯定这里有人会用一个花哨的名字来形容这个……但最后都是dfa。)大小/速度的权衡可以通过改变字母大小(操作字节、半字节,甚至是位)来调整。