Your scheme is very similar to Cuckoo Hashing. In Cuckoo Hashing you have two (or, in variations, more) independent hash functions $h,g$. To insert an item $x$ you check at location $h(x)$. If that location is occupied, you suggest to check at $g(x)$. If we were to do it that way, we would have a problem in case $g(x)$ is also occupied and would have to fall back to another scheme, e.g. linear probing, with the associated problems. In Cuckoo hashing we employ a trick. If $h(x)$ is occupied by some item $y$, we store $x$ at that location anyway and try to store $y$ its alternate location (so either $g(y)$ or $h(y)$). If those locations are occupied as well, we repeat the process of kicking out the existing item and trying to place it at its alternate location.
You might wonder whether this process doesn't lead to loops and how long insertion can take. After all the sequence of kicking out and trying alternate spots doesn't seem to have a defined bound.
And indeed, if your hashtable is too full, the insertion can fail.
Consider the graph in which table positions are vertices and there is an edge between two vertices when we need to insert an item that maps to them. Usually this graph is called the cuckoo graph. We seek a matching of edges to vertices. By Hall’s theorem it exists if and only if there is no subgraph that has more edges than vertices.
We can use the first moment method to find a bound for the appearance of such subgraphs. Hence we have to calculate their expected number. There are many graphs with more edges than vertices, too many to tackle the expectation with our limited knowledge of probability theory. Luckily we can make a clever observation. If there are no subgraphs with more edges than vertices, there can’t be subgraphs with exactly one more edge than vertices.
There are only two types of these graphs, see the figure below. Both can be characterized by three numbers. Either the length of the three paths, or the size of the two cycles and the length of the connecting path. As all of these numbers must be smaller than $n$, there can be at most a cubic number of forbidden subgraphs. If we simplify the problem a little (actually we would have to use a random graph model where we fix the number of edges to the number items. For our purposes these two models are similar enough.) and consider the graph to be a $G_{n,p}$, a random graph on $n$ vertices where every edge is present with probability $p$, a fixed subgraph with $k$ edges is contained with probability $p^{-k}$. Hence the probability that a fixed forbidden graph appears is certainly smaller than $p^{-3}$.
As we have at most $n^3$ forbidden subgraphs, the expected number is at most $n^3p^{-3}$. This value goes to zero for $p < 1/n$ and thus (modulo our simplified graph model) for graphs with less than $n/2$ edges. Therefore in such graphs no forbidden subgraphs occur with high probability and insertion can work in principle.
But how about our greedy algorithm, is it sufficient for inserting new elements? Let’s consider a directed version of the cuckoo graph. Every edge is directed towards the position where the element is moved to in case it gets kicked out of its current spot. Hence elements reside at the edges tails and every node has at most one outgoing edge. Inserting a new element corresponds to inserting a new edge and directing it. If both endpoints already have an outgoing edge, we select an arbitrary one and kick the element out of its position. This means we reverse the edge and check at the new position whether there is already an outgoing edge.
This process fails if we cross an edge for the third time. The first time we see it, we flip it and continue. If we see it again, there was a directed cycle somewhere further down the path, that made us return. Note that this cycle still exists, only it now has the opposite direction. If we see the edge a third time, there was also a directed cycle on the other side–the process loops forever between these cycles.
But we’ve shown that these types of subgraphs don’t appear with high probability for hash tables with an occupancy of less than 0.5. So if you keep the occupancy low, insertion is very likely to succeed.
If you use more hash-functions the maximum occupancy goes up very quickly (see for example https://arxiv.org/pdf/0910.5147.pdf)
Using similar reasoning over the random graph model I described above you can show that insertion takes constant time in expectation.
