Zobrist hashing
A way to hash board positions by XORing together one random number per piece and square — and updating the hash with two XORs per move.
At startup a 64-bit random number is generated for every combination of piece type and square, plus a few for side to move and special rights such as castling. A position's hash is the XOR of the numbers for every piece on the board. Since XOR is its own inverse, moving a piece means XORing out the old square and XORing in the new one; nobody has to rehash the whole board.
Albert Zobrist published the method in 1970, and it remains the key into the transposition table of practically every chess and Go engine. Collisions do happen, but at 64 bits they're rare enough that engines mostly just check the stored move is legal and carry on.