The Fundamentals of Data Structures and Algorithms: Hash Tables
After completing The Flatiron School software engineering program, I began preparations for my job hunt. A topic that was not covered during the program was data structures and algorithms, which is an imperative topic to understand for technical interviews with companies. For those of you who are new to data structures and algorithms, in computer science data structures are organized collections of data values, the relationships among them and their functions. Algorithms are a method or process used to solve certain types of problems or perform some type of computation. In my studies of data structures and algorithms, I discovered hash tables!
What Are Hash Tables and Why Are They Important?
A hash table is a data structure that maps key to values and uses lookup, insert and delete functions in an effective way. They are more commonly referred to as hash maps and they are often used in many different types of computer software. They are an important data structure to understand and utilize because they are able to provide access to elements in constant time(O(1), if this is confusing for you, here is a link that can give you some background on time complexity), which means they are extremely efficient particularly with search and data retrieval operations. They are mainly used for associative arrays, database indexing, caches and sets.
How Do Hash Tables Work?
Hash tables are made up of two parts, an object and a hash function. the object is the table where the data is stored. It holds all of the key-value pairs and its size is determined by the amount of data expected. Hash functions are the methods that determine the index of our key-value pair. They are one-way functions that produce a different hash for each key.
Hash maps begin their work when a key is sent to the hash function that performs specific operations that return an index of the key-value pair. When a value needs to be returned, the index can be used to find the pair and ultimately the value. Let’s check out a very basic example of a hash map in action.
CodeWars Example
I was working on codewars.com to practice data structures and algorithms when I came across a code challenge called, “Highest Scoring Word”. Given a string of words, I had to find the highest scoring word. Each letter of a word scores points according to its position in the alphabet and I was to return the highest scoring word as a string.
I began by creating a hash table of key-value pairs for each of the letters in the alphabet with its corresponding point value.
Once I developed the table, I created a hash function that would return the point value given an input of the letter (key).
Next, I split the string of words into an array and looped through each word in the array and then looped through each letter of every word. It was a loop inside of a loop where I called on the hash function to determine the points for each letter and adding the sum of the points for each word (count). After iterating through a word, I pushed the total in the sums array. Once I looped through all of the words in the array, my sums array contained all of the point totals for each word.
Finally, I returned the word in the array with the most points by using the index from the sums array. I located the index of the largest number in the sums array and used that same index to determine which word in the array to return as the one with the most points.
Conclusion
Although this may not be the most efficient way to solve the problem at hand, I was still able to solve it and pass all of the tests on CodeWars for this particular challenge. I had the opportunity to use the hash map data structure and find a solution. Hopefully after reading this post, your understanding of hash tables is a bit clearer and not as daunting as it was for me in the beginning. The best way to truly grasp the concept is to practice and CodeWars, LeetCode, and HackerRank are great places to practice. Thanks for reading and I will see you next week for my next post!