liveBook · Manning

Avalanche effect

As explained in Clojure: The Essential Reference

The avalanche effect is a hashing property in which a small input change alters at least about half of the output bits.

The avalanche effect measures how widely a hashing algorithm spreads input changes across its output. A strong hash changes at least about half of its output bits when the input changes. section 6.6

Collection hashing improves this behavior by mixing the accumulated bits after processing the items. Clojure exposes mix-collection-hash for this final step when implementing a compatible hashing function. section 6.6

Hash changes for nearby inputs

Clojure’s hash produces widely different integers for adjacent long keys: (map hash [-3 -2 -1 0 1 2]) yields (-1797448787 -1438076027 1651860712 0 1392991556 -971005196), unlike their small hashCode values (2 1 0 0 1 2). section 6.6

Listing 6.6. → Hashing function
(hash [x])
(hash-ordered-coll [coll])
(hash-unordered-coll [coll])
(mix-collection-hash [hash-basis count])

Browse the hashing API, including hash, ordered and unordered collection hashing, and the final mixing function. section 6.6

How Clojure: The Essential Reference covers it

How deep it goes
Defines the bit-change property and identifies final bit mixing, without deriving the underlying mathematics.
Examples
Contrasts hashCode and hash outputs for nearby numeric keys and composite collection keys.
What you can do after
Evaluate hashing behavior and apply a final mixing step when implementing collection-compatible hashes.
How it connects
Connects hashing with hash functions, Murmur3, hash-unordered-coll, and mix-collection-hash.
Cover of Clojure: The Essential Reference
liveBookmanning.com
Read Clojure: The Essential Reference on liveBook Get the book at manning.com

This explainer was generated by Manning's knowledge graph from the text of Clojure: The Essential Reference. The section links point to the parts of the book it draws on.