Concept of Hashing and Hash Functions

A Hash Table (or Hash Map / Dictionary) is a data structure that implements an associative array abstract data type, mapping keys to values. It provides near-instantaneous, average O(1) constant time for search, insertion, and deletion.

At the core of this magic lies the Hash Function.

What is Hashing?

Hashing is the process of transforming any arbitrary-sized input (string, object, image, file) into a fixed-size integer value called a hash code (or hash value).

Copy codeKey ("user_1024") ---> [ Hash Function ] ---> Hash Code (3928174)
                              |
                              v Modulo Array Capacity
                        Bucket Index (6)

The Two-Step Index Resolution

To store a key-value pair in a hash table array:

1. Hash Code Generation: Compute an integer from the key:

   h = hashCode(key)

2. Bucket Compression (Modulo): Map the large integer into a valid array index between 0 and capacity - 1:

   Index = |h| mod Capacity

In high-performance systems where capacity is a power of two (2ᵏ), modulo is replaced by a bitwise AND:

Index = h & (Capacity - 1)

Properties of an Effective Hash Function

Not all functions that return integers are good hash functions. A production-grade hash function must satisfy four critical criteria:

1. Determinism: The same key must always produce the exact same hash value throughout the application's runtime.
2. Uniform Distribution: Keys must be evenly scattered across all available buckets to minimize collisions.
3. Speed: Computing the hash must take O(1) time and minimal CPU cycles.
4. Avalanche Effect: A change in a single bit or character of the key should result in a drastically different hash value.

Hash Codes in Java and Kotlin: The equals() Contract

In Kotlin and Java, every object inherits equals() and hashCode() from Any/Object. There is a strict legal contract between them:

If two objects are equal according to equals(), their hashCode() MUST be identical.

Copy codeclass Employee(val id: Int, val name: String) {
    override fun equals(other: Any?): Boolean {
        if (this === other) return true
        if (other !is Employee) return false
        return id == other.id && name == other.name
    }

    // Correct: Incorporates the same fields used in equals()
    override fun hashCode(): Int {
        var result = id
        result = 31 * result + name.hashCode()
        return result
    }
}

If you override equals() without overriding hashCode(), two identical employee objects will land in different hash buckets, breaking HashMap.get() and HashSet.contains()!

Summary

• Hashing maps arbitrary keys to fixed integer hash codes.
• Bucket Index is determined via modulo or bitwise masking: hash & (capacity - 1).
• A good hash function is deterministic, uniform, and fast.
• Always maintain the equals/hashCode contract when using custom classes as map keys.