Search⌘ K
AI Features
Home
Courses
Data Structures for Coding Interviews in Java

Hash Functions

Explore how hash functions work in Java hash tables, including methods like modular arithmetic, truncation, and folding. Understand how these functions compute indices and influence the efficiency of hashing mechanisms in data structures.

We'll cover the following...

🔍 Hash Function?

A hash function simply takes a key of an item and returns a calculated index in the array for that item.

This index calculation can be a simple or a very complicated encryption method. However, it is very important to choose an efficient Hashing function, as it directly affects the performance of the Hashing mechanism.

What Hash Functions Do?

Have a look at the following illustration to get the analogy of a Hash function.

We can consider the Hash function as a method that takes key as an input and returns the corresponding index to that key.

Commonly Used Hash Functions

These are the most common hashing functions in use:

  • Arithmetic Modular
    Take mod of the key with the size of an array (called table)

index=key MOD tableSizeindex = key \text{ } MOD \text{ } tableSize

Hence, the index will always stay between 0 and tableSize - 1.

Java
class HashFunctions 
{
   public static int hashModular(int key, int size)
  {
    return key % size;
  }
  public static void main( String args[] ) 
  {
    int [] list = new int[10];// List of size 10
    int key = 35;
    int index = hashModular(key, 10); // Fit the key into the list size
    System.out.println("The index for key " + key + " is " + index);
  }
}
  • Truncation

Select a part of the key as the index rather than the whole key. Once again, we can use a mod function for this operation, although it does not need to be based on the list size:

key=123456 −> index=3456 key = 123456 \text{ } -> \text{ } index = 3456

Java
class HashFunctions 
{
   public static int hashTruncation(int key)
  {
    return key % 500; // we will use key upto 3 digits
  }
  public static void main( String args[] ) 
  {
    int key = 123456;
    int index = hashTruncation(key); // Fit the key into the list size
    System.out.println("The index for key " + key + " is " + index);
  }
}
  • Folding
    Divide the key into smaller chunks and apply different strategies at each chunk. For example, you can add the divided chunks and re-build a different Hashed key:

key=456789  −> index=45+67+89key = 456789 \text{ } \text{ } -> \text{ } index = 45+67+89

Java
class HashFunctions
{
  public static int hashFold(int key, int chunkSize) // Define the size of each divided portion
  {  
      System.out.println ("Key: "+ key);
      String strKey = Integer.toString(key); // Convert integer into string for slicing
      int hashVal = 0;
      System.out.println("Chunks:");
    
      for(int i = 0; i < strKey.length(); i+=chunkSize)
      {
        if(i + chunkSize < strKey.length())
        {
            System.out.println(strKey.substring(i,i+chunkSize));
            hashVal += Integer.parseInt(strKey.substring(i,i+chunkSize));
        }
        else
        {
          System.out.println(strKey.substring(i,strKey.length()));
          hashVal+= Integer.parseInt(strKey.substring(i,strKey.length()));
        }
      }
    return hashVal;
  }
   public static void main( String args[] ) 
   {
       int key = 3456789;
       int chunkSize = 2;
       System.out.println("Hash Key: " + hashFold(key, chunkSize));
       //try another case with different values    
   }    
}