flat_map internals

C++
Author

dev::author

Published

August 30, 2026

Introduction

We use hash-tables a lot in software programming and there has been a strong desire for a more space and run-time efficient representation of a map among C++ users. I recently watched Matt Kulukundis’ CppCon 2017 talk, Designing a fast, efficient, cache-friendly hash Table, step by step. In this blog-post, I would like to explore the implementation details of the abseil library’s flat_hash_map data-structure.

%load_ext itikz

The standard library’s unordered_set

Our starting point is the standard library’s implementation of a hash-table called the unordered_set. Here, we have a table(array) S, of size \(2^n\). The array elements \(S[0],\ldots,S[2^n - 1]\) are called slots. A new element is inserted into the table by hashing it, to find the correct slot. The element is stored at hash(item) % capacity() index. Two elements with the same hash-code, would have to be stored at the same slot; so we need a way to resolve collisions. unordered_set uses chaining, so each slot S[i] is more like a bucket, it is a linked-list of all items that hash to the same hash-code.

Show the code 
%%itikz --temp-dir --tex-packages=tikz,color --tikz-libraries=arrows.meta --implicit-standalone
\begin{tikzpicture}[scale=2.5,transform shape]
  \pagecolor{white}
  \draw[fill=white!91!blue!90!cyan] (0,3) rectangle (0.3,0);
  \draw (0,2.25) -- (0.3,2.25);
  \draw (0,1.5) -- (0.3,1.5);
  \draw (0,1.25) -- (0.3,1.25);
  \draw (0,1) -- (0.3,1);
  \draw (0,0.25) -- (0.3,0.25);
  \draw[fill=pink] (0,2.75) rectangle (0.3,2.49);
  \draw[fill=pink] (1,2.75) rectangle (1.3,2.49);
  \draw[fill=pink] (1.3,2.75) rectangle (1.6,2.49);
  \draw[fill=pink] (1.6,2.75) rectangle (1.9,2.49);
  \draw[fill=pink] (2.3,2.75) rectangle (2.6,2.49);
  \draw[fill=pink] (2.6,2.75) rectangle (2.9,2.49);
  \draw[fill=pink] (2.9,2.75) rectangle (3.2,2.49);
  \draw[fill=yellow!30] (0,2) rectangle (0.3,1.74);
  \draw[fill=yellow!30] (1,2) rectangle (1.3,1.74);
  \draw[fill=yellow!30] (1.3,2) rectangle (1.6,1.74);
  \draw[fill=yellow!30] (1.6,2) rectangle (1.9,1.74);
  \draw[fill=green!30] (0,0.73) rectangle (0.3,0.47);
  \draw[fill=green!30] (1,0.73) rectangle (1.3,0.47);
  \draw[fill=green!30] (1.3,0.73) rectangle (1.6,0.47);
  \draw[fill=green!30] (1.6,0.73) rectangle (1.9,0.47);
  \draw[fill=green!30] (2.3,0.73) rectangle (2.6,0.47);
  \draw[fill=green!30] (2.6,0.73) rectangle (2.9,0.47);
  \draw[fill=green!30] (2.9,0.73) rectangle (3.2,0.47);
  \draw[fill=green!30] (3.7,0.73) rectangle (4,0.47);
  \draw[fill=green!30] (4,0.73) rectangle (4.3,0.47);
  \draw[fill=green!30] (4.3,0.73) rectangle (4.6,0.47);
  \draw[arrows=-Latex] (0.15,2.6) -- (1.05,2.6);
  \draw[arrows=-Latex] (0.16,1.86) -- (1.06,1.86);
  \draw[arrows=-Latex] (0.15,0.58) -- (1.05,0.58);
  \node[draw=none, node font=\small] at (0.15,3.33) {$S[0,...,2^n-1]$};
  \node[draw=none, node font=\ttfamily] at (1.15,2.6) {H};
  \node[draw=none, node font=\small] at (3.06,2.62) {$\phi$};
  \node[draw=none, node font=\small] at (4.45,0.59) {$\phi$};
  \node[draw=none, node font=\small] at (1.74,1.88) {$\phi$};
  \node[draw=none, node font=\ttfamily] at (1.15,1.86) {H};
  \node[draw=none, node font=\ttfamily] at (1.15,0.61) {H};
  \node[draw=none, node font=\ttfamily] (node1) at (2.45,2.62) {H};
  \draw[arrows=-Latex] (1.72,2.61) -- (2.36,2.62);
  \draw[arrows=-Latex] (1.69,0.6) -- (2.33,0.61);
  \draw[arrows=-Latex] (3.07,0.58) -- (3.71,0.59);
  \node[draw=none, node font=\ttfamily] at (2.47,0.59) {H};
  \node[draw=none, node font=\ttfamily] at (3.86,0.6) {H};
  \node[draw=none, node font=\ttfamily] at (1.45,2.61) {V};
  \node[draw=none, node font=\ttfamily] at (1.46,1.85) {V};
  \node[draw=none, node font=\ttfamily] at (1.46,0.6) {V};
  \node[draw=none, node font=\ttfamily] at (2.75,2.61) {V};
  \node[draw=none, node font=\ttfamily] (node2) at (2.75,0.58) {V};
  \node[draw=none, node font=\ttfamily] at (4.15,0.6) {V};
  \draw (1.46,0.91) -- (2.8,1.4);
  \draw (2.66,0.9) -- (2.8,1.4);

  \draw (4.15,0.8) -- (2.8,1.4);
  \node[draw=none, node font=\small] at (2.89,1.58) {Bucket chain};
\end{tikzpicture}

The unordered_set

The H in the diagram is the hash-code. It is 64-bits. V is the actual value - the thing that we want to store. Because, each item lives in a separate node, different from the primary data-structure - the bucket array S, we say it has pointer-stability. No matter, what happens to the internals of the hash-table, the value doesn’t move, it lives at the same memory address. This is a property guaranteed by the standard. \(\phi\) denotes nullptr; it is used to indicate the end of linked-lists. The green nodes are all in the same bucket chain.

The above mental picture is ballpark correct. The actual picture is more like this:

Show the code 
%%itikz --temp-dir --tex-packages=tikz,color --tikz-libraries=arrows.meta --implicit-standalone
\begin{tikzpicture}[scale=2.5,transform shape]
  \pagecolor{white}
  \draw[fill=white!91!blue!90!cyan] (0,3) rectangle (0.3,0);
  \draw (0,2.25) -- (0.3,2.25);
  \draw (0,1.5) -- (0.3,1.5);
  \draw (0,1.25) -- (0.3,1.25);
  \draw (0,1) -- (0.3,1);
  \draw (0,0.25) -- (0.3,0.25);
  \draw[fill=pink] (0,2.75) rectangle (0.3,2.49);
  \draw[fill=pink] (1,2.75) rectangle (1.3,2.49);
  \draw[fill=pink] (1.3,2.75) rectangle (1.6,2.49);
  \draw[fill=pink] (1.6,2.75) rectangle (1.9,2.49);
  \draw[fill=pink] (2.3,2.75) rectangle (2.6,2.49);
  \draw[fill=pink] (2.6,2.75) rectangle (2.9,2.49);
  \draw[fill=pink] (2.9,2.75) rectangle (3.2,2.49);
  \draw[fill=yellow!30] (0,2) rectangle (0.3,1.74);
  \draw[fill=yellow!30] (1,2) rectangle (1.3,1.74);
  \draw[fill=yellow!30] (1.3,2) rectangle (1.6,1.74);
  \draw[fill=yellow!30] (1.6,2) rectangle (1.9,1.74);
  \draw[fill=green!30] (0,0.73) rectangle (0.3,0.47);
  \draw[fill=green!30] (1,0.73) rectangle (1.3,0.47);
  \draw[fill=green!30] (1.3,0.73) rectangle (1.6,0.47);
  \draw[fill=green!30] (1.6,0.73) rectangle (1.9,0.47);
  \draw[fill=green!30] (2.3,0.73) rectangle (2.6,0.47);
  \draw[fill=green!30] (2.6,0.73) rectangle (2.9,0.47);
  \draw[fill=green!30] (2.9,0.73) rectangle (3.2,0.47);
  \draw[fill=green!30] (3.7,0.73) rectangle (4,0.47);
  \draw[fill=green!30] (4,0.73) rectangle (4.3,0.47);
  \draw[fill=green!30] (4.3,0.73) rectangle (4.6,0.47);
  \node[draw=none, node font=\small] at (0.15,3.76) {$S[0,...,2^n-1]$};
  \node[draw=none, node font=\ttfamily] (node6) at (1.15,2.6) {H};
  \node[draw=none, node font=\small] at (4.45,0.59) {$\phi$};
  \node[draw=none, node font=\ttfamily] (node5) at (1.15,1.86) {H};
  \node[draw=none, node font=\ttfamily] (node8) at (1.15,0.61) {H};
  \node[draw=none, node font=\ttfamily] (node1) at (2.45,2.62) {H};
  \draw[arrows=-Latex] (1.72,2.61) -- (2.36,2.62);
  \draw[arrows=-Latex] (1.69,0.6) -- (2.33,0.61);
  \draw[arrows=-Latex] (3.07,0.58) -- (3.71,0.59);
  \node[draw=none, node font=\ttfamily] at (2.47,0.59) {H};
  \node[draw=none, node font=\ttfamily] at (3.86,0.6) {H};
  \node[draw=none, node font=\ttfamily] (node4) at (1.45,2.61) {V};
  \node[draw=none, node font=\ttfamily] (node9) at (1.46,1.85) {V};
  \node[draw=none, node font=\ttfamily] at (1.46,0.6) {V};
  \node[draw=none, node font=\ttfamily] (node7) at (2.75,2.61) {V};
  \node[draw=none, node font=\ttfamily] (node2) at (2.75,0.58) {V};
  \node[draw=none, node font=\ttfamily] at (4.15,0.6) {V};
  \draw (1.46,0.91) -- (2.8,1.4);
  \draw (2.66,0.9) -- (2.8,1.4);

  \draw (4.15,0.8) -- (2.8,1.4);
  \node[draw=none, node font=\small] at (2.89,1.58) {Bucket chain};
  \node[draw, node font=\small, fill=white!97!blue!88!cyan] (node3) at (-0.68,3.25) {head};
  \draw[arrows=Circle-Latex] (0.2,2.65) .. controls (-0.87,2.25) and (-0.77,2.8) .. (-0.82,3.02);
  \draw[arrows=Circle-Latex] (node3.east) .. controls (0.3,3.48) and (0.92,3.5) .. (1.12,2.76);

  \draw[arrows=Circle-Latex] (0.1,1.84) .. controls (0.57,2.5) and (1.37,1.85) .. (2.36,2.49);

  \draw[arrows=Circle-Latex] (3.05,2.62) .. controls (3.7,2.31) and (2.5,2.39) .. (1.9,2);

  \draw[arrows=Circle-Latex] (0.15,0.55) .. controls (1,1) and (0.3,1.58) .. (node5.west);

  \draw[arrows=Circle-Latex] (1.73,1.9) .. controls (1.4,0.73) and (0.18,1.08) .. (1,0.5);
\end{tikzpicture}

More realistic implementation details of unordered_set

If we zoom out and think for a bit, it makes more sense, why it is implemnented like this. Let’s rearrange the above picture.

Show the code 
%%itikz --temp-dir --tex-packages=tikz,color --tikz-libraries=arrows.meta --implicit-standalone
\begin{tikzpicture}[scale=2.5,transform shape]
  \pagecolor{white}
  \draw[fill=white!91!blue!90!cyan, rotate=90] (-0.3,1.1) rectangle (0,-2.46);
  \draw (-0.2,0) -- (-0.2,-0.3);
  \draw (0.7,0) -- (0.7,-0.3);
  \draw (0.99,0) -- (0.99,-0.3);
  \draw (1.3,0) -- (1.3,-0.3);
  \draw (2.12,0) -- (2.12,-0.3);
  \draw[fill=pink] (-0.8,0) rectangle (-0.48,-0.3);
  \draw[fill=pink] (-1.42,1.13) rectangle (-1.12,0.87);
  \draw[fill=pink] (-1.12,1.13) rectangle (-0.8,0.87);
  \draw[fill=pink] (-0.8,1.13) rectangle (-0.51,0.87);
  \draw[fill=pink] (-0.09,1.13) rectangle (0.21,0.87);
  \draw[fill=pink] (0.21,1.13) rectangle (0.51,0.87);
  \draw[fill=pink] (0.51,1.13) rectangle (0.81,0.87);
  \draw[fill=yellow!30] (0.1,0) rectangle (0.41,-0.3);
  \draw[fill=yellow!30] (1.24,1.15) rectangle (1.54,0.89);
  \draw[fill=yellow!30] (1.54,1.15) rectangle (1.84,0.89);
  \draw[fill=yellow!30] (1.84,1.15) rectangle (2.14,0.89);
  \draw[fill=green!30] (1.56,0) rectangle (1.82,-0.3);
  \draw[fill=green!30] (2.6,1.13) rectangle (2.9,0.87);
  \draw[fill=green!30] (2.9,1.13) rectangle (3.2,0.87);
  \draw[fill=green!30] (3.2,1.13) rectangle (3.5,0.87);
  \draw[fill=green!30] (3.9,1.13) rectangle (4.2,0.87);
  \draw[fill=green!30] (4.2,1.13) rectangle (4.5,0.87);
  \draw[fill=green!30] (4.5,1.13) rectangle (4.8,0.87);
  \draw[fill=green!30] (5.3,1.13) rectangle (5.6,0.87);
  \draw[fill=green!30] (5.6,1.13) rectangle (5.9,0.87);
  \draw[fill=green!30] (5.9,1.13) rectangle (6.2,0.87);
  \node[draw=none, node font=\small] at (0.72,-0.55) {$S[0,...,2^n-1]$};
  \node[draw=none, node font=\ttfamily] (node4) at (-1.28,0.98) {H};
  \node[draw=none, node font=\small] at (6.05,0.99) {$\phi$};
  \node[draw=none, node font=\ttfamily] at (1.39,1.01) {H};
  \node[draw=none, node font=\ttfamily] at (2.75,1.01) {H};
  \node[draw=none, node font=\ttfamily] (node1) at (0.05,1) {H};
  \draw[arrows=-Latex] (-0.69,0.99) -- (-0.04,1);
  \draw[arrows=-Latex] (-2.09,0.99) -- (-1.44,1);
  \draw[arrows=-Latex] (0.63,0.99) -- (1.28,1);
  \draw[arrows=-Latex] (1.96,1) -- (2.61,1.01);
  \draw[arrows=-Latex] (3.29,1) -- (3.93,1.01);
  \draw[arrows=-Latex] (4.67,0.98) -- (5.31,0.99);
  \node[draw=none, node font=\ttfamily] at (4.07,0.99) {H};
  \node[draw=none, node font=\ttfamily] at (5.46,1) {H};
  \node[draw=none, node font=\ttfamily] at (-0.97,0.99) {V};
  \node[draw=none, node font=\ttfamily] at (1.7,1) {V};
  \node[draw=none, node font=\ttfamily] at (3.06,1) {V};
  \node[draw=none, node font=\ttfamily] (node5) at (0.36,0.99) {V};
  \node[draw=none, node font=\ttfamily] (node2) at (4.35,0.98) {V};
  \node[draw=none, node font=\ttfamily] at (5.75,1) {V};


  \node[draw, node font=\small, fill=white!97!blue!88!cyan] (node3) at (-2.5,0.98) {head};
  \draw[arrows=-Latex] (-0.66,-0.15) -- (node3.south);
  \draw[arrows=-Latex] (0.26,-0.15) -- (-0.09,0.89);
  \draw[arrows=-Latex] (1.71,-0.15) -- (1.36,0.89);
\end{tikzpicture}

Implementation details of unordered_set

Now, if we look more closely, we are storing both the hash-codes and pointers for each element. That’s an extra 16-bytes per entry. When we iterate across the unordered_set, we actually end up walking this linked-list. That takes \(O(\texttt{size})\) runtime. The iteration order of this container is reproducible, for a given insertion order.

How does .find(val) operate on this table?

We want to find the element highlighted in red; it happens to be the second element in the bucket chain.

Show the code 
%%itikz --temp-dir --tex-packages=tikz,color --tikz-libraries=arrows.meta --implicit-standalone
\begin{tikzpicture}[scale=2.5,transform shape]
  \pagecolor{white}
  \draw[fill=white!91!blue!90!cyan, rotate=90] (-0.3,1.1) rectangle (0,-2.46);
  \draw (-0.2,0) -- (-0.2,-0.3);
  \draw (0.7,0) -- (0.7,-0.3);
  \draw (0.99,0) -- (0.99,-0.3);
  \draw (1.3,0) -- (1.3,-0.3);
  \draw (2.12,0) -- (2.12,-0.3);
  \draw[fill=pink] (-0.8,0) rectangle (-0.48,-0.3);
  \draw[fill=pink] (-1.42,1.13) rectangle (-1.12,0.87);
  \draw[fill=pink] (-1.12,1.13) rectangle (-0.8,0.87);
  \draw[fill=pink] (-0.8,1.13) rectangle (-0.51,0.87);
  \draw[fill=pink] (-0.09,1.13) rectangle (0.21,0.87);
  \draw[fill=pink] (0.21,1.13) rectangle (0.51,0.87);
  \draw[fill=pink] (0.51,1.13) rectangle (0.81,0.87);
  \draw[fill=yellow!30] (0.1,0) rectangle (0.41,-0.3);
  \draw[fill=yellow!30] (1.24,1.15) rectangle (1.54,0.89);
  \draw[fill=yellow!30] (1.54,1.15) rectangle (1.84,0.89);
  \draw[fill=yellow!30] (1.84,1.15) rectangle (2.14,0.89);
  \draw[fill=green!30] (1.56,0) rectangle (1.82,-0.3);
  \draw[fill=green!30] (2.6,1.13) rectangle (2.9,0.87);
  \draw[fill=green!30] (2.9,1.13) rectangle (3.2,0.87);
  \draw[fill=green!30] (3.2,1.13) rectangle (3.5,0.87);
  \draw[fill=green!30] (3.9,1.13) rectangle (4.2,0.87);
  \draw[fill=green!30] (4.2,1.13) rectangle (4.5,0.87);
  \draw[fill=green!30] (4.5,1.13) rectangle (4.8,0.87);
  \draw[fill=green!30] (5.3,1.13) rectangle (5.6,0.87);
  \draw[fill=green!30] (5.6,1.13) rectangle (5.9,0.87);
  \draw[fill=green!30] (5.9,1.13) rectangle (6.2,0.87);
  \node[draw=none, node font=\small] at (0.72,-0.55) {$S[0,...,2^n-1]$};
  \node[draw=none, node font=\ttfamily] (node4) at (-1.28,0.98) {H};
  \node[draw=none, node font=\small] at (6.05,0.99) {$\phi$};
  \node[draw=none, node font=\ttfamily] at (1.39,1.01) {H};
  \node[draw=none, node font=\ttfamily] at (2.75,1.01) {H};
  \node[draw=none, node font=\ttfamily] (node1) at (0.05,1) {H};
  \draw[arrows=-Latex] (-0.69,0.99) -- (-0.04,1);
  \draw[arrows=-Latex] (-2.09,0.99) -- (-1.44,1);
  \draw[arrows=-Latex] (0.63,0.99) -- (1.28,1);
  \draw[arrows=-Latex] (1.96,1) -- (2.61,1.01);
  \draw[arrows=-Latex] (3.29,1) -- (3.93,1.01);
  \draw[arrows=-Latex] (4.67,0.98) -- (5.31,0.99);
  \node[draw=none, node font=\ttfamily, text=red] at (4.07,0.99) {H};
  \node[draw=none, node font=\ttfamily] at (5.46,1) {H};
  \node[draw=none, node font=\ttfamily] at (-0.97,0.99) {V};
  \node[draw=none, node font=\ttfamily] at (1.7,1) {V};
  \node[draw=none, node font=\ttfamily] at (3.06,1) {V};
  \node[draw=none, node font=\ttfamily] (node5) at (0.36,0.99) {V};
  \node[draw=none, node font=\ttfamily, text=red] (node2) at (4.35,0.98) {V};
  \node[draw=none, node font=\ttfamily] at (5.75,1) {V};


  \node[draw, node font=\small, fill=white!97!blue!88!cyan] (node3) at (-2.5,0.98) {head};
  \draw[arrows=-Latex] (-0.66,-0.15) -- (node3.south);
  \draw[arrows=-Latex] (0.26,-0.15) -- (-0.09,0.89);
  \draw[arrows=-Latex] (1.71,-0.15) -- (1.36,0.89);
\end{tikzpicture}

.find(val) operation

We compute the hash(val) % capacity() to figure out the slot in the bucket array.

Show the code 
%%itikz --temp-dir --tex-packages=tikz,color --tikz-libraries=arrows.meta --implicit-standalone
\begin{tikzpicture}[scale=2.5,transform shape]
  \pagecolor{white}
  \draw[fill=white!91!blue!90!cyan, rotate=90] (-0.3,1.1) rectangle (0,-2.46);
  \draw (-0.2,0) -- (-0.2,-0.3);
  \draw (0.7,0) -- (0.7,-0.3);
  \draw (0.99,0) -- (0.99,-0.3);
  \draw (1.3,0) -- (1.3,-0.3);
  \draw (2.12,0) -- (2.12,-0.3);
  \draw[fill=pink] (-0.8,0) rectangle (-0.48,-0.3);
  \draw[fill=pink] (-1.42,1.13) rectangle (-1.12,0.87);
  \draw[fill=pink] (-1.12,1.13) rectangle (-0.8,0.87);
  \draw[fill=pink] (-0.8,1.13) rectangle (-0.51,0.87);
  \draw[fill=pink] (-0.09,1.13) rectangle (0.21,0.87);
  \draw[fill=pink] (0.21,1.13) rectangle (0.51,0.87);
  \draw[fill=pink] (0.51,1.13) rectangle (0.81,0.87);
  \draw[fill=yellow!30] (0.1,0) rectangle (0.41,-0.3);
  \draw[fill=yellow!30] (1.24,1.15) rectangle (1.54,0.89);
  \draw[fill=yellow!30] (1.54,1.15) rectangle (1.84,0.89);
  \draw[fill=yellow!30] (1.84,1.15) rectangle (2.14,0.89);
  \fill[green!30, draw=blue, ultra thick] (1.56,0) rectangle (1.82,-0.3);
  \draw[fill=green!30] (2.6,1.13) rectangle (2.9,0.87);
  \draw[fill=green!30] (2.9,1.13) rectangle (3.2,0.87);
  \draw[fill=green!30] (3.2,1.13) rectangle (3.5,0.87);
  \draw[fill=green!30] (3.9,1.13) rectangle (4.2,0.87);
  \draw[fill=green!30] (4.2,1.13) rectangle (4.5,0.87);
  \draw[fill=green!30] (4.5,1.13) rectangle (4.8,0.87);
  \draw[fill=green!30] (5.3,1.13) rectangle (5.6,0.87);
  \draw[fill=green!30] (5.6,1.13) rectangle (5.9,0.87);
  \draw[fill=green!30] (5.9,1.13) rectangle (6.2,0.87);
  \node[draw=none, node font=\small] at (0.72,-0.56) {$S[0,...,2^n-1]$};
  \node[draw=none, node font=\ttfamily] (node4) at (-1.28,0.98) {H};
  \node[draw=none, node font=\small] at (6.05,0.99) {$\phi$};
  \node[draw=none, node font=\ttfamily] at (1.39,1.01) {H};
  \node[draw=none, node font=\ttfamily] at (2.75,1.01) {H};
  \node[draw=none, node font=\ttfamily] (node1) at (0.05,1) {H};
  \draw[arrows=-Latex] (-0.69,0.99) -- (-0.04,1);
  \draw[arrows=-Latex] (-2.09,0.99) -- (-1.44,1);
  \draw[arrows=-Latex] (0.63,0.99) -- (1.28,1);
  \draw[arrows=-Latex] (1.96,1) -- (2.61,1.01);
  \draw[arrows=-Latex] (3.29,1) -- (3.93,1.01);
  \draw[arrows=-Latex] (4.67,0.98) -- (5.31,0.99);
  \node[draw=none, node font=\ttfamily, text=red] at (4.07,0.99) {H};
  \node[draw=none, node font=\ttfamily] at (5.46,1) {H};
  \node[draw=none, node font=\ttfamily] at (-0.97,0.99) {V};
  \node[draw=none, node font=\ttfamily] at (1.7,1) {V};
  \node[draw=none, node font=\ttfamily] at (3.06,1) {V};
  \node[draw=none, node font=\ttfamily] (node5) at (0.36,0.99) {V};
  \node[draw=none, node font=\ttfamily, text=red] (node2) at (4.35,0.98) {V};
  \node[draw=none, node font=\ttfamily] at (5.75,1) {V};


  \node[draw, node font=\small, fill=white!97!blue!88!cyan] (node3) at (-2.5,0.98) {head};
  \draw[arrows=-Latex] (-0.66,-0.15) -- (node3.south);
  \draw[arrows=-Latex] (0.26,-0.15) -- (-0.09,0.89);
  \draw[arrows=-Latex] (1.71,-0.15) -- (1.36,0.89);
\end{tikzpicture}

Compute hash(val) to figure out the bucket

We follow that to the entry before the first entry in the green bucket chain.

Show the code 
%%itikz --temp-dir --tex-packages=tikz,color --tikz-libraries=arrows.meta --implicit-standalone
\begin{tikzpicture}[scale=2.5,transform shape]
  \pagecolor{white}
  \fill[yellow!30, draw=blue, ultra thick] (1.24,1.15) rectangle (2.12,0.89);
  \draw[fill=white!91!blue!90!cyan, rotate=90] (-0.3,1.1) rectangle (0,-2.46);
  \draw (-0.2,0) -- (-0.2,-0.3);
  \draw (0.7,0) -- (0.7,-0.3);
  \draw (0.99,0) -- (0.99,-0.3);
  \draw (1.3,0) -- (1.3,-0.3);
  \draw (2.12,0) -- (2.12,-0.3);
  \draw[fill=pink] (-0.8,0) rectangle (-0.48,-0.3);
  \draw[fill=pink] (-1.42,1.13) rectangle (-1.12,0.87);
  \draw[fill=pink] (-1.12,1.13) rectangle (-0.8,0.87);
  \draw[fill=pink] (-0.8,1.13) rectangle (-0.51,0.87);
  \draw[fill=pink] (-0.09,1.13) rectangle (0.21,0.87);
  \draw[fill=pink] (0.21,1.13) rectangle (0.51,0.87);
  \draw[fill=pink] (0.51,1.13) rectangle (0.81,0.87);
  \draw[fill=yellow!30] (0.1,0) rectangle (0.41,-0.3);
  \fill[green!30, draw=blue, very thick] (1.56,0) rectangle (1.82,-0.3);
  \draw[fill=green!30] (2.6,1.13) rectangle (2.9,0.87);
  \draw[fill=green!30] (2.9,1.13) rectangle (3.2,0.87);
  \draw[fill=green!30] (3.2,1.13) rectangle (3.5,0.87);
  \draw[fill=green!30] (3.9,1.13) rectangle (4.2,0.87);
  \draw[fill=green!30] (4.2,1.13) rectangle (4.5,0.87);
  \draw[fill=green!30] (4.5,1.13) rectangle (4.8,0.87);
  \draw[fill=green!30] (5.3,1.13) rectangle (5.6,0.87);
  \draw[fill=green!30] (5.6,1.13) rectangle (5.9,0.87);
  \draw[fill=green!30] (5.9,1.13) rectangle (6.2,0.87);
  \node[draw=none, node font=\small] at (0.72,-0.56) {$S[0,...,2^n-1]$};
  \node[draw=none, node font=\ttfamily] (node4) at (-1.28,0.98) {H};
  \node[draw=none, node font=\small] at (6.05,0.99) {$\phi$};
  \node[draw=none, node font=\ttfamily] at (1.39,1.02) {H};
  \node[draw=none, node font=\ttfamily] at (2.75,1.01) {H};
  \node[draw=none, node font=\ttfamily] (node1) at (0.05,1) {H};
  \draw[arrows=-Latex] (-0.69,0.99) -- (-0.04,1);
  \draw[arrows=-Latex] (-2.09,0.99) -- (-1.44,1);
  \draw[arrows=-Latex] (0.63,0.99) -- (1.28,1);
  \draw[arrows=-Latex] (1.96,1) -- (2.61,1.01);
  \draw[arrows=-Latex] (3.29,1) -- (3.93,1.01);
  \draw[arrows=-Latex] (4.67,0.98) -- (5.31,0.99);
  \node[draw=none, node font=\ttfamily, text=red] at (4.07,0.99) {H};
  \node[draw=none, node font=\ttfamily] at (5.46,1) {H};
  \node[draw=none, node font=\ttfamily] at (-0.97,0.99) {V};
  \node[draw=none, node font=\ttfamily, minimum width=8pt] (node6) at (1.68,1.01) {V};
  \node[draw=none, node font=\ttfamily] at (3.06,1) {V};
  \node[draw=none, node font=\ttfamily] (node5) at (0.36,0.99) {V};
  \node[draw=none, node font=\ttfamily, text=red] (node2) at (4.35,0.98) {V};
  \node[draw=none, node font=\ttfamily] at (5.75,1) {V};
  \node[draw, node font=\small, fill=white!97!blue!88!cyan] (node3) at (-2.5,0.98) {head};
  \draw[arrows=-Latex] (-0.66,-0.15) -- (node3.south);
  \draw[arrows=-Latex] (0.26,-0.15) -- (-0.09,0.89);
  \draw[arrows=-Latex] (1.71,-0.15) -- (1.36,0.89);

  \draw (1.88,1.12) -- (1.88,0.92);\draw (1.53,1.12) -- (1.53,0.92);
\end{tikzpicture}

Jump to the entry before the first entry in the green bucket chain

We always just skip this one. Then, we go to the first entry that’s actually there. We compare the computed hash hash(val) against the hash stored in the node. If that matches, we compare the value V against the value that we want.

Show the code 
%%itikz --temp-dir --tex-packages=tikz,color --tikz-libraries=arrows.meta --implicit-standalone
\begin{tikzpicture}[scale=2.5,transform shape]
  \pagecolor{white}
  \fill[yellow!30, draw=blue, ultra thick] (1.24,1.15) rectangle (2.12,0.89);
  \fill[fill=green!30, draw=blue, ultra thick] (2.57,1.13) rectangle (3.44,0.87);
  \draw[fill=white!91!blue!90!cyan, rotate=90] (-0.3,1.1) rectangle (0,-2.46);
  \draw (-0.2,0) -- (-0.2,-0.3);
  \draw (0.7,0) -- (0.7,-0.3);
  \draw (0.99,0) -- (0.99,-0.3);
  \draw (1.3,0) -- (1.3,-0.3);
  \draw (2.12,0) -- (2.12,-0.3);
  \draw[fill=pink] (-0.8,0) rectangle (-0.48,-0.3);
  \draw[fill=pink] (-1.42,1.13) rectangle (-1.12,0.87);
  \draw[fill=pink] (-1.12,1.13) rectangle (-0.8,0.87);
  \draw[fill=pink] (-0.8,1.13) rectangle (-0.51,0.87);
  \draw[fill=pink] (-0.09,1.13) rectangle (0.21,0.87);
  \draw[fill=pink] (0.21,1.13) rectangle (0.51,0.87);
  \draw[fill=pink] (0.51,1.13) rectangle (0.81,0.87);
  \draw[fill=yellow!30] (0.1,0) rectangle (0.41,-0.3);
  \fill[green!30, draw=blue, very thick] (1.56,0) rectangle (1.82,-0.3);
  \draw[fill=green!30] (3.9,1.13) rectangle (4.2,0.87);
  \draw[fill=green!30] (4.2,1.13) rectangle (4.5,0.87);
  \draw[fill=green!30] (4.5,1.13) rectangle (4.8,0.87);
  \draw[fill=green!30] (5.3,1.13) rectangle (5.6,0.87);
  \draw[fill=green!30] (5.6,1.13) rectangle (5.9,0.87);
  \draw[fill=green!30] (5.9,1.13) rectangle (6.2,0.87);
  \node[draw=none, node font=\small] at (0.72,-0.56) {$S[0,...,2^n-1]$};
  \node[draw=none, node font=\ttfamily] (node4) at (-1.28,0.98) {H};
  \node[draw=none, node font=\small] at (6.05,0.99) {$\phi$};
  \node[draw=none, node font=\ttfamily] at (1.39,1.02) {H};
  \node[draw=none, node font=\ttfamily] at (2.73,1) {H};
  \node[draw=none, node font=\ttfamily] (node1) at (0.05,1) {H};
  \draw[arrows=-Latex] (-0.69,0.99) -- (-0.04,1);
  \draw[arrows=-Latex] (-2.09,0.99) -- (-1.44,1);
  \draw[arrows=-Latex] (0.63,0.99) -- (1.28,1);
  \draw[arrows=-Latex] (1.96,1) -- (2.61,1.01);
  \draw[arrows=-Latex] (3.29,1) -- (3.93,1.01);
  \draw[arrows=-Latex] (4.67,0.98) -- (5.31,0.99);
  \node[draw=none, node font=\ttfamily, text=red] at (4.07,0.99) {H};
  \node[draw=none, node font=\ttfamily] at (5.46,1) {H};
  \node[draw=none, node font=\ttfamily] at (-0.97,0.99) {V};
  \node[draw=none, node font=\ttfamily, minimum width=8pt] (node6) at (1.68,1.01) {V};
  \node[draw=none, node font=\ttfamily] at (2.99,0.99) {V};
  \node[draw=none, node font=\ttfamily] (node5) at (0.36,0.99) {V};
  \node[draw=none, node font=\ttfamily, text=red] (node2) at (4.35,0.98) {V};
  \node[draw=none, node font=\ttfamily] at (5.75,1) {V};
  \node[draw, node font=\small, fill=white!97!blue!88!cyan] (node3) at (-2.5,0.98) {head};
  \draw[arrows=-Latex] (-0.66,-0.15) -- (node3.south);
  \draw[arrows=-Latex] (0.26,-0.15) -- (-0.09,0.89);
  \draw[arrows=-Latex] (1.71,-0.15) -- (1.36,0.89);

  \draw (1.88,1.12) -- (1.88,0.92);
  \draw (2.85,1.1) -- (2.85,0.9);
  \draw (3.14,1.1) -- (3.14,0.9);\draw (1.53,1.12) -- (1.53,0.92);
\end{tikzpicture}

Jump to the first entry in bucket chain, compare the hash code and the value against what we want

In our case, we jump to the next node, because it didn’t match. Now, we actually get to the one we want.

Show the code 
%%itikz --temp-dir --tex-packages=tikz,color --tikz-libraries=arrows.meta --implicit-standalone
\begin{tikzpicture}[scale=2.5,transform shape]
  \pagecolor{white}
  \fill[yellow!30, draw=blue, ultra thick] (1.24,1.15) rectangle (2.12,0.89);
  \fill[fill=green!30, draw=blue, ultra thick] (2.57,1.13) rectangle (3.44,0.87);
  \draw[fill=white!91!blue!90!cyan, rotate=90] (-0.3,1.1) rectangle (0,-2.46);
  \draw (-0.2,0) -- (-0.2,-0.3);
  \draw (0.7,0) -- (0.7,-0.3);
  \draw (0.99,0) -- (0.99,-0.3);
  \draw (1.3,0) -- (1.3,-0.3);
  \draw (2.12,0) -- (2.12,-0.3);
  \draw[fill=pink] (-0.8,0) rectangle (-0.48,-0.3);
  \draw[fill=pink] (-1.42,1.13) rectangle (-1.12,0.87);
  \draw[fill=pink] (-1.12,1.13) rectangle (-0.8,0.87);
  \draw[fill=pink] (-0.8,1.13) rectangle (-0.51,0.87);
  \draw[fill=pink] (-0.09,1.13) rectangle (0.21,0.87);
  \draw[fill=pink] (0.21,1.13) rectangle (0.51,0.87);
  \draw[fill=pink] (0.51,1.13) rectangle (0.81,0.87);
  \draw[fill=yellow!30] (0.1,0) rectangle (0.41,-0.3);
  \fill[green!30, draw=blue, very thick] (1.56,0) rectangle (1.82,-0.3);
  \draw[fill=green!30] (5.3,1.13) rectangle (5.6,0.87);
  \draw[fill=green!30] (5.6,1.13) rectangle (5.9,0.87);
  \draw[fill=green!30] (5.9,1.13) rectangle (6.2,0.87);
  \node[draw=none, node font=\small] at (0.72,-0.56) {$S[0,...,2^n-1]$};
  \node[draw=none, node font=\ttfamily] (node4) at (-1.28,0.98) {H};
  \node[draw=none, node font=\small] at (6.05,0.99) {$\phi$};
  \node[draw=none, node font=\ttfamily] at (1.39,1.02) {H};
  \node[draw=none, node font=\ttfamily] at (2.73,1) {H};
  \node[draw=none, node font=\ttfamily] (node1) at (0.05,1) {H};
  \draw[arrows=-Latex] (-0.69,0.99) -- (-0.04,1);
  \draw[arrows=-Latex] (-2.09,0.99) -- (-1.44,1);
  \draw[arrows=-Latex] (0.63,0.99) -- (1.28,1);
  \draw[arrows=-Latex] (1.96,1) -- (2.61,1.01);
  \draw[arrows=-Latex] (3.29,1) -- (3.93,1.01);
  \draw[arrows=-Latex] (4.67,0.98) -- (5.31,0.99);
  \node[draw=none, node font=\ttfamily] at (5.46,1) {H};
  \node[draw=none, node font=\ttfamily] at (-0.97,0.99) {V};
  \node[draw=none, node font=\ttfamily, minimum width=8pt] (node6) at (1.68,1.01) {V};
  \node[draw=none, node font=\ttfamily] at (2.99,0.99) {V};
  \node[draw=none, node font=\ttfamily] (node5) at (0.36,0.99) {V};
  \node[draw=none, node font=\ttfamily] at (5.75,1) {V};
  \node[draw, node font=\small, fill=white!97!blue!88!cyan] (node3) at (-2.5,0.98) {head};
  \draw[arrows=-Latex] (-0.66,-0.15) -- (node3.south);
  \draw[arrows=-Latex] (0.26,-0.15) -- (-0.09,0.89);
  \draw[arrows=-Latex] (1.71,-0.15) -- (1.36,0.89);
  \draw (1.88,1.12) -- (1.88,0.92);
  \draw (2.85,1.1) -- (2.85,0.9);
  \draw (3.14,1.1) -- (3.14,0.9);
  \fill[fill=green!30, draw=blue, ultra thick] (3.92,1.16) rectangle (4.78,0.9);
  \draw (4.2,1.13) -- (4.2,0.93);
  \draw (4.49,1.13) -- (4.49,0.93);
  \draw (1.53,1.12) -- (1.53,0.92);
  \node[draw=none, node font=\ttfamily, text=red] (node2) at (4.35,1.02) {V};
  \node[draw=none, node font=\ttfamily, text=red] at (4.09,1.03) {H};
\end{tikzpicture}

Jump to the second entry, which matches against what we want.

This required \(4\) different memory accesses to find the element highlighted in red. In performance-terms, this is costly, because these nodes might not even be in L1d cache, and every cache miss is expensive. We now have a rough idea of how bucket-chaining hash tables work.

absl::flat_hash_map high-level design

The absl::flat_hash_map directly stores the value_type inside the container’s main array to avoid memory indirections. Because they move data when they rehash, elements do not get pointer stability compared to node-based associative containers like std::unordered_map.

A nice summary of some of the tradeoffs between node-based and flat associative containers is given in the Boost documentation:

  • Faster lookup than the standard(node-based) associative containers.

  • Much faster iteration than the standard(node-based) associative containers.

  • Less memory consumption for each element.

  • Improved cache performance (as data is stored contiguously in memory).

  • Slower insertion and erasure the standard associative containers.

absl::flat_hash_map holds a densely packed array of metadata, containing presence information for entries in the hash table. An extra 1-byte of meta-data is stored in the control bytes array per entry in the main array. The array of meta-data and the main array are parallel arrays.

flat_hash_map inheritance hierarchy

The flat_hash_map is a class template with the key type typename K ,the value type typename V, the hash-function typename Hash, the equality comparison operator typename Eq, the allocator type Allocator as template parameters. flat_hash_map inherits from a base class which is derived as follows.

absl/container/flat_hash_map.h
template <
    class K, class V,
    class Hash =
        typename container_internal::FlatHashMapPolicy<K, V>::DefaultHash,
    class Eq = typename container_internal::FlatHashMapPolicy<K, V>::DefaultEq,
    class Allocator =
        typename container_internal::FlatHashMapPolicy<K, V>::DefaultAlloc>
class ABSL_ATTRIBUTE_OWNER flat_hash_map
    : public absl::container_internal::InstantiateRawHashMap<
          absl::container_internal::FlatHashMapPolicy<K, V>, Hash, Eq,
          Allocator>::type {

absl::container_internal::InstantiateRawHashMap is like a type metafunction that accepts 4 types as inputs: the Policy, the hash functor type Hash, the equality comparison operator type Eq and the allocator type Alloc and returns a concrete type that serves as the base-class for flat_hash_map.

absl/container/internal/raw_hash_map.h
template <class Policy, class... Params>
class raw_hash_map;

template <typename Policy, typename Hash, typename Eq, typename Alloc>
struct InstantiateRawHashMap {
  using type = typename ApplyWithoutDefaultSuffix<
      raw_hash_map,
      TypeList<int, typename Policy::DefaultHash, typename Policy::DefaultEq,
               typename Policy::DefaultAlloc>,
      TypeList<Policy, Hash, Eq, Alloc>>::type;
};

It internally calls another meta-function ApplyWithoutDefaultSuffix with the types raw_hash_map, a list of types TypeList<int, Policy::DefaultHash, Policy::DefaultEq, Policy::DefaultAlloc>, a second list of types TypeList<Policy, Hash, Eq, Alloc>.

absl/container/internal/common.h
// Eg
//   ApplyWithoutDefaultSuffix<Template, TypeList<a, b, c>, TypeList<a, X, c>>
// evaluates to
//   Template<a, X>
template <template <typename...> class Template, typename D, typename T,
          typename L = TypeList<>, typename = void>
struct ApplyWithoutDefaultSuffix {
  using type = typename L::template Apply<Template>;
};
template <template <typename...> class Template, typename D, typename... Ds,
          typename T, typename... Ts, typename... L>
struct ApplyWithoutDefaultSuffix<
    Template, TypeList<D, Ds...>, TypeList<T, Ts...>, TypeList<L...>,
    std::enable_if_t<!std::is_same_v<TypeList<D, Ds...>, TypeList<T, Ts...>>>>
    : ApplyWithoutDefaultSuffix<Template, TypeList<Ds...>, TypeList<Ts...>,
                       TypeList<L..., T>> {};

ApplyWithoutDefaultSuffix is another metafunction. Given two typelists - a default list: TypeList<D, Ds...> and list of Ts: <TypeList<T, Ts...>>, it tests if the two typelists are different (observe that we have !std::is_same_v<T1,T2>), and recursively calls itself, passing the arguments i) tail of the default typelist ii) the tail TypeList<Ts...> iii) a third typelist which is used to accumulateT. As we walk through the two type-lists in lock-step fashion, eachTgets appended to the list of types accumulated so far on line 296 asTypeList<L…, T>`.

At the point, when the reduced typelists have an identical tail, the recursion stops. Recall that, std::enable_if_t<Predicate, T = void> returns T if the Predicate evaluates to std::true_type, otherwise it fails. Because of SFINAE(substitution failure is not an error), this does not mean a compile-time error. Effectively, ApplyWithoutDefaultSuffix<Template, TypeList<D1,D2,D3,T4>, TypeList<T1,T2,T3,D4>> evaluates to Template<T1,T2,T3>. The comments on lines 282-284 also elucidate this point.

The ApplyWithoutDefaultSuffix metafunction returns the type L::Apply<Template> on line 288.

Since L is a TypeList<T1,T2,T3>, this simply evaluates to Template<T...> or Template<T1,T2,T3>.

absl/container/internal/common.h
struct TypeList {
  template <template <typename...> class Template>
  using Apply = Template<T...>;
};

To summarize, therefore, flat_hash_map inherits from raw_hash_map<Policy, Traits...> where we use the user-supplied policy traits: the hash-function, equality and allocator as long as they differ from the default policy.

absl/container/flat_hash_map.h
template <
    class K, class V,
    class Hash =
        typename container_internal::FlatHashMapPolicy<K, V>::DefaultHash,
    class Eq = typename container_internal::FlatHashMapPolicy<K, V>::DefaultEq,
    class Allocator =
        typename container_internal::FlatHashMapPolicy<K, V>::DefaultAlloc>
class ABSL_ATTRIBUTE_OWNER flat_hash_map
    : public absl::container_internal::InstantiateRawHashMap<
          absl::container_internal::FlatHashMapPolicy<K, V>, Hash, Eq,
          Allocator>::type {

The raw_hash_map type in turn inherits from raw_hash_set.

absl/container/internal/raw_hash_map.h
template <class Policy, class... Params>
class raw_hash_map : public raw_hash_set<Policy, Params...> {

The raw_hash_set data structure

The raw_hash_set data-structure is a Compressedtuple of CommonFields, hasher, key_equal and CharAlloc types.

struct raw_hash_set{
  // ...
  absl::container_internal::CompressedTuple<
  CommonFields, hasher, key_equal,CharAlloc>
      settings_{
        CommonFields::CreateDefault<SooEnabled()>(), 
        hasher{},key_equal{}, CharAlloc{}
      };
};

The tuple’s first element CommonFields holds those fields in a raw_hash_set that do not depend on the template parameters, and therefore, can be passed conveniently to helper functions. It has two member fields:

class CommonFields{
  // ...
  HashtableInlineData inline_data_;

  // Either the heap pointer or the SOO slot.
  HeapOrSoo heap_or_soo_;
}

inline_data_ member is of type HashtableInlineData. HashTableInlineData is a type alias for HashtableInlineDataImpl<kCapacityByLog>.

absl/container/internal/raw_hash_set.h
#ifndef ABSL_SWISSTABLE_INTERNAL_ENABLE_CAPACITY_BY_VALUE
using HashtableInlineData = HashtableInlineDataImpl<kCapacityByLog>;

The control-bytes array and the main array containing the elements of the flat_hash_set reside in a single contigous block of memory allocated dynamically on the heap. If the elements are small enough, they can be stored on the stack using SOO. HeapOrSoo is a C-style union of two alternatives: 1) a field heap which contains the memory address of the blob of memory holding the control-bytes array and the main array 2) a byte-array soo_data.

absl/container/internal/raw_hash_set.h
union HeapOrSoo {
  MaybeInitializedPtr<ctrl_t>& control() {
    ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(heap.control);
  }
  MaybeInitializedPtr<ctrl_t> control() const {
    ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(heap.control);
  }
  void* get_soo_data() {
    ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(soo_data);
  }
  const void* get_soo_data() const {
    ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(soo_data);
  }

  HeapPtrs heap;
  unsigned char soo_data[MaxSooSlotSize()];
};

The HeapPtrs is just a wrapper over a pointer to a byte-array.

absl/container/internal/raw_hash_set.h
struct HeapPtrs {
  // The control bytes (and, also, a pointer near to the base of the backing
  // array).
  //
  // This contains `capacity + 1 + NumClonedBytes()` entries.
  //
  // Note that growth_info is stored immediately before this pointer.
  // May be uninitialized for small tables.
  MaybeInitializedPtr<ctrl_t> control;
};

The control bytes array

As I mentioned earlier, we keep a little parallel array of metadata. What do we need to keep in the meta-data array? We need to know, if a slot in the main array is empty, whether it’s full or whether it’s deleted. What the implementation does is something very clever.

absl/container/internal/hashtable_control_bytes.h
// states: empty, deleted, full (which has an associated seven-bit h2_t value)
// and the sentinel. They have the following bit patterns:
//
//      empty: 1 0 0 0 0 0 0 0
//    deleted: 1 1 1 1 1 1 1 0
//       full: 0 h h h h h h h  // h represents the hash bits.
//   sentinel: 1 1 1 1 1 1 1 1
//
// These values are specifically tuned for SSE-flavored SIMD.
// The static_asserts below detail the source of these choices.
//
// We use an enum class so that when strict aliasing is enabled, the compiler
// knows ctrl_t doesn't alias other types.
enum class ctrl_t : int8_t {
  kEmpty = -128,   // 0b10000000
  kDeleted = -2,   // 0b11111110
  kSentinel = -1,  // 0b11111111
  // Special value used in the slow path of resizing.
  kMarkedForSlowTransfer = -3,
};

The control byte array is an array of ctrl_t. If a slot in the main array of elements is empty or deleted, it corresponding control byte has its high-bit (MSB) = 1. IF its empty, the control byte is 0b1000 0000 or 0x80. If its deleted, the control byte is 0b1111 1110 (the 2s complement of 0b1000 000) or 0xFE. If the slot of the main array is full (occupied), the control byte has its high-bit = 0. What about the last 7-bits of the control byte, in case a slot is occupied?

Now, the hash function produces a 64-bit hash value. The most significant 7-bits, are used to store metadata for this element. These 7-bits are stored in the control byte for this element.

H1(size_t) is just the hash. H2 is the most significant 7-bits of the hash.

absl/container/internal/raw_hash_set.h
// H1 is just the low bits of the hash.
inline size_t H1(size_t hash) { return hash; }

// Extracts the H2 portion of a hash: the 7 most significant bits.
//
// These are used as an occupied control byte.
inline h2_t H2(size_t hash) { return hash >> (sizeof(size_t) * 8 - 7); }

So, we have a 2-level hash-table. H1 is the 64-bit hash, and it tells us where to look in our main array of elements. H1 is what we take the modulus of, when we are initially figuring out a slot in the hash-table. H2 gives us this little bitmask that has to appear in the control bytes. Note, therefore, that the hash function now is extremely important. If the hash-function hides all its entropy in the most significant 7-bits, we are going to have a lot of H1 collisions. If the hash-function puts none of its entropy in the most significant 7-bits, we are going to have a lot of H2 collisions.

How does .find(key) work for the raw_hash_set?

The control bytes array containing metadata and the main array of elements are split into Groups of size Group::kWidth elements each. Group::kWidth is a magic number set to 16 elements.

Group is an alias for GroupSse2Impl - an SSE2 implementation. The SSE2 instruction set is a guarantee on modern x86 and ARM processors.

absl/container/internal/hashtable_control_bytes.h
using GroupFullEmptyOrDeleted = GroupSse2Impl;

GroupSse2Impl is a wrapper over a 128-bit vector(16 things of size 8-bits each).

struct GroupSse2Impl{
  //...
  __m128i ctrl;
};

We start by creating a probe_seq<Group::kWidth> object representing the probe sequence.

absl/container/internal/raw_hash_set.h
template <size_t Width>
class probe_seq {
 public:
  // Creates a new probe sequence using `hash` as the initial value of the
  // sequence and `capacity` as the mask to apply to each value in the
  // progression.
  probe_seq(ProbeCapacity capacity, size_t hash)
      : capacity_(capacity.capacity), offset_(hash & capacity_) {}

  // The offset within the table, i.e., the value `p(i)` above.
  size_t offset() const { return offset_; }
  size_t offset(size_t i) const { return (offset_ + i) & capacity_; }

  void next() {
    index_ += Width;
    offset_ += index_;
    offset_ &= capacity_;
  }
  // 0-based probe index, a multiple of `Width`.
  size_t index() const { return index_; }

 private:
  size_t capacity_;
  size_t offset_;
  size_t index_ = 0;
};

The first thing you do, is figure out what group you are in. So, you take the H1(hash), modulo it with the capacity_. There’s an infinite while loop, that advances through the groups one at a time. You are trying to find groups that have matches. Advancing to the next group is done by calling .next() on the probe_seq<16> object.

The Group::match(h2_t hash) function

absl/container/internal/hashtable_control_bytes.h
  BitMaskType Match(h2_t hash) const {
    auto match = _mm_set1_epi8(static_cast<char>(hash));
    return BitMaskType(MoveMask(_mm_cmpeq_epi8(match, ctrl)));
  }

_mm_set1_epi8(h2) will initialize a 128-bit vector(that can hold 16 things each of size 8-bits) with the h2 hash.

__mm_cmpeq_epi8(a,b) component-wise compares two 128-bit vectors(16 control bytes) and produces a 128-bit vector result. If any two corresponding components of a and b compare equal, the corresponding component in the result is set to 0xFF.

Consider the following example. __m128i is a 128-bit vector.

#include <emmintrin.h>  // SSE2
#include <stdint.h>
#include <stdio.h>

int main() {

    uint8_t ctrl[16] = {
        0x7f, 0xdf, 0x96, 0x32, 0xf1, 0xf8, 0xeb, 0x43,
        0x7f, 0xdf, 0x96, 0x32, 0xf1, 0xf8, 0xeb, 0x43
    };
    uint8_t h2 = 0x96;

    // Load 16 bytes into a __m128i. 
    __m128i a = _mm_loadu_si128((__m128i const*)ctrl);
    __m128i b = _mm_set1_epi8(h2);
    __m128i result = _mm_cmpeq_epi8(a, b);

    uint8_t dst[16];
    _mm_storeu_si128((__m128i*)dst, result);

    for (int i = 0; i < 16; i++) {
        printf("%02x ", dst[i]);
    }

    // dst = {
    // 0x00, 0x00, 0xFF, 0x00, 0x00, 0x00, 0x00, 0x00,
    // 0x00, 0x00, 0xFF, 0x00, 0x00, 0x00, 0x00, 0x00,
    //}

}

Compiler Explorer

MoveMask is a wrapper over _mm_movemask_epi8(a).

absl/container/internal/hashtable_control_bytes.h
  BitMaskType Match(h2_t hash) const {
    auto match = _mm_set1_epi8(static_cast<char>(hash));
    return BitMaskType(MoveMask(_mm_cmpeq_epi8(match, ctrl)));
  }

_mm_movemask_epi8 takes our 128-bit thing and squishes it. It takes the high-bit of each byte and gives us a 16-bit thing, that has 0s where they didnt match and 1s where they do match. This tell us which of our 16-control bytes had the proper h2(hash).

#include <emmintrin.h>  // SSE2
#include <stdint.h>
#include <stdio.h>
#include <cassert>

int main() {

    uint8_t bitmask[16] = {
        0x00, 0x00, 0xFF, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0xFF, 0x00, 0x00, 0x00, 0x00, 0x00,
    };
    uint16_t expected = 0x0404;

    // Load 16 bytes into a __m128i. 
    __m128i a = _mm_loadu_si128((__m128i const*)bitmask);
    uint16_t result = _mm_movemask_epi8(a);
    assert(result == expected);
}

Compiler Explorer

Therefore, GroupSse2Impl::Match(h2) tells us, which of our 16 control-bytes have the proper h2 hash.

absl/container/internal/hashtable_control_bytes.h
  BitMaskType Match(h2_t hash) const {
    auto match = _mm_set1_epi8(static_cast<char>(hash));
    return BitMaskType(MoveMask(_mm_cmpeq_epi8(match, ctrl)));
  }

The BitMaskType

The BitMaskType is a type alias for BitMask<MaskInt, kWidth>. BitMask<T,SignificantBits, Shift, NullifyBitsOnIteration> is a strong type for working with bitsets.

absl/container/internal/hashtable_control_bytes.h
struct GroupSse2Impl {
  static constexpr size_t kWidth = 16;  // the number of slots per group
  // There are only 16 bits, but using uint32_t instead of uint16_t allows for
  // better codegen. In particular, there is no blsr instruction for a 16 bit
  // register, but there is for a 32 bit register (used in BitMask::operator++).
  using MaskInt = uint32_t;
  using BitMaskType = BitMask<MaskInt, kWidth>;
  using NonIterableBitMaskType = NonIterableBitMask<MaskInt, kWidth>;

  explicit GroupSse2Impl(const ctrl_t* pos) {
    ctrl = _mm_loadu_si128(reinterpret_cast<const __m128i*>(pos));
  }

As the comment in GroupSse2Impl struct reads, a group has 16 slots. The result of Match returns 16-bits. But, using uint32_t to store the output of Match allows for better codegen.

absl/container/internal/hashtable_control_bytes.h
template <class T, int SignificantBits, int Shift = 0,

T controls the number of bits in the bitset. BitMask<T,SignificantBits, Shift, NullifyBitsOnIteration> inherits from the base class NonIterableBitMask<T, SignificantBits, Shift>.

absl/container/internal/hashtable_control_bytes.h
template <class T, int SignificantBits, int Shift = 0>
class NonIterableBitMask {
 public:
  explicit NonIterableBitMask(T mask) : mask_(mask) {}

  explicit operator bool() const { return mask_ != 0; }

  // Returns the index of the lowest *abstract* bit set in `self`.
  uint32_t LowestBitSet() const {
    return container_internal::TrailingZeros(mask_) >> Shift;
  }

  // Returns the number of trailing zero *abstract* bits.
  uint32_t TrailingZeros() const {
    return container_internal::TrailingZeros(mask_) >> Shift;
  }

  // Returns the number of leading zero *abstract* bits.
  uint32_t LeadingZeros() const {
    constexpr int total_significant_bits = SignificantBits << Shift;
    constexpr int extra_bits = sizeof(T) * 8 - total_significant_bits;
    return static_cast<uint32_t>(
               countl_zero(static_cast<T>(mask_ << extra_bits))) >>
           Shift;
  }

  T mask_;
};

First, let’s analyse the functions LowestBitSet(), TrailingZeros() and LeadingZeros in the NonIterableBitMask class.

NonIterableBitMask::LowestBitSet

To quickly understand LowestBitSet(), we go a couple of layers deeper.

absl/container/internal/hashtable_control_bytes.h
  uint32_t LowestBitSet() const {
    return container_internal::TrailingZeros(mask_) >> Shift;
  }

LowestBitSet returns the index of the lowest abstract bit set in the BitMask. First, we count the number of trailing zeros in the BitMask.

absl/container/internal/hashtable_control_bytes.h
template <typename T>
uint32_t TrailingZeros(T x) {
  ABSL_ASSUME(x != 0);
  return static_cast<uint32_t>(countr_zero(x));
}

The countr_zero(T x) is utility function defined in the absl/numeric/bits.h header.

absl/numeric/bits.h
template <class T>
ABSL_INTERNAL_CONSTEXPR_CTZ inline std::enable_if_t<std::is_unsigned_v<T>, int>
countr_zero(T x) noexcept {
  return numeric_internal::CountTrailingZeroes(x);
}

Using SFINAE, the countr_zero(T x) is instantiated at compile-time, only if T is an unsigned type. countr_zero(T x) in turn calls numeric_internal::CountTrailingZeres(x).

absl/numeric/internal/bits.h
template <class T>
ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CTZ inline int
CountTrailingZeroes(T x) noexcept {
  static_assert(std::is_unsigned_v<T>, "T must be unsigned");
  static_assert(IsPowerOf2(std::numeric_limits<T>::digits),
                "T must have a power-of-2 size");
  static_assert(sizeof(T) <= sizeof(uint64_t), "T too large");
  return x == 0 ? std::numeric_limits<T>::digits
                : (sizeof(T) <= sizeof(uint16_t)
                       ? CountTrailingZeroesNonzero16(static_cast<uint16_t>(x))
                       : (sizeof(T) <= sizeof(uint32_t)
                              ? CountTrailingZeroesNonzero32(
                                    static_cast<uint32_t>(x))
                              : CountTrailingZeroesNonzero64(x)));
}

This function first runs a bunch of compile-time asserts. T must be an unsigned type. std::numeric_limits::digits is the number of digits in std::numeric_limits::radix base(2 for fundamental types) that the type T can hold. So, for example, std::numeric_limits<uint32_t>::digits equals 32. The function checks at compile-time if the number of digits that can be held by T is a power of 2.

If x == 0, the number of trailing zeroes is just std::numeric_limits<T>::digits. Else, if sizeof(T) <= sizeof(uint16_t), we branch to CountTrailingZeroesNonzero16(static_cast<uint16_t>(x)). Let’s look at the definition of the 32-bit version: CountTrailingZeroesNonzero32(uint32_t x).

absl/numeric/internal/bits.h
ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CTZ inline int
CountTrailingZeroesNonzero32(uint32_t x) {
#if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_ctz)
  static_assert(sizeof(unsigned int) == sizeof(x),
                "__builtin_ctz does not take 32-bit arg");
  return __builtin_ctz(x);
#elif defined(_MSC_VER) && !defined(__clang__)
  unsigned long result = 0;  // NOLINT(runtime/int)
  _BitScanForward(&result, x);
  return result;
#else
  int c = 31;
  x &= ~x + 1;
  if (x & 0x0000FFFF) c -= 16;
  if (x & 0x00FF00FF) c -= 8;
  if (x & 0x0F0F0F0F) c -= 4;
  if (x & 0x33333333) c -= 2;
  if (x & 0x55555555) c -= 1;
  return c;
#endif
}

First we check, if the compiler supports the intrinsic __builtin_ctz. Compiler intrinsics are functions, whose implementation is handled specially by the compiler. The standard way of checking this is querying __has_builtin(__builtin_ctz). In the case, this intrinsic is not supported, we have a fall-back. _MSC_VER is a built-in preprocessor macro always defined in Microsoft Visual C++ compiler. So, if the compiler is MSVC, we use _BitScanForward. If none of the above conditions are true, we use the following algorithm.

Step 1. Since x is non-zero, the number of trailing zeroes can be atmost 31.

Step 2. Turn on the rightmost 1-bit in a quad-word. Consider the following code snippet:

#include <cstdint>
#include <cassert>

int main() {
    const uint8_t x = 0b0101'1000;
    const uint8_t neg_x = ~x;
    static_assert(neg_x == 0b1010'0111);
    const uint8_t neg_x_plus_one = neg_x + 1;
    static_assert(neg_x_plus_one == 0b1010'1000);
    const uint8_t y = x & (~x + 1);
    static_assert(y == 0b0000'1000);
}

Compiler Explorer

Step 3. The rightmost 1-bit lies in either the left double-word or right double-word. We apply the mask 0x0000FFFF to determine which half it lies in. If it lies on the right, we can safely subtract 16 from the number of trailing zeroes. We apply the above logic recursively. Using binary search, we can find the index of the rightmost 1-bit in \(\log_2(32) \approx 5\) steps.

The index of the rightmost 1-bit is numerically equal to the number of trailing zeroes.