哈希表上线性探测的运行时间 [英] Run Time for Linear Probing on Hash table

问题描述

进行插入，删除和搜索的线性探测的运行时间(大哦).

what is the running time (big Oh) for linear probing on insertion, deletion and searching.

谢谢

推荐答案

理论上最差的情况是O(n)，因为如果碰巧插入所有元素使其连续发生碰撞，则必须将最后插入的元素放入表n从其原始哈希位置开始移动.

Theoretical worst case is O(n) since if you happen to insert all the elements such that they consecutively collide then the last element inserted will have to be put into the table n steps from its original hash position.

但是，如果您知道输入元素的分布(可能假设是随机的，但当然是母亲……)，知道哈希函数的分布(希望是均匀的，但这取决于算法的质量)，哈希表的长度和插入的元素数.

You could however calculate the average expected number of steps if you know the distribution of your input elements (possibly assuming random, but of course assumption is the mother...), know the distribution of your hashing function (hopefully uniform, but it depends on the quality of your algorithm), the length of your hash table and the number of elements inserted.

如果您的哈希函数足够统一，则可以使用生日问题来计算冲突的概率，并从这些概率中计算出预期的探测长度.

If your hashing function is sufficiently uniform you can calculate the probability of collisions using the birthday problem and from those probabilities calculate expected probing lengths.

这篇关于哈希表上线性探测的运行时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！