For a user's active login, clearly it's best to use the slowest algorithm possible with the least collisions possible in order to prevent an attacker from signing in as another user.
When it comes to storing password history, the main concern is protecting the plaintext of the user's old password because they may still use it in other places or use a similar password as their current.
I'm thinking that a truncated MD5 or CRC hash would allow the system to check password history, albeit with occasional false positives (the user can just think of something else), but make them impossible* to reverse. When I say impossible, I mean that there would be colliding plaintexts by design and those would be indiscernible from the plaintext of the original password chosen by the user.
If password history must be maintained, is this a practical approach?
An attacker could search through those collisions looking for which password was most likely human input - perhaps looking for dictionary words or "1234" type suffixes.
With high enough collisions would that kind of narrowing be impractical? Maybe hash half of their password?
Would too many collisions from password history disallow too many new passwords?