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

Trees

Tools

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