Probability distribution of hash table lookup cost in Robin Hood hashing.

robin_hood.jl

LOAD_FACTOR = 0.909

PRECISION = 6000
N_LIMIT = 250

setprecision(512)

function psi(n, a::BigFloat)
	p = 1 / a - 1
	q = BigFloat(0)
	n = BigInt(n)
	for k in BigInt(PRECISION):-1:1
		q = e^-a * a / (k + n) * ((1 - k * a / (k + n + 1)) * k^(k + n) + q)
	end
	return p * q * a^n / factorial(BigInt(n))
end

a = BigFloat(LOAD_FACTOR)

values = map((n) -> psi(n, a), 1:N_LIMIT)
pr = map((n) -> sum(values[n:length(values)]), 1:N_LIMIT)

println("Pr_a sum = ", sum(values) + psi(0, a))
for i in 1:128
	println("Pr_a{displacement >= $i} = $(pr[i])")
end