In this tutorial, you'll learn the following:

• Constant and linear time complexity.
• Why use a hash map?
• Things to consider when writing hash functions.
• How to solve the Two Sum problem in PHP and JavaScript.

What is Constant Time Complexity - O(1)?

O(1) indicates that the running time of an algorithm is constant, regardless of the input size.

This implies that the algorithm's performance isn't dependent on the size of the input. An example is accessing an index of an array.

<?php

function constantTimeAlgorithm($arr) 
{

    echo $arr[0] . PHP_EOL;
}

Here is a non-code example to illustrate the concept of constant time complexity:

Imagine sending a file through an airline to your friend, and the airline has a policy where they charge based on the weight of the package.

Now, whether your file weighs 2 grams or 20 kilograms, the airline's processing time remains constant. This means that the time it takes for the airline to handle your package doesn't depend on the weight of the file – it's always the same.

In other words, the processing time is constant irrespective of the size of the file.

What is Linear Time Complexity - O(n)?

O(n) indicates that the running time of an algorithm grows linearly with the size of the input.

The performance of the algorithm is directly proportional to the input size. An example is traversing a for loop and printing elements.

<?php

function linearTimeAlgorithm($arr) 
{
    foreach ($arr as $element) {
        echo $element . PHP_EOL;
    }
}

Here's a non-code example to illustrate the concept of linear time complexity:

Consider using an electronic transfer service to send a file to your friend. In this scenario, the time it takes to transfer the file increases linearly with the size of the file.

For instance, if it takes 1 minutes to transfer a 100 MB file, it would take approximately 100 minutes to transfer a 10 GB file using the same service.

This linear relationship between the size of the file and the time it takes to transfer it reflects linear time complexity. The time taken to transfer the file increases proportionally or linearly with the size of the input or file.

Why use a Hash Map?

Illustration of how a hash map works

A hash map is a concrete implementation of the abstract data type known as an associative array.

In a hash map, keys are hashed to determine the index where the corresponding values will be stored, allowing for efficient retrieval and storage of key-value pairs.

This implementation typically provides fast access times for operations like insertion, deletion, and lookup of values based on their associated keys.

In languages like PHP or JavaScript, when you use an associative array, you are essentially using a hash map. Their associative arrays are implemented using hash tables behind the scenes.

You can use strings, integers, or other data types as keys, and the language's internal hashing mechanism efficiently maps these keys to their corresponding values. Additionally, JavaScript provides the Map object for more advanced hash map functionalities.

Time and Space Complexity for Hash Map

The time and space complexity for a hash map (or hash table) is not necessarily O(n) for all operations. The typical and desired time complexity for basic operations like insertion, lookup, and deletion in a well-designed hash map is O(1) on average.

Here's a breakdown of time and space complexity for a hash map:

Time Complexity:

Average Case:

• Insertion (average): O(1)
• Lookup (average): O(1)
• Deletion (average): O(1)

Worst Case:

• Insertion (worst): O(n), where n is the size of the hash map. This occurs when there are many hash collisions, leading to linear probing or other collision resolution strategies that may involve traversing the entire hash map.
• Lookup and Deletion (worst): O(n), for the same reason as insertion.

Space Complexity:

• The space complexity is typically O(n). Where n is the number of key-value pairs stored in the hash map. Each key-value pair occupies constant space, and the space required grows linearly with the number of elements.

In algorithm analysis, the notation O(1) and O(n) represent the upper bounds on the time complexity of an algorithm, where n is the size of the input.

Operations

1. Insertion: The key-value pair is hashed, and the resulting index is used to store the value in the corresponding slot. If a collision occurs, the collision resolution strategy is applied.
2. Deletion: The key is hashed to find the index, and the item at that index is removed. Collision resolution may be necessary.
3. Lookup: The key is hashed to find the index, and the value at that index is returned. Collision resolution may be applied if needed.

Things to consider When Creating Hash Tables

When creating hash tables, there are several important considerations to ensure efficiency, including fast computation of hash codes and effective collision resolution strategies.

Fast Computation

Hash codes should be computed quickly to ensure efficient insertion, lookup, and deletion operations. A good hash function contributes to the speed of hash code computation.

Avoid collision

A collision happens when two or more keys produce the same hash code. In other words, multiple keys map to the same array index.

How to Handle Collisions

Hash maps use collision resolution techniques to deal with collisions. Common strategies include:

Chaining

To manage several values with the same hash code, chaining involves storing a linked list or other data structure at each array index. If a collision occurs, the new key-value pair is appended to the linked list at the relevant index.

Open addressing

When a collision happens in a hash table, a technique called open addressing is employed to resolve it by searching for the next open space.

All it does is search the array for the next empty slot where the key-value combination can be placed. Methods including double hashing, quadratic probing, and linear probing are applied.

Linear Probing: In linear probing, the algorithm moves linearly to the next index in the array in order to find the next open slot when a collision occurs.

Quadratic Probing: In this method, an algorithm employs a quadratic function to find the next slot that becomes available.

Double Hashing: In double hashing, the algorithm calculates the step size between probes using a secondary hash function.

In order to reduce the possibility of collisions, a good hash function should generate distinct hash codes for various inputs. By making sure the hash codes are evenly distributed throughout the range of potential values, collisions can be prevented.

How to Solve the Two Sum Problem

Two sum problem

The Two Sum problem involves finding all pairs of elements in an array that sum up to a specific target value. Now let's look at the problem statement.

Problem statement

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to the target.

Example 1:

Input: nums = [3,2,4, 8], target = 12

Output: [2, 3]

Example 2:

Input: nums = [5,5], target = 10

Output: [0,1]

Solution

To solve the Two Sum problem, we can use a hash table. The idea is to traverse the nums array and, for each element, check if the complement (the difference between the target and the current element) is already in the hash table. If it is, we have found a pair of indices whose elements add up to the target.

Here are the steps to follow:

1. To hold the elements and their respective indices, create an empty hash table upon initialization.
2. Go over the array of nums.
3. Do the complement calculation (target - current element) for each element.
4. Verify if the complement has already been added to the hash table. If yes, return the current index and the index stored in the hash table for the complement.
5. If the complement is not in the hash table, store the current element and its index in the hash table.
6. If no such pair is found during the traversal, it implies that there is no solution.

PHP Code Solution

<?php

function twoSum($nums, $target) {
    $hashTable = [];

    foreach ($nums as $i => $num) {
        $complement = $target - $num;

        if (array_key_exists($complement, $hashTable)) {

            // Found the pair, return the indices
            return [$hashTable[$complement], $i];
        }

        // Store the current element in the hash table
        $hashTable[$num] = $i;
    }

    // No solution found
    return [];
}

// Example usage:
$nums = [2, 7, 11, 5, 15, 30];
$target = 12;
$result = twoSum($nums, $target);

echo "Indices of the two numbers: [" . implode(", ", $result) . "]";

JavaScript Code Solution using map Function

function twoSum(nums, target) {
    const hashTable = new Map();

    for (const [index, num] of nums.entries()) {
        const complement = target - num;

        // Check if the complement is in the Map
        if (hashTable.has(complement)) {

            // Found the pair, return the indices
            return [hashTable.get(complement), index];
        }

        // Store the current number and its index in the Map
        hashTable.set(num, index);
    }

    // No solution found
    return [];
}

// Example usage:
const nums = [2, 7, 11, 5, 15, 30];
const target = 12;
const result = twoSum(nums, target);

console.log(`Indices of the two numbers that add up to ${target}: [${result.join(', ')}]`);

This approach has a time complexity of O(n) because we iterate through the array once. The space complexity is also O(n) due to the storage of elements in the hash map.

Resources

1. Hash table From Wikipedia
2. Hash maps in Python

Conclusion

In this article, you learned about hash maps, things to consider when writing hash functions and a real world problem that involves solving the Two Sum problem.

Keep learning, and Happy Coding!

You can find me on LinkedIn and Twitter.

A Hash Table transforms a key into an integer index using a hash function, and the index will decide where to store the key/value pair in memory:

_Hash table for storing phone books (from Wikipedia)_

You'll commonly use a Hash Table because of its fast search, insertion, and delete operations:

Source from Wikipedia

This tutorial will help you understand Hash Table implementation in JavaScript as well as how you can build your own Hash Table class.

First, let's look at JavaScript's Object and Map classes.

How to Use Hash Tables with Object and Map Classes in JavaScript

The most common example of a Hash Table in JavaScript is the Object data type, where you can pair the object's property value with a property key.

In the following example, the key Nathan is paired with the phone number value of "555-0182" and the key Jane is paired with the value "315-0322":

let obj = {
  Nathan: "555-0182",
  Jane: "315-0322"
}

But JavaScript's Object type is a special kind of Hash Table implementation for two reasons:

• It has properties added by the Object class. Keys you input may conflict and overwrite default properties inherited from the class.
• The size of the Hash Table is not tracked. You need to manually count how many properties are defined by the programmer instead of inherited from the prototype.

For example, the Object prototype has the hasOwnProperty() method which allows you to check if a property is not inherited:

const obj = {};
obj.name = "Nathan";

console.log(obj.hasOwnProperty("name")); // true

JavaScript doesn't block an attempt to overwrite the hasOwnProperty() method, which may cause an error like this:

const obj = {};
obj.name = "Nathan";
obj.hasOwnProperty = true;

console.log(obj.hasOwnProperty("name")); 
// Error: obj.hasOwnProperty is not a function

To handle these shortcomings, JavaScript created another implementation of the Hash Table data structure which is called Map

Just like Object, Map allows you to store key-value pairs inside the data structure. Here's an example of Map in action:

const collection = new Map();

collection.set("Nathan", "555-0182");
collection.set("Jane", "555-0182");

console.log(collection.get("Nathan")); // 555-0182
console.log(collection.size); // 2

Unlike the Object type, Map requires you to use the set() and get() methods to define and retrieve any key-pair values that you want to be added to the data structure.

You also can't overwrite Map inherited properties. For example, the following code tried to overwrite the size property value to false:

const collection = new Map();

collection.set("Nathan", "555-0182");
collection["size"] = false;

console.log(collection.get("size")); // undefined
console.log(collection.size); // 1

As you can see from the code above, you can't add a new entry to the Map object without using the set() method.

The Map data structure is also iterable, which means you can loop over the data as follows:

const myMap = new Map();

myMap.set("Nathan", "555-0182");
myMap.set("Jane", "315-0322");

for (let [key, value] of myMap) {
  console.log(`${key} = ${value}`);
}

Now that you've learned how JavaScript implements Hash Tables in the form of Object and Map data structures, let's see how you can create your own Hash Table implementation next.

How to Implement a Hash Table Data Structure in JavaScript

Although JavaScript already has two Hash Table implementations, writing your own Hash Table implementation is one of the most common JavaScript interview questions.

You can implement a Hash Table in JavaScript in three steps:

• Create a HashTable class with table and size initial properties
• Add a hash() function to transform keys into indices
• Add the set() and get() methods for adding and retrieving key/value pairs from the table.

Alright, let's start with creating the HashTable class. The code below will create a table of buckets with the size of 127:

class HashTable {
  constructor() {
    this.table = new Array(127);
    this.size = 0;
  }
}

All your key/value pairs will be stored inside the table property.

How to write the hash() method

Next, you need to create the hash() method that will accept a key value and transform it into an index.

A simple way to create the hash would be to sum the ASCII code of the characters in the key using the charCodeAt() method as follows. Note that the method is named using _ to indicate that it's a private method:

_hash(key) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash += key.charCodeAt(i);
  }
  return hash;
}

But since the HashTable class only has 127 buckets, this means that the _hash() method must return a number between 0 and 127.

To ensure that the hash value doesn't exceed the bucket size, you need to use the modulo operator as shown below:

_hash(key) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash += key.charCodeAt(i);
  }
  return hash % this.table.length;
}

Now that you have the _hash() method completed, it's time to write the set() and get() methods.

How to write the set() method

To set the key/value pair in your Hash Table, you need to write a set() method that accepts (key, value) as its parameters:

• The set() method will call the _hash() method to get the index value.
• The [key, value] pair will be assigned to the table at the specified index
• Then, the size property will be incremented by one

set(key, value) {
  const index = this._hash(key);
  this.table[index] = [key, value];
  this.size++;
}

Now that the set() method is complete, let's write the get() method to retrieve a value by its key.

How to write the get() method

To get a certain value from the Hash Table, you need to write a get() method that accepts a key value as its parameter:

• The method will call the _hash() method to once again retrieve the table index
• Return the value stored at table[index]

get(key) {
  const index = this._hash(key);
  return this.table[index];
}

This way, the get() method will return either the key/value pair back or undefined when there is no key/value pair stored in the specified index.

So far so good. Let's add another method to delete key/value pair from the Hash Table next.

How to write the remove() method

To delete a key/value pair from the Hash Table, you need to write a remove() method that accepts a key value as its parameter:

• Retrieve the right index using the _hash() method
• Check if the table[index] has a truthy value and the length property is greater than zero. Assign the undefined value to the right index and decrement the size property by one if it is.
• If not, simply return false

remove(key) {
  const index = this._hash(key);

  if (this.table[index] && this.table[index].length) {
    this.table[index] = undefined;
    this.size--;
    return true;
  } else {
    return false;
  }
}

With that, you now have a working remove() method. Let's see if the HashTable class works properly.

How to Test the Hash Table Implementation

It's time to test the Hash Table implementation. Here's the full code for the Hash Table implementation again:

class HashTable {
  constructor() {
    this.table = new Array(127);
    this.size = 0;
  }

  _hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % this.table.length;
  }

  set(key, value) {
    const index = this._hash(key);
    this.table[index] = [key, value];
    this.size++;
  }

  get(key) {
    const target = this._hash(key);
    return this.table[target];
  }

  remove(key) {
    const index = this._hash(key);

    if (this.table[index] && this.table[index].length) {
      this.table[index] = [];
      this.size--;
      return true;
    } else {
      return false;
    }
  }
}

To test the HashTable class, I'm going to create a new instance of the class and set some key/value pairs as shown below. The key/value pairs below are just arbitrary number values paired with country names without any special meaning:

const ht = new HashTable();
ht.set("Canada", 300);
ht.set("France", 100);
ht.set("Spain", 110);

Then, let's try to retrieve them using the get() method:

console.log(ht.get("Canada")); // [ 'Canada', 300 ]
console.log(ht.get("France")); // [ 'France', 100 ]
console.log(ht.get("Spain")); // [ 'Spain', 110 ]

Finally, let's try to delete one of these values with the remove() method:

console.log(ht.remove("Spain")); // true
console.log(ht.get("Spain")); // undefined

Alright, all the methods are working as expected. Let's try another insertion with a new HashTable instance and retrieve those values:

const ht = new HashTable();

ht.set("Spain", 110);
ht.set("ǻ", 192);

console.log(ht.get("Spain")); // [ 'ǻ', 192 ]
console.log(ht.get("ǻ")); // [ 'ǻ', 192 ]

Oops! Looks like we got into some trouble here. 😨

How to Handle Index Collision

Sometimes, the hash function in a Hash Table may return the same index number. In the test case above, the string "Spain" and "ǻ" both return the same hash value because the number 507 is the sum of both of their ASCII code.

The same hash value will cause the index to collide, overwriting the previous entry with the new one.

Right now, the data stored in our Hash Table implementation looks as follows:

[
    [ "Spain", 110],
    [ "France", 100]
]

To handle the index number collision, you need to store the key/value pair in a second array so that the end result looks as follows:

[
    [
        [ "Spain", 110 ],
        [ "ǻ", 192 ]
    ],
    [
        ["France", 100]
    ],
]

To create the second array, you need to update the set() method so that it will:

• Look to the table[index] and loop over the array values.
• If the key at one of the arrays is equal to the key passed to the method, replace the value at index 1 and stop any further execution with the return statement.
• If no matching key is found, push a new array of key and value to the second array.
• Else, initialize a new array and push the key/value pair to the specified index
• Whenever a push() method is called, increment the size property by one.

The complete set() method code will be as follows:

set(key, value) {
  const index = this._hash(key);
  if (this.table[index]) {
    for (let i = 0; i < this.table[index].length; i++) {
      // Find the key/value pair in the chain
      if (this.table[index][i][0] === key) {
        this.table[index][i][1] = value;
        return;
      }
    }
    // not found, push a new key/value pair
    this.table[index].push([key, value]);
  } else {
    this.table[index] = [];
    this.table[index].push([key, value]);
  }
  this.size++;
}

Next, update the get() method so that it will also check the second-level array with a for loop and return the right key/value pair:

get(key) {
  const target = this._hash(key);
  if (this.table[target]) {
    for (let i = 0; i < this.table.length; i++) {
      if (this.table[target][i][0] === key) {
        return this.table[target][i][1];
      }
    }
  }
  return undefined;
}

Finally, you need to update the remove() method so that it will loop over the second-level array and remove the array with the right key value using the splice() method:

remove(key) {
  const index = this._hash(key);

  if (this.table[index] && this.table[index].length) {
    for (let i = 0; i < this.table.length; i++) {
      if (this.table[index][i][0] === key) {
        this.table[index].splice(i, 1);
        this.size--;
        return true;
      }
    }
  } else {
    return false;
  }
}

With that, your HashTable class will be able to avoid any index number collision and store the key/value pair inside the second-level array.

As a bonus, let's add a display() method that will display all key/value pairs stored in the Hash Table. You just need to use the forEach() method to iterate over the table and map() the values to a string as shown below:

display() {
  this.table.forEach((values, index) => {
    const chainedValues = values.map(
      ([key, value]) => `[ ${key}: ${value} ]`
    );
    console.log(`${index}: ${chainedValues}`);
  });
}

Here's the complete HashTable class code again with the collision avoidance applied for your reference:

class HashTable {
  constructor() {
    this.table = new Array(127);
    this.size = 0;
  }

  _hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % this.table.length;
  }

  set(key, value) {
    const index = this._hash(key);
    if (this.table[index]) {
      for (let i = 0; i < this.table[index].length; i++) {
        if (this.table[index][i][0] === key) {
          this.table[index][i][1] = value;
          return;
        }
      }
      this.table[index].push([key, value]);
    } else {
      this.table[index] = [];
      this.table[index].push([key, value]);
    }
    this.size++;
  }

  get(key) {
    const index = this._hash(key);
    if (this.table[index]) {
      for (let i = 0; i < this.table.length; i++) {
        if (this.table[index][i][0] === key) {
          return this.table[index][i][1];
        }
      }
    }
    return undefined;
  }

  remove(key) {
    const index = this._hash(key);

    if (this.table[index] && this.table[index].length) {
      for (let i = 0; i < this.table.length; i++) {
        if (this.table[index][i][0] === key) {
          this.table[index].splice(i, 1);
          this.size--;
          return true;
        }
      }
    } else {
      return false;
    }
  }

  display() {
    this.table.forEach((values, index) => {
      const chainedValues = values.map(
        ([key, value]) => `[ ${key}: ${value} ]`
      );
      console.log(`${index}: ${chainedValues}`);
    });
  }
}

You can test the implementation by creating a new HashTable instance and do some insertion and deletion:

const ht = new HashTable();

ht.set("France", 111);
ht.set("Spain", 150);
ht.set("ǻ", 192);

ht.display();
// 83: [ France: 111 ]
// 126: [ Spain: 150 ],[ ǻ: 192 ]

console.log(ht.size); // 3
ht.remove("Spain");
ht.display();
// 83: [ France: 111 ]
// 126: [ ǻ: 192 ]

Now there's no collision inside the HashTable instance. Great work!

Conclusion

In this tutorial, you've learned what a Hash Table is and how JavaScript uses it to create the Object and Map data structure.

You've also learned how to implement your own HashTable class as well as how to prevent the Hash Table's key indices from colliding by using the chaining technique.

By using a Hash Table data structure, you will be able to create an associative array with fast search, insertion, and delete operations. 😉

If you enjoyed this article and want to take your JavaScript skills to the next level, I recommend you check out my new book Beginning Modern JavaScript here.

The book is designed to be easy to understand and accessible to anyone looking to learn JavaScript. It provides a step-by-step gentle guide that will help you understand how to use JavaScript to create a dynamic application.

Here's my promise: You will actually feel like you understand what you're doing with JavaScript.

Until next time!

If you have programmed before, you are sure to have come across hashing and hash tables. Many developers have used hash tables in one form or another, and beginner developers must learn this fundamental data structure. There is just one problem:

All the tutorials you come across are sure to discuss hashing and hash tables in JavaScript, Python, or some other programming language.

What this means is that you may understand a little about how hashing works and how to use a hash table in [insert language here], but may miss the principles of how it works.

Wouldn't it be great if we could learn about hashing without knowing any particular language? If you know how hashing works, and what a hash table is, the language shouldn't matter.

That is the codeless approach, and in this post I will teach you all about hashing and hash tables regardless of which programming language you are currently using. Whether you're a junior or senior dev, everyone will learn something from this post.

So What's a Hash Function Anyway?

Before we get into all the fancy stuff, let me tell you what hashing is. To make it easy let's imagine we have a black box:

I'm a Black Box

This black box is special. It is called a function box. We'll call it a function box because this box will map an independent variable on the input to a dependent variable on the output (it sounds mathy but bear with me).

Our function box works like this: if we put a letter into the box, we get a number out. Since our box is a function box, there can only be one output for every input into the box.

Our function box will take a letter from A-J on the input and output a corresponding number from 0 to 9 on the output. So if we input C we will get 2 on the output.

Function Box

This forms the basics of what a hash function is. The hash function, however, takes it a step further. We will map data on the input to some numeric value on the output, usually a hexadecimal sequence.

Hash Function

So essentially all hashing does is it uses a function to map data to a representative numeric or alphanumeric value. For the hash function, regardless of the size of the input, the output will always remain the same.

What about Hash Tables?

So at this point you may be wondering what a hash table is. Hash tables utilize hashing to form a data structure.

Hash tables use an associative method to store data by using what is known as a key-value lookup system. All that means is that, in a hash table, keys are mapped to unique values.

This system of organizing data results in a very fast way to find data efficiently. This is because since each key is mapped to a unique value – once we know a key then we can find the associated value instantly.

Hash tables are extremely fast, having a time complexity that is in the order of O(1).

Confused? Take a look at this diagram, where we have multiple function boxes generating hash values.

Multiple Function Boxes

In this scenario, each character on the input (each is a key) has a hash function applied to it, and the hash function in the function box generates the hash value. This resulting value is then mapped to an index in the underlying linked list or array used to implement the hash table.

The resulting structure will look like this:

Hash Table

Hash Collisions

This is a good time to talk about collision in hash functions and hash tables.

A function in mathematics is ideal in that an element in the input is mapped to exactly one element in the output.

In a hash function, however, it is not always like this. Sometimes differing hash values in the input may produce the same hash value in the output. When this occurs you get what is known as a hash collision.

Hash collisions are not very common in most use cases, as a small change in the input can produce a dramatically differing output. But the more data you have to input to the hash function, the more likely a collision is to occur.

In the hash table example we provided earlier, we assumed that an array was used to implement the hash table. While this is good for simple hash tables, in practice these are not very good for handling collisions.

As such, a method known as chaining is used. In chaining, if the hash table returns the same hash value for multiple elements, we simply "chain" the elements together with the same hash values at the same index in the hash table.

This way instead of being implemented as an array with an index, we implement the hash table using a linked list where each element is a list rather than merely having a single value assigned to it.

But as the length of the chain increases, the time complexity of the hash table can get worse. A method known as open addressing is also used. In it, alternate locations in the underlying data structure implementing the hash table are found. Just keep in mind that this method will reduce the efficiency of the hash table and has a worse time complexity.

Is Hashing the Same as Encryption or Encoding?

Many people tend to associate hashing with encryption or encoding. So is hashing encryption? Is it the same as encoding?

You see, in encryption we muddle data so that only someone with the key needed to decrypt the data will have access to it. When we utilize an encryption cipher, we not only make the data encrypted, but we also want to decrypt the data at some point. In encryption we want to recover the original data.

Hashing, on the other hand, takes data and produces an output for the purpose of confirming the integrity of data. In hashing we have no intention of recovering the original data.

Encoding differs from encryption and hashing in that the goal of encoding is not to obscure data for any security purpose, but merely to convert the data into a format that another system can use.

What Can I Do with Hashing?

Hashes and hash tables have numerous uses! These include:

1. Cryptosystems
2. Cyclic Redundancy Checks
3. Search Engines
4. Databases
5. Compilers

Or any system that has a complex lookup process.

Wrapping Up

In this post we've covered the basics of hashing, all without writing a single line of code! This was easy right? The codeless approach is a much easier way of learning about these fundamental topics.

We learned that hash functions can be used to convert objects into a fixed length alphanumeric output. We also learned that hash tables are key-value lookup systems and, while they work well, are not perfect and sometimes suffer from collisions.

By the end of this post you should know the difference between hashing, encryption, and encoding, and also have an idea of where hashes can be used.

Did you like the codeless approach? Want to go further?

Learn about hash tables and other data structures and algorithms in the book "Codeless Data Structures and Algorithms". You'll get an expansion of what was covered in this post and learn about many more topics, all without writing a single line of code!

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. Even if the list of words are lexicographically sorted, like in a dictionary, you will still need some time to find the word you are looking for.

Hashing is a technique to make things more efficient by effectively narrowing down the search at the outset.

What is hashing?

Hashing means using some function or algorithm to map object data to some representative integer value.

This so-called hash code (or simply hash) can then be used as a way to narrow down our search when looking for the item in the map.

Generally, these hash codes are used to generate an index, at which the value is stored.

How hashing works

In hash tables, you store data in forms of key and value pairs. The key, which is used to identify the data, is given as an input to the hashing function. The hash code, which is an integer, is then mapped to the fixed size we have.

Hash tables have to support 3 functions.

• insert (key, value)
• get (key)
• delete (key)

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 in the map.

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:

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.
We do waste a bit of space because, for example, there are no 1-letter keys in our data, nor keys between 8 and 10 letters.

But in this case, the wasted space isn’t so bad either. Taking the length of a string is nice and fast, and so is the process of finding the value associated with a given key (certainly faster than doing up to five string comparisons).

But, what do we do if our dataset has a string which has more than 11 characters?
What if we have one another word with 5 characters, “India”, and try assigning it to an index using our hash function. Since the index 5 is already occupied, we have to make a call on what to do with it. This is called a collision.

If our dataset had a string with thousand characters, and you make an array of thousand indices to store the data, it would result in a wastage of space. If our keys were random words from English, where there are so many words with same length, using length as a hashing function would be fairly useless.

Collision Handling

Two basic methods are used to handle collisions.

1. Separate Chaining
2. Open Addressing

Separate Chaining

Hash collision handling by separate chaining, uses an additional data structure, preferrably linked list for dynamic allocation, into buckets. In our example, when we add India to the dataset, it is appended to the linked list stored at the index 5, then our table would look like this.

To find an item we first go to the bucket and then compare keys. This is a popular method, and if a list of links is used the hash never fills up. The cost for get(k) is on average O(n) where n is the number of keys in the bucket, total number of keys be N.

The problem with separate chaining is that the data structure can grow with out bounds.

Open Addressing

Open addressing does not introduce any new data structure. If a collision occurs then we look for availability in the next spot generated by an algorithm. Open Addressing is generally used where storage space is a restricted, i.e. embedded processors. Open addressing not necessarily faster then separate chaining.

Methods for Open Addressing

• [Linear Probing
• Quadratic Probing
• Double Hashing

How to use hashing in your code.

Python

   # Few languages like Python, Ruby come with an in-built hashing support.
   # Declaration
    my_hash_table = {}
    my_hash_table = dict()

   # Insertion
    my_hash_table[key] = value

   # Look up
    value = my_hash_table.get(key) # returns None if the key is not present || Deferred in python 3, available in python 2
    value = my_hash_table[key] # throws a ValueError exception if the key is not present

    # Deletion
    del my_hash_table[key] # throws a ValueError exception if the key is not present

    # Getting all keys and values stored in the dictionary
    keys = my_hash_table.keys()
    values = my_hash_table.values()

Run Code

Java

    // Java doesn't include hashing by default, you have to import it from java.util library
    // Importing hashmaps
    import java.util.HashMap;

   // Declaration
    HashMap<Integer, Integer> myHashTable = new HashMap<Integer, Integer>(); // declares an empty map.

   // Insertion
    myHashTable.put(key, value);

   // Deletion
    myHashtable.remove(key);

    // Look up
    myHashTable.get(key); // returns null if the key K is not present
    myHashTable.containsKey(key); // returns a boolean value, indicating the presence of a key

    // Number of key, value pairs in the hash table
    myHashTable.size();

Run Code

More info on hashing

• The codeless guide to hashing and hash tables
• How to implement a simple hash table in JavaScript
• Hash tables explained