How Does The Google URL Shortener Generate A 5 Digit Hash Without Collisions

They have a database which tracks all previously generated URLs and the longer URL that each of those maps to. Easy to make sure that newly generated URLs don't already exist in that table. A little tricky to scale out (they surely have multiple servers so each one needs to be assigned a bucket of values from which it can give out to users). If they ever reach the point of having generated 916,132,832 URLs, they'll just add another character.

They have a hash table with hash to url.

Count the number of rows in that table and encrypt it with a stream cipher then encode with base62.

Using a stream cipher instead of a hash will give you a short pseudo random output that doesn't collide with any previous output so you don't need to check the table.