Real-World Uses: Caches, Maps, Sets

Explore how hash tables are specialized into fundamental building blocks across production Android and distributed systems.

1. Sets: Mathematical Uniqueness via Hash Keys

A Set is an Abstract Data Type that stores unique elements with zero duplicates.

How is HashSet implemented under the hood? A HashSet is simply a HashMap where values are dummy placeholder objects!

Copy code// Conceptual implementation of HashSet
class MyHashSet<E> {
    private val PRESENT = Any() // Shared dummy value
    private val map = HashMap<E, Any>()

    fun add(element: E): Boolean = map.put(element, PRESENT) == null
    fun contains(element: E): Boolean = map.containsKey(element)
    fun remove(element: E): Boolean = map.remove(element) != null
}

Every set operation (add, remove, contains) runs in O(1) time by delegating directly to hash table keys.

2. Android Memory Optimization: SparseArray

In standard Java/Kotlin:

Copy codeval map = HashMap<Int, String>()

Because Java generics require objects, every primitive int key must be autoboxed into an Integer object:

• Integer overhead: 16-byte object header + 4-byte payload = 24 bytes per key!
• Plus Map.Entry node overhead: 32 bytes!

Android's Solution: SparseArray

Android provides custom memory-optimized collections in the platform SDK:

• SparseArray<E> (maps primitive int → Object)
• SparseIntArray (maps primitive int → int)
• LongSparseArray<E> (maps primitive long → Object)

Copy codeSparseArray Internal Structure (No autoboxing, no linked nodes!):
mKeys:   [ 10,  25,  40,  99 ] (Contiguous primitive IntArray)
mValues: [ obj1, obj2, obj3, obj4 ] (Contiguous Array of Object pointers)

SparseArray trades O(1) hashing for O(log n) binary search across contiguous arrays, saving hundreds of kilobytes of RAM on mobile devices.

3. Distributed In-Memory Caches (Redis & Memcached)

At server scale, Redis is essentially a massive, thread-safe, network-accessible Hash Table:

• Stores billions of key-value pairs in RAM.
• Employs progressive background rehashing to avoid blocking the server while resizing large tables.

Summary

• HashSet is implemented directly on top of HashMap keys with dummy values.
• Android provides SparseArray to eliminate the heavy autoboxing overhead of HashMap<Int, V>.
• In-memory key-value databases like Redis are distributed hash tables.