Model

Linear probing: probes by load factor

The dial is load factor, and its cost curve is a hyperbola.

hit \approx \frac{1}{2} (1 + \frac{1}{1 - α}), miss or insert \approx \frac{1}{2} (1 + \frac{1}{( 1 - α ) ^{2}})

$α$: Load factor; the fraction of slots that are full

Recurring principle: Queues explode near full load

How it behaves

One input on the horizontal axis, the others held fixed.

hitmiss or insert

Data table

Expected probes by load factor
Load factor α	series	Expected probes
0	hit	1
0.012	hit	1.01
0.024	hit	1.01
0.036	hit	1.02
0.048	hit	1.02
0.059	hit	1.03
0.071	hit	1.04
0.083	hit	1.05
0.095	hit	1.05
0.107	hit	1.06
0.119	hit	1.07
0.131	hit	1.08
0.142	hit	1.08
0.154	hit	1.09
0.166	hit	1.1
0.178	hit	1.11
0.19	hit	1.12
0.202	hit	1.13
0.214	hit	1.14
0.226	hit	1.15
0.237	hit	1.16
0.249	hit	1.17
0.261	hit	1.18
0.273	hit	1.19
0.285	hit	1.2
0.297	hit	1.21
0.309	hit	1.22
0.321	hit	1.24
0.332	hit	1.25
0.344	hit	1.26
0.356	hit	1.28
0.368	hit	1.29
0.38	hit	1.31
0.392	hit	1.32
0.404	hit	1.34
0.416	hit	1.36
0.427	hit	1.37
0.439	hit	1.39
0.451	hit	1.41
0.463	hit	1.43
0.475	hit	1.45
0.487	hit	1.47
0.499	hit	1.5
0.511	hit	1.52
0.522	hit	1.55
0.534	hit	1.57
0.546	hit	1.6
0.558	hit	1.63
0.57	hit	1.66
0.582	hit	1.7
0.594	hit	1.73
0.606	hit	1.77
0.617	hit	1.81
0.629	hit	1.85
0.641	hit	1.89
0.653	hit	1.94
0.665	hit	1.99
0.677	hit	2.05
0.689	hit	2.11
0.701	hit	2.17
0.713	hit	2.24
0.724	hit	2.31
0.736	hit	2.4
0.748	hit	2.49
0.76	hit	2.58
0.772	hit	2.69
0.784	hit	2.81
0.796	hit	2.95
0.807	hit	3.1
0.819	hit	3.27
0.831	hit	3.46
0.843	hit	3.69
0.855	hit	3.95
0.867	hit	4.26
0.879	hit	4.62
0.891	hit	5.07
0.903	hit	5.63
0.914	hit	6.34
0.926	hit	7.28
0.938	hit	8.58
0.95	hit	10.5
0	miss or insert	1
0.012	miss or insert	1.01
0.024	miss or insert	1.02
0.036	miss or insert	1.04
0.048	miss or insert	1.05
0.059	miss or insert	1.07
0.071	miss or insert	1.08
0.083	miss or insert	1.09
0.095	miss or insert	1.11
0.107	miss or insert	1.13
0.119	miss or insert	1.14
0.131	miss or insert	1.16
0.142	miss or insert	1.18
0.154	miss or insert	1.2
0.166	miss or insert	1.22
0.178	miss or insert	1.24
0.19	miss or insert	1.26
0.202	miss or insert	1.28
0.214	miss or insert	1.31
0.226	miss or insert	1.33
0.237	miss or insert	1.36
0.249	miss or insert	1.39
0.261	miss or insert	1.42
0.273	miss or insert	1.45
0.285	miss or insert	1.48
0.297	miss or insert	1.51
0.309	miss or insert	1.55
0.321	miss or insert	1.58
0.332	miss or insert	1.62
0.344	miss or insert	1.66
0.356	miss or insert	1.71
0.368	miss or insert	1.75
0.38	miss or insert	1.8
0.392	miss or insert	1.85
0.404	miss or insert	1.91
0.416	miss or insert	1.96
0.427	miss or insert	2.03
0.439	miss or insert	2.09
0.451	miss or insert	2.16
0.463	miss or insert	2.23
0.475	miss or insert	2.31
0.487	miss or insert	2.4
0.499	miss or insert	2.49
0.511	miss or insert	2.59
0.522	miss or insert	2.69
0.534	miss or insert	2.81
0.546	miss or insert	2.93
0.558	miss or insert	3.06
0.57	miss or insert	3.2
0.582	miss or insert	3.36
0.594	miss or insert	3.53
0.606	miss or insert	3.71
0.617	miss or insert	3.92
0.629	miss or insert	4.14
0.641	miss or insert	4.38
0.653	miss or insert	4.66
0.665	miss or insert	4.96
0.677	miss or insert	5.29
0.689	miss or insert	5.66
0.701	miss or insert	6.08
0.713	miss or insert	6.55
0.724	miss or insert	7.08
0.736	miss or insert	7.69
0.748	miss or insert	8.38
0.76	miss or insert	9.18
0.772	miss or insert	10.1
0.784	miss or insert	11.2
0.796	miss or insert	12.5
0.807	miss or insert	14
0.819	miss or insert	15.8
0.831	miss or insert	18.1
0.843	miss or insert	20.8
0.855	miss or insert	24.3
0.867	miss or insert	28.7
0.879	miss or insert	34.5
0.891	miss or insert	42.3
0.903	miss or insert	53.1
0.914	miss or insert	68.7
0.926	miss or insert	92.4
0.938	miss or insert	131
0.95	miss or insert	200

Worked examples, recomputed

Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.

Where it appears

Each mechanism states it in its own names. The general symbol each name stands for is shown with it.

Core Data Structures
How do we choose a data structure when the real cost is set by the hardware, not by Big-O?
$\frac{1}{2} \times (1 + 1/ (1 - α)), \frac{1}{2} \times (1 + 1/ (1 - α)^{2})$
Read it in place →