Creating a Short Url Hash


I was a bit bored today and thought about creating a simple hash to create Tiny URL type endings. This is largely led by a multiple blog idea I am toying with. I wanted to be able to make my own TinyUrl. Initially, I was going to set up a TinyURL library, but this was a bit of fun.

Essentially, what I am doing is creating a Base62 converter. I found some algorithms on the web, but they were a bit too long or used VB training wheels libraries, so I had to pitch them. Great for research however. Playing around a bit, I came up with this idea.

Converting to AlphaNumeric “hash”

To convert to Base62, the easiest way is to set up a base 62 string and start poking at it. The string looks something like this:

private readonly string startingBaseString = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

To convert to base62 is fairly easy.

  1. Create a empting working string
  2. If number = 0, then return “0”, else reduce number until it hits 0
  3. Get the modulus of the number divided by 62 and find the value in the string
  4. Append this to the front of the string

The routine looks like this:

public string ConvertToBase(long num)
{
    string working = string.Empty;

    if (num != 0)
    {
        while (num > 0)
        {
            int modulo = (int)num % 62;
            working = startingBaseString.Substring(modulo, 1) + working;
            num /= 62;
        }
    }
    else
        working = "0";

    return working;
}

After playing a bit, I wanted to make this a bit more useful, so I threw in the ability to convert to other bases (and even change the base string you use). the coverted code starts with the constructor. For a simple, vary the base string, I have the following:

private string baseChars;
private int numberBase;

public BaseConverter(int numBase)
{
    if (numberBase > 62)
        throw new ApplicationException("Can only go to base 62");

    baseChars = base62String.Substring(0, numBase);
    numberBase = numBase;
}

But what if you want to change the order of the numbers so you can have alphabetic characters first or only alpha characters. You could do this:

public BaseConverter(int numBase, string charString)
{
    if (charString.Length < numBase)
        throw new ApplicationException(
       
"You must have at least as many characters in your string as the base you are converting to.");

    startingBaseString = charString;

    baseChars = base62String.Substring(0, numBase);
    numberBase = numBase;
}

Now we have a refactor, as there is the code smell of duplicate code. Right click in Visual Studio and choose Refactor and Extract method on the last two lines. The result is this:

private string baseChars;
private int numberBase;

public BaseConverter(int numBase)
{
    if (numberBase > 62)
        throw new ApplicationException("Can only go to base 62");

    LoadConverter(numBase);
}

public BaseConverter(int numBase, string charString)
{
    if (charString.Length < numBase)
        throw new ApplicationException("You must have at least as many characters in your string as the base you are converting to.");

    startingBaseString = charString;

    LoadConverter(numBase);
}

private void LoadConverter(int numBase)
{
    baseChars = startingBaseString.Substring(0, numBase);
    numberBase = numBase;
}

But we should have a Base62 default constructor. This can be coded by chaining the default constructor, like so:

public BaseConverter()
    : this(62)
{
}

Now we can alter the converter to allow any base.

public string ConvertToBase(long num)
{
    string working = string.Empty;

    if (num != 0)
    {
        while (num > 0)
        {
            int modulo = (int)num % numberBase;
            working = baseChars.Substring(modulo, 1) + working;
            num /= numberBase;
        }
    }
    else
        working = "0";

    return working;
}

Pretty cool so far. Now let’s get back numbers from a string.

Converting From Base62

To return back to a number is a bit more complex (a few more lines of code). It follows this logic:

  1. Create a character array of the string
  2. Get the length of this array
  3. Loop through the array and do the following
    1. Create a Regex class with the current working value
    2. Search the Base 62 string for the Regex value
    3. Take the index of the match and multiply it by 62 to the power of (hashLength minus 1) minus the loop value
    4. Add to your return value

I am fairly certain there is some way to simplify this even farther, but here it is:

public long FromBase62(string hash)
{
    char[] hashChars = hash.ToCharArray();
    int hashLength = hashChars.Length;
    long returnValue = 0;

    for (int i = 0; i < hashLength; i++)
    {
        char working = hashChars[i];
        Regex regex = new Regex(working.ToString());
        Match match = regex.Match(baseChars);
        double multipland = Math.Pow(numberBase, (hashLength – 1) – i);
        returnValue += (long)(match.Index * multipland);
    }

    return returnValue;
}

The final step is using the library.

Blogging with the Hash

To get a number from the converter, you can use any of the following constructors:

BaseConverter converter = new BaseConverter();
BaseConverter converter2 = new BaseConverter(32);
BaseConverter converter3 = new BaseConverter(52, "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz");

You then take the number you want to convert and use ConvertToBase. Here is a little test to ensure the algorithm is working correctly:

[TestMethod]
public void should_convert_to_number_and_back()
{
    for(long l=0;l<1000;l++)
    {
        TestSpecificNumber(num);
    }
}

private void TestSpecificNumber(long num)
{
    Converter converter = new Converter();
    string hash = converter.ConvertToBase(num);
    long convertBackNum = converter.ConvertFromBase(hash);

    Assert.AreEqual(num, convertBackNum, "The converted number does not match the original");
}

To use this in a blog, just convert the primary key to the hash and you can then use that hash in a short url like:

http://mysite.com/1yq

I will cover how to make the routing work in a blog entry in the next few days.

Peace and Grace,
Greg

Twitter: @gbworld

Advertisements

One Response to Creating a Short Url Hash

  1. Pingback: How to create your own private URL redirect/shorten service | My Own Home Server

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: