The heart of the project is to understand how to write a good Hashing function.
Let us look at the the model.py inside the smallify app in the above project.
class URL(models.Model):
original_url = models.CharField(max_length=300, unique= True)
shortened_url = models.CharField(max_length=30, unique = True)
def shorten_url(self):
self.shortened_url = self.__fnv_hash(self.original_url)
if(len(self.shortened_url) >= len(self.original_url)):
self.shortened_url = self.original_url
@staticmethod
def __fnv_hash(key):
h = 2166136261
for k in key:
h = (h*16777619)^ord(k)
# Return 8 bit URL
return base64.encode(h%281474976710656)
def __str__(self):
return models.Model.__str__(self)
It makes use of the FNV hashing algorithm. Look at the private method __fnv_hash in the above code snippet. It converts an arbitary length of string key into a 8 bit URL. Here every character of the key (original url) is XORed with a random integer h which is also multiplied at each stage to get a good folding effect. XORing gives a good uniform distribution. After this we encode the given integer to base64. Like a binary base has only 2 digits to represent every possible number, base64 uses 64 different characters. This gives us a more compact representation of the integer h. Finally, we do modular division by (281474976710655 + 1) to get a 8 bit compact URL.
Why 281474976710656 ?
As we can see from the below commands, the 64th character (starts with 0 to 63) is an underscore " _ ". So the value of 8 consecutive " _ " is 281474976710655 and hence we do a modular division with (281474976710655 + 1)
With this, we have some basic understanding of URL Shorteners. The demo project url-shortener in quite naive and created for this tutorial. Do check it out and let me know if you have any improvements in it. Feel free to send a pull request and looking forward to your views, opinions, and tips in the comments below.
