algorithm - 哈希表加载因子 a 和 n 个槽，为冲突打开寻址

Question

我参加了高频交易面试，他们问我数据结构的所有数学方面的一个问题是：负载因子 a=1-1/(sqrt(n)logn)，搜索不成功的时间是多少？仅使用“n”陈述答案

Answer 1

随着增加，该术语1-1/(sqrt(n)*log(n))接近 1.0 。n当 时n==10，值为 0.9048。当 时n==1000000，值为 0.9999。（我正在使用对数基数 2。）

使用完整的哈希表（负载因子为 1.0 的含义）和开放式寻址，您必须检查每个项目。所以搜索不成功的时间是 O(n)。