Hashing

 

🔐 Hashing in Data Structures

✅ What is Hashing?

Hashing is a technique used to uniquely identify and access data using a key. It transforms an input (or key) into a fixed-size value called a hash code or hash value, typically for efficient searching, insertion, and deletion in hash tables.

🧮 Example Scenario

Suppose you want to store student records by roll number:

  • Traditional structures like arrays or linked lists might need linear search.

  • With hashing, you compute a hash index for each roll number and directly access it in O(1) average time.

🔑 What is a Hash Function?

A hash function is a function h(k) that takes a key k and returns an index in the hash table.

➕ Example:

plaint
h(k) = k % m

Where:

  • k = key

  • m = size of the hash table

Example:
For key 2025 and table size 10:
h(2025) = 2025 % 10 = 5
→ Store the item at index 5.

⭐ Desirable Properties of Hash Functions

  1. Deterministic

    • Same input always produces the same output.

    • h(123) = 3 must always return 3.

  2. Uniformity

    • Distributes keys evenly across the table to avoid clustering.

  3. Fast Computation

    • Should be computationally simple and quick to evaluate.

  4. Minimize Collisions

    • A collision occurs when two keys map to the same index.

    • Good hash functions minimize this risk.

  5. Avalanche Effect (in cryptographic hashing)

    • A small change in input should produce a significantly different hash (not critical in basic DS applications, but important in cryptography).

🔄 Handling Collisions

Common methods to resolve hash collisions:

1. Chaining

  • Use a linked list at each index to store multiple keys.

2. Open Addressing

  • Find the next available slot by probing:

    • Linear Probing: h(k) + i

    • Quadratic Probing: h(k) + i²

    • Double Hashing: Use a second hash function.

📌 Summary Table

TermDescription
Hashing    Technique to map data to a fixed-size table
Hash Function        Function to compute index from a key
Collision    Two keys hash to the same index
Chaining    Use linked lists to resolve collisions
Open Addressing    Find alternate slots on collision

Comments

Post a Comment

Popular posts from this blog

Data Structures and Algorithms PCCST303 KTU 2024 Scheme- Dr Binu V P

About Me Syllabus and evaluation scheme  1.Basic Concepts of Data Structures     Data structures and data abstraction     Time and Space Complexity     Asymptotic Analysis and Asymptotic Notations     Best case, Worst case and Average Case Analysis of Algorithms     Frequency Count Method of Algorithm Analysis     Polynomial Representation using arrays      Polynomial Addition using arrays      Sparse Addition and Transpose     Stacks     Multi Stacks      Queue using array      Circular Queue using array      Double ended Queue using array     Infix to postfix and postfix evaluation     Infix to prefix and prefix evaluation    2.Linked List and Memory Management          Self Referential Data Structures     Dynamic Memory Allocation in C     Singly Linked...
Read more

Performance Analysis - Time and Space Complexity

Image
  📚 Performance Analysis  Performance analysis means studying how efficient an algorithm or data structure is. Mainly, we check two things: Time Complexity — How much time (number of operations) the algorithm takes. Space Complexity — How much memory (space) the algorithm uses. ✅ Goal : To predict how the algorithm will behave as the input size grows without running the code. 📍 1. Time Complexity Measures the amount of time an algorithm takes to complete. It is expressed as a function of the input size n . We usually use Big-O notation (e.g., O(n), O(log n), O(n²)) to express it. ⏳ Why it matters? Because we want algorithms that are fast even for large inputs . Example for Time Complexity: Suppose we have a simple loop: for ( int i = 0 ; i < n; i++) { printf ( "%d " , i); } The loop runs n times . Each printf is a constant-time operation. So, Time Complexity = O(n) (linear time). Types of Common Time Complexities...
Read more

Data Structures and Data Abstraction

  What is a Data Structure? A data structure is a way to organize, manage, and store data so that it can be used efficiently . It defines how data is arranged in memory and how operations like insertion , deletion , searching , and updating can be performed. In simple words: Data structures are like containers that hold data together in a certain format so that computers can easily access and modify them.   More formally   "A data structure is a mathematical and logical model of a particular organization of data. It describes the relationship among the data elements, and the operations that can be performed on them." ➔ Key points: Organization of data. Logical relationship between data elements. Set of operations that can be applied (like insert, delete, search, etc.). Key Points about Data Structures: They help in organizing large amounts of data easily. They improve the efficiency of algorithms. They decide how fast and efficient prog...
Read more