Some properties of the scatter storage technique with linear probing
J. Kral · The Computer Journal · 1971
Let M(n, k) be (for a scatter storage technique) the average number of probes necessary to find an item in a table T of length n containing k items. Some identities allowing us to compute M(n, k) for the scatter storage technique with linear probing for various n and k are given. From the behaviour of M(n, k), as asymptotical formula given in Morris (1968) follows. For n ≧1,024 and k/n ≦ 0·8 the values of M(n, k) are practically equal to the corresponding asymptotical values. A comparison with some other scatter storage methods is made. It is shown that in may cases the linear probing method is the best one.