Re: Sigh ...
you can't just keep the last N hashes, if someone decides that your passwords have to be dissimilar then there is no way to test for this. The has for password1 is completely different to the hash for password2 so there is no way to tell from the hashes that the user has just changed the number on the end of the password.
An alternative, hash the password, store that and use that for authentication. At the same time, encrypt a file with that password which stores that, and previous passwords.
At the time of password change, the user must authenticate with the current one, so you'll be able to use that password to decrypt the old password blob and see what was used before. If the new password is good enough, add in the old password to the decrypted blob and encrypt it with the new one.
If someone steals the blob, they'll have to figure out the salted hash before they can get at old passwords.
Also some systems, banks for example, ask you to enter the 3rd and 7th characters of your password. Again this isn't possible with a one way hash unless you hash each character individually and then rainbow tables are going to be pretty quick to construct.
Don't know about you, but my memory for passwords works like a linked-list. I call it "muscle memory", and it can only be traversed in one direction from start to finish, not indexed like an array or iterated in reverse. So I wouldn't have the foggiest clue what was the 12th character or the 6th.
So this means of "protection" will only help those who have written down passwords. A behaviour the IT industry has been trying to discourage for a long time.
That said, nothing stops you from picking select characters at random, and storing those separately, if you really want to make your users suffer in this manner.