Common Hash Functions in Development (Part 1)

Hash functions are foundational tools in software development, underpinning everything from data structures to cybersecurity. Whether you're working with Java’s HashMap, optimizing Redis performance, or securing user passwords, understanding how hash functions work—and why certain design choices are made—is critical for building efficient and secure systems.

This article explores the core principles of hash functions, their applications in data structures and cryptography, and real-world implementation details in systems like Java and Redis. We’ll also demystify common questions such as why Java uses 31 in string hashing, why Redis tolerates load factors greater than 1, and whether consistent hashing is truly useful.

By the end, you'll have a deeper grasp of how hash functions shape modern computing—and how to choose and use them wisely.

What Is a Hash Function?

A hash function—also known as a hash algorithm or散列函数—is a method that converts input data of arbitrary size into a fixed-size value, typically a string of characters or an integer. This output, called a hash value, hash code, or digest, acts as a unique "fingerprint" of the original data.

According to Wikipedia, a good hash function should:

• Be deterministic: The same input always produces the same output.
• Exhibit the avalanche effect: A small change in input leads to a significant change in output.
• Be collision-resistant: It should be computationally difficult to find two different inputs that produce the same hash.
• Be one-way (pre-image resistant): Given a hash, it should be infeasible to reverse-engineer the original input.

These properties make hash functions indispensable across multiple domains—from accelerating data lookups to ensuring message integrity.

👉 Discover how secure hashing powers next-gen digital platforms

Key Applications of Hash Functions

Data Structures: Speeding Up Lookups

In programming languages, hash functions enable high-performance data structures like hash tables, hash maps, and dictionaries. These structures map keys to values using a hash function to compute an index into an array of buckets or slots.

The goal? Achieve average-case O(1) time complexity for insertions and lookups by trading space for speed. For example:

• Java’s HashMap
• Python’s dict
• Redis’ internal dictionary (dict)

In this context, speed and uniform distribution matter more than cryptographic security. Developers often prioritize fast computation and low collision rates over resistance to deliberate attacks.

Cryptography: Ensuring Integrity and Security

In security-critical applications, hash functions serve as cryptographic checksums. They ensure data hasn’t been tampered with and protect sensitive information like passwords.

Common uses include:

• Password storage: Storing hash(password + salt) instead of plaintext.
• Digital signatures: Verifying authenticity via message digests.
• Blockchain and token systems: Securing transaction integrity.
• Session tokens: Generating secure CSRF or JWT tokens.

Here, collision resistance and pre-image resistance are paramount. Algorithms like SHA-256 and SM3 are preferred over faster but weaker ones like MD5.

Hash Functions in Data Structures

At the heart of many data structures lies the hash table, which stores key-value pairs using a hash function to determine where each entry should reside.

Despite their efficiency, hash tables face one fundamental challenge: collisions—when two distinct keys produce the same hash index.

Collision Resolution Techniques

Several strategies exist to handle collisions:

• Chaining (linked lists): Each bucket holds a list of entries. Used by Java’s HashMap and Redis’ dict.
• Open addressing: When a collision occurs, probe for another available slot (linear, quadratic, or double hashing).
• Rehashing: Use a secondary hash function if the first fails.
• Cuckoo hashing: Evict conflicting entries and relocate them.

Java and Redis both use chaining with linked lists, switching to balanced trees under heavy collision pressure—a strategy we’ll explore shortly.

Popular General-Purpose Hash Algorithms

Not all hash functions are created equal. Some prioritize speed; others emphasize randomness or low collision rates.

Common non-cryptographic hash functions include:

• MurmurHash: Extremely fast, excellent distribution. Used in Cassandra, HBase, and Redis HLL.
• FNV (Fowler–Noll–Vo): Simple and fast, uses prime numbers (e.g., 16777619) for mixing bits.
• DJB2 (a.k.a. "Times 33"): Fast string hashing; used in legacy systems like Perl and early Redis.
• SipHash: Designed for short strings and DoS protection; now default in Redis 4.0+.
• CityHash / FarmHash: Google-developed variants optimized for performance on modern CPUs.

While MurmurHash dominates benchmarks for speed and quality, newer systems increasingly adopt SipHash due to its resistance to hash flooding attacks.

👉 Learn how advanced hashing enhances blockchain security

Why Multiply by 31 or 33 in String Hashing?

You may have noticed that Java’s String.hashCode() multiplies each character by 31:

h = 31 * h + str.charAt(i);

Why 31? Because it's an odd prime—and more importantly, because it enables compiler optimization via bit-shifting:

31 * i == (i << 5) - i

This trick speeds up multiplication on older processors.

But why not 33? Interestingly, 33 = 32 + 1 = (1 << 5) + 1, so DJB2 hash uses:

hash = ((hash << 5) + hash) + c; // i.e., hash * 33 + c

Both 31 and 33 offer good dispersion with minimal computational cost. Empirical tests show:

• 31 and 33 yield similar collision rates (~0.13–0.14%)
• Larger primes like 127 reduce collisions further but slow down computation

Thus, 31 strikes a balance between performance and effectiveness, making it ideal for general-purpose string hashing.

Java’s Hash Implementation Deep Dive

Default Object.hashCode(): Not Based on Memory Address

Contrary to popular belief, Java’s default hashCode() does not return the object’s memory address. Instead, it generates a pseudorandom value using one of several strategies controlled by the JVM (-XX:hashCode=n):

This randomness helps mitigate hash collision denial-of-service (DoS) attacks, where malicious users craft inputs that all map to the same bucket, degrading performance from O(1) to O(n).

Once computed, the hash is cached in the object’s header for future use.

Evolution from Java 7 to Java 8

Java 7 introduced randomized hashing via hashSeed to defend against DoS attacks. However, this caused issues with serialization and debugging due to non-deterministic behavior.

Java 8 simplified the approach:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

This single XOR operation mixes high and low bits effectively while avoiding costly rotations. Combined with the switch from linked lists to red-black trees after eight collisions, it provides robust protection against worst-case scenarios without sacrificing predictability.

Why Convert to Red-Black Tree After 8 Collisions?

In Java 8+, when a bucket in HashMap accumulates eight or more entries, the linked list is converted into a red-black tree.

Why eight? The JDK documentation cites probabilistic reasoning based on the Poisson distribution:

Under random hash codes, bin sizes follow a Poisson distribution with parameter ~0.5.

Expected frequency of bins with k elements:

• k=0: 60.6%
• k=1: 30.3%
• k=2: 7.6%
• ...
• k=8: <0.000006%

The chance of encountering eight colliding keys is less than 1 in 10 million under normal conditions.

So why do it at all?

Because this change isn’t about everyday performance—it’s a defense mechanism against algorithmic complexity attacks. The red-black tree ensures worst-case lookup time remains O(log n), preventing attackers from overwhelming the system with pathological input.

Tree nodes consume about twice as much memory as regular nodes, so this conversion only makes sense under extreme conditions.

Why Are Hash Table Sizes Powers of Two?

Unlike traditional advice suggesting modulus with prime numbers, Java’s HashMap uses power-of-two table sizes. Why?

Because it allows fast indexing via bitwise AND:

index = (n - 1) & hash;

This replaces expensive modulo operations with efficient bit masking—critical for high-throughput applications.

To compensate for potential poor distribution (especially in lower bits), Java applies additional bit mixing:

h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);

This brings the behavior closer to multiplicative hashing while retaining speed advantages.

Is Load Factor 0.75 Optimal?

Java’s HashMap resizes when the load factor exceeds 0.75, meaning the number of entries reaches three-quarters of the bucket count.

This value is empirical—balancing memory usage and collision probability. At 0.75:

• Space is used efficiently
• Collision rate stays manageable
• Resize frequency remains acceptable

But is it mandatory?

No. For memory-constrained environments, you might set a higher load factor (e.g., 2–4), accepting slower lookups (~O(1+a)) in exchange for reduced memory footprint.

Benchmarking shows:

• With load factor = 4, memory usage drops to ~1/8
• Query performance slows by ~1.4x–2.8x

For GC-sensitive applications or caches with predictable access patterns, this trade-off can be worthwhile.

Redis vs. Java: Divergent Design Philosophies

Redis takes a different approach:

Redis allows load factors greater than 1 because:

• It supports incremental rehashing, reducing pause times.
• Its dictionaries can shrink as well as grow.
• It prioritizes responsiveness over strict O(1) guarantees.

Moreover, Redis migrated from MurmurHash2 to SipHash to prevent hash flooding attacks—proving that even fast non-cryptographic hashes need security considerations.

FAQ: Common Questions About Hash Functions

Q: Is consistent hashing used in Redis Cluster?

A: No. Official Redis Cluster uses CRC16(key) mod 16384 to assign keys to slots—not consistent hashing. Tools like Twemproxy or client libraries may implement it, but native Redis does not rely on it.

Q: Can MD5 still be used securely?

A: Only in limited contexts—like checksums for non-security purposes. For passwords or digital signatures, use SHA-256 or better. MD5 is vulnerable to practical collision attacks.

Q: What is SipHash good for?

A: SipHash excels at protecting against DoS attacks in hash tables handling untrusted input (e.g., web servers parsing form data). It's fast for short strings and cryptographically strong enough for authentication tags.

Q: Why did Java remove random hashSeed in version 8?

A: While effective against DoS attacks, random seeds broke assumptions about object equality across JVM instances and caused issues in distributed systems and debugging tools.

Q: How does salting prevent rainbow table attacks?

A: Salting adds unique random data to each password before hashing. Since every user has a different salt, precomputed tables become ineffective unless attacker generates one per salt—which defeats the purpose.

Q: Does Bloom Filter ever give false positives?

A: Yes—it may incorrectly indicate an element exists (false positive) but never incorrectly says it doesn't (no false negatives). Accuracy improves with more bits and optimal hash functions like Murmur3.

👉 Explore how modern platforms leverage hashing for scalability

Final Thoughts

Hash functions are far more than simple utilities—they’re foundational building blocks shaping how we store, retrieve, and secure data.

From Java’s careful tuning of HashMap to Redis’ aggressive DoS defenses with SipHash, every design choice reflects trade-offs between speed, memory, security, and reliability.

Understanding these nuances empowers developers to make informed decisions—whether optimizing application performance or hardening systems against attack.

As distributed systems evolve and threats grow more sophisticated, expect continued innovation in hashing techniques—especially at the intersection of performance and security.

Core Keywords:
hash function, Java HashMap, Redis dict, collision resolution, SipHash, load factor, consistent hashing, cryptographic hash