Trouble Understanding Yao's "Basic Model" for Hashing

Question

I am trying to understand the probing model proposed by Yao in the paper "Should Tables Be Sorted?". Yao suggests a "Basic Model" (in the section appropriately titled "Basic Model") but there seems to be some disconnect in the way I remember hash tables and the way it is presented here.

Consider sorted table vs cyclic table example Yao gives. My thought process was that the $\{1, 2\}$, $\{2, 3\}$ and $\{1, 3\}$ were key-value pairs. But this cannot be the case. In the cyclic model ${1, 3}$ results in what I believe is a key of $3$ and value of $1$.

Another problem I have is I do not understand what exactly is meant by a "query". I would have assumed that both the sorted and cyclic results in a look up of time of 1, but Yao states the sorted requires $2$ queries. For if one looks at the Sparknotes link above, the hash table will look something like this:

$$1 \to 2, 3$$ $$2 \to 3$$

So, making the query $1$ will give $2$ immediately (and $3$ will require two look ups). Similarly, for cyclic the look up table looks like

$$1 \to 2$$ $$2 \to 3$$ $$3 \to 1$$

and the query $1$ would give $2$ immediately as well.

I suppose in principle, for the sorted example, it could depend how $3$ is inserted, so in the worst case, the sorted table could look like:

$$1 \to 3, 2$$ $$2 \to 3$$

in which case $2$ queries would be needed for $2$. This then goes back to what exactly is query in this context? Sorry if my understanding is completely wrong, any guidance is appreciated.

Answer 1

Following @Tassle's comment here is what I have gathered since more careful reading:

The $\{1,3\}$, $\{2,3\}$, etc. are not key value pairs they are values to be inserted into a table. The boxed values are potential arrangements for a table given the corresponding insertion.

For the example Yao considers for $n=2, m=3$ there are two separate query strategies (one that queries the first entry first, the other that queries the second entry first). For the sorted case, the worst possible number of queries needed to determine if two is in the table is two.

This is because if you query the first entry and see a $1$ then you must query the second entry to determine if a $3$ was inserted or a $2$ was inserted. If you query the second entry first, and you receive a $3$ you must make a further query to determine whether $2$ or $1$ was the first entry. This problem does not exist for the cyclic variation. For instance, if one queries a $3$ choosing the first entry, then it is immediately known that $1$ is the second entry. A similar argument can be seen for the other combinations.