Hashing

 

The Core Concept: Hashing

Both Hash Maps and Hash Sets use a technique called hashing to achieve near-instant lookups.

What is Hashing?

Hashing is the process of taking an input (the key) and converting it into a fixed-size numerical value (the hash code or hash value). This hash code is then used as an index into an underlying array, where the data is stored.


  • Hash Function: A mathematical function that converts the key into an integer. For example, for a string "ABC," the hash function might calculate the sum of the ASCII values of 'A', 'B', and 'C'.


  • Index Calculation: Since the hash code can be very large, it is typically reduced to a valid index using the modulo operator (%) with the size of the underlying array (e.g., index = hash_code % array_size).


    The Goal of a Good Hash Function

    The primary goal is to minimize collisions. A collision occurs when two different keys map to the same array index.



    • Comments

    Post a Comment

    Popular posts from this blog

    1. Repeated DNA Sequences

    Image
     T he  DNA sequence  is composed of a series of nucleotides abbreviated as  'A' ,  'C' ,  'G' , and  'T' For example,  "ACGAATTCCG"  is a  DNA sequence . When studying  DNA , it is useful to identify repeated sequences within the DNA. Given a string  s  that represents a  DNA sequence , return all the  10 -letter-long  sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in  any order .   Example 1: Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" Output: ["AAAAACCCCC","CCCCCAAAAA"] Ex ample 2: Input: s = "AAAAAAAAAAAAA" Output: ["AAAAAAAAAA"]
    Read more

    Top K Elements

    Image
      The  top k elements  pattern is an important technique in coding that helps us efficiently find a specific number of elements, known as  k, from a set of data. This is particularly useful when we’re tasked with identifying the largest, smallest, or most/least frequent elements within an unsorted collection. Which data structure can we use to solve such problems? A heap is the best data structure to keep track of the smallest or largest k  elements. With this pattern, we either use a max heap or a min heap to find the smallest or largest k elements, respectively, because they allow us to efficiently maintain a collection of elements ordered in a way that gives us quick access to the smallest (min heap) or largest (max heap) element. Algorithm Max Heap => Smallest k elements Min Heap => Largest k elements Top 3 largest numbers
    Read more

    1. Valid palindrome

    Image
    Algorithm: Initialize two pointers, left at the start and right at the end of the string. Iterate until the left pointer is before the right pointer, skipping non-alphanumeric characters for both pointers. Compare characters positioned at the left and right pointers in lowercase; if they differ, return FALSE. Move left forward and right backward to check the next pair of characters. If the traversal completes without mismatches, return TRUE indicating the string is a palindrome. valid palindrome
    Read more