线性散列复杂性

Question

我正在浏览Wiki上的线性散列文章。有一句话让我迷惑不解：“哈希表扩展的成本分散在每个哈希表插入操作中，而不是一次性发生。2”

在线性散列的情况下，如果要插入的项的散列值小于拆分变量，则创建新的节点(或桶)，并根据上面的行在that.And中插入值(时间复杂性是在每个“插入操作”上测量的，如果与我们进行分期分析的“动态数组”实现相比，线性散列中的插入必须花费O(n)时间。如果我错了，请纠正我。还有一件事: wiki上的第二行写着“线性散列因此非常适合交互式应用。”

我可以在“交互式情况”中将B+树与线性散列进行比较吗(因为两者都是可扩展的搜索技术)？

Answer 1

据我所知，O(n)是最差的时间复杂度，但在大多数情况下，哈希表将以固定的时间返回结果，这是O(1)。与必须遍历树的B+树相反，哈希表适用于哈希函数，其中哈希函数的结果指向存储值的地址。在最坏的情况下，如果所有的键都有相同的散列结果，那么时间复杂度可能会变成O(n)，因为所有的结果都将存储在一个存储桶中。

根据维基百科的说法，b+ tree的时间复杂度如下。

插入记录需要O(logbn)运算查找记录需要O(logbn)运算

Answer 2

LH实现可以保证严格限定的插入时间。如果冲突是由溢出处理的，那么拆分位置和键散列位置就没有理由相关。诀窍是将创建溢出槽链接到拆分操作。

例如，如果每隔N个插槽总是被保留为溢出插槽，那么您需要执行至多N-1个拆分来创建新的溢出插槽。在实践中，它少于(N-1)个/2拆分，因为拆分一个插槽可以释放一个溢出插槽。

描述为http://goo.gl/6dbuH，源代码为https://github.com/mischasan/hx。