Skip to main content

Hashing

Part 1:

Hashing is the last topic of all these data structure blogs I have been writing about. I will try to sum up hashing from the basics, but in easier languages and as usual with algorithms and full programs. This post will be also a long and ever increasing post. So, keep close and keep studying.

Introduction:

Let me say that you are coding a database for a coaching institute and want to create a system for looking up each student's result. Now, here the main requirement is to have a high lookup speed. First thought which will come to your mind is the balanced binary tree. In this binary tree, it is guaranteed to have log(n) timed search, updating and balancing operation. But, although log(n) is not high, it can soon go up to higher numbers pretty soon. So, we, in this post, will discuss a much better approach. 

What is hashing? 

Hashing is a technique of creating a array where the entry of the array and the index are related by a certain function, enabling the search of the items in that array makes faster. 

The technique is specifically achieved by Hashing functions. Hashing functions are functions, which take a data as input, and create a index out of it. Because of the computational barriers, hashing functions are required to have
(1) easy and fast computability
(2) uniform (in case of crytographic functions, independent) distribution of the keys among the data.

This second point can be harder to understand. This second point kind of means, that it is sometimes desired of the hashing function that if you can find a pattern or distribution or probability distribution out of the keys, this distribution should be not dependent or biased to the distribution of the data from which the keys are produced. If you do not currently understand it, its not a big deal; a big chunk of the following content does not use it. 

Hash table: 

In the above description, we have referred to a array which stores the data or a reference to data. This array itself is called hash table. Hash table either stores each data with its calculated index, or it stores a link to the list of data with same key. From this, we come to the first block in our road. 

Collision problem:

The problem arrives with a "bad" hashing function. Actually hashing functions can not always guarantee to let all the points of the data to have different key. So, it happens that number of them may end up having the same key. Now, the same key can be avoided in two ways. 
I will talk about the two ways, (1) chain creation and (2) open addressing

Chain creation

Let us assume that the collision happens as there are many elements with the same key. The easiest way to deal with is to create a table with the possible keys as indices. Then, for each key, we create one chain of (implemented as linked list) elements with the same key. Therefore, our ultimate structure is an array of linked lists. If you have read about graphs, this is a analogous structure with the adjacency list. 

Next , I will present a program to create a hashing table with chain creation.

Comments

Post a Comment

Popular posts from this blog

20 Must-Know Math Puzzles for Data Science Interviews: Test Your Problem-Solving Skills

Introduction:   When preparing for a data science interview, brushing up on your coding and statistical knowledge is crucial—but math puzzles also play a significant role. Many interviewers use puzzles to assess how candidates approach complex problems, test their logical reasoning, and gauge their problem-solving efficiency. These puzzles are often designed to test not only your knowledge of math but also your ability to think critically and creatively. Here, we've compiled 20 challenging yet exciting math puzzles to help you prepare for data science interviews. We’ll walk you through each puzzle, followed by an explanation of the solution. 1. The Missing Dollar Puzzle Puzzle: Three friends check into a hotel room that costs $30. They each contribute $10. Later, the hotel realizes there was an error and the room actually costs $25. The hotel gives $5 back to the bellboy to return to the friends, but the bellboy, being dishonest, pockets $2 and gives $1 back to each friend. No...
Post a Comment
Read more

GAM model : PyGAM package details Analysis and possible issue resolving

Introduction:                  picture credit to peter laurinec. I have been studying about PyGAM package for last couple of days. Now, I am planning to thoroughly analyze the code of PyGAM package with necessary description of GAM model and sources whenever necessary. This is going to be a long post and very much technical in nature. Pre-requisites: For understanding the coding part of PyGAM package, first you have to learn what is a GAM model. GAM stands for generalized additive model, i.e. it is a type of statistical modeling where a target variable Y is roughly represented by additive combination of set of different functions. In formula it can be written as: g(E[Y]) = f 1 (x 1 ) + f 2 (x 2 ) + f 3 (x 3 ,x 4 )+...etc where g is called a link function and f are different types of functions. In technical terms, in GAM model, theoretically expectation of the link transformed target variable is assume...
Post a Comment
Read more

Pyarabic: python package for Arabic language

 Introduction:  In languages which are non-english and non-european as well, NLP work has progressed slowly in the last few decades because of the lesser number of scholars working on them as well as a lack of global interest in them. But now the time has changed and people from all over the world are collaborating on these lesser explored libraries and they are building resources for working on these languages with the same ease with that of english.  Pyarabic is a package created from such a similar effort which deals with the intricate details of the arabic language and helps processing all kinds of arabic texts. While trying to learn it, being from a non-arab background, I couldn't read lots of parts of the main readthedocs site and had to work my around it. So in this blog post, I will summarize my learnings in english language, so that you can learn it and use the package with much more ease than me. [Credit where credit is due: this article heavily uses the ac...
Post a Comment
Read more