# Detecting and correcting collisions in (Zorbist) hashing to avoid errors in transposition table

Context

Say I have a transposition table that uses keys produced by (e.g. Zorbist) hashing game positions.

The table has a finite recycled memory (key % p is the index of the key, p is table size and prime).

That is, at table[index(key)] (there) we store key and (game position) evaluation.

So, when fetching cached evaluation of a game position P that was hashed into key:

• If key matches with key stored at index(key), we return evaluation stored there.
• Else, we return default value (indicating "empty"), then rewrite key and evaluation there.

(I've basically summarized how a simple transposition table can be implemented.)

Collision problem

The problem is when two different game positions P1 and P2 are hashed into the same key (collision).

Say that we encounter position P1 first. First time reading this key, "empty" value will be returned and evaluation1 for P1 will be stored in table[index(key)]. Second time reading this key (matching key at index), evaluation1 for P1 will be returned. This will either:

• Be fine, in the case that we encountered P1 again.

• Be an error in the game evaluation, in the case that we encountered P2.

How can this error be detected and corrected, efficently?

Apparently stockfish uses something like this Zorbist hashing and has verification "Every entry is carefully validated before use,...", meaning that "...this (game engine) would work even if every hash table access would return random numbers."; But, how is this verification implemented?