= Key equality
{title2=$x\sim y$}
The <equivalence relation> used to decide whether two keys name the same record. A <hash function> must respect <key equality>; a <hash collision> does not establish <key equality>.
The choice of <key equality> is part of the map's meaning. In the one-value-per-key policy of <hash table>, one record represents each stored <equivalence class> of keys: `put(k,v)` updates an existing equal key and adds a record only if no equal key is present. A collection that deliberately retains repeated equal keys has a different policy; its load count must count those extra records too. Repeated calls and distinct stored records are different quantities.<6.006 Introduction to Algorithms, Fall 2011 by Massachusetts Institute of Technology, 6.006 course staff/Lecture 8: Hashing I>[6.006 Introduction to Algorithms, Fall 2011 by Massachusetts Institute of Technology, 6.006 course staff; p. 1, Dictionary Problem: distinct keys or replacement on repeated insertion]{ref}
For an original example, restrict keys to two-letter <strings> using letters `A` through `Z` or `a` through `z`. Declare two keys equal when replacing every uppercase letter by its lowercase counterpart gives the same <string>. Assign each letter its position $1,\ldots,26$ in the alphabet, ignoring case, and define the bucket-index <hash function> as the sum of the two positions modulo $8$, using <modular arithmetic>. Then `AB` and `ab` are equal keys and both select <hash bucket> $3$. Key `ba` also selects <hash bucket> $3$ because $2+1=3$, but is unequal to `ab`: order still matters. Starting empty, `put(AB,7)`, `put(ab,9)`, `put(ba,4)` leave two records, with values $9$ for the `ab` <equivalence class> and $4$ for `ba`; the <hash table load factor> is $2/8=1/4$, not $3/8$.
The compatibility rule is one-way: $x\sim y\Rightarrow h_m(x)=h_m(y)$. Otherwise a lookup using an equal spelling could search a different <hash bucket> and incorrectly report absence. Equal indices merely allow a <key equality> check. Both the <equivalence relation> and the <hash function> must stay consistent while records are stored; changing equality-relevant key contents can invalidate the lookup rule. The Java contract imposes these consistency and equality requirements on `equals` and `hashCode`.<Java Platform, Standard Edition 25 API Specification by Oracle/Object (Java SE 25 & JDK 25)>[Java Platform, Standard Edition 25 API Specification by Oracle; Method Details, equals equivalence-relation contract and hashCode general contract]{ref}
Back to article page
