How to write a pro-grade hashtable

[Asymptotic]

I see all of these basic hashtable tutorials where they just calculate a hash with a modulus and they say "dont use this in production."

So my question is... What CAN I use in production? What does a good hash table configuration look like? Which operators should I use besides modulus the hash table size?

[ordak]

I see all of these basic hashtable tutorials where they just calculate a hash with a modulus and they say "dont use this in production."

So my question is... What CAN I use in production? What does a good hash table configuration look like? Which operators should I use besides modulus the hash table size?

Hash table in chess programming link.

[ordak]

I see all of these basic hashtable tutorials where they just calculate a hash with a modulus and they say "dont use this in production."

So my question is... What CAN I use in production? What does a good hash table configuration look like? Which operators should I use besides modulus the hash table size?

Let me tell an example based on my experience. Suppose you want to solve Sudoku. At one stage you want to know whether two Sudoku states are equal or not. Some Sudoku cells are bounded (they have a single value). Some unbounded (they can have multiple values).

The obvious way to compare two Sudoku states is to compare all 9*9 cells. If all bounded cells are equal, they are the same states.

This method is OK, but there is a drawback here. The number of comparisons is high.

Here is a trick. Let me introduce a new variable for each Sudoku state. I define it as number of bounded cells. Let us call this hash.

There are two possibilities when comparing hashes of two Sudoku states. If hashes are different then the two states are different. Think of saved computations here. Otherwise in case of hashes being equal, I need a full states comparison.

Conclusion : At the cost of tiny extra memory and tiny extra computation, Huge gain in resources is achieved.

[Asymptotic]

@ordak honestly you might like to check into Microsoft Z3 SMT Solver. It sounds like you could use this for your Sudoku work as well. I've used it to solve other constrained problems. Check out this page: Z3Py Guide But note that Z3 also has a C API: Z3: C API

[ordak]

@ordak honestly you might like to check into Microsoft Z3 SMT Solver. It sounds like you could use this for your Sudoku work as well. I've used it to solve other constrained problems. Check out this page: Z3Py Guide But note that Z3 also has a C API: Z3: C API

I already have a Sudoku solver here.