La statistique des alvéoles

import random

m = 1000
n = 1000
longueurs = [0] * m

# Simulation de l'insertion de n clés distribuées au hasard
for _ in range(n):
    indice_aleatoire = random.randrange(m)
    longueurs[indice_aleatoire] += 1

# Statistiques
nb_vides = longueurs.count(0)
proport_vides = nb_vides / m
alv_occupees = [l for l in longueurs if l > 0]
moyenne_non_vides = sum(alv_occupees) / len(alv_occupees)
longueur_max = max(longueurs)

print(f"Proportion d'alvéoles vides : {proport_vides * 100:.2f}%")
print(f"Longueur moyenne des chaînes non vides : {moyenne_non_vides:.2f}")
print(f"Longueur maximale observée : {longueur_max}")

Analyses et interprétations :

• La proportion d'alvéoles vides mesurée tourne autour de $36,8\%$. C'est en parfait accord avec la théorie de la distribution de Poisson et la limite $(1-1/m{)}^n\approx e^{-1}\approx 0,3678$.
• La longueur moyenne des chaînes non vides est d'environ $1,58$. Ainsi, l'accès moyen à une clé ne demande qu'à peine plus d'une comparaison.
• La longueur maximale oscille généralement entre $5$ et $7$. Même pour les éléments les moins bien répartis, la recherche reste extrêmement rapide.