Posts

Featured post

Hash Tables : Scratching the Surface

Image
Have you ever worked with key-value data stores where you can attach one value to a key and store it in some form to perform easy lookups ? If yes, then i guess you have already seen hash tables in action. Hash Tables are so common these days that you don't even realise when you start using them but not a lot of people are familiar with the internals of hash tables and how these can be used in real world problems like cryptography. This a series of articles all about hashing. So sit tight and enjoy the journey. What Problems Does Hashing Solve ?Simple Implementation of Hash TableCollision ResolutionChainingOpen AddressingDesining Hash FunctionsHow Python Dictionaries WorkHashing in Action What Problems Does Hashing Solve ?Hash Tables are the most popular data structure in computer science. We forget to worry about time complexities of finding our data in hash table as its basically constant. But it doesn't show how hashing solves real world …

Hash Tables : Designing Hash Functions

Image
In the last post, we saw how collision in handled in a hash table. Now its time to explore some real world scenarios because come on, what is the use of learning all this if we can't apply it in real world softwares. As we learned that open addressing and chaining were both good in different scenarios only if we met a condition that the keys are uniformaly distributed. But its not the application job to pass distributed keys to hash tables, its our job to map any key to some random location. We do this using a hash function (or prehash function, whatever term you prefer). A hash function should map the keys as uniform as possible. So lets discuss some decent hash functions to some high end hash functions. What Problems Does Hashing Solve ?Simple Implementation of Hash TableCollision ResolutionChainingOpen AddressingDesining Hash FunctionsProperties of Hash FunctionsBasic Hash FunctionsCryptographic Hash FunctionsHow Python Dictionaries Work

Hash Tables : Handling Collision

Image
We saw in the previous post how a simple hash table can be constructed without much effort. But, and that is a big But, that table was prone to collisions and could result in corrupted data. Of course we don't want a data structure which can corrupt our data even if it is faster. So to avoid data corruption we will study some collision resolution techniques and will see how to evenly distribute a key over the table to minimize collision. Lets continue the journey. What Problems Does Hashing Solve ?Simple Implementation of Hash TableCollision ResolutionChainingOpen AddressingDesigning Hash FunctionsHow Python Dictionaries WorkHashing in Action Collision Resolution First of all, what is collision ? Collision is a phenomenon which happens when 2 or more distinct keys are mapped to the same hash table entry. But we don't want that so using some technique, we relocate that key to some other empty location. The technique used to do that is called collision resolu…

Cache : Replacement, Mapping and Writing

Image
In the previous article, we discussed about cache and its properties. We also learnt some concepts and terminology related to cache. If you haven't read that article, i will recommend you to read that article first. This article contains many terms which i've discussed in that article. In this article, we will learn cache replacement strategies, cache mapping techniques and cache writing techniques. Below is the index of this complete cache tutorial. Cache IntroductionCache OrganisationUnderstanding a few ConceptsCache Replacement StrategiesRandom ReplacementLeast Recently Used (LRU) ReplacementCache Mapping TechniquesDirect Mapped CacheSet Associative Mapped CacheFully Associative Mapped CacheThe Tedious Task of Cache WritingWrite ThroughNo Allocate (write around)AllocateWrite BackBasic Cache Simulator Cache Replacement StrategiesIn the previous article, we looked at the process of searching data for an address in the cache but there was 1 step missing in that process. We di…

Wondering Cache

Image
Some of you may have already heard about the computer cache in your curriculum or some of you may have not. But this article is intended for all of those who want to understand cache concepts. The next part of it consists of developing a cache simulator using C programming language. I believe that this article will give a clear insight of cache and how it works. So lets see what we will be learning in this series of articles. Cache IntroductionCache OrganisationUnderstanding a few ConceptsCache Replacement StrategiesRandom ReplacementLeast Recently Used (LRU) ReplacementCache Mapping TechniquesDirect Mapped CacheSet Associative Mapped CacheFully Associative Mapped CacheThe Tedious Task of Cache WritingWrite ThroughNo Allocate (write around)AllocateWrite BackBasic Cache Simulator Cache Introduction The first thing we should know what are we talking about. Cache is a highly efficient (really fast) memory which can bring data to processor at a much more speed than our typical RAM. CPU…

Image Search Engine Using Python

Image
Images provide a lot more information than audio or text. Image processing is the prime field of research for robotics as well as search engines. In this article we will explore the concept of finding similarity between digital images using python. Then we will use our program to find top 10 search results inside a dataset of images for a given picture. It won't be as good as google's search engine because of the technique we will be using to find similarity between images. But what we are going to make will be pretty cool. So lets start. Setting up the EnvironmentOur AlgorithmHow the code looksLets build the GUIAdditional Techniques Setting up the Environment The code we are going to write requires a few tools which we need to install first. I will try to be as precise as i can and if you get stuck into installing some tool then you can drop a comment below and i will help you sort out the problem. So here are the tools and the steps to install those tools in ubuntu (16.04 …

Authentication System : Basic Design

Image
Being a system administrator, it is our main concern to protect users' data from theft and corruption. Regarding theft, we focus in building a sophisticated but secure authentication system which can fulfill all the basic needs we discussed in the last article. In the previous 2 articles, we learned about authentication and authorization. Also we understood the complications in building a secure system which can prevent tresspassing. But we have not code anything yet to build something. So in this article we will be designing an authentication system which will provide the functionalities we want and which will help us understand how the tech giants like google have taken security to another level. We will be writing code in php but the same applies to other languages also.What we'll be usingBlueprintBuilding the systemRunning the systemAdditional Care What we'll be usingLets see what are the languages we will be using and database plus some extra librariesLanguagesPHP, Jav…