Software Bits Newsletter • 206 implied HN points • 14 Jan 26
- XOR is an involution: applying the same XOR twice cancels it out, so adding and removing an element use the same operation and let you update combined hashes in O(1).
- Zobrist hashing leverages XOR to update a chessboard hash with only a few XORs per move, enabling fast transposition-table lookups and huge search speedups; collisions are possible but usually acceptable or verifiable.
- More generally, pick the algebraic tool that matches your needs — use involutions like XOR for O(1) incremental updates when collisions are tolerable, rolling linear hashes for sliding windows, or Merkle trees when cryptographic integrity is required.