Hash tables

Hash tables are among the most widely used data structures in computing and are characterized by fast insertion and lookup speeds. Other names for hash tables are associative arrays and dictionaries.

In this article, I will explain, in simple terms, what makes hash tables special without too much technical detail. But please note that a solid understanding of arrays and linked lists are prerequesits for understanding hash tables.

There are many ways to store data in memory and on disk using hash tables, but the simplest way to understand hash tables is to understand the problem they solve, and conceptually how they store data. 

In this article, I will explain one way to store data in memory using a hash table. This concept is also used for storing data on disks, but reading and writing to disks is much more complicated, since it must be optimized for how HDDs store data in sectors and SSDs store data in pages with a fixed size.

Hash tables are similar to arrays in that they are a fixed-length block of memory. The difference is that a hash table doesn't store data at offsets as arrays do. Instead, a hash table is an address space that contains an array of pointers. These pointers point to linked lists where the data is stored. 

By using hash tables, you get the flexibility of a linked list, but you don't have to loop through the entire linked list to access data. This makes it much more effective for accessing stored data.

When you insert an element in the hash table, you pass the index into a hashing function that generates a hash of that index. The calculated hash is based on the size of the hash table. The simplest example is a hashtable with a length of 10 and a hashing algorithm that uses the modulo of the hash table length to determine which index to use. 

• If the index is 6, the hash table index will be 6.
• If the index is 12, the hash table index will be 2.
• If the index is 255, the hash table index will be 5.

The insertion algorithm will then go to that index in the hash table. There, it will find a pointer to a linked list of all the data that had the same hash. The algorithm will then loop through the linked list, looking for an entry with the same index as itself. If a match is found, the data is replaced. If the index was not found, the data will be appended to the end of the linked list.

The lookup function, like the insertion/replacement function, uses a hashing algorithm to find the index in the hash table that points to the linked list of data. It will then loop through the linked list looking for the index. If the index is found, the data will be returned. If the index was not found, depending on the programming language or library used for hash tables, an exception will be raised, or null will be returned.

A set is simply a hash table without any values, just indexes.

DSA (Data Structures and Algorithms) can only be learned by using them. I believe the most effective approach to learning DSA is first to understand the theory and then solve challenges.

I encourage you first to solve these challenges by first using a brute force algorithm, then try to solve them with a time and space complexity of less than O(n²).

Here are the problems I solved when first learning about hash tables using JavaScript:

• Create a custom hash table class from scratch
  • Hashing method based on the hash table array size
  • Set method where each hash table array element is an array
  • Get method where each hash table array element is an array
  • Set method where each hash table array element is a linked list
  • Get method where each hash table array element is a linked list
  • Print all keys method
     
• Create a custom set class from scratch
  • Insert method
  • "Is in the set" method (returns a bool)