What's the best way to generate a short hash string from a longer string

Question

I'm trying to create short non-colliding strings from longer strings in Ruby. What's the best way to do this? Base64 encode a MD5 hash?

This is the use case:

loop do
  key = short_hash("#{user_id}-#{timestamp}")
  break if $redis.setnx(key, "0")
end

I don't want key to be too long.

Answer 1

I often use a SHA has for this similar to the example you have. It's not guaranteed to be unique, but is usually good enough for most purposes:

require 'digest/sha1'
Digest::SHA1.hexdigest("#{user_id}-#{Time.now.to_i}-#{rand}")

The ruby UUID gem is another option.

But in your specific case since you're using redis, why not just use the redis INCR command? Then you can guarantee the uniqueness at least within your database. For example:

unique_key = $redis.incr('users:next')

Answer 2

You can use a hash function to create shorter strings that aren't likely to collide. However, the Pigeonhole principle guarantees that you will be able to find two longer strings that will hash to the same value.

To generate truly unique values, you may have to assign a sequential identification number. But this would also require that you keep track of which identification number you have associated with which input string.