Greeting fellow coder.
Thank you for checking out my blog on breaking down Hash table. I will go over what it is, how to use it, and why you need to know this data-structure.
What is Hash Table?
A hash table, is a data structure that uses a hash function to efficiently map keys to values, for efficient search/retrieval, insertion, and/or removals.
Hash table is one of many data structure in computer science, for which their purpose is to essentially organize data, using a variety of management and storage format that enables us to efficiently access and modify them.
There are many other data structures like array, linked list, binary tree, etc.
For this article I will focus on Hash Table, which is widely used in many kinds of computer software, particularly for associative arrays, database indexing, caches, and sets.
How do you use it ?
Like any data structure, hash table is use to help solve data problems.
Basically how efficient in time and space can you....
- searching for an item
- insert an item
- delete an item
The way a Hash table work is using Key => value lookup
A.) You take input keys run it through a hash function where it will map those input keys into numbers which corresponds to number of indexes in an array.
Lets say I have a list of names Michael, Bob, Jack, Becky. (these are my input keys)
B.) Run these inputs through a hash function.
There are many ways you can code a hash function, but essentially the hash function should take in a input string (the names we listed) converts them into an integer, and then remaps that integer into an index in an arrays.
C.) Boom we have associative values. Where we can now search, insert, and delete our data by using the Array index.
note: The array that stores the data from the hash table will likely always be much smaller than all of the available potential hash code or key inputs.
D.) Example
So lets picture we ran those names listed earlier into a hash function that holds the a max index of 7.
[undefined, [Bob], undefined, undefined,[Becky], [[Michael], [Jack]], undefined,]
So you can see there is 7 index in the array and all of those names have been map to a particular index.
We can now search for a particular name, like Bob is at array[1] Becky is at [4] so on and so forth.
*but what about array [5] which holds Michael and Jack.....well what a perfect segway into my-
"last but not least" note: because of a finite index, this opens the door for "collision" which is when 2 or more hash code is map in the same index.
There are different ways to resolve a collision, a very common way is by storing them in a linked list rather than just the strings. Just think of it as assigning an id to each name then storing it on a hash table.
So when looping through an index with multiple keys you are able to reference the specific name you want with their linked id.
That's about the basics of how a hash table operates. If you wish to learn more about hash tables the website below VisuAlgo does a great job in presenting hash tables and other data structure in easy to understand slides and interactive activities.
https://visualgo.net/en/hashtable?slide=1
Why do you need to know hash table ?
To do well in tech interview of course....
Technically yes, but also remember data structures like hash table are methods to efficiently search, insert, and delete data. And hash table is one of the more popular methods use because of how efficient they are.
In terms of Big O notation, the average time to search, insert, and delete data is O(1) which is pretty fast compare to all of the other data structure methods.
hopefully this article was helpful.
Thanks for reading me !
Latest comments (0)