Augmenter la taille d'une table de hachage, c'est un coût amorti de O(1), pour peu que tu utilises une progression géométrique.
C'est un coût amorti de O(1) que pour ceux qui considère que hasher une chaîne se fait en O(1). Moi je parlait d'un coût en O(l) pour une chaîne de taille l.
[^] # Re: Les vrais théoriciens s'en foutent
Posté par Batchyx . En réponse à la dépêche Le colonel Moutarde, sur la table (de hachage), avec un livre de maths. Évalué à 2.
C'est un coût amorti de O(1) que pour ceux qui considère que hasher une chaîne se fait en O(1). Moi je parlait d'un coût en O(l) pour une chaîne de taille l.