Hashing is an essential concept in data structures that plays a crucial role in various applications. It involves the use of a hash function to transform data into a fixed-size value, called a hash code or simply a hash. This hash code is used to index and retrieve data quickly from memory or storage.
Understanding Hashing
Hashing is primarily used for efficient data retrieval, as it offers constant time complexity for searching, inserting, and deleting elements. The process begins with the input data being passed through a hash function, which generates the hash code. The resulting hash code is then used as an index to store or retrieve the corresponding value.
The primary goal of hashing is to minimize collisions – situations where two different inputs produce the same hash code. Collisions can lead to ambiguity and slower retrieval times. Hash functions are designed to distribute the data evenly across available slots or buckets.
Types of Hashing
1. Division Hashing
In division hashing, the key (input) is divided by the table size, and the remainder obtained becomes the index for storage or retrieval. The table size should ideally be prime to reduce collisions and distribute data uniformly.
Example: Consider a table with 10 slots and three keys: 12, 25, and 38. Using division hashing, we calculate their respective indices as follows:
- Key: 12 → Index: 12 % 10 = 2
- Key: 25 → Index: 25 % 10 = 5
- Key: 38 → Index: 38 % 10 = 8
Therefore, the keys 12, 25, and 38 are stored at indices 2, 5, and 8 respectively.
2. Multiplication Hashing
Multiplication hashing involves multiplying the key with a constant value between 0 and 1 (typically chosen based on the golden ratio) and extracting the fractional part of the result. This fractional part is then multiplied by the table size to obtain the final index.
Example: Let’s consider a table with 10 slots and the key as 29. Using multiplication hashing, we can calculate its index as follows:
- Key: 29 → Multiplication factor: (29 * (√5 – 1) / 2) = 11.48
- Fractional part: (11.48 – floor(11.48)) = 0.48
- Index: Fractional part * Table size = (0.48 * 10) ≈ 4.8 → 4
Hence, the key value of 29 is stored at index 4.
3. Folding Hashing
Folding hashing involves dividing the key into equal-sized parts (except for possibly the last part), adding these parts together, and then taking the modulo of this sum with respect to the table size.
Example: Consider a table with ten slots and a key value of 12345 using folding hashing:
- Splits: 12, 34, and 5
- Sum of splits: 12 + 34 + 5 = 51
- Index: Sum of splits % Table size = 51 % 10 = 1
The key value of 12345 is stored at index 1.
In Conclusion
Hashing is a powerful technique that allows for efficient storage and retrieval of data. By using hash functions and appropriate hashing methods like division, multiplication, and folding hashing, we can minimize collisions and achieve constant time complexity for various operations. Understanding the different types of hashing techniques helps in selecting the most suitable method based on specific requirements.