Stack Bash - Master data structures and algorithms

Hash Table Data Structure

A hash table is a data structure that stores data in a way where each data can be accessed via a known index, or key.
Think of a hash table as similar to an array, but the key does not need to be a number, it can be a string or really any immutable value.
This is possible because a key can be decoded into an index, which can then be used to access data at that location. We'll talk about this process later.
In Python, a hash table is represented by both a dictionary and a set.
A = {
'alice': 24,
'rohit': 33,
'bob': 27
print(A['bob']) # prints 27
Hash tables have many synonyms. In other languages, a hash table is represented by an object or a hash map.
They're all the same.

Hash Table Big O Overview


How does hashing work

As promised, let's talk about how a range of keys can be decoded into a indices in an array.
This is possible via a hash function, which is a function that accepts our key and returns the appropriate index, or location in memory.
Most computers have pretty advanced hashing techniques. But let's use our example above to demonstrate what hashing could look like.
When we access A['bob'], the key bob can be hashed as follows:
  • Convert each character to a number. Python's ord converts a unicode character to its unicode code representation
  • Sum the unicode codes of all characters
  • Mod % the sum by the underlying hash table size to get the location.
It's possible that the hash function could return the same location for multiple keys.
This is known as a hash collision.
Under the hood, hash tables usually handle collisions by storing the collided key's values in a linked list as the hash table entry.
That way, we don't have to overwrite collided keys and lose info.

Hash Table Pros

The biggest pro is that on average, inserting, deleting and lookups can be done in constant time O(1).

Hash Table Cons

  • On occasion, it's possible that a hash collision occurs, and it takes longer than constant time to retrieve data.
  • There's no ordering of the time that entries are added to the hash table.
Tip: Python's collections library has a neat utitlty called OrderedDict which does track the order entries are added to the hash table.

Hash Table in Python

See the implementation of a HashTable in Python, as well as the hash function _hash.
In a coding interview, you should use existing hashing libraries, such as Python's built-in dictionary or set. As long as you can articulate how it works under the hood.

6 Essential Hash Tables Coding Interview Problems

Master Hash Tables by trying the coding challenges below.
  1. 1.Two sumEasy
  2. 2.Palindrome CheckEasy
  3. 3.Cover SetMedium
  4. 4.Missing numberMedium
  5. 5.Crypto ExchangeMedium
  6. 6.Distinct SubarrayHard

Want to confidently pass your next coding interview?

Stack Bash helps new and veteran software engineers master data structures and algorithms for technical interviews.