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

Popular posts from this blog

Mastering SQL for Data Science: Top SQL Interview Questions by Experience Level

Introduction: SQL (Structured Query Language) is a cornerstone of data manipulation and querying in data science. SQL technical rounds are designed to assess a candidate’s ability to work with databases, retrieve, and manipulate data efficiently. This guide provides a comprehensive list of SQL interview questions segmented by experience level—beginner, intermediate, and experienced. For each level, you'll find key questions designed to evaluate the candidate’s proficiency in SQL and their ability to solve data-related problems. The difficulty increases as the experience level rises, and the final section will guide you on how to prepare effectively for these rounds. Beginner (0-2 Years of Experience) At this stage, candidates are expected to know the basics of SQL, common commands, and elementary data manipulation. What is SQL? Explain its importance in data science. Hint: Think about querying, relational databases, and data manipulation. What is the difference between WHERE

What is Bort?

 Introduction: Bort, is the new and more optimized version of BERT; which came out this october from amazon science. I came to know about it today while parsing amazon science's news on facebook about bort. So Bort is the newest addition to the long list of great LM models with extra-ordinary achievements.  Why is Bort important? Bort, is a model of 5.5% effective and 16% total size of the original BERT model; and is 20x faster than BERT, while being able to surpass the BERT model in 20 out of 23 tasks; to quote the abstract of the paper,  ' it obtains performance improvements of between 0 . 3% and 31%, absolute, with respect to BERT-large, on multiple public natural language understanding (NLU) benchmarks. ' So what made this achievement possible? The main idea behind creation of Bort is to go beyond the shallow depth of weight pruning, connection deletion or merely factoring the NN into different matrix factorizations and thus distilling it. While methods like knowle

Spacy errors and their solutions

 Introduction: There are a bunch of errors in spacy, which never makes sense until you get to the depth of it. In this post, we will analyze the attribute error E046 and why it occurs. (1) AttributeError: [E046] Can't retrieve unregistered extension attribute 'tag_name'. Did you forget to call the set_extension method? Let's first understand what the error means on superficial level. There is a tag_name extension in your code. i.e. from a doc object, probably you are calling doc._.tag_name. But spacy suggests to you that probably you forgot to call the set_extension method. So what to do from here? The problem in hand is that your extension is not created where it should have been created. Now in general this means that your pipeline is incorrect at some level.  So how should you solve it? Look into the pipeline of your spacy language object. Chances are that the pipeline component which creates the extension is not included in the pipeline. To check the pipe eleme