Hash Functions Overview

Hash Functions Overview

• Hash functions transform input data (keys) into a fixed-size string of characters, which is typically a numerical value.
• Common methods of generating hash values include Division, Mid Square, Folding, and Multiplication.

Division Method

• Simple and efficient, calculates hash using remainder from dividing key k by table size M: h(K) = k mod M.
• Best performance when M is a prime number to ensure uniform key distribution.
• Example: For k = 12345 and M = 95, h(12345) = 90; for k = 1276 and M = 11, h(1276) = 0.
• Pros: Quick computation; works for any M.
• Cons: Poor performance with consecutive keys; requires careful selection of M.

Mid Square Method

• Involves squaring the key and extracting the middle digits as the hash value: h(K) = h(k²).
• Example: For k = 60; 60 x 60 = 3600, extract middle digits yields h(60) = 60.
• Pros: Utilizes all digits of the key for a better hash value; less affected by the original key’s digit distribution.
• Cons: Limited by key size; potential for collisions.

Folding Method

• Divides key k into parts, sums them to generate the hash: h(K) = s = k1 + k2 + ... + kn.
• Example: For k = 12345, split into k1 = 12, k2 = 34, k3 = 5; s = 12 + 34 + 5 = 51.
• Allows for different sized parts based on table size.

Multiplication Method

• Uses a constant A (0 < A < 1) to compute the hash: h(K) = floor(M * (kA mod 1)).
• Example: For k = 12345, A = 0.357840, and M = 100; results in h(12345) = 53.
• Pros: Suitable for various values of A; quick with powers of two for M.
• Cons: Requires careful selection of A for optimal results.

Properties of a Good Hash Function

• Efficient computation.
• Uniform key distribution to reduce collisions.
• Low load factor to maintain performance.

Collision Handling Methods

• Separate Chaining: Each cell in the hash table points to a linked list of records sharing the same hash value, requires extra memory.
• Open Addressing: Alternative slots are sought within the table for keys colliding at the same hash index.

Open Addressing Techniques

• Quadratic Probing: Uses a quadratic formula to find next slot upon collision: H + 12, H + 22, H + 32, etc..
• Double Hashing: Employs two hash functions to resolve collisions, using the form h(k, i) = (h1(k) + i * h2(k)) % n.

Load Factor

• Defined as Total elements in hash table / Size of hash table.
• A high load factor indicates the need for rehashing to maintain efficiency.

Rehashing

• Involves expanding the hash table (commonly doubling its size) when the load factor exceeds a threshold (default 0.75), redistributing keys to maintain performance.

Applications of Hash Structures

• Hashes are utilized for indexing in databases, disk data structures, and implementation of objects in programming languages.
• Real-time uses include cache mapping, password verification, cryptographic processes, and pattern matching algorithms.

Advantages and Disadvantages

• Advantages: Efficient synchronization, constant time complexity for average operations (search, insert, delete).
• Disadvantages: Inefficiency due to collisions, unmanageable colliding scenarios for large key sets, and lack of support for null values.

Conclusion

• Hashing enhances efficiency in data retrieval, providing a structured way to quickly locate items in large datasets without linear searches.