  There is a large amount of work constructing hashmaps to minimize the number
of collisions. However, to the best of our knowledge no known hashing technique
guarantees group fairness among different groups of items. We are given a set
$P$ of $n$ tuples in $\mathbb{R}^d$, for a constant dimension $d$ and a set of
groups $\mathcal{G}=\{\mathbf{g}_1,\ldots, \mathbf{g}_k\}$ such that every
tuple belongs to a unique group. We formally define the fair hashing problem
introducing the notions of single fairness ($Pr[h(p)=h(x)\mid p\in
\mathbf{g}_i, x\in P]$ for every $i=1,\ldots, k$), pairwise fairness
($Pr[h(p)=h(q)\mid p,q\in \mathbf{g}_i]$ for every $i=1,\ldots, k$), and the
well-known collision probability ($Pr[h(p)=h(q)\mid p,q\in P]$). The goal is to
construct a hashmap such that the collision probability, the single fairness,
and the pairwise fairness are close to $1/m$, where $m$ is the number of
buckets in the hashmap.
  We propose two families of algorithms to design fair hashmaps. First, we
focus on hashmaps with optimum memory consumption minimizing the unfairness. We
model the input tuples as points in $\mathbb{R}^d$ and the goal is to find the
vector $w$ such that the projection of $P$ onto $w$ creates an ordering that is
convenient to split to create a fair hashmap. For each projection we design
efficient algorithms that find near optimum partitions of exactly (or at most)
$m$ buckets. Second, we focus on hashmaps with optimum fairness
($0$-unfairness), minimizing the memory consumption. We make the important
observation that the fair hashmap problem is reduced to the necklace splitting
problem. By carefully implementing algorithms for solving the necklace
splitting problem, we propose faster algorithms constructing hashmaps with
$0$-unfairness using $2(m-1)$ boundary points when $k=2$ and $k(m-1)(4+\log_2
(3mn))$ boundary points for $k>2$.
