Page 97 - Data Structures Handout_Neat

9.2 Hash Functions

A hash function is the mathematical core of hashing. It takes an input (called a key)

and produces a fixed-size integer value, known as the hash code. This hash code is then used
as an index in a hash table, allowing data to be stored and retrieved efficiently. The

effectiveness of hashing depends heavily on the quality of the hash function. A poorly

designed hash function can lead to excessive collisions, wasted memory, and degraded

performance, while a well-designed hash function ensures uniform distribution of keys and

efficient operations.
Hash functions are not only used in data structures but also in cryptography,

networking, and security. For example, cryptographic hash functions like SHA-256 are used to

verify data integrity and secure passwords. In contrast, simple hash functions like division or
multiplication methods are used in hash tables for fast lookups.

9.2.1 Properties of Good Hash Functions

A good hash function should satisfy several properties:

• Uniform Distribution: Keys should be spread evenly across the hash table to
minimize collisions.

• Determinism: The same input must always produce the same hash value.

• Efficiency: The function should be fast to compute, even for large inputs.

• Low Collision Probability: Different inputs should rarely produce the same hash

value.
• Scalability: The function should work well regardless of the size of the dataset.

9.2.2 Simple Hash Functions (Division, Multiplication)

The simplest hash functions are based on arithmetic operations.
• Division Method: The key is divided by the table size, and the remainder is used

as the index.

• Multiplication Method: The key is multiplied by a constant fraction, and the
fractional part is scaled to the table size.

97