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.
Ca ne change rien : si tu considères que hasher une chaîne se fait en O(l), le coût amorti est en O(l).
Mais rééquilibrer ton arbre se fait aussi en O(l log n) : il faut bien comparer ton élément, non ? (même si la comparaison est en O(l) dans le pire cas alors que le hash est en O(l) dans tous les cas, c'est pareil).
Et ce serait pareil avec un trie, tu auras toujours ce facteur O(l), étant donné que la comparaison/égalité est en O(l).
Ensuite, par exemple dans CPython, les hashs des objets immutables (string, bytes...) sont stockés avec l'objet, donc tu ne passes pas ton temps à les recalculer.
[^] # Re: Les vrais théoriciens s'en foutent
Posté par neologix . En réponse à la dépêche Le colonel Moutarde, sur la table (de hachage), avec un livre de maths. Évalué à 4.
Ca ne change rien : si tu considères que hasher une chaîne se fait en O(l), le coût amorti est en O(l).
Mais rééquilibrer ton arbre se fait aussi en O(l log n) : il faut bien comparer ton élément, non ? (même si la comparaison est en O(l) dans le pire cas alors que le hash est en O(l) dans tous les cas, c'est pareil).
Et ce serait pareil avec un trie, tu auras toujours ce facteur O(l), étant donné que la comparaison/égalité est en O(l).
Ensuite, par exemple dans CPython, les hashs des objets immutables (string, bytes...) sont stockés avec l'objet, donc tu ne passes pas ton temps à les recalculer.