Hashing in Data Structure: Definition, Working, and Types Explained

When you start learning data structure, concepts like arrays, stacks, and linked lists come first. But when you learn more, you come across the term that takes data and storage to a whole different level: Hashing in data structures. Hashing is helpful for a programmer to hold data and retrieve it almost instantly. It uses a method of transforming each individual item of data into a unique number. Hashing may seem intimidating now, but once you are familiar with it, you will see its elegance, simplicity, and ability!

In this blog, you will learn about hashing in data structures, why it is important, how it works, and the real-world applications of hashing.

Quick Answer

Hashing converts a key into a hash value that helps determine where its associated data should be stored. A well-designed hash table provides average O(1) search, insertion, and deletion.

Common uses include:

• Hash maps: Store and retrieve key-value pairs quickly.
• Databases: Support hash indexes, caching, and fast equality searches.
• Password verification: Store salted password hashes instead of plain-text passwords.

Hashing does not guarantee that every key receives a unique table index. Different keys can produce the same index, creating a collision that must be handled correctly.

What is a Hash Function?

Hashing in Data Structure is a procedure of assigning data (also referred to as keys) to a particular position in a data table based on a mathematical algorithm referred to as a hash function.

In simple terms:

• All the keys (such as name, ID, or number) are inputted in a hash function.
• The hash algorithm transforms it into a hash code (unique number).
• This hash value then defines the place where the information is stored in a table known as a hash table

So that the hash function will find that data practically in a moment when you need it, without having to search the whole set of data.

Why is Hashing Important in Data Structures?

If there is no hashing, the retrieval of data can be very difficult.

For example:

• You may be required to search an element in arrays or linked lists at a time, which is an O(n) operation.
• In binary search trees, the complexity is lowered to O(log n), but still, that is not immediate.

Hashing, however, can usually provide O(1) average time complexity; that is, the access time does not increase with the amount of data.

That’s why hashing forms the foundation for many efficient data structures, like:

• Hash tables
• Hash maps
• Sets
• Dictionaries

Key Terms in Hashing

It is important to know some key terminologies in hashing before going any further:

How Hashing Works (Step-by-Step)

Let’s see how hashing works with a simple example

Assume you would like to save student IDs:

Student IDs: 101, 102, 103, 104, 105

Hash function: h(key) = key % 10

Now apply the hash function:

h(101) = 1

h(102) = 2

h(103) = 3

h(104) = 4

h(105) = 5

The hash table will appear as follows:

The hash function simply refers to index 3 when you need to access the ID 103. No searching at all!

What is a Hash Function?

Hashing is based on a hash function. It transforms a specified key into a smaller size fixed number, also known as a hash value or index, to store and access data.

Properties of a Good Hash Function

• Reduces collisions: Different keys should ideally produce different hash values.
• Even distribution: The data is expected to be evenly distributed over the hash table.
• Quick calculation: Must be able to calculate hash values fast.
• Deterministic: The same input must generate the same hash.

Examples of Simple Hash Functions

• Division Method:
  • h(key) = key % tablesize
• Multiplication Method:
  • h(key) = floor(tablesize (key  A % 1))
  • where A is a constant that is in the range of 0 to 1.
• Mid-Square Method:
  • Square the key and extract some middle digits.

Also Explore: 5 Best Reasons to Learn Data Structures and Algorithms [DSA]

What is a Hash Table?

A hash table is a data structure in which key-value pairs are stored in hashing.

It contains:

• An array of slots (buckets)
• Each bucket stores data at the index produced by the hash function.

For Example:

Let’s store employee names using their employee IDs as a key.

The hash function maps each key to a table index, allowing quick access.

Hash Table Implementation in Python Using Separate Chaining

Separate chaining stores a collection at every table index. Keys producing the same index are placed inside the same bucket.

class ChainedHashTable:
    def __init__(self, capacity=10):
        if capacity <= 0:
            raise ValueError("Capacity must be greater than zero")

        self.capacity = capacity
        self.buckets = [[] for _ in range(capacity)]
        self.size = 0

    def _hash(self, key):
        return hash(key) % self.capacity

    def put(self, key, value):
        """Insert a new key-value pair or update an existing key."""
        index = self._hash(key)
        bucket = self.buckets[index]

        for position, (stored_key, _) in enumerate(bucket):
            if stored_key == key:
                bucket[position] = (key, value)
                return

        bucket.append((key, value))
        self.size += 1

    def get(self, key):
        """Return the value associated with a key."""
        index = self._hash(key)
        bucket = self.buckets[index]

        for stored_key, stored_value in bucket:
            if stored_key == key:
                return stored_value

        raise KeyError(f"Key not found: {key}")

    def delete(self, key):
        """Remove a key-value pair from the table."""
        index = self._hash(key)
        bucket = self.buckets[index]

        for position, (stored_key, _) in enumerate(bucket):
            if stored_key == key:
                del bucket[position]
                self.size -= 1
                return

        raise KeyError(f"Key not found: {key}")

    def display(self):
        for index, bucket in enumerate(self.buckets):
            print(f"Index {index}: {bucket}")


# Example usage
table = ChainedHashTable(capacity=5)

table.put(101, "Visha")
table.put(106, "Priya")  # May collide with 101
table.put(111, "Meera")  # May collide with 101 and 106

print(table.get(106))
table.delete(101)
table.display()

How the Chaining Implementation Works

The _hash() method converts a key into a valid bucket index. Each bucket contains a Python list of key-value pairs.

A collision does not overwrite existing data. The new pair is added to the same bucket and checked during future searches.

Average search, insertion, and deletion remain close to O(1) with a good distribution. Performance may degrade to O(n) when many keys enter the same bucket.

Hash Table Implementation in Python Using Open Addressing

Open addressing stores every element inside the table itself. Linear probing checks the next position when the preferred index is occupied.

class OpenAddressHashTable:
    _EMPTY = object()
    _DELETED = object()

    def __init__(self, capacity=8):
        if capacity <= 0:
            raise ValueError("Capacity must be greater than zero")

        self.capacity = capacity
        self.keys = [self._EMPTY] * capacity
        self.values = [None] * capacity
        self.size = 0

    def _hash(self, key):
        return hash(key) % self.capacity

    def _find_slot(self, key):
        start = self._hash(key)
        first_deleted = None

        for step in range(self.capacity):
            index = (start + step) % self.capacity
            stored_key = self.keys[index]

            if stored_key is self._EMPTY:
                if first_deleted is not None:
                    return first_deleted, False
                return index, False

            if stored_key is self._DELETED:
                if first_deleted is None:
                    first_deleted = index
                continue

            if stored_key == key:
                return index, True

        if first_deleted is not None:
            return first_deleted, False

        return None, False

    def put(self, key, value):
        """Insert a new key-value pair or update an existing key."""
        if (self.size + 1) / self.capacity > 0.7:
            self._resize(self.capacity * 2)

        index, found = self._find_slot(key)

        if index is None:
            self._resize(self.capacity * 2)
            index, found = self._find_slot(key)

        if not found:
            self.size += 1

        self.keys[index] = key
        self.values[index] = value

    def get(self, key):
        """Return the value associated with a key."""
        start = self._hash(key)

        for step in range(self.capacity):
            index = (start + step) % self.capacity
            stored_key = self.keys[index]

            if stored_key is self._EMPTY:
                break

            if stored_key is not self._DELETED and stored_key == key:
                return self.values[index]

        raise KeyError(f"Key not found: {key}")

    def delete(self, key):
        """Mark an entry as deleted without breaking probe chains."""
        start = self._hash(key)

        for step in range(self.capacity):
            index = (start + step) % self.capacity
            stored_key = self.keys[index]

            if stored_key is self._EMPTY:
                break

            if stored_key is not self._DELETED and stored_key == key:
                self.keys[index] = self._DELETED
                self.values[index] = None
                self.size -= 1
                return

        raise KeyError(f"Key not found: {key}")

    def _resize(self, new_capacity):
        old_keys = self.keys
        old_values = self.values

        self.capacity = new_capacity
        self.keys = [self._EMPTY] * new_capacity
        self.values = [None] * new_capacity
        self.size = 0

        for key, value in zip(old_keys, old_values):
            if key is not self._EMPTY and key is not self._DELETED:
                self.put(key, value)

    def display(self):
        for index, key in enumerate(self.keys):
            if key is self._EMPTY:
                entry = "EMPTY"
            elif key is self._DELETED:
                entry = "DELETED"
            else:
                entry = f"{key}: {self.values[index]}"

            print(f"Index {index}: {entry}")


# Example usage
table = OpenAddressHashTable(capacity=5)

table.put(101, "Visha")
table.put(106, "Priya")
table.put(111, "Meera")

print(table.get(111))
table.delete(106)
table.display()

Download HCL GUVI’s free Data Structures & Algorithms eBook and start mastering problem-solving skills that every top developer needs!

Collision in Hashing

A collision happens when two different keys are mapped to the same index in a hash table by the hash function. 

For example, if we use the hash function h(key) = key % 10 and have keys 101 and 111, both will produce the same index 1.

Since the table can’t store both at the same position, this creates a collision. Collisions are inevitable because the number of possible keys usually exceeds the number of available slots.

If collisions are not handled correctly, they may lead to data being overwritten or you may get an access error for the data. For this reason, all hashing strategies have a way to account for and handle collisions.

The two most common collision-handling strategies are the following:

• Open Addressing: All elements are kept in the hash table itself.
• Separate Chaining: Each index in the hash table maintains a linked list of keys that contain the same hash value.

Also Read: Is DSA Important for Placement in 2026?

Collision Handling Techniques

1. Open Addressing

In Open Addressing, every item is kept directly in the hash table itself. If there is a collision, the algorithm will find the next available slot in a predetermined sequence. No auxiliary data structure (like a linked list) is used for storing items. Everything is kept inside the table. 

There are three types of open addressing: 

• Linear Probing:

In this method, if there is a collision, the algorithm looks at the next slot in the sequence and checks that slot to see whether it is empty. 

• Formula: index = (hash + i) % table_size
• Disadvantage: it can create clustering, which is where several keys end up being grouped together. This can lessen the performance of a search.
• Quadratic Probing:

This function jumps in increasing squares instead of moving just one slot at a time (1, 4, 9, etc.). 

• Formula: index = (hash + i²) % table_size
• Advantage: quadratic probing creates less clustering than linear probing, and thus generally increases the speed of lookups.
• Double Hashing:

When a collision happens, the algorithm performs another hash value (from the hash value) to calculate how far to move next.

• Formula: index = (h1(key) + i*h2(key)) % table_size
• Advantage: this form reduces both primary and secondary clustering, which makes it the quickest of the three hashing types.

Also Read: Best DSA Roadmap Beginners Should Know

2. Separate Chaining

In the Separate Chaining approach, each slot in the hash table contains a linked list (or sometimes a different data structure, such as a dynamic array) that holds all the elements that share the same hash index. Instead of checking for another empty slot in the table, the collided elements are simply added to the same chain.

For example:

If both keys 101 and 111 hash to index 1, they are stored as follows:

Index 1 → [101 → 111]

Advantages:

• Simple and easy to understand and implement.
• Unlike linear probing, the hash table does not need to be resized often because the chains can grow dynamically.

Disadvantages:

• The downside is that it does require additional memory for the linked lists.
• In the worst case (when many elements collide to the same index) the search time can degrade to O(n) rather than O(1).
• Hash Function and Collision Resolution Comparison
• The time required to hash a string usually depends on its length. Therefore, hashing a key containing k characters normally takes O(k), even when the final table lookup is treated as O(1).

Hash Function and Collision Resolution Comparison

The time required to hash a string usually depends on its length. Therefore, hashing a key containing k characters normally takes O(k), even when the final hash-table lookup is described as an average O(1) operation.

Collision resolution methods such as chaining and open addressing apply to hash tables. Cryptographic hashing serves a different purpose and does not normally use probing or chaining to resolve collisions.

Open Addressing vs Chaining: Which Is Better and When?

Open addressing and separate chaining both resolve collisions. Neither method is universally better.

Choose Open Addressing When

Open addressing works well when:

• Memory overhead must remain low.
• The expected number of elements is known.
• Cache locality matters.
• The load factor can be controlled.
• Insertions and deletions are not highly unpredictable.

Linear probing is simple but may create primary clustering. Quadratic probing reduces primary clustering, while double hashing usually distributes probe sequences more effectively.

Choose Separate Chaining When

Separate chaining works well when:

• The table size changes frequently.
• The number of stored entries is difficult to predict.
• Frequent deletion is required.
• A load factor above 1 may occur.
• Simpler collision handling is preferred.

Chaining uses additional memory, but resizing is less urgent because each bucket can store multiple elements.

Which One Is Faster?

Open addressing can be faster at lower load factors because elements remain close together in memory.

Chaining can perform better when the table becomes crowded or receives unpredictable insertions. Hash quality, load factor, bucket implementation, and resizing policy matter more than the method name alone.

Load Factor and Rehashing

The load factor (λ) of a hash table quantifies the fullness of the table. The load factor is calculated as shown below:

Load Factor (λ) = Number of elements stored/Table size 

A low load factor indicates that there will be a high number of empty slots in the hash table and resulting in lower collisions, while higher load factors will result in more collisions and increased slowness. 

To keep efficiency + performance well and relatively low, many hashing utility libraries will set the load factor threshold to 0.7 (70% full). When the load factor threshold has been hit or exceeded, rehashing will be conducted. 

Rehashing means the library will create a new hash table that is larger than the old one by usually twice 2 size of the old hash table’ size and will insert the current hash table elements into the new hash table. This would ensure all elements are hashed anew through the past or newer improved hash function and allows for better distribution of the data, reduced number of collisions, and keeps the average performance time complexity of all three operations (inserting, deletion, search) at nearly O(1) from its past state while growing and size of the data in the dataset.

Simple Python Hashing Example

import hashlib

message = "Data Structures"
digest = hashlib.sha256(message.encode("utf-8")).hexdigest()

print(digest)

This code creates a digest. It does not provide a method for reconstructing the original message.

Simple Python Encryption Example

# Conceptual flow

plaintext = "Private message"
ciphertext = encrypt(plaintext, secret_key)
recovered_text = decrypt(ciphertext, secret_key)

Encryption must allow an authorized receiver to recover the original plaintext using the correct key.

Hashing vs Encryption: Key Difference

Hashing and encryption are often confused during technical interviews. They solve different security problems.

Also, Explore About 10 Best Data Structures and Algorithms Courses

Applications of Hashing in Data Structures

• Databases: databases utilize indexing, which is a method of fast data retrieval based on hashing.
• Password management software: Systems store passwords as hash codes for security.
• Compilers: Compilers use a technique called hash tables as an effective way to store a symbol table that contains names of previously defined variables and function names.
• Caches: Lookups of caches are accomplished through hash maps.
• Blockchain: Blockchain systems use cryptographic hash functions as a means to ensure data integrity.
• File systems: File systems use hashes as a means to efficiently traverse files in a folder or an organization system, as well as to identify duplicates.
• Search engines:  URL hashing is use to quickly retrieve a previously indexed web page quickly and efficiently.

If you found hashing fascinating, it’s time to take your DSA learning to the next level. Join HCL GUVI’s AI Software Development, co-created with IIT-M Pravartak, and master concepts like hashing, sorting, trees, and graphs with real-world projects and expert mentors.

Hashing Interview Questions Asked at Product Companies

The following questions represent common hashing patterns used in product-company interviews. The exact problem set changes according to the company, role, and interview level.

1. What Is Hashing?

Hashing converts a key into a hash value that determines where data should be stored or located.

2. What Is a Collision?

A collision occurs when two different keys map to the same hash-table index.

3. Can a Hash Function Completely Prevent Collisions?

A general-purpose hash function cannot prevent all collisions when the number of possible keys exceeds the available indexes.

Perfect hashing can avoid collisions for a known and fixed key set.

4. What Is the Average Time Complexity of a Hash Table?

Search, insertion, and deletion generally take average O(1) time.

Poor key distribution or excessive collisions may increase the worst-case complexity to O(n).

5. What Is Load Factor?

Load factor measures how full a hash table is.

Load Factor = Number of Stored Elements / Number of Buckets

A rising load factor usually increases collision frequency.

6. What Is Rehashing?

Rehashing creates a larger table and inserts the existing entries again using indexes calculated for the new capacity.

Existing indexes cannot simply be copied because the table size influences the hash calculation.

7. Why Must Keys Be Immutable?

Changing a key after insertion may change its hash value. The table may then search at a different index and fail to locate the entry.

Python therefore allows immutable values such as strings and tuples as dictionary keys but rejects mutable lists.

8. What Makes a Good Hash Function?

A strong hash function should be:

• Deterministic
• Fast to calculate
• Evenly distributed
• Sensitive to the complete key
• Resistant to patterns that create repeated collisions

9. How Is Hashing Different From Binary Search?

Hashing provides average O(1) equality lookup but does not naturally maintain sorted order.

Binary search provides O(log n) lookup on sorted data and supports ordered operations more naturally.

10. How Do Python Dictionaries Use Hashing?

Python dictionaries use hash values to locate key-value entries. Exact implementation details may change between Python versions, but keys must remain hashable and equality-compatible.

11. Why Must Equal Objects Have Equal Hash Values?

Hash tables first use the hash value to narrow the search location. Equal objects producing different hash values could be placed in different locations and treated as separate keys.

The rule is:

a == b  ⇒  hash(a) == hash(b)

Different objects may still share the same hash value.

12. How Would You Find Duplicate Elements Using Hashing?

Store each observed element inside a set. An element already present in the set is a duplicate.

def find_duplicates(values):
    seen = set()
    duplicates = set()

    for value in values:
        if value in seen:
            duplicates.add(value)
        else:
            seen.add(value)

    return duplicates


print(find_duplicates([1, 2, 3, 2, 4, 1]))

13. How Would You Solve the Two Sum Problem?

Store each value and its index inside a hash map. For every number, check whether its required complement has already appeared.

def two_sum(numbers, target):
    positions = {}

    for index, number in enumerate(numbers):
        complement = target - number

        if complement in positions:
            return [positions[complement], index]

        positions[number] = index

    return []


print(two_sum([2, 7, 11, 15], 9))

The algorithm takes O(n) time and O(n) additional space.

14. How Would You Group Anagrams?

Use a normalized representation of each word as the hash-map key.

from collections import defaultdict


def group_anagrams(words):
    groups = defaultdict(list)

    for word in words:
        key = tuple(sorted(word))
        groups[key].append(word)

    return list(groups.values())


print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))

Sorting each word gives O(k log k) processing for a word containing k characters.

15. How Would You Design an LRU Cache?

An LRU cache commonly combines:

• A hash map for O(1) key lookup
• A doubly linked list for O(1) ordering updates

The most recently used item moves to one end. The least recently used item remains at the opposite end and is removed when the cache reaches capacity.

16. How Would You Count Element Frequencies?

Use a hash map where each key represents an element and each value stores its count.

def count_frequencies(values):
    frequencies = {}

    for value in values:
        frequencies[value] = frequencies.get(value, 0) + 1

    return frequencies


print(count_frequencies(["a", "b", "a", "c", "b", "a"]))

17. What Happens During a Hash-Flooding Attack?

An attacker deliberately supplies keys that produce excessive collisions. Table operations may then degrade from expected O(1) to O(n).

Defences may include randomized hashing, collision-resistant table designs, input limits, and balanced collision buckets.

18. Why Are Cryptographic Hash Functions Not Always Ideal for Hash Tables?

Cryptographic hash functions prioritize collision resistance and security properties. They may require more computation than a fast non-cryptographic table hash.

Hash tables usually prioritize speed and distribution unless the environment requires protection from hostile input.

19. What Is Consistent Hashing?

Consistent hashing distributes keys across servers or cache nodes while minimizing the number of keys that move when a node joins or leaves.

It is commonly discussed in distributed cache, database-sharding, and load-distribution interviews.

20. Which Hashing Problems Should Candidates Practise?

Important practice patterns include:

• Two Sum
• Contains Duplicate
• Valid Anagram
• Group Anagrams
• Longest Consecutive Sequence
• Subarray Sum Equals K
• First Non-Repeating Character
• Top K Frequent Elements
• Isomorphic Strings
• LRU Cache
• Design HashMap
• Design HashSet

Strong candidates should explain why a hash map improves the solution, what extra memory it uses, and how collisions affect theoretical performance.

Wrapping it Up…

Hashing in Data structures is the key to fast data access, rapid searching, and efficient memory usage in today’s computing.

From storing passwords securely to performing fast database queries, hashing is present in almost every digital system you use. Studying hashing may help you design better algorithms, provide ideas for improving code performance, and certainly augment your foundations in computer science.

So next time you are thinking of searching through data, think of hashing, because now you don’t have to search!

Hope this blog made the concept of Hashing in Data structures simple, clear, and practical for your learning journey. Happy learning!

1. What is hashing in a data structure?

Hashing is a technique to map data into a fixed-size table using of a hash function to find, insert, and delete data quickly.

2. What is a hash function?

A hash function will take an input (key) and convert it into a hash value which is used as an index to store the data in a hash table.

3. What is a collision in hashing?

A collision occurs when two different keys have the same hash value or index.

4. How are collisions handled?

Collisions are handled through chaining, open addressing, linear probing, or double hashing.

5. What is the load factor?

A load factor is a measure of how full the hash table is, and when the load factor exceeds a certain amount, rehashing typically occurs to improve efficiency.