Thanks for sharing that experience - it's a perfect illustration of why understanding the property matters more than knowing the technique.
The table size red herring is really common. When you're hitting performance issues with hashing, the instinct is "make the table bigger" or "use a better hash function." But if the bottleneck is O(n) rehashing on every update, no table size fixes that. You need the operation itself to be O(1).
What's elegant about the involution framing is it makes the solution discoverable. Once you ask "what operation lets me undo without tracking history?", XOR emerges naturally. It's not a trick you have to memorize — it's the answer to a well-posed question.
Thanks for sharing that experience - it's a perfect illustration of why understanding the property matters more than knowing the technique.
The table size red herring is really common. When you're hitting performance issues with hashing, the instinct is "make the table bigger" or "use a better hash function." But if the bottleneck is O(n) rehashing on every update, no table size fixes that. You need the operation itself to be O(1).
What's elegant about the involution framing is it makes the solution discoverable. Once you ask "what operation lets me undo without tracking history?", XOR emerges naturally. It's not a trick you have to memorize — it's the answer to a well-posed question.