Practice
Resources
Contests
Online IDE
New
Free Mock
Events New Scaler
Practice
Improve your coding skills with our resources
Contests
Compete in popular contests with top coders
logo
Events
Attend free live masterclass hosted by top tech professionals
New
Scaler
Explore Offerings by SCALER

Hashing

Go to Problems

Level 1

Jump to Level 2

Level 2

Jump to Level 3

Level 3

Jump to Level 4

Level 4

Jump to Level 5

Level 5

Jump to Level 6

Level 6

Jump to Level 7

Level 7

Jump to Level 8

Level 8

Be a Code Ninja!

Introduction to hashing

What is hashing? How does it work?

Hashing is the process of converting a given key into another smaller value for O(1) retrieval time.

  • This is done by taking the help of some function or algorithm which is called as hash function to map data to some encrypted or simplified representative value which is termed as “hash code” or “hash”. This hash is then used as an index to narrow down search criteria to get data quickly. 
  • Hashing can be considered as a significant improvement over DAT to reduce the space complexity.
  • In our example of employee system that we have seen in the Introduction part, we can simply pass the employee ID to our hash function, get the hash code and use it as key to query over records.
  • Let us see one more example to understand how hashing works.

Purely as an example to help us grasp the concept, let us suppose that we want to map a list of string keys to string values (for example, map a list of countries to their capital cities). So let’s say we want to store the data in Table 1 in the map.

Key             |    Value
----------------|-------------
Cuba            |    Havana
England         |    London
France          |    Paris
Spain           |    Madrid
Switzerland     |    Berne

And let us suppose that our hash function is to simply take the length of the string.

For simplicity, we will have two arrays: one for our keys and one for the values. So to put an item in the hash table, we compute its hash code (in this case, simply count the number of characters), then put the key and value in the arrays at the corresponding index. 
For example, Cuba has a hash code (length) of 4. So we store Cuba in the 4th position in the keys array, and Havana in the 4th index of the values array etc. And we end up with the following:

Position             |   Keys array     |  Values array
(hash = key length)  |                  |
---------------------|------------------|---------------
   1                 |                  |
   2                 |                  |
   3                 |                  |
   4                 |    Cuba          |    Havana
   5                 |    Spain         |    Madrid
   6                 |    France        |    Paris
   7                 |    England       |    London
   8                 |                  | 
   9                 |                  |
   10                |                  |
   11                |  Switzerland     |    Berne

Now, in this specific example things work quite well. Our array needs to be big enough to accommodate the longest string, but in this case that’s only 11 slots. And we do waste a bit of space because, for example, there’s no 1-letter keys in our data, nor keys between 8 and 10 letters. But in this case, the waste isn’t so bad either. And taking the length of a string is nice and fast, so so is the process of finding the value associated with a given key (certainly faster than doing up to five string comparisons)1.

We can also easily see that this method would not work for storing arbitrary strings. If one of our string keys was a thousand characters in length but the rest were small, we would waste the majority of the space in the arrays. More seriously, this model can’t deal with collisions: that is, what to do when there is more than one key with the same hash code (in this case, more than one string of a given length). For example, if our keys were random words of English, taking the string length would be fairly useless. Granted, the word “psuedoantidisestablishmentarianistically” would probably get its own place in the array. But on the other hand, we’d be left with thousands of, say, 6-letter words all competing for the same slot in the array.

In this topic, we explore hashing, a technique very widely used in interview questions. Hashing is designed to solve the problem of needing to efficiently find or store an item in a collection. 
For example, if we have a list of 10,000 words of English and we want to check if a given word is in the list, it would be inefficient to successively compare the word with all 10,000 items until we find a match. Hashing is a technique to make things more efficient by effectively narrowing down the search at the outset.

 

 

Serious about Learning Programming ?

Learn this and a lot more with Scaler Academy's industry vetted curriculum which covers Data Structures & Algorithms in depth.

Hashing Problems

Hash search
Problem Score Companies Time Status
Colorful Number 150 44:55
Largest Continuous Sequence Zero Sum 200
68:45
Longest Subarray Length 200 54:59
First Repeating element 200 21:21
2 Sum 300 49:18
4 Sum 325 72:07
Valid Sudoku 325 50:31
Diffk II 375
29:06
Key formation
Problem Score Companies Time Status
Pairs With Given Xor 200 26:50
Anagrams 350 46:36
Equal 350
71:16
Copy List 450 56:01
Maths and hashing
Problem Score Companies Time Status
Check Palindrome! 200 18:13
Fraction 450 81:36
Points on the Straight Line 450 78:23
Incremental hash
Hashing two pointer
Free Mock Assessment
Fill up the details for personalised experience.
All fields are mandatory
Current Employer *
Enter company name *
Graduation Year *
Select an option *
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
Phone Number *
OTP will be sent to this number for verification
+1 *
+1
Change Number
Phone Number *
OTP will be sent to this number for verification
+1 *
+1
Change Number
Graduation Year *
Graduation Year *
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
*Enter the expected year of graduation if you're student
Current Employer *
Company Name *
Please verify your phone number
Edit
Resend OTP
By clicking on Start Test, I agree to be contacted by Scaler in the future.
Already have an account? Log in
Free Mock Assessment
Instructions from Interviewbit
Start Test