Pollux (./50) :

PpHd (./49) :
Ben j'optimise pas du tout l'insertion d'un nouvel élément dans une somme.

A moins que ça soit trop compliqué ce serait pas rentable d'optimiser pour simplifier l'API ? (et accélérer par la même occasion les programmes qui n'ont pas été écrits de la façon la plus optimisée)

Ce n'est pas si simple. Je pourrais enlever le facteur log(n) mais pas le facteur n^2 (donc intérêt très limité) dans le pire cas.
Car dans add(add(add(add()))) à chaque étape il faut réallouer un nouvel espace de taille + 1 pour stocker la nouvelle chaine et recalculer son hash.
Par exemple, dans le cas où on ajoute un identifieur unique à chaque étape, on obtient N^2 de complexité.

add_c(add_c(add_c... est en N*ln(N) car chaque construction ne réalloue pas toute la chaine (pas besoin de calculer les hash intermédiares des sommes).

Mais c'est vraiment le seul cas pratique, où il y a une réelle différence de performance à utiliser add_c.