Okay, Nate, you asked for this....
"have done" is the present perfect tense of the verb "do". "should" indicates modality, and this particular mood requires the verb that it modifies to be in present tense, either imperfect the "do" or the perfect "have done". English is confusing in this regard because, although "have done" is two words, it is actually a single verb, and that verb's modality is affected by the preceding "should".
This confusion is compounded when English speakers create a contraction that involves only one word of the verb cluster. "should've" is formed when the weak "h" sound is entirely dropped, the the "a" is destressed to a shwa (represented by the upside-down "e", sounds like "uh") making something like "shood'uhv".
The problem after this is that some kids grow up saying "should've" and are never told that it is a contraction for "should have". When they have to write it down, they write it like it sounds, and it sounds like "should of", which makes no grammatical sense. This is the reason, in my opinion, for a lot of spelling and grammatical errors - people pronounce things incorrectly, and then try to write it as they say it.
Sorry, Nate, but you asked for that.
---
This signature has performed an illegal operation and has been shut down.