I thought everyone knew about tinyurl
Sorry, woulda told you before!
I think it just stores the url, and assigns a short "hash" (but really just random number) to it, and passes it on whever it is called. I suppose that after a while, either they will run out of short url's, or will recycle ones that haven't been called for a month or so... This is what I would do anyway, obviously I have no idea, I'm just guessing
Edit - Turns out they never expire (according to the homepage), so I guess its a non-expiring hashmap type object