问使用外部链接插入哈希表的时间性能
EN

Stack Overflow用户

提问于 2017-07-04 19:58:42

回答 1查看 50关注 0票数 0

假设我要使用外部链接将一个新元素插入到哈希表中。如果表格正在调整大小，我知道插入操作的时间是θ1。

但是，我不明白为什么当存储桶大小固定时，性能会有所不同。它不是应该插入到链表中吗，链表也是大的θ1？

这是来自CS61B @UCB的幻灯片。

发布于 2018-04-25 00:42:00

“固定大小”与“调整大小”是指存储桶的数量，而不是每个单独存储桶的大小。

我们的想法是，如果我们有固定数量的存储桶，假设是k存储桶，我们将n元素插入到哈希表中，然后使用具有完美扩散的哈希函数，每个存储桶将包含k/n元素。

由于查找存储桶中的所有项需要使用O(k/n)，而k只是一个常量，因为它是固定的，所以我们的查找时间是O(n)。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/44905420

复制

相似问题

问使用外部链接插入哈希表的时间性能EN