Hash collision
A hash collision occurs when distinct inputs to a hash function produce the same hash value or map to the same hash-table location.
Grokking Algorithms, Second Edition
A hash collision occurs when distinct keys produce the same hash value or table position.
- How it is used
- Explains why hash tables need collision handling and how collisions influence lookup, insertion, and deletion performance.
- How deep it goes
- Defines collisions, demonstrates linked-list chaining, and connects crowding to O(n) worst-case behavior without implementing hash tables.
- Examples
- Uses apples, avocados, and bananas sharing alphabetic slots, plus hash-function distribution exercises involving names, battery sizes, and book titles.
- What you can do after
- Diagnose collision-related slowdowns by checking hash-function distribution and load factor, while relying on built-in hash-table implementations.
Read how Grokking Algorithms, Second Edition explains hash collision →
Clojure: The Essential Reference
A hash collision occurs when distinct keys produce the same hash-table index or hash value.
- How it is used
- Explains how hashing choices affect map keys, composite-key efficiency, and Java interoperability.
- How deep it goes
- Contrasts Java hashCode with Clojure hash through concrete outputs, but stops short of explaining hash-table bucket algorithms.
- Examples
- Uses colliding longs and composite sets, then compares Java hashCode outputs with Clojure hash outputs.
- What you can do after
- Evaluate key-hashing behavior and choose Clojure collection hashing when Java hashCode produces frequent collisions.
Read how Clojure: The Essential Reference explains hash collision →
100 Java Mistakes and How to Avoid Them
- How it is used
- Explains why collisions and mutable collection keys can make HashSet membership checks fail.
- How deep it goes
- Demonstrates crafted collisions, bucket treeification, and mutation failure while stopping short of general collision algorithms.
- Examples
- Uses StringBuilder objects, a deliberately colliding bucket, and post-insertion mutation to expose lookup failure.
- What you can do after
- Diagnose/debug collection lookups by checking key mutation, hash collisions, and inconsistent equals() and compareTo() behavior.
Read how 100 Java Mistakes and How to Avoid Them explains hash collision →
Software Security for Developers
A hash collision occurs when two different inputs produce the same hash value.
- How it is used
- Explains why cryptographic hashes must resist attackers finding different inputs with the same output.
- How deep it goes
- Defines collisions and collision resistance, but defers the mathematical design and assessment of secure hash functions.
- Examples
- Uses SHA-256 values for lowercase and uppercase letters and a large disk image to show fixed-size outputs.
- What you can do after
- Evaluate hash-function choices and avoid designing custom cryptographic hash functions.
Read how Software Security for Developers explains hash collision →
Related concepts
- hash functionaddressed by · A hash function deterministically maps input data to a value in a bounded output range, commonly for indexing, lookup, comparison, or integrity checking.
- birthday attackaddressed by · A birthday attack is a collision-finding method that generates approximately the square root of the hash output space to obtain a substantial probability of matching digests for distinct inputs.
- false positiveproduces · A false positive is a result that incorrectly indicates a condition or class is present when it is absent.
- machine learningaddressed by · Machine learning is a field of computational methods in which systems learn patterns or relationships from data to make predictions, decisions, or other outputs.
- duplex mismatchproduced by · A duplex mismatch is a link condition in which two connected interfaces use different duplex settings or incompatible autonegotiation behavior.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.