# 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

A tree is a graph that is not cyclic.

### Binary tree

This is a subset of trees where nodes can only have up to to 2 child, usually named left and right.

There are a couple of ordering mechanism: take the following binary tree

      <A>
/   \
<B>   <C>
/   \
<D>   <E>


pre-order returns A, B, D, E, Cperforming the following steps

• return the root node
• traverse recursively the left subtree
• traverse recursively the right subtree

in-order returns D, B, E, A, C performing the following steps

• traverse recursively the left subtree
• return the root node
• traverse recursively the right subtree

post-order returns D, E, B, C, A instead with the following procedure

• traverse recursively the left subtree
• traverse recursively the right subtree
• return the root node

level-order returns A, B, C, D, E, the steps are

1. add the root node to a queue
2. pop the last node from the queue and return it
3. add all children of popped node to queue and continue from step 2 until queue is empty

The number of unlabeled trees with $$N$$ nodes is given by the Catalan's numbers

$$T(N) = \sum_{i=1}^{N} T(i - 1)\cdot T(N - i) = {(2N)!\over(N + 1)!N!}$$

instead for labeled binary tree we have

$$T^\prime(N)= N!T(N) = {(2N)!\over(N + 1)!}$$

## Tools

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