The FKS scheme uses a 2-level hash function. The first hash function is to partition the elements of the universe $\mathcal{U}$ into the dictionary $\mathcal{S}$. Obviously many elements of $\mathcal{U}$ will be mapped to the same position in the main table , that s why we use a perfect hash function in each sub-table to resolve collisions. The algorithm given by Fredman, Komlós and Szémeredi FKS scheme keeps track on the number of insertion and deletion operations that have been made and check if the sum of all the sub-tables reaches a certain threshold, if it is the case then the main table ( and the sub-tables) will be fully rehashed or only a specific sub-table will be rehashed.

Now, if we want to save the change of the table in tree, in which each inner node presents a hash function and the leaves are the keys being inserted in to the dictionary.

Let $\mathcal{H}_s$ be the family of universal hash functions with $$\mathcal{H}_s=\{h :\mathcal{U} \rightarrow \{0,1,\dots,s-1\} \mid h(x)=(kx \text{ mod }p)\text{ mod } s \},$$ where $p$ is a prime number and is chosen large enough so that every possible key $k$ is in the range $0$ to $p-1$, inclusive. The given family of hash functions partition the elements belong to $\mathcal{U}$ and to be stored into $s$ sets and in each of these subsets.

Let $D$ be a rooted tree, in which the inner nodes $v$ are labelled with a hash function $h_v \in \mathcal{H}_{m_v}$, where $m_v $ is the number of children of node $v$ and $m_v \geq 2$. Furthermore, we define $A(v) \subseteq U$ as the set of keys sent to $v$ by the upper hash function in the path from root to $v$. We define inductively: $A(v)= \mathcal{U}$ for $v$ the root and ${A(v_q)= \{x \in A(v)| h_v(x)=q\}}$, $0\leq q< m_v$, where $v_q$ is child of $v$.

Now what i really don t understand is the construction of the tree. If after inserting n elements into the dictionary and the $x_{n+1}$ causes a rehash at the root, how does the structure of the tree change.

I will appreciate, if someone can draw me a small graphic example. Thank you in advance.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.