Posts

Showing posts from February, 2018

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 Table Collision Resolution Chaining Open Addressing Desining

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 Table Collision Resolution Chaining Open Addressing Designing Hash Functions How Python Dictionaries Work Hashing 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 wa

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 Table Collision Resolution Chaining Open Addressing Desining Hash Functions How Python Dictionaries Work Hashing in Action What Problems Does Hashing Solve ? Hash Tables are the most popular data structure in computer science. We forget