Extended Concepts in Arrays and Hash Tables
1. Array Processing
Array processing means performing operations on the elements of an array. Since arrays are stored in sequential memory, we can easily access and manipulate them.
Common Array Processing Tasks:
- Traversal – visiting each element.
- Insertion – adding a new element (needs shifting).
- Deletion – removing an element (needs shifting).
- Searching – linear or binary search.
- Sorting – arranging elements (bubble sort, quick sort, etc.).
int arr[5] = {10, 20, 30, 40, 50};
for(int i=0; i<5; i++) {
printf("%d ", arr[i]);
}2. Sparse Matrices
A sparse matrix is a matrix with many zero values. Instead of storing all values, we store only non-zero values with their row and column positions.
Compact Representation:
(Row, Col, Value)
(0, 0, 5)
(1, 1, 8)
(2, 3, 3)
(3, 1, 6)3. Transpose of Sparse Matrices
Transpose means flipping rows into columns. For sparse matrices, we just swap row and column values in the compact form.
Example:
Original: (0,1,2) → Transpose: (1,0,2)4. Hash Tables (Review)
A hash table stores key-value pairs using a hash function to compute the index.
| Roll No | Name |
|---|---|
| 101 | Amit |
| 102 | Riya |
| 103 | Neha |
5. Direct Address Tables
In a direct address table, the key itself is used as the index. No hash function is needed.
Advantage: Very fast (O(1)). Disadvantage: Wastes memory if key range is large.
6. Hash Functions
A hash function converts a key into an index. A good hash function is fast, uniform, and minimizes collisions.
Example: Division method: index = key % table_size
7. Open Addressing
When two keys map to the same index (collision), open addressing finds another slot.
- Linear Probing – check next index.
- Quadratic Probing – jump in squares (1², 2², 3²).
- Double Hashing – use another hash function.
8. Perfect Hashing
Perfect hashing is when the hash function produces no collisions. Possible only if the set of keys is fixed and known in advance.
Example: Compiler keyword lookup (if, else, while, for).
Final Summary
- Array Processing: Traversal, insertion, deletion, searching, sorting.
- Sparse Matrices: Store only non-zero values.
- Transpose: Swap row and column in compact form.
- Hash Tables: Key-value pairs using hash functions.
- Direct Address Tables: Keys used directly as indexes.
- Hash Functions: Generate indexes, should minimize collisions.
- Open Addressing: Handles collisions by probing.
- Perfect Hashing: Collision-free hashing for fixed key sets.
Hi I am Avinash S. working as teacher and blogger, my aim to start this blog is to make the most challenging topics easy for everyone to learn. I’m always open for feedback and you can send me your review about this blog.