# Data structures

## Hash tables

### Multiplicative hashing

We start with defining an hash function that takes a value from w-bit integer and returns a d-bit integer (the hash)

hash(x):
return ((z*x) mod 2**w) >> (w - d)


z is an odd integer chosen at random. Mathematically this works because the set of odd integers module $$2^w$$ forms a modular multiplicative group (I know $$x$$ can be even but hey, this is not cryptography :P). Moreover

$$\left(Z/2^k Z\right)^\times\sim C_2\times C_{2^{k - 2}}$$

not being a cyclic group we know that it will not span all the domain.

• multiplicative hashing POC hash.c

## Tools

• visualgo.net: visualising data structures and algorithms through animation