Why do we have double hashing function as [(hash1(key) + i * hash2(key)) % TABLE_SIZE] but not simply as [(i * hash2(key)) % TABLE_SIZE]?

A quick summary of this answer:

1. There is a practical performance hit to your modified version, though it's not very large.
2. I think this is due to there not being as many different probe sequences as in regular double hashing, leading to some extra collisions due to the birthday paradox.

Now, the actual answer. :-)

Let's start off with some empirical analysis. What happens if you switch from the "standard" version of double hashing to the variant of double hashing that you've proposed?

I wrote a C++ program that generates uniformly-random choices of h₁ and h₂ values for each of the elements. It then inserts them into two different double-hashing tables, one using the normal approach and one using the variant. It repeats this process multiple times and reports the average number of probes required across each insertion. Here's what I found:

#include <iostream>
#include <vector>
#include <random>
#include <utility>
using namespace std;

/* Table size is picked to be a prime number. */
const size_t kTableSize = 5003;

/* Load factor for the hash table. */
const double kLoadFactor = 0.9;

/* Number of rounds to use. */
const size_t kNumRounds = 100000;

/* Random generator. */
static mt19937 generator;

/* Creates and returns an empty double hashing table. */
auto emptyTable(const size_t numSlots) {
  return vector<bool>(numSlots, false);
}

/* Simulation of double hashing. Each vector entry represents an item to store.
 * The first element of the pair is the value of h1(x), and the second element
 * of the pair is the value of h2(x).
 */
auto hashCodes(const size_t numItems) {
  vector<pair<size_t, size_t>> result;
  
  uniform_int_distribution<size_t> first(0, kTableSize - 1), second(1, kTableSize - 1);
  
  for (size_t i = 0; i < numItems; i++) {
    result.push_back({ first(generator), second(generator) });
  }
  
  return result;
}

/* Returns the probe location to use given a number of steps taken so far.
 * If modified is true, we ignore h1.
 */
size_t locationOf(size_t tableSize, size_t numProbes, size_t h1, size_t h2, bool modified) {
  size_t result = (numProbes == 0 || !modified)? h1 : 0;
  result += h2 * numProbes;
  return result % tableSize;
}

/* Performs a double-hashing insert, returning the number of probes required to 
 * settle the element into its place.
 */
size_t insert(vector<bool>& table, size_t h1, size_t h2, bool modified) {
  size_t numProbes = 0;
  while (table[locationOf(table.size(), numProbes, h1, h2, modified)]) {
    numProbes++;
  }
  
  table[locationOf(table.size(), numProbes, h1, h2, modified)] = true;
  return numProbes + 1; // Count the original location as one probe
}

int main() {
  size_t normalProbes = 0, variantProbes = 0;

  for (size_t round = 0; round < kNumRounds; round++) {
    auto normalTable  = emptyTable(kTableSize);
    auto variantTable = emptyTable(kTableSize);

    /* Insert a collection of items into the table. */
    for (auto [h1, h2]: hashCodes(kTableSize * kLoadFactor)) {
      normalProbes  += insert(normalTable, h1, h2, false);
      variantProbes += insert(variantTable, h1, h2, true);
    }
  }
  
  cout << "Normal probes:  " << normalProbes << endl;
  cout << "Variant probes: " << variantProbes << endl;
}

Output:

Normal probes:  1150241942
Variant probes: 1214644088

So, empirically, it looks like the modified approach leads to about 5% more probes being needed to place all the elements. The question, then, is why this is.

I do not have a fully-developed theoretical explanation as to why the modified version is slower, but I do have a reasonable guess as to what's going on. Intuitively, double hashing works by assigning each element that's inserted a random probe sequence, which is some permutation of the table slots. It's not a truly-random permutation, since not all permutations can be achieved, but it's random enough for some definition of "random enough" (see, for example, Guibas and Szemendi's "The Analysis of Double Hashing).

Let's think about what happens when we do an insertion. How many times, on expectation, will we need to look at the probe sequence beyond just h₁? The first item has 0 probability of needing to look at h₂. The second item has 1/T probability, since it hits the first element with probability 1/T. The second item has 2/T probability, since it has a 2/T chance of hitting the first two items. More generally, using linearity of expectation, we can show that the the expected number of times an item will be in a spot that's already taken is given by

1/T + 2/T + 3/T + 4/T + ... + (n-1)/T

=(1+2+3+...+(n-1))/T

= n(n-1)/2T

Now, let's imagine that the load factor on our hash table is α, meaning that αT = n. Then the expected number of collisions works out to

αT(αT - 1) / 2T

≈ α²T / 2.

In other words, we should expect to see a pretty decent number of times where we need to inspect h₂ when using double hashing.

Now, what happens when we look at the probe sequence? The number of different probe sequences using traditional double hashing is T(T-1), where T is the number of slots in the table. This is because there are T possible choices of h₁(x) and T-1 choices for h₂(x).

The math behind the birthday paradox says that once approximately √(2T(T-1)) ≈ T√2 items have been inserted into the table, we have a 50% chance that two of them will end up having the same probe sequence assigned. The good news here is that it's not possible to insert T√2 items into a T-slot hash table - that's more elements than slots! - and so there's a fairly low probability that we see elements that get assigned the same probe sequences. That means that the conflicts we get in the table are mostly due to collisions between elements that have different probe sequences, but coincidentally end up landing smack on top of one another.

On the other hand, let's think about your variation. Technically speaking, there are still T(T-1) distinct probe sequences. However, I'm going to argue that there are "effectively" more like only T-1 distinct probe sequences. The reason for this is that

1. probe sequences don't really matter unless you have a collision when you do an insertion, and
2. once there's a collision after an insertion, the probe sequence for a given element is determined purely by its h₂ value.

This is not a rigorous argument - it's more of an intuition - but it shows that we have less variation in how our permutations get chosen.

Because there are only T-1 different probe sequences to pick from once we've had a collision, the birthday paradox says that we need to see about √(2T) collisions before we find two items with identical values of h₂. And indeed, given that we see, on expectation, α²T/2 items that need to have h₂ inspected, this means that we have a very good chance of finding items whose positions will be determined by the exact same sequence of h₂ values. This means that we have a new source of collisions compared with "classical" double hashing: collisions from h₂ values overlapping one another.

Now, even if we do have collisions with h₂ values, it's not a huge deal. After all, it'll only take a few extra probes to skip past items placed with the same h₂ values before we get to new slots. But I think that this might be the source of the extra probes seen during the modified version.

Hope this helps!

The proof of double hashing goes through under some weak assumptions about h1 and h2, namely, they're drawn from universal families. The result you get is that every operation is expected constant time (for every access that doesn't depend on the choice of h1 and h2).

With h2 only you need to either strengthen the condition on h2 or give the time bound as stated. Pick a prime p congruent to 1 mod 4, let P* = {1, …, p−1} be the set of units mod p, and consider the following mediocre but universal family of hash functions from {L, R} × P*. Draw a random scalar c ← P* and a random function f ← (P* → P*) and define

h2((L, x)) = cx mod p
h2((R, x)) = f(x).

This family is universal because the (L, x) keys never collide with each other, and every other pair collides with probability exactly 1/|P*|. It's a bad choice for the double-hashing-with-only-h2 algorithm because it's linear on half of its range, and linearity preserves arithmetic sequences.

Consider the following sequence of operations. Fill half of the hash table at random by inserting (R, 1), …, (R, (p−1)/2), then insert half again as many elements (L, (p−1)/4), …, (L, 1). The table load is at most 3/4, so everything should run in expected constant time. Consider what happens, however, when we insert (L, 1). With probability 1/2, the location h2((L, 1)) is occupied by one of the R keys. The i^th probe i h2((L, 1)) hits the same location as h2((L, i)), which for i ≤ (p−1)/4 is guaranteed to be full by earlier operations. Therefore the expected cost of this operation is linear in p even though the sequence of keys didn't depend on the hash function, which is unacceptable.

Putting h1 back in the mix smashes this structure.

(Ugh this didn't quite work because the proof of expected constant time assumes strong universality, not universality as stated in the abstract.)

Taking another bite at the apple, this time with strong universality. Leaving my other answer up because this one uses a result by Patrascu and Thorup as a black box (and your choice of some deep number theory or some handwaving), which is perhaps less satisfying. The result is about linear probing, namely, for every table size m that's a power of 4, there exists a 2-universal (i.e., strongly univeral) hash family and a sequence of operations such that, in expectation over the random hash function, one operation (referred to as The Query) probes Theta(√m) cells.

In order to use this result, we'd really like a table of size p−1 where p is a prime, so fixing m and the bad-for-linear-probing hash family H_m (whose functions have codomain {0, …, m-1}), choose p to be the least prime greater than m. (Alternatively, the requirement that m be a power of 4 is basically for convenience writing up the proof; it seems tedious but possible to generalize Patrascu and Thorup's result to other table sizes.) Define the distribution H_p by drawing a function h'' ← H_m and then define each value of h' independently according to the distribution

h'(x) = | h''(x) + 1 with probability m/(p-1)
        | m          with probability 1/m
        ...
        | p-1        with probability 1/m.

Letting K be the field mod p, the functions h have codomain K* = {1, …, p-1}, the units of K. Unless I botched the definition, it's straightforward to verify that H_p is strongly universal. We need to pull in some heavy-duty number theory to show that p - m is O(m^2/3) (this follows from the existence of primes between sufficiently large successive cubes), which means that our linear probe sequence of length O(√m) for The Query remains intact with constant probability for Omega(m^1/3) steps, well more than constant.

Now, in order to change this family from a linear probing wrecker to a "double" hash wrecker, we need to give the key involved in The Query a name, let's say q. (We know for sure which one it is because the operation sequence doesn't depend on the hash function.) We define a new distribution of hash functions h by drawing h' as before, drawing c ← K*, and then defining

h(x) = | c h'(x) if x ≠ q
       | c       if x = q.

Let's verify that this is still 2-universal. Given keys x and y both not equal to q, it's clear that (h(x), h(y)) = (c h'(x), c h'(y)) has uniform distribution over K* × K*. Given q and some other key x, we examine the distribution of (h(q), h(x)) = (c, c h'(x)), which is as needed because c is uniform, and h'(x) is uniform and independent of c, hence so is c h'(x).

OK, the point of this exercise at last. The probe sequence for The Query will be c, 2c, 3c, etc. Which keys hash to (e.g.) 2c? They are the x's that satisfy the equation

h(x) = c h'(x) = 2c

from which we derive

h'(x) = 2,

i.e., the keys whose preferred slot is right after The Query's in linear probe order. Generalizing from 2 to i, we conclude that the bad linear probe sequence for The Query for h' becomes a bad "double" hashing probe sequence for The Query for h, QED.